Bài giảng Chương trình dịch - Biên dịch dựa cú pháp

Nguyễn Phương Thái Bộ môn Khoa học Máy tính  Nội dung Cú pháp điều khiển Các loại thuộc tính Đồ thị phụ thuộc Lược đồ dịch Cú pháp điều khiển trong phân tích LL Cú pháp điều khiển Cú pháp điều khiển (syntax-directed definition): là một dạng tổng quát hoá của văn phạm phi ngữ cảnh, trong đó mỗi ký hiệu văn phạm có một tập thuộc tính đi kèm, được chia thành 2 tập con là thuộc tính tổng hợp (synthesized attribute) và thuộc tính kế thừa (inherited attribute) của ký hiệu văn phạm đó. Một cây phân tích cú pháp có trình bày các giá trị của các thuộc tính tại mỗi nút được gọi là cây phân tích cú pháp có chú giải (ngữ nghĩa) (annotated parse tree). Cú pháp điều khiển (tiếp) Định nghĩa: Trong mỗi cú pháp điều khiển, mỗi sản xuất A-> có thể được liên kết với một tập các qui tắc ngữ nghĩa có dạng b=f(c1, . . .,ck) với f là một hàm và b là một thuộc tính tổng hợp của A, còn c1, . . .,ck là các thuộc tính của các ký hiệu trong sản xuất đó. Hoặc b là một thuộc tính kế thừa của một trong những ký hiệu ở vế phải của sản xuất, còn c1, . . . ,ck là thuộc tính của các ký hiệu văn phạm. Ví dụ về thuộc tính tổng hợp F1.val=3 (syntax: F1->3 semantic: F1.val=3.lexical) F2.val=4 (syntax: F2->3 semantic: F2.val=4.lexical) T2.val=3 (syntax: T2->F1 semantic: T2.val=F1.val ) T1.val=3*4=12 (syntax: T1->T2*F2 semantic: T1.val=T2.val*F2.val) F3.val=4 (syntax: F3->4 semantic: F3.val=4.lexical) T3.val=4 (syntax: T3->F3 semantic: T3.val=F3.val ) E1.val=12+4=16 (syntax: E1->E2+T3 semantic: E1.val=E2.val+T3.val) “16” (syntax: L->E1 n semantic: print(E1.val)) L E1 E2 T3 T1 T2 * F2 F1 3 + F3 n 4 4 Câu vào “3*4+4” Ví dụ về thuộc tính kế thừa Chúng ta duyệt và thực hiện các hành động ngữ nghĩa theo chiều sâu và từ trái sang phải. sẽ có kết quả lần lượt như sau: T.type = interger (syntax:T->int semantic: T.type=interger) L1.in = interger (syntax: D -> T L1 semantic: L1.in=T.type) L2.in = interger (syntax: L1 -> L2 , a 	 semantic: L2.in = L1.in ) a.entry = interger (syntax: L1 -> L2 , a semantic: addtype(a.entry,L1.in) ) L3.in = interger (syntax: L2 -> L3 , b 	 semantic: L3.in = L2.in ) b.entry = interger (syntax: L2 -> L3 , b semantic: addtype(b.entry,L2.in) ) c.entry = interger (syntax: L3 -> c semantic: addtype(c.entry,L3.in) ) D T L1 int L2 a , L3 b , c Câu vào “int c, b, a” Đồ thị phụ thuộc Nếu một thuộc tính b tại một nút trong cây phân tích cú pháp phụ thuộc vào một thuộc tính c, thì hành động ngữ nghĩa cho b tại nút đó phải được thực hiện sau khi thực hiện hành động ngữ nghĩa cho c. Sự phụ thuộc qua lại của các thuộc tính tổng hợp và kế thừa tại các nút trong một cây phân tích cú pháp có thể được mô tả bằng một đồ thị có hướng gọi là đồ thị phụ thuộc (dependency graph). Đồ thị phụ thuộc (tiếp) for mỗi nút n trong cây phân tích cú pháp do 	for mỗi thuộc tính a của ký hiệu văn phạm tại n do 	xây dựng một nút trong đồ thị phụ thuộc cho a; for mỗi nút n trong cây phân tích cú pháp do 	for mỗi hành động ngữ nghĩa b:=f(c1,c2, . . .,ck) 	đi kèm với sản xuất được dùng tại n do 	for i:=1 to k do 	xây dựng một cạnh từ nút ci đến nút b D T L real c L , b L , a type in in in entry entry entry f f f Thứ tự duyệt các hành động ngữ nghĩa Trên đồ thị DAG được xây dựng như ví dụ trên, chúng ta phải xác định thứ tự của các nút để làm sao cho khi duyệt các nút theo thứ tự này thì một nút sẽ có thứ tự sau nút mà nó phụ thuộc ta gọi là một sắp xếp topo. Tức là nếu các nút được đánh thứ tự m1, m2, . . .,mk thì nếu có mi ->mj là một cạnh từ mi đến mj thì mi xuất hiện trước mj trong thứ tự đó hay i X1 X2 . . . Xn với 1 T R R -> + T {print(‘+’)} R R ->  T -> num {print(num.val)} Ví dụ (tiếp) Kết quả dịch là “3 1 + 5 +” E T R 3 + T R + T R 1 5 1: print(‘3’) 2: print(‘1’) 3: print(‘+’) 4: print(‘5’)  5: print(‘+’) Ví dụ (tiếp) Nếu ta dùng lược đồ dịch: E -> T R R -> + T R {print(‘+’)} R ->  T -> num {print(num.val)}   Kết quả dịch là “3 1 5 + +” E T R 3 + T R + T R 1 5 1: print(‘3’) 2: print(‘1’) 5: print(‘+’) 3: print(‘5’)  4: print(‘+’) Khi thiết kế lược đồ dịch, chúng ta cần một số điều kiện để đảm bảo rằng một giá trị thuộc tính phải có sẵn khi chúng ta tham chiếu đến nó: Một thuộc tính kế thừa cho một ký hiệu ở vế phải của một sản xuất phải được tính ở một hành động nằm trước ký hiệu đó. Một hành động không được tham chiếu đến thuộc tính của một ký hiệu ở bên phải của hành động đó. Một thuộc tính tổng hợp cho một ký hiệu không kết thúc ở vế trái chỉ có thể được tính sau khi tất cả thuộc tính nó cần tham chiếu đến đã được tính xong. Hành động như thế thường được đặt ở cuối vế phải của luật sinh. Ví dụ lược đồ dịch sau đây không thoả mãn các yêu cầu này: S -> A1 A2 {A1.in:=1; A2.in:=2} A -> a {print(A.in)} Những điều kiện này được thoả nếu văn phạm có điều khiển thuần tính L. Khi đó chúng ta sẽ đặt các hành động theo nguyên tắc như sau: Hành động tính thuộc tính kế thừa của một ký hiệu văn phạm A bên vế phải được đặt trước A. Hành động tính thuộc tính tổng hợp của ký hiệu vế trái được đặt ở cuối luật sản xuất. Ví dụ Cho văn phạm biểu diễn biểu thức gồm các toán tử + và - với toán hạng là các số: E -> T R R -> + T R R -> - T R R ->  T -> ( E ) T -> num Ví dụ (tiếp) “6+4-1” E T R num(6) + T R - T R  num(4) num(1) Ví dụ (tiếp) Lược đồ dịch: E -> 	T {R.i:=T.val} 	R {E.val:=R.s} R -> 	+ 	T {R1.i:=R.i+T.val} 	R1 {R.s:=R1.s } R -> 	- 	T { R1.i:=R.i-T.val } 	R1 {R.s:=R1.s} R -> 	 {R.s:=R.i} T -> 	( E ) {T.val:=E.val} T -> 	num {T.val:=num.val} Trong đó: val là thuộc tính chứa giá trị tính được của các ký hiệu văn phạm E và T. s là thuộc tính tổng hợp và i là thuộc tính kế thừa để chứa giá trị tính được của ký hiệu R. R.i chứa giá trị của phần biểu thức đứng trước R và R.s chứa kết quả. Ví dụ (tiếp) E val=9 T val=6 R i=6 s=9 num(6) + T val=4 R i=10 s=9 - T val=1 R i=9 s=9  num(4) num(1) Cú pháp điều khiển trong phân tích LL Thiết kế dịch là dịch một lượt, tức là khi chúng ta đọc đầu vào đến đâu thì chúng ta sẽ phân tích cú pháp đến đó và thực hiện các hành động ngữ nghĩa luôn. Một phương pháp xây dựng chương trình phân tích cú pháp kết hợp với thực hiện các hành động ngữ nghĩa như sau: với mỗi một ký hiệu không kết thúc được gắn với một hàm thực hiện. Giả sử với ký hiệu không kết thúc A, ta có hàm thực hiện void ParseA(Symbol A); mỗi ký hiệu kết thúc được gắn với một hàm đối sánh xâu vào Cú pháp điều khiển trong phân tích LL (tiếp) giả sử ký hiệu không kết thúc A là vế trái của các luật A-> 1 | 2 | . . . | n Khi đó hàm phân tích ký hiệu A sẽ được định nghĩa như sau: void ParseA(Symbol A, Rule r, ...) {	if(r==A->1) 	gọi hàm xử lý ngữ nghĩa tương ứng luật A->1 	else if(r==A->2) 	gọi hàm xử lý ngữ nghĩa tương ứng luật A->2 	. . . 	else if(r==A->n) 	gọi hàm xử lý ngữ nghĩa tương ứng luật A->n   } Cú pháp điều khiển trong phân tích LL (tiếp) Đối chiếu ký hiệu đầu vào và A, tìm trong bảng phân tích LL xem sẽ khai triển A theo luật nào. Chẳng hạn ký hiệu xâu vào hiện thời a  first(i), chúng ta sẽ khai triển A theo luật A -> X1. . . Xk với i = X1. . . Xk Ở đây, ta sẽ sử dụng lược đồ dịch để kết hợp phân tích cú pháp và ngữ nghĩa. Do đó đó khi khai triển A theo vế phải, ta sẽ gặp 3 trường hợp sau: nếu phần tử đang xét là một ký hiệu kết thúc, ta gọi hàm đối sánh với xâu vào, nếu thoả mãn thì nhẩy con trỏ đầu vào lên một bước, nếu trái lại là lỗi. nếu phần tử đang xét là một ký hiệu không kết thúc, chúng ta gọi hàm duyệt ký hiệu không kết thúc này với tham số bao gồm các thuộc tính của các ký hiệu anh em bên trái, và thuộc tính kế thừa của A. nếu phần tử đang xét là một hành động ngữ nghĩa, chúng ta thực hiện hành động ngữ nghĩa này. Ví dụ E -> 	T {R.i:=T.val} 	R {E.val:=R.s} R -> 	+ 	T {R1.i:=R.i+T.val} 	R1 {R.s:=R1.s} R -> 	 {R.s:=R.i} T -> 	( E ) {T.val:=E.val} T -> 	num {T.val:=num.val} Ví dụ (tiếp) void ParseE(...) {	// chỉ có một lược đồ dịch: // E -> 	T {R.i:=T.val} 	// R {E.val:=R.s} 	ParseT(...);	R.i := T.val 	ParseR(...);	E.val := R.s	 } void ParseR(...) {	// trường hợp 1 //R -> 	+ 	//T {R1.i:=R.i+T.val} 	//R1 {R.s:=T.val+R1.i} 	if(luật=R->TR1) 	{ 	match(‘+’);// đối sánh 	ParseT(...); 	R1.i:=R.i+T.val; 	ParseR(...); R.s:=R1.s   	} 	else if(luật=R->) 	{ // R -> {R.s:=R.i} 	R.s:=R.i	 	}  } Ví dụ (tiếp) First(E)=First(T) = {(,num} First(R) = {,+} Follow(R) = {$,)} Ví dụ (tiếp)