Bài giảng Chương trình dịch - Chương III: Phân tích cú pháp

 
s 11 
blank: error 
9 
r 1 
s 7 
r 1 
r 1 
10 
r 3 
r 3 
r 3 
r 3 
11 
r 5 
r 5 
r 5 
r 5 
Ví dụ 3.9: Xét văn phạm cho các phép toán số học + và * 
39 
STACK 
INPUT 
ACTION 
(1) 
(2) 
(3) 
(4) 
(5) 
(6) 
(7) 
(8) 
(9) 
(10) 
(11) 
(12) 
(13) 
(14) 
0 
0  id 5 
0  F  3 
0  T  2 
0  T  2  *   7 
0  T  2  *   7  id  5 
0  T  2  *   7  F   10 
0  T  2 
0  E  1 
0  E  1  +  6 
0  E  1  +  6  id 5 
0  E  1  +  6  F  3 
0  E  1  +  6  T  9 
0  E  1 
id * id + id $ 
* id + id $ 
* id + id $ 
* id + id $ 
 id + id $ 
 + id $ 
+ id $ 
+ id $ 
+ id $ 
id  $ 
$ 
$ 
$ 
$ 
shift 
reduce by F ® id 
reduce by T ® F 
shift 
shift 
reduce by F ® id 
reduce by T ® T * F 
reduce by E ® T 
shift 
shift 
reduce by F ® id 
reduce by T ® F 
reduce by E ® E + T 
accept 
 Với chuỗi nhập id*id+id quá trình phân tích như sau: 
40 
Xây dựng SLR parsing table 
Có 3 phương pháp xây dựng một bảng phân tích cú pháp LR từ văn phạm là Simple LR (SLR), Canonical LR và Lookahead- LR (LALR), các phương pháp khác nhau về tính hiệu quả cũng như tính dễ cài đặt 
Phương pháp SLR, là phương pháp yếu nhất nếu tính theo số lượng văn phạm có thể xây dựng thành công, nhưng đây lại là phương pháp dễ cài đặt nhất 
Một văn phạm có thể xây dựng được SLR parser được gọi là một văn phạm SLR 
41 
Một mục LR(0) (hoặc item) của một văn phạm G là một luật sinh của G với một dấu chấm tại vị trí nào đó trong vế phải 
Ví dụ 3.10:    Luật sinh A  XYZ có 4 mục như sau: 
	A  .XYZ 
	A  X.YZ 
	A  XY.Z 
	A  XYZ. 
Luật sinh A   chỉ tạo ra một mục A  . 
42 
Văn phạm tăng cường (Augmented Grammar): G là một văn phạm với ký hiệu bắt đầu S, thêm một ký hiệu bắt đầu mới S' và luật sinh S'  S để được văn phạm mới G' gọi là văn phạm tăng cường 
Phép toán bao đóng (Closure): Giả sử I là một tập các mục của văn phạm G thì bao đóng closure(I) là tập các mục được xây dựng từ  I như sau:  
1. Tất cả các mục của I được thêm vào closure(I). 
2. Nếu A  .B closure(I) và B   là một luật sinh thì thêm B  . vào closure(I) nếu nó chưa có trong đó. Lặp lại bước này cho đến khi không thể thêm vào closure(I) được nữa 
43 
Ví dụ 3.11: Xét văn phạm tăng cường 
	E'  E 
	E   E + T | T 
	T   T * F | F 
	F   (E) | id 
Nếu I= {E'  · E} thì closure(I) bao gồm các mục sau: 
 	E'  · E                 
	E  · E + T           
	E  · T                 
	T  · T * F            
	T  · F                 
	F  · (E)              
	F  · id                
44 
Phép toán goto: Nếu I là một tập các mục và X là một ký hiệu văn phạm thì goto(I, X) là bao đóng của tập hợp các mục  A   X.  sao cho A  . X  I 
Cách tính goto(I, X): 
	1. Tạo một tập I' =  
	2. Nếu A  . X  I thì đưa A   X.  vào I', tiếp tục quá trình này cho đến khi xét hết tập I. 
	3. goto(I, X) = closure(I') 
45 
Ví dụ 3.12: Giả sử I = { E'  E., E  E . + T } 
Ta có I' = { E  E + . T } 
goto (I, +)  = closure(I') bao gồm các mục : 
	E  E + . T                       
	T  . T * F                        
	T  . F                              
	F  . (E)                           
	F  . id 
46 
Giải thuật xây dựng họ tập hợp các mục LR(0) (kí hiệu là C) của văn phạm G' 
	procedure Item (G') 
	begin 
	C := {closure({ S'  . S}) }; 
	 repeat 
	For Với mỗi tập các mục I  C và mỗi ký hiệu 	văn phạm X sao cho goto (I, X)  và 
	goto(I, X)  C thì thêm goto(I, X) vào C; 
	until  Không còn tập hợp mục nào có thể thêm vào C; 
	end; 
47 
Ví dụ 3.13: Xây dựng họ tập hợp các mục trong ví dụ 3.11 
closure({E'  E}) I 0 : 
goto ( I 0 , E)    I 1 :   
goto ( I 0 , T)    I 2 :   
goto (I 0 ,F)    I 3 :  
goto (I 0 , ( )    I 4 : 
E'  · E 
E  · E + T 
E  · T 
T  · T * F 
T  · F 
F  · (E) 
F  · id 
E'  E · 
E  E · + T 
E  T · 
T  T · * F 
T  F · 
F  (· E) 
E  · E + T 
E  · T 
T  · T *  F 
T  · F 
F  · (E) 
F  · id 
goto ( I 0 , id)   I 5 : 
goto ( I 1 , +)    I 6 : 
goto ( I 2 , *)     I 7 : 
goto ( I 4 , E)     I 8 : 
goto ( I 6 ,T)      I 9 :    
goto ( I 7 ,F)    I 10 : 
goto (I 8 ,) )     I 11 : 
F  id · 
E  E + · T 
T  · T * F 
T  · F 
F  · (E) 
F  · id 
T  T* · F 
F  · (E) 
F  · id 
F  (E ·) 
E  E · + T 
E  E + T · 
T  T · * F 
T  T * F · 
F  (E) · 
48 
Xây dựng SLR parsing table 
1. Xây dựng họ tập hợp các mục của G': C = { I 0 , I 1 , ..., I n } 
2. Trạng thái i được xây dựng từ  I i .Các action tương ứng trạng thái i xác định như sau: 
a) Nếu A  .a I i và goto (I i , a) = I j thì action[i, a] = "shift j", 
	a là ký hiệu kết thúc 
b) Nếu A   .  I i thì action[i, a] = "reduce (A  ) ", với mọi a  FOLLOW(A), A  S' 
c) Nếu S'  S ·  I i thì action[i, $] = "accept". 
	Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là SLR(1). Giải thuật thất bại 
3. Nếu goto (I i ,A)=I j thì goto [i, A] = j, A là kí hiệu chưa kết thúc 
4. Các ô không xác định được bởi 2 và 3 đều là “error” 
5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa S’  · S 
49 
Xây dựng bảng phân tích LR chính tắc 
LR chính tắc (canonical LR) là kĩ thuật chung nhất để xây dựng LR parsing table cho một văn phạm 
Một mục LR(1) (item) là một cặp [A  ., a] trong đó A   là một luật sinh, a- là kí tự lookahead là một kí hiệu kết thúc hoặc $ 
Nếu  thì a không có ý nghĩa nhưng nếu = thì việc reduce theo luật A   chỉ được thực hiện nếu kí tự đọc vào tiếp theo là a 
50 
Phép toán bao đóng (Closure): Giả sử I là một tập các mục LR(1) của văn phạm G thì bao đóng closure(I) là tập các mục được xây dựng từ  I như sau:  
1. Tất cả các mục của I được thêm vào closure(I). 
2. Nếu [A  .B, a] closure(I), B   là một luật sinh và b  FIRST(  a) thì thêm [B  ., b] vào closure(I) nếu nó chưa có trong đó. Lặp lại bước này cho đến khi không thể thêm vào closure(I) được nữa 
Phép toán goto: Nếu I là một tập các mục và X là một ký hiệu văn phạm thì goto(I, X) là bao đóng của tập hợp các mục  [A   X. , a] sao cho [A  . X , a] I 
51 
Giải thuật xây dựng họ tập hợp các mục LR(1) (kí hiệu là C) của văn phạm G' 
	procedure Item (G') 
	begin 
	C := {closure({[ S'  . S, $ ]})}; 
	 repeat 
	For Với mỗi tập các mục I  C và mỗi ký hiệu 	văn phạm X sao cho goto (I, X)  và 
	goto(I, X)  C thì thêm goto(I, X) vào C; 
	until  Không còn tập hợp mục nào có thể thêm vào C; 
	end; 
52 
closure({S'  S }) I 0 : 
goto ( I 0 , S)    I 1 :   
goto ( I 0 , C)    I 2 :   
goto (I 0 , c)    I 3 :  
S'  · S, $ 
S  · CC, $ 
C  · cC, c/d 
C  · d, c/d 
S'  S ·, $ 
S  C ·C, $ 
C  · cC, $ 
C  · d, $ 
C  c ·C, c/d 
C  · cC, c/d 
C  · d, c/d 
goto (I 0 , d )    I 4 : 
goto ( I 2 , C)   I 5 : 
goto ( I 2 , c)    I 6 : 
goto ( I 2 , d)     I 7 : 
goto ( I 3 , C)     I 8 : 
goto ( I 6 ,C)    I 9 :   
C  d ·, c/d 
S  CC ·, $ 
C  c · C, $ 
C  · cC, $ 
C  · d, $ 
C  d ·, $ 
C  cC ·, c/d 
C  cC ·, $ 
Ví dụ 3.14: Xây dựng họ tập hợp các mục LR(1) cho văn phạm dưới đây 
	 S'  S 
	(1)    S  CC 
	(2)    C  cC 
	(3) C  d 
53 
Xây dựng canonical LR parsing table 
1. Xây dựng họ tập hợp các mục LR(1) của G': C = {I 0 , I 1 ,.., I n } 
2. Trạng thái i được xây dựng từ  I i .Các action tương ứng trạng thái i xác định như sau: 
a) Nếu [A  .a, b] I i và goto (I i , a) = I j thì action[i, a] = "shift j", a là ký hiệu kết thúc 
b) Nếu [A   ., a]  I i thì action[i, a] = "reduce (A  .) ", A  S' 
c) Nếu [S'  S ·, $]  I i thì action[i, $] = "accept". 
	Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là LR(1). Giải thuật thất bại 
3. Nếu goto (I i ,A)=I j thì goto [i, A] = j, A là kí hiệu chưa kết thúc 
4. Các ô không xác định được bởi 2 và 3 đều là “error” 
5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa [S’  · S, $] 
54 
State 
Action 
Goto 
c 
d 
$ 
S 
C 
0 
s3 
s4 
1 
2 
1 
acc 
2 
s6 
s7 
5 
3 
s3 
s4 
8 
4 
r3 
r3 
5 
r1 
6 
s6 
s7 
9 
7 
r3 
8 
r2 
r2 
9 
r2 
 Canonical LR parsing table cho văn phạm trong ví dụ 3.14 
55 
LALR là phương pháp canonical parsing trong đó các trạng thái được nhóm lại với nhau nhờ đó bảng phân tich cấu trúc có kích thước nhỏ hơn (có thể so sánh với SLR) 
Hạt nhân (core) của một tập hợp mục LR(1) có dạng {[A . , a ]}, trong đó A  là một luật sinh và a là ký hiệu kết thúc có hạt nhân (core) là tập hợp {A . }. 
Trong họ tập hợp các mục LR(1) C = {I 0 , I 1 ,..., I n } có thể có các tập hợp các mục có chung một hạt nhân. 
Xây dựng bảng phân tích LALR 
56 
Xây dựng LALR parsing table 
1. Xây dựng họ tập hợp các mục LR(1) của G': C = {I 0 , I 1 ,.., I n } 
2. Nhóm các mục có cùng core trong C được C' = {J 0 , J 1 ,.., J m } 
3. Trạng thái i được xây dựng từ  J i .Các action tương ứng trạng thái i xác định tương tự như canonical LR 
	Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là LALR(1). Giải thuật thất bại 
3. Xây dựng bảng goto : Giả sử J = I 1  I 2  .  I k . Vì I 1 , I 2 , ... I k có chung hạt nhân nên goto (I 1 ,X), goto (I 2 ,X), ..., goto (I k ,X) cũng có chung hạt nhân. 
	Ðặt K bằng hợp tất cả các tập hợp có chung hạt nhân với goto (I1,X) khi đó goto(J, X) =K. 
57 
State 
Action 
Goto 
c 
d 
$ 
S 
C 
0 
s36 
s47 
1 
2 
1 
acc 
2 
s36 
s47 
5 
36 
s36 
s47 
89 
47 
r3 
r3 
r3 
5 
r1 
89 
r2 
r2 
r2 
 LALR parsing table cho văn phạm trong ví dụ 3.14 
58 
Công cụ phân tích cú pháp Yacc 
Giống như Lex, Yacc (yet another compiler compiler) là câu lệnh sẵn có của UNIX và là một công cụ hữu hiệu cho phép xây dựng bộ phân tích cú pháp một cách tự động 
Yacc được tạo bởi S. C. Johnson vào những năm đầu của thập kỉ 70 
 Yacc sử dụng phương pháp LALR 
59 
Yacc specification 
translate.y 
Yacc 
compiler 
y.tab.c 
y.tab.c 
C 
compiler 
a.out 
input 
a.out 
output 
60