›
›

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

Download
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  
PRODUCTION  
SYMANTIC RULES  
L → En  
print(E.val)  
E → E1 + T  
E → T  
E.val := E1.val + T.val  
E.val := T.val  
T → T1 * F  
T → F  
T.val := T1.val * F.val  
T.val := F.val  
F → (E)  
F → digit  
F.val := E.val  
F.val := digit.lexval  
• 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  
• 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  
Ví dụ 4.2: ĐNTTCP trong ví dụ 4.1 là định nghĩa  
S- thuộc tính. Cây chú thích cho biểu thức  
3*5+4n (n kí hiệu cho newline) như sau:  
L
|
n
E.val=19  
|
T.val=4  
+
E.val=15  
|
F.val=4  
|
|
T.val=15  
|
*
F.val=5  
digit.lexval=4  
T.val=3  
|
|
F.val=3  
|
digit.lexval=5  
digit.lexval=3  
• 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ó.  
Ví dụ 4.3: Xét định nghĩa trực tiếp cú pháp sau  
cho sự khai báo kiểu cho biến  
PRODUCTION  
SYMANTIC RULES  
D → TL  
L.in := T.type  
T → int  
T.type := integer  
T.type := real  
T → real  
L → L1, id  
L1.in := L.in;  
addtype (id.entry, L.in)  
addtype (id.entry, L.in)  
L → id  
• Các luật kết hợp với luật sinh của L gọi thủ tục  
addtype dùng để nhập kiểu cho mục vào của  
định danh trong symbol table  
Ví dụ 4.4: Cây chú thích cho dòng lệnh  
real id1, id2, id3; như sau  
D
L.in=real  
T.type=real  
|
,
|
real  
L.in=real  
id3  
|
,
id2  
L.in=real  
|
id1  
• Đồ thị phụ thuộc (dependency graph): Trong 1  
cây cú pháp có thể chứa cả thuộc tính tổng hợp  
và thuộc tính kế thừa, ta dùng đồ thị phụ thuộc  
để biểu diễn các loại thuộc tính đó  
Ví dụ 4.5: Với định nghĩa S- thuộc tính  
E → E1 + E2  
E.val := E1.val + E2.val  
Ta có đồ t
Ví dụ 4.6: Đồ thị phụ thuộc cho cây chú thích  
trong ví dụ 4.4  
Xây dựng cây cú pháp  
• Câ y cú phá p (syntax - tree) là dạng rút gọn của  
cây phân tích cú pháp dùng để biểu diễn cấu  
trúc ngôn ngữ  
• Trong cây cú pháp các toán tử và từ khóa không  
phải là nút lá mà là các nút trong. Ví dụ với luật  
sinh S → if B then S1 else S2 được biểu diễn  
bởi cây cú pháp:  
If-then-else  
B
S2  
S1  
• Trong cây cú pháp các toán hạng và từ khoá  
không xuất hiện ở nút lá  
• 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  
• Ðể xây dựng cây cú pháp cho biểu thức chúng  
ta sử dụng các hàm sau đây:  
1. mknode(op, left, right): Tạo một nút toán tử có  
nhã n là op và hai trường chứa con trỏ, trỏ tới left  
và right  
2. mkleaf(id, entry): Tạo một nút lá với nhãn là id  
và một trường chứa con trỏ entry, trỏ tới ô trong  
bảng ký hiệu  
3. mkleaf(num,val): Tạo một nút lá với nhãn là  
num và trường val, giá trị của số  
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  
• Cây cú pháp cho biểu thức a - 4 + c  
• 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 → E1 - T  
E → T  
E.nptr := mknode(‘+’, E1.nptr, T.nptr)  
E.nptr := mknode(‘-’, E1.nptr, T.nptr)  
E.nptr := T.nptr  
T → (E)  
T → id  
T → num  
T.nptr := E.nptr  
T. nptr := mkleaf(id, id.entry)  
T.nptr := mkleaf(num, num.val)  
Ví dụ 4.9: Cây cú pháp cho biểu thức a-4+c  
Đá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  
• STACK được cài đặt bởi một cặp mảng state và  
val. Mỗi ô trong stack là một con trỏ trỏ tới bảng  
phân tích LR(1). Nếu phần tử thứ i của STACK  
là ký hiệu A thì val[i] là giá trị thuộc tính kết hợp  
với A  
• Giả sử luật ngữ nghĩa A.a := f ( X.x, Y.y, Z.z )  
kết hợp với luật sinh A → XYZ. Trước khi XYZ  
được rút gọn thành A thì val[top] = Z.z, val[top -  
1] = Y.y, val[top - 2] = X.x. Sau khi rút gọn, top bị  
giảm 2 đơn vị, A nằm trong state[top] (vị trí của  
X trước đó) và thuộc tính tổng hợp nằm trong  
val[top].  
Tải về để xem bản đầy đủ
ppt 27 trang yennguyen 13/04/2022 3600
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Chương trình dịch - Chương 4: Dịch trực tiếp cú pháp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pptbai_giang_chuong_trinh_dich_chuong_4_dich_truc_tiep_cu_phap.ppt