Tài liệu Trình biên dịch

MOÂN HOÏC TRÌNH BIEÂN DÒCH MUÏC LUÏC „ „ „ „ „ CHƯƠNG I Giới thiệu về trình bieân dòch CHƯƠNG 2 Trình bieân dòch ñơn giản CHƯƠNG 3 Phaân tích từ vựng CHƯƠNG 4 Phaân tích cuù phaùp CHƯƠNG 5 Trình bieân dịch trực tiếp cuù phaùp „ „ „ „ „ CHƯƠNG 6 Xử lí ngữ nghĩa CHƯƠNG 7 Quản lí bộ nhớ trong thời gian thực thi CHƯƠNG 8 Tổ chức bảng danh biểu CHƯƠNG 9 Sinh maõ ñoái töôïng CHƯƠNG 10 Toái öu maõ TAØI LIEÄU THAM KHAÛO 1) Alfred V.Aho, Jeffrey D.Ullman (1986). Compilers, Principles techniques, and tools. Addison – Wesley Publishing Company. 2) Alfred V.Aho, Jeffrey D.Ullman (1972). The theory of parsing, translation and compiling. Prentice – Hall, inc. 3) Terrence W. Pratt. Programming Languages: design and implementation second edition. Prebtice – Hall International editions. 4)Allen I. Holub. Compiler design in C. Prentice – Hall International editions. 5) D. Gries (1976). Compiler construction. Springger – Verlag. 6) Jeffrey D. Ullman (1977). Fundamental concepts of programming system. Addion Wesley Publsihing Company. 7) Döông Tuaán Anh (1986) Giaùo trình Trình bieân dòch. Ñaïi hoïc Baùch Khoa TP. Hoà Chí Minh. 8) Nicklaus Wirth (1976), Algorithms + Data Structure = program. Prentice – Hall International editions. 9) Alfred V.Aho, Jeffrey D. Ullman (1977). Principles of compiler design. Addison – Wesley, Reading, Mass. 10) Leâ Hoàng Sôn, Luaän vaên toát nghieäp “Xaây döïng giaûi thuaät toái öu maõ trung gian cuûa trình bieân dòch” – Khoa CNTT Tröôøng ÑH Baùch khoa 2002. 11) Phan Thò Töôi (2001). Trình Bieân Dòch. Ñaïi hoïc Baùch Khoa TP. Hoà Chí Minh YEÂU CAÀU „ „ „ Phaàn Lyù thuyeát: SV hoïc 42 tieát lyù thuyeát Phaàn Thöïc haønh: SV tham döï thöïc haønh – thöïc hieän Baøi taäp Moân hoïc 14t (1 Baøi taäp Moân hoïc / 1 SV) Hình thöùc ñaùnh giaù: „ „ „ Kieåm tra Baøi taäp Moân hoïc Æ Ñieåm TH Thi vieát Lyù thuyeát cuoái kyø Æ Ñieåm LT Caùch tính ñieåm: Ñieåm toång keát moân = LT * 60% + BTTH * 40% CHÖÔNG 1 GIÔÙI THIEÄU VEÀ TRÌNH BIEÂN DÒCH 1.1. Ngoân ngöõ laäp trình 1. Giôùi thieäu Phaân loaïi Chöông trình dòch - Trình bieân dòch Döõ lieäu Chöông trình nguoàn Trình bieân dòch Chöông trình ñích Maùy tính thöïc thi Keát quaû Hình 1.1. Chöông trình thöïc thi theo cô cheá dòch cuûa trình bieân dòch - Trình thoâng dòch Chöông trình nguoàn Trình thoâng dòch Keát quaû Döõ lieäu Hình 1.2. Chöông trình thöïc thi theo cô cheá dòch cuûa trình thoâng dòch Ñaëc taû ngoân ngöõ laäp trình 1. Taäp caùc kyù hieäu caàn duøng trong caùc chöông trình hôïp leä 2. Taäp caùc chöông trình hôïp leä 3. Nghóa cuûa chöông trình hôïp leä - Phöông phaùp thöù nhaát laø ñònh nghóa baèng pheùp aùnh xaï. Söû duïng pheùp toaùn haøm: haøm Lamda. - Phöông phaùp thöù hai: Maùy tröøu töôïng. - Phöông phaùp thöù ba: Taäp (x,y) laø söï bieân dòch. 2. Cuù phaùp vaø ngöõ nghóa - AÙnh xaï cuù phaùp (syntactic mapping) the pig is the pen Hình 1.3 Caáu truùc caây cuûa caâu tieáng Anh: the pig is in the pen - AÙnh xaï cuù phaùp + a ∗ b c Hình 1.4. Caây cuù phaùp cuûa bieåu thöùc soá hoïc a + b * c 1.2. Trình bieân dòch 1. Caùc thaønh phaàn cuûa trình bieân dòch 1. Phaân tích töø vöïng Nhaän daïng token. Token: danh bieåu, haèng, töø khoùa, caùc toaùn töû pheùp toaùn, caùc kyù hieäu phaân caùch, khoaûng traéng, caùc kyù hieäu ñaëc bieät Ví duï: COST := ( PRICE + TAX )*65 Ñaàu ra cuûa boä phaân tích töø vöïng: () := ( () + () ) * (,4) Vieát goïn : id1 := (id2 + id3) * num4 Boä phaân tích töø vöïng thao taùc tröïc tieáp Boä phaân tích töø vöïng thao taùc khoâng tröïc tieáp 2. Baûng danh bieåu Ví duï: COST := (PRICE + TAX) * 65 Baûng 1.1 Baûng danh bieåu Chæ soá token lexeme Caùc thoâng tin khaùc 1 id COST bieán thöïc 2 3 id id PRICE TAX bieán thöïc bieán thöïc 4 num 65 haèng soá nguyeân 3. Phaùt hieän vaø thoâng baùo loãi 4. Phaân tích cuù phaùp Ví duï: COST := (PRICE + TAX) * 65 Keát quaû phaân tích töø vöïng: id1 := ( id2 + id3 )* num4 Keát quaû phaân tích cuù phaùp: n3 id1 id2 := n1 + n2 * id3 num4 Hình 1.6. Caây cuù phaùp cuûa phaùt bieåu 5. Phaân tích ngöõ nghóa n3 id1 id2 := n2 n2 + id3 * intoreal (65) 65.0 PRICE TAX Hình 1.7. Caây cuù phaùp coù xöû lyù ngöõ nghóa 6. Sinh maõ trung gian temp1 := intoreal (65) temp2 := id2 + id3 temp3 := temp2 * temp1 id1 := temp3 7. Toái öu maõ trung gian temp1 := id2 + id3 id1 := temp1 + 65.0 8. Sinh maõ ñoái töôïng movF id2, R1 movF id3, R2 addF R2, R1 multF # 65.0, R1 movF R1, id1 COST := (PRICE + TAX) * 65 Boä phaân tích töø vöïng id := (id2 + id3) * num4 Boä phaân tích cuù phaùp n1 id1 := n3 id2 + n2 * num4 id3 Boä phaân tích ngöõ nghóa n1 id1 id2 := n3 + n2 * intoreal (65) id3 Boä sinh maõ trung gian temp1 := intoreal (65) temp2 := id3 + id3 temp3 := temp2 * temp1 id1 := temp3 Boä toái öu trung gian temp1 := id2 + id3 id1 := temp1 * 65.0 Boä sinh maõ ñoái töôïng movF id2 , R1 movF id3 , R2 ADDF R2 . R1 mulF # 65.0, R1 movF R1 ,id1 Hình 1.8. Bieân dòch phaùt bieåu 1.3. Caùc moái lieân quan vôùi trình bieân dòch 1. Boä tieàn xöû lyù - Xöû lyù macro (macro processing) - Cheâm taäp tin (file inclusion) - Boä xöû lyù hoaø hôïp (rational processor) - Môû roäng ngoân ngöõ (language extension) Thí duï veà xöû lyù macro: - Heä thoáng maùy ñaùnh chöõ typesetting: \define