intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nam Trinhviet | Ngày: | Loại File: PPT | Số trang:79

Thêm vào BST
Báo xấu
94
lượt xem 11
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ỉ …

Chủ đề:

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

Lưu

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

  1. IT4073:NGÔN NGỮ và PHƯƠNG PHÁP DỊCH Phạm Đăng Hải haipd@soict.hut.edu.vn
  2. Chương 5: Sinh mã 1. Sinh mã trung gian 2. Sinh mã đích 3. Tối ưu mã 05/29/13 2
  3. 1. 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 3
  4. 1. 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 4
  5. 1. 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 5
  6. 1. 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 6
  7. 1. Sinh mã trung gian Chú giải cây suy dẫn 05/29/13 7
  8. 1. 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 8
  9. 1. 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 9
  10. 1. 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 10
  11. 1. 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 11
  12. 1. 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 12
  13. 1. 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 13
  14. 1. 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) 2 5 T.Link =mkNode(*,T1.Link,F.Link) F.Link =mkLeaf(5) F.Link =mkNode(+,E1.Link,T.Link) F.Link =mkLeaf(2) 05/29/13 14
  15. 1. 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 15
  16. 1. Sinh mã trung gian Ký pháp Ba lan sau (Reverse Polish notation) Ký pháp Ba lan: Là một ký hiệu toán học trong đó dấu đặt trước/ sau toán hạng – Ký pháp thông thường (giữa): 5 + 6 – Ký pháp Ba lan trước: + 5 6 – Ký pháp Ba lan sau (ngược): 5 6 + Mục đích: – Giảm thiểu bộ nhớ và dùng stack để tính toán Sử dung: – Trong một số loại máy tính tay 05/29/13 16
  17. 1. Sinh mã trung gian Quy tắc dịch dạng trung tố → dạng hậu tố Sản xuất Ký pháp hậu tố Ký pháp tiền tố E → E+T E →E T + E →+ E T E →T E →T E →T T →T * F T →T F * T →* T F T →F T →F T →F F → (E) F →E F →E F → digit F → digit F → digit 05/29/13 17
  18. 1. Sinh mã trung gian Ký pháp Ba lan sau → Ví dụ 1 a+b*c+d E ⇒E + T ⇔ E ⇒E T + ⇒E + T + T ⇔ ⇒E T + T + ⇒T + T + T ⇔ ⇒T T + T + ⇒F + T + T ⇔ ⇒F T + T + ⇒a + T + T ⇔ ⇒a T + T + ⇒a + T * F + T ⇔ ⇒a T F * + T + ⇒a + F * F + T ⇔ ⇒a F F * + T + ⇒a + b * F + T ⇔ ⇒a b F * + T + ⇒ a + b * c + T⇔ ⇒a b c * + T + ⇒ a + b * c + F⇔ ⇒a b c * + F + ⇒a + b * c + d ⇔ 05/29/13 ⇒a b c * + d + 18
  19. 1. Sinh mã trung gian Ký pháp Ba lan sau → Ví dụ 2 (a+b) * (c+d) E ⇒T ⇔ E ⇒T + ⇒T * F ⇔ ⇒T F * ⇒F * F ⇔ ⇒F F * ⇒ (E) * F ⇔ ⇒E F * ⇒ (T + F) * F ⇔ ⇒T F + F * ⇒ (F + F) * F ⇔ ⇒F F + F * ⇒ (a + F) * F ⇔ ⇒a F + F * ⇒ (a + b) * F ⇔ ⇒a b + F * ⇒ (a + b) * (E) ⇔ ⇒a b + E * ⇒ (a + b) * (T + F) ⇔ ⇒a b + T F + * ⇒ (a + b) * (F + F) ⇔ ⇒a b + F F + * ⇒ (a + b) * (c + F) ⇔ ⇒a b + c F + * ⇒ 05/29/13 (a + b) * (c + d) ⇔ ⇒ a b + c d19 * +
  20. 1. 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 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2