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

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
Nội dung trích xuất từ tài liệu:
NGÔN NGỮ và PHƯƠNG PHÁP DỊCH THÀNH CÔNG - Chương 5: Sinh mãIT4073:NGÔN NGỮ vàPHƢƠNG PHÁP DỊCH THÀNH CÔNG 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ã11/18/2012 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ỉ … 11/18/2012 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 11/18/2012 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 11/18/2012 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 ) 11/18/2012 61. Sinh mã trung gian Chú giải cây suy dẫn 11/18/2012 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 11/18/2012 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 11/18/2012 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 11/18/2012 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 11/18/2012 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 11/18/2012 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) 11/18/2012 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 * ...