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

CHƯƠNG IVDị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 (c 1 , c 2 ,..., c k ) 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à c 1 , c 2 ,..., c k 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à c 1 , c 2 ,..., c k 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 à E n 
E à E 1 + T 
E à T 
T à T 1 * F 
T à F 
F à (E) 
F à digit 
print(E.val) 
E.val := E 1 .val + T.val 
E.val := T.val 
T.val := T 1 .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 
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 
| 
E.val=19 
| 
+ 
E.val=15 
| 
T.val=15 
| 
* 
T.val=3 
| 
F.val=3 
| 
digit .lexval=3 
F.val=5 
| 
digit .lexval=5 
T.val=4 
| 
F.val=4 
| 
digit .lexval=4 
n 
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 
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 
PRODUCTION 
SYMANTIC RULES 
D à TL 
T à int 
T à real 
L à L 1 , id 
L à id 
L.in := T.type 
T.type := integer 
T.type := real 
L 1 .in := L.in; 
addtype (id.entry, L.in) 
addtype (id.entry, L.in) 
Ví dụ 4.4: Cây chú thích cho dòng lệnh 
	 real id 1 , id 2 , id 3 ; như sau 
D 
T.type=real 
| 
real 
L.in=real 
| 
, 
id 3 
L.in=real 
| 
id 1 
L.in=real 
| 
, 
id 2 
Đồ 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ó đồ thị phụ thuộc: 
Ví dụ 4.6: Đồ thị phụ thuộc cho cây chú thích trong ví dụ 4.4 
Luật ngữ nghĩa addtype ( id . entry, L.in) tạo ra các nút giả 6,8 và 10 
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: 
Trong cây cú pháp các toán hạng và từ khoá không xuất hiện ở nút lá 
B 
If-then-else 
S 2 
S 1 
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): p 1 := mkleaf ( id , entry a)  (4): p 4 := mkleaf ( id , entryc ) 
	(2): p 2 := mkleaf (num , 4 )        (5): p 5 := mknode (‘+’, p 3 , p 4 ) 
	(3): p 3 := mknode ( ‘-‘, p 1 , p 2 )   
Cây được xây dựng từ dưới lên 
p 1 , p 2 ,..., p 5 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 à E 1 + T 
E à E 1 - T 
E à T 
T à (E) 
T à id 
T à num 
E.nptr := mknode(‘+’, E 1 .nptr, T.nptr) 
E.nptr := mknode(‘-’, E 1 .nptr, T.nptr) 
E.nptr := T.nptr 
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]. 
Ví dụ 4.10: Biểu diễn một máy tính đơn giản với LR parser 
state 
val 
... 
... 
X 
X.x 
Y 
Y.y 
top 
Z 
Z.z 
... 
... 
PRODUCTION 
CODE FRAGMENT 
L à E n 
E à E 1 + T 
E à T 
T à T 1 * F 
T à F 
F à (E) 
F à digit 
print(val[top]) 
val[ntop] := val[top - 2] + val[top] 
val[ntop] := val[top - 2] * val[top] 
val[ntop] := val[top - 1] 
Bảng sau trình bày quá trình thực hiện của bộ phân tích cú pháp với chuỗi nhập vào 3*5+4 n 
IINPUT 
state 
val 
PRODUCTION USED 
3 * 5 + 4 n 
* 5 + 4 n 
* 5 + 4 n 
 *5 + 4 n 
5 + 4 n 
+ 4 n 
+ 4 n 
+ 4 n 
+ 4 n 
4 n 
n 
n 
n 
n 
_ 
3 
F 
T 
T* 
T * 5 
T * F 
T 
E 
E + 
E + 4 
E + F 
E + T 
E 
E n 
L 
_ 
3 
3 
3 
3 - 
3 - 5 
3 - 5 
15 
15 
15 - 
15 - 4 
15 - 4 
15 - 4 
19 
19 - 
19 
F à digit 
T à F 
F à digit 
T à T * F 
E à T 
F à digit 
T à F 
E à E + T 
L à En   
Ðị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 X j (1 j n) trong vế phải của luật sinh A X 1 X 2 ...X n chỉ phụ thuộc vào: 
	1. Các thuộc tính của X 1 , X 2 ,..., X j-1   
	2. Các thuộc tính kế thừa của A. 
Lược đồ dịch 
Lược đồ dịch (translation scheme) là một văn phạm phi ngữ cảnh trong đó các thuộc tính được kết hợp với các ký hiệu văn phạm và các hành vi ngữ nghĩa đặt trong cặp dấu { } được xen vào bên phải của luật sinh 
Ví dụ 4.11 : Lược đồ dịch một biểu thức trung tố với phép cộng và trừ thành dạng hậu tố: 
	E T R 
	R addop   T { print ( addop .lexeme) } R 1 |  
	T num        { print ( num .val) } 
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 
R 
- 
T 
+ 
T 
R 
2 
{ print('9') } 
9 
{ print('-') } 
{ print('5') } 
5 
R 
T 
{ print('+') } 
{ print('2') } 
 
Cách xây dựng một lược đồ dịch  
	- Trường hợp chỉ chứa thuộc tính tổng hợp: Với mỗi một luật ngữ nghĩa, ta tạo ra lệnh gán tương ứng và đặt vào cuối vế phải luật sinh 
Ví dụ 4.12: 
	Luật sinh                  Luật ngữ nghĩa 
 T T 1 * F                T.val := T 1 .val * F.val 
	Ta có lược đồ dịch: 
	T T 1 * F { T.val := T 1 .val * F.val} 
	- 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