Tài liệu Giáo trình trình biên dịch đh bkhcm

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õ MUÏC LUÏC 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 TAØI LIEÄU THAM KHAÛO Ñieåm TH Ñieåm LT Caùch tính ñieåm: Ñieåm toång keát moân = LT * 60% + BTTH * 40% Kieåm tra Baøi taäp Moân hoïc Thi vieát Lyù thuyeát cuoái kyø Hình thöùc ñaùnh giaù: 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) Phaàn Lyù thuyeát: SV hoïc 42 tieát lyù thuyeát YEÂU CAÀU Trình bieân dòch Chöông trình ñích Maùy tính thöïc thi Döõ lieäu 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 Chöông trình nguoàn - Trình bieân dòch Chöông trình dòch Phaân loaïi 1. Giôùi thieäu 1.1. Ngoân ngöõ laäp trình GIÔÙI THIEÄU VEÀ TRÌNH BIEÂN DÒCH CHÖÔNG 1 Döõ lieäu Trình thoâng dòch Keát quaû Ñ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. Hình 1.2. Chöông trình thöïc thi theo cô cheá dòch cuûa trình thoâng dòch Chöông trình nguoàn - Trình thoâng dòch pig the 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 2. Cuù phaùp vaø ngöõ nghóa - AÙnh xaï cuù phaùp (syntactic mapping) b c Hình 1.4. Caây cuù phaùp cuûa bieåu thöùc soá hoïc a + b * c a + - AÙnh xaï cuù phaùp Boä phaân tích töø vöïng thao taùc khoâng tröïc tieáp Boä phaân tích töø vöïng thao taùc tröïc tieáp 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 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 id id id num 1 2 3 4 65 TAX PRICE COST lexeme 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 token Chæ soá haèng soá nguyeân bieán thöïc bieán thöïc bieán thöïc Caùc thoâng tin khaùc 2. Baûng danh bieåu Ví duï: COST := (PRICE + TAX) * 65 Baûng 1.1 Baûng danh bieåu + := n1 id3 * n2 num4 + n2 := id3 * n2 65.0 intoreal (65) PRICE TAX Hình 1.7. Caây cuù phaùp coù xöû lyù ngöõ nghóa id2 id1 Hình 1.6. Caây cuù phaùp cuûa phaùt bieåu 5. Phaân tích ngöõ nghóa n3 id2 id1 Keát quaû phaân tích cuù phaùp: n3 maõ trung gian temp1 := intoreal (65) temp2 := id2 + id3 temp3 := temp2 * temp1 id1 := temp3 8. Sinh maõ ñoái töôïng movF id2, R1 movF id3, R2 addF R2, R1 multF # 65.0, R1 movF R1, id1 7. Toái öu maõ trung gian temp1 := id2 + id3 id1 := temp1 + 65.0 6. Sinh + n3 := id3 * n2 + id2 n3 := id1 n1 num4 * intoreal (65) id3 n2 Boä phaân tích ngöõ nghóa id2 id1 n1 Boä phaân tích cuù phaùp id := (id2 + id3) * num4 Boä phaân tích töø vöïng COST := (PRICE + TAX) * 65 movF R1 ,id1 mulF # 65.0, R1 ADDF R2 . R1 movF id3 , R2 movF id2 , R1 Boä sinh maõ ñoái töôïng id1 := temp1 * 65.0 temp1 := id2 + id3 Boä toái öu trung gian id1 := temp3 temp3 := temp2 * temp1 temp2 := id3 + id3 temp1 := intoreal (65) Boä sinh maõ trung gian Hình 1.8. Bieân dòch phaùt bieåu Thí duï veà xöû lyù macro: - Heä thoáng maùy ñaùnh chöõ typesetting: \define