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...
Đnh nghĩa tr c ti p cú phápị ự ế
•Ðịnh nghĩa trực tiếp cú pháp (syntax- directed
definition) là sự tổng quát hóa một văn phạm phi
ngữ cảnh, trong đó mỗi ký hiệu văn phạm kết hợp
với một tập các thuộc tính (attribute)
•Các thuộc tính có thể là một xâu, một số, một kiểu
dữ liệu, một địa chỉ trong bộ nhớ...
•Giá trị các thuộc tính được tính bởi các luật ngữ
nghĩa (semantic rule) đi kèm. Mỗi luật ngữ nghĩa
được viết như lời gọi các thủ tục hoặc một đoạn
chương trình
•Cây phân tích cú pháp có trình bày giá trị các thuộc
tính tại mỗi nút gọi là cây chú thích
•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
Ví dụ 4.1: Định nghĩa trực tiếp cú pháp (ĐNTTCP)
cho một máy tính đơn giản
•Token digit có thuộc tính tổng hợp lexval mà giá trị
được cung cấp bởi bộ phân tích từ vựng
PRODUCTION SYMANTIC RULES
L En
E E1 + T
E T
T T1 * F
T F
F (E)
F digit
print(E.val)
E.val := E1.val + T.val
E.val := T.val
T.val := T1.val * F.val
T.val := F.val
F.val := E.val
F.val := digit.lexval
•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