NGÔN NGỮ và PHƯƠNG PHÁP DỊCH - Chương 5: Sinh mã

Bộ sinh mã trung gian chuyển chương trình nguồn sang chương trình tương đương trong ngôn ngữ trung gianChương trình trung gian là một chương trình cho một máy trừu tượngNgôn ngữ trung gian được người thiết kế trình biên dịch quyết định, có thể là:Cây cú pháp Ký pháp Ba Lan sau (hậu tố)Mã 3 địa chỉ …
Nội dung trích xuất từ tài liệu:
NGÔN NGỮ và PHƯƠNG PHÁP DỊCH - Chương 5: Sinh mãIT4073:NGÔN NGỮ và PHƯƠNG PHÁP DỊCH Phạm Đăng Hải haipd@soict.hut.edu.vn Chương 5: Sinh mã1. Sinh mã trung gian2. Sinh mã đích3. Tối ưu mã05/29/13 21. Sinh mã trung gian Giới thiệu • Bộ sinh mã trung gian chuyển chương trình nguồn sang chương trình tương đương trong ngôn ngữ trung gian – Chương trình trung gian là một chương trình cho một máy trừu tượng • Ngôn ngữ trung gian được người thiết kế trình biên dịch quyết định, có thể là: – Cây cú pháp – Ký pháp Ba Lan sau (hậu tố) – Mã 3 địa chỉ … 05/29/13 31. Sinh mã trung gian Nội dung • Chương trình dịch định hướng cú pháp • Cây cú pháp • Ký pháp Ba lan sau • Mã 3 địa chỉ – Các dạng mã – Dịch trực tiếp cú pháp thành mã 3 địa chỉ – Sinh mã cho khai báo – Sinh mã cho lệnh gán – Sinh mã cho các biểu thức logic – Sinh mã cho các cấu trúc lập trình 05/29/13 41. Sinh mã trung gian Chương trình dịch định hướng cú pháp Mỗi ký hiệu VP liên kết với một tập thuộc tính: – Thuộc tính tổng hợp: • Giá trị của thuộc tính tại một nút trong cây được xác định từ giá trị của các nút con của nó. – Thuộc tính kế thừa: • Giá trị của thuộc tính được định nghĩa dựa vào giá tr ị nút cha và/hoặc các nút anh em của nó. • Tồn tại một tập luật ngữ nghĩa dùng để tính giá trị thuộc tính 05/29/13 51. Sinh mã trung gian Ví dụ Sản xuất Quy tắc ngữ nghĩa L → E return Print (E.val) E → E1+T E.val = E1.val + T.val E →T E.val = T.val T → T1 * F T.val = T1.val * F.val T →F T.val = F.val F → (E) F.val = E.val F → digit F.val = digit.lexval •Các ký hiệu E, T, F có thuộc tính tổng hợp val •Từ tố digit có thuộc tính tổng hợp lexval ( Được bộ phân tích từ vựng đưa ra ) 05/29/13 61. Sinh mã trung gian Chú giải cây suy dẫn 05/29/13 71. Sinh mã trung gian Nội dung • Chương trình dịch định hướng cú pháp • Cây cú pháp • Ký pháp Ba lan sau • Mã 3 địa chỉ – Các dạng mã – Dịch trực tiếp cú pháp thành mã 3 địa chỉ – Sinh mã cho khai báo – Sinh mã cho lệnh gán – Sinh mã cho các biểu thức logic – Sinh mã cho các cấu trúc lập trình 05/29/13 81. Sinh mã trung gian Cây cú pháp (Syntax tree) • Cây cú pháp (syntax tree) là dạng thu gọn của cây phân tích (parse tree) dùng để biểu diễn cấu trúc của ngôn ngữ • Trong cây cú pháp các toán tử và từ khóa không xuất hiện ở các nút lá mà đưa vào các nút trong. – Cha của các nút lá là các toán hạng tương ứng • Cây cú pháp có ý nghĩa dụng trong cài đặt – Cây phân tích (cú pháp) chỉ ý nghĩa về mặt logic 05/29/13 91. Sinh mã trung gian Cây cú pháp →Ví dụ 1 Ví dụ: S → If B Then S1 Else S2 Cây suy dẫn If Then Else If Then Else Cây cú pháp 05/29/13 101. Sinh mã trung gian Xây dựng cây cú pháp →Ví dụ 2 E→ E+T | T 5*2+4 E T→ T*F | F E + T F →(E) | num T F + 4 T * F * 4 F 2 5 2 5 Cây cú pháp Cây phân tích 05/29/13 111. Sinh mã trung gian Xây dựng cây cú pháp cho biểu thức • Các ký hiệu không kết thúc có thuộc tính tổng hợp link để lưu con trỏ, trỏ tới một nút trên cây cú pháp • Sử dụng các hàm ptr = mkLeaf(Num) ptr = mkNode(op, L, R) ptr ptr op Num L R 05/29/13 121. Sinh mã trung gian Cây cú pháp (Syntax tree) Sản xuất Luật ngữ nghĩa E → E1 + T E.link := mkNode(+,E1.link,T.link) E →T E.link := T.link T → T1 * F T.link := mkNode(*,T1.link,F.link) T →F T.link := F.link F → (E) F.link := E.link F → num F.link := mkLeaf(num) Cây cú pháp được xây dựng từ dưới lên trên – Sau khi phân tích xong một sản xu ất mới gọi lu ật ng ữ nghĩa tương ứng (duyệt thứ tự sau) 05/29/13 131. Sinh mã trung gian Xây dựng cây cú pháp →Ví dụ 5*2+4 E Cây phân tích E + T T F + T * F 4 F 2 * 4 5 F.Link =mkLeaf(4) ...