Bài giảng Xây dựng chương trình dịch - Chương 4: Dịch trực tiếp cú pháp

Nội dung text: Bài giảng Xây dựng chương trình dịch - Chương 4: Dịch trực tiếp cú pháp

1. CHƯƠNG IV Dịch trực tiếp cú pháp Mục tiêu: • Vai trò của dịch trực tiếp cú pháp • Hiểu được các khái niệm: Định nghĩa trực tiếp cú pháp, thuộc tính tổng hợp và thuộc tính kế thừa, cây cấu trúc
2. • Trong một định nghĩa trực tiếp cú pháp, mỗi luật sinh A → kết hợp một tập luật ngữ nghĩa có dạng b:= f (c1, c2, , ck) trong đó f là một hàm và: 1) b là một thuộc tính tổng hợp (synthesized attribute) của A và c1, c2, , ck là các thuộc tính của các ký hiệu văn phạm của luật sinh. Hoặc 2) b là một thuộc tính kế thừa (inherited attribute) của một trong các ký hiệu văn phạm trong vế phải của luật sinh và c1, c2, , ck là các thuộc tính của các ký hiệu văn phạm của luật sinh
3. • Thuộc tính tổng hợp là thuộc tính mà giá trị của nó tại mỗi nút trên cây phân tích cú pháp được tính từ giá trị thuộc tính tại các nút con của nó • Ðịnh nghĩa trực tiếp cú pháp chỉ sử dụng các thuộc tính tổng hợp gọi là định nghĩa S- thuộc tính (S- attributed definition) • Trong cây phân tích cú pháp của định nghĩa S- thuộc tính, các luật ngữ nghĩa tính giá trị các thuộc tính cho các nút từ dưới lên, từ lá đến gốc
4. • Thuộc tính kế thừa là một thuộc tính mà giá trị của nó được xác định từ giá trị các thuộc tính của các nút cha hoặc nút anh em của nó • Nói chung ta có thể viết một định nghĩa trực tiếp cú pháp thành một định nghĩa S- thuộc tính. Nhưng trong một số trường hợp, việc sử dụng thuộc tính kế thừa lại thuận tiện vì tính tự nhiên của nó.
5. Ví dụ 4.4: Cây chú thích cho dòng lệnh real id1, id2, id3; như sau D T.type=real L.in=real | | real , L.in=real id3 | , L.in=real id2 | id1
6. Ví dụ 4.6: Đồ thị phụ thuộc cho cây chú thích trong ví dụ 4.4
7. • Xây dựng cây cú pháp cho biểu thức: ➢ Tương tự như việc dịch một biểu thức thành dạng hậu tố ➢ Xây dựng cây con cho biểu thức con bằng cách tạo ra một nút cho mỗi toán hạng và toán tử ➢ Mỗi một nút có thể cài đặt bằng một bản ghi có nhiều trường ➢ Trong nút toán tử, có một trường chỉ toán tử, các trường còn lại chứa con trỏ, trỏ tới các nút toán hạng
8. Ví dụ 4.7: Xây dựng cây cú pháp cho biểu thức: a - 4 + c ta dùng một dãy các lời gọi các hàm (1): p1 := mkleaf(id, entrya) (4): p4 := mkleaf(id, entryc) (2): p2 := mkleaf(num,4) (5): p5 := mknode(‘+’, p3, p4) (3): p3 := mknode(‘-‘, p1, p2) • Cây được xây dựng từ dưới lên • p1, p2, , p5 là các con trỏ, trỏ tới các nút • entrya, entryc là các con trỏ, trỏ tới mục vào của a và c trong symbol table
9. • Xây dựng cây cú pháp từ định nghĩa trực tiếp cú pháp: Căn cứ vào các luật sinh văn phạm và luật ngữ nghĩa kết hợp mà ta gọi các hàm mknode và mkleaf để tạo ra cây cú pháp Ví dụ 4.8: Ðịnh nghĩa trực tiếp cú pháp giúp việc xây dựng cây cú pháp cho biểu thức (thuộc tính tổng hợp nptr theo dõi con trỏ được trả về khi gọi các hàm) PRODUCTION SYMANTIC RULES E → E1 + T E.nptr := mknode(‘+’, E1.nptr, T.nptr) E → E1 - T E.nptr := mknode(‘-’, E1.nptr, T.nptr) E → T E.nptr := T.nptr T → (E) T.nptr := E.nptr T → id T. nptr := mkleaf(id, id.entry) T → num T.nptr := mkleaf(num, num.val)
10. Đánh giá từ dưới lên với định nghĩa S- thuộc tính • Các thuộc tính tổng hợp được đánh giá bằng cách phân tích cú pháp từ dưới lên • Bộ phân tích cú pháp lưu trữ giá trị các thuộc tính và các kí hiệu văn phạm trong STACK • Khi áp dụng reduction, giá trị tổng hợp mới được tạo từ các thuộc tính của các kí tự văn phạm bên vế phải luật sinh được lưu trữ trong STACK
11. state val X X.x Y Y.y top→ Z Z.z Ví dụ 4.10: Biểu diễn một máy tính đơn giản với LR parser PRODUCTION CODE FRAGMENT L → En print(val[top]) E → E1 + T val[ntop] := val[top - 2] + val[top] E → T T → T1 * F val[ntop] := val[top - 2] * val[top] T → F F → (E) val[ntop] := val[top - 1] F → digit
12. Ðịnh nghĩa L- thuộc tính • Mỗi định nghĩa trực tiếp cú pháp là một định nghĩa L- thuộc tính nếu mỗi một thuộc tính kế thừa của Xj (1 j n) trong vế phải của luật sinh A → X1X2 Xn chỉ phụ thuộc vào: 1. Các thuộc tính của X1, X2, , Xj-1 2. Các thuộc tính kế thừa của A.
13. • Với biểu thức 9 - 5 + 2 ta có cây phân tích cú pháp phía dưới. Khi áp dụng phép duyệt cây depth- first sẽ có kết quả dạng hậu tố là 95-2+ E T R 9 { print('9') } - T { print('-') } R 5 { print('5') } + T { print('+') } R 2 { print('2') } 
14. - Trường hợp chứa cả thuộc tính tổng hợp và thuộc tính kế thừa phải thoả mãn 3 điều kiện: 1. Thuộc tính kế thừa của một ký hiệu trong vế phải của luật sinh phải được xác định trong hành vi nằm trước ký hiệu đó 2. Một hành vi không được tham khảo tới thuộc tính tổng hợp của một ký hiệu nằm bên phải hành vi đó 3. Thuộc tính tổng hợp của ký hiệu chưa kết thúc trong vế trái chỉ có thể được xác định sau khi tất cả các thuộc tính mà nó tham khảo đã được xác định. Hành vi xác định các thuộc tính này luôn đặt cuối vế phải của luật sinh