Giáo trình môn học Trình biên dịch - Chương 1: Giới thiệu về trình biên dịch

MOÂN HOÏC TRÌNH BIEÂN DÒCH „ 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 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 Ñ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. 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 2. Cuù phaùp vaø ngöõ nghóa - AÙnh xaï cuù phaùp (syntactic mapping) Hình 1.3 Caáu truùc caây cuûa caâu tieáng Anh: the pig is in the pen the pig is the pen - AÙnh xaï cuù phaùp a + ∗ cb 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 id PRICE bieán thöïc 3 id TAX 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: Hình 1.6. Caây cuù phaùp cuûa phaùt bieåu 5. Phaân tích ngöõ nghóa Hình 1.7. Caây cuù phaùp coù xöû lyù ngöõ nghóa id1 := n2 n1 id2 num4* id3+ n3 id1 := n2 n2 id2 intoreal (65)* id3 65.0+ PRICE TAX n3 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 Boä phaân tích töø vöïng Boä phaân tích cuù phaùp Boä phaân tích ngöõ nghóa id := (id2 + id3) * num4 COST := (PRICE + TAX) * 65 n1 id1 n2:= n3 num4* id2 + id3 n1 id1 n2:= n3 id2 + id3 intoreal (65)* Boä sinh maõ trung gian Boä toái öu trung gian Boä sinh maõ ñoái töôïng temp1 := intoreal (65) temp2 := id3 + id3 temp3 := temp2 * temp1 id1 := temp3 temp1 := id2 + id3 id1 := temp1 * 65.0 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 {} Thí duï macro ñònh nghóa veà söï trích daãn cuûa taïp chí ACM: \define\JACM # 1; #2; #3 {{\S1J.ACM}{\bf #1}: #2, pp.#3} Khi duøng macro: \JACM 17; 4; 715-728 Seõ ñöôïc hieåu nhö sau: J.ACM 17 : 4 , pp. 715-728 2. Trình bieân dòch hôïp ngöõ Phaùt bieåu gaùn b := a + 2 ñöôïc dòch ra maõ hôïp ngöõ MOV a, R1 ADD #2 , R1 MOV R1, b 3. Trình bieân dòch hôïp ngöõ hai chuyeán - Chuyeán thöù nhaát: ñoïc maõ hôïp ngöõ vaø taïo baûng danh bieåu Danh bieåu Ñiaï chæ töông ñoái a 0 b 4 - Chuyeán thöù hai: ñoïc maõ hôïp ngöõ vaø dòch sang maõ maùy khaû ñònh vò ñòa chæ: MOV a, R1 0001 010000000000* ADD #2, R1 0010 0110 00000010 (1.6) MOV R1, b 0100 010000000100* 4. Boä caát lieân keát soaïn thaûo Loader laø chöông trình thöïc hienä hai nhieäm vuï: caát vaø soaïn thaûo lieân keát. Quaù trình caát bao goàm laáy maõ maùy khaû ñònh vò tính laïi thaønh ñòa chæ tuyeät ñoái. Nhö ôû ví duï phaàn 3: Giaû söû maõ maùy ñöôïc caát trong boä nhôù trong taïi ñòa chæ L = 00001111; ñòa chæ tuyeät ñoái cuûa a, b laø 00001111 vaø 00010011. Ba chæ thò (1.6) ñöôïc vieát laïi döôùi daïng maõ maùy tuyeät ñoái: 0001010000001111 0011011000000010 (1.7) 0010010000010011 Link-editor cho pheùp taïo moät chöông trình duy nhaát töø nhieàu taäp tin ôû daïng maõ maùy khaû ñònh vò cuûa nhöõng laàn bieân dòch rieâng bieät vaø töø caùc taäp tin thö vieän do heä thoáng cung caáp. Chöông trình nguoàn vieát taét Boä tieàn xöû lyù Trình bieân dòch Trình bieân dòch hôïp ngöõ Boä caát/ lieân keát – soaïn thaûo Chöông trình nguoàn Chöông trình ñoái töôïng trong maõ hôïp ngöõ Chöông trình trong maõ maùy khaû ñònh vò Chöông trình maõ maùy ñòa chæ tuyeät ñoái Hình 1.19. Heä thoáng xöû lyù ngoân ngöõ Thö vieän heä thoáng, caùc taäp tin ñoái töôïng khaû ñònh vò ñòa chæ 1.4. Nhoùm caùc giai ñoaïn cuûa trình bieân dòch - Giai ñoaïn tröôùc vaø giai ñoaïn sau (front end and back end) - Caùc chuyeán - Thu giaûm soá löôïng caùc chuyeán Thí duïï: goto L : goto L : L : a = b + c „ „