tailieunhanh - Bài giảng môn học Trình biên dịch - Chương 2: Trình biên dịch đơn giản

Bài giảng chương 2 trình bày những nội dung cơ bản như: Định nghĩa cú pháp, sự biên dịch trực tiếp cú pháp (syntax-directed translation), phân tích cú pháp, trình biên dịch cho biểu thức đơn giản, sự phân tích từ vựng, sự hình thành bảng danh biểu, máy trừu tượng kiểu chồng,. . | CHÖÔNG 2 . Toång quaùt Chuoãi kyù töï TRÌNH BIEÂN DÒCH ÑÔN GIAÛN 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 . Caáu truùc trình bieân dòch “front end” . Ñò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ï . Cho vaên phaïm G: P: list → list + digit | list – digit | digit digit → 0 |1| 2 | |9 Thí duï . Vaên phaïm mieâu taû phaùt bieåu hoãn hôïp begin end cuûa Pascal P : block → begin opt_stmts end opt_stmts → stmt_list |€ stmt_list → stmt_list ; stmt | stmt - Caây phaân tích Söï khoâng töôøng minh Thí duï . Vaên phaïm G sau ñaây laø khoâng töôøng minh: P : string → string + string | string – string | 0 | 1 | . |9 Caâu 9 – 5 + 2 cho hai caây phaân tích: string string string 9 string + - string a) 5 string 2 string - string 9 string + 5 Hình Hai caây phaân tích cuûa caâu 9 – 5 + 2 b) string 2 Söï keát hôïp cuûa caùc toaùn töû Möùc öu tieân cuûa caùc toaùn töû: * vaø / coù möùc öu tieân hôn + , - . Döïa vaøo nguyeân taéc treân chuùng ta xaây döïng cuù phaùp cho bieåu thöùc soá hoïc: exp → exp + term | exp – term | term term → term * factor | term / factor | factor factor → digit | ( exp ) Löu yù: pheùp toaùn luõy thöøa vaø pheùp gaùn trong C laø pheùp toaùn keát hôïp phaûi. Vaên phaïm cho pheùp gaùn nhö sau: right → letter = right | letter letter → a | b | | z . Söï bieân dòch tröïc tieáp cuù phaùp (Syntax-Directed Translation) 1. Kyù hieäu haäu toá 1) Neáu E laø bieán hoaëc haèng soá thì kyù hieäu haäu toá cuûa E chính laø E. 2) Neáu E laø bieåu thöùc coù daïng E1 op E2 vôùi op laø toaùn töû hai ngoâi thì kyù hieäu haäu toá cuûa E laø E1’ E2’ op. 3) Neáu E laø bieåu thöùc coù daïng (E1) thì kyù hieäu haäu toá cuûa E1 cuõng laø kyù hieäu haäu toá cuûa E. Löu yù: Khoâng caàn coù daáu ñoùng, môû ngoaëc trong kyù hieäu haäu toá. 2. Ñònh nghiaõ tröïc tieáp cuù phaùp (Syntax-directed .