Bài giảng Trình biên dịch

Chia sẻ: Đinh Trường Gấu | Ngày: | Loại File: PDF | Số trang:359

Thêm vào BST

Báo xấu

103
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Trình biên dịch với kết cấu gồm 10 chương giới thiệu những nội dung về: Trình biên dịch, trình biên dịch đơn giản, phân tích từ vựng, phân tích cú pháp, trình biên dịch trực tiếp cú pháp, xử lí ngữ nghĩa, quản lí bộ nhớ trong thời gian thực thi, tổ chức bảng danh biểu, sinh mã đối tượng và tối ưu mã.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Trình biên dịch

MOÂN HOÏC TRÌNH BIEÂN DÒCH
MUÏC LUÏC CHƯƠNG I CHƯƠNG 6 Giới thiệu về trình bieân dòch Xử lí ngữ nghĩa CHƯƠNG 2 CHƯƠNG 7 Trình bieân dòch ñơn giản Quản lí bộ nhớ trong thời CHƯƠNG 3 gian thực thi Phaân tích từ vựng CHƯƠNG 8 CHƯƠNG 4 Tổ chức bảng danh biểu Phaân tích cuù phaùp CHƯƠNG 9 CHƯƠNG 5 Sinh maõ ñoái töôïng Trình bieân dịch trực tiếp cuù CHƯƠNG 10 phaùp 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 Chöông Maùy tính Keát quaû trình nguoàn bieân dòch trình ñích thöïc thi 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 Trình thoâng Keát quaû nguoàn dòch 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 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: n3 id1 n2 := n1 num4 * id2 + id3 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 n2 := n2 intoreal (65) * id2 + id3 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 n2 := n3 * num4 id2 + id3 Boä phaân tích ngöõ nghóa n1 n2 id1 := n3 * intoreal (65) id2 + 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 Hình 1.8. Bieân dòch phaùt bieåu movF R1 ,id1
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ù Chöông trình nguoàn Trình bieân dòch Chöông trình ñoái töôïng trong maõ hôïp ngöõ Trình bieân dòch hôïp ngöõ Chöông trình trong maõ maùy khaû ñònh vò Thö vieän heä thoáng, caùc taäp tin ñoái töôïng Boä caát/ lieân keát – soaïn thaûo khaû ñònh vò ñòa chæ 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öõ
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
CHÖÔNG 2 TRÌNH BIEÂN DÒCH ÑÔN GIAÛN 2.1. Toång quaùt Chuoãi kyù töï Boä phaân tích Chuoãi token Boä bieân dòch tröïc Maõ trung gian töø vöïng tieáp cuù phaùp Hình 2.1. Caáu truùc trình bieân dòch “front end” 2.2. Ñònh nghóa cuù phaùp Vaên phaïm phi ngöõ caûnh (PNC) ñöôïc ñònh nghóa: G2 = (Vt, Vn, S, P) P : A → α1 | α2 |………|αn Thí duï 2.1. Cho vaên phaïm G: P: list → list + digit | list – digit | digit digit → 0 |1| 2 | …|9