Trình biên dịch - Chương 4: Phân tích cú pháp

ành. Sử dụng 
nguyên tắc kết hợp mỗi else với một then chưa kết hợp gần nhất trước đó nên ta phải 
Shift else vào Stack để kết hợp với then nên action [4, e] = s5. 
 Ví dụ 4.29: Với chuỗi nhập i i a e a 
(if expr1 then if expr2 then a1 else a2) 
 106
 Stack Input Output 
0 
0 i 2 
0 i 2 i 2 
0 i 2 i 2 a 3 
0 i 2 i 2 S 4 
0 i 2 i 2 S 4 e 5 
0 i 2 i 2 S 4 e 5 a 3 
0 i 2 i 2 S 4 e 5 S 6 
0 i 2 S 4 
0 s 1 
i i a e a $
i a e a $
a e a $
e a $
a $
$
$
$
$
$
Shift s2 
Shift s2
Shift s3
Reduce by S Æ a 
Shift s5
Shift s3
Reduce by S Æ a 
Reduce by S Æ iS eS 
Reduce by S Æ iS 
VIII. BỘ SINH BỘ PHÂN TÍCH CÚ PHÁP 
Phần này trình bày cách dùng một bộ sinh bộ phân tích cú pháp (parser 
generator) hỗ trợ cho việc xây dựng kỳ đầu của một trình biện dịch. Một trong những 
bộ sinh bộ phân tích cú pháp là YACC (Yet Another Compiler - Compiler). Phiên bản 
đầu tiên của Yacc được S.C.Johnson tạo ra và hiện Yacc được cài đặt như một lệnh 
của hệ UNIX và đã được dùng để cài đặt cho hàng trăm trình biên dịch. 
1. Bộ sinh thể phân tích cú pháp Yacc 
 Đặc tả Yacc 
Translate.y 
Yacc 
Compiler 
Y.tab.c 
Y.tab.c C Compiler 
Input
a.out 
Output a.out 
Hình 4.18 - Tạo một chương trình dịch input / output với Yacc 
 Một chương trình dịch có thể được xây dựng nhờ Yacc bằng phương thức được 
minh họa trong hình 4.18 trên. Trước tiên, cần chuẩn bị một tập tin, chẳng hạn là 
translate.y, chứa một đặc tả Yacc của chương trình dịch. Lệnh yacc translate.y của hệ 
UNIX sẽ biến đổi tập tin translate.y thành một chương trình C có tên là y.tab.C bằng 
phương pháp LALR đã trình bày ở trên. Chương trình y.tab.C là một biểu diễn của bộ 
phân tích cú pháp LALR được viết bằng ngôn ngữ C cùng với các thủ tục C khác có 
thể do người sử dụng chuẩn bị. Bằng cách dịch y.tab.C cùng với thư viện ly chứa 
chương trình phân tích cú pháp LR nhờ lệnh cc y.tab.C - ly chúng ta thu được một 
chương trình đối tượng a.out thực hiện quá trình dịch được đặc tả bởi chương trình 
Yacc ban đầu. Nếu cần thêm các thủ tục khác, chúng có thể được biên dịch hoặc được 
tải vào y.tab.C giống như mọi chương trình C khác. 
 107
 2. Ðặc tả YACC 
Một chương trình nguồn Yacc bao gồm 3 phần: 
Phần khai báo 
% % 
Các luật dịch 
%% 
Các thủ tục 
Ví dụ 4.30: Ðể minh họa việc chuẩn bị một chương trình nguồn Yacc, chúng ta 
hãy xây dựng một chương trình máy tính bỏ túi đơn giản, đọc một biểu thức số học, 
ước lượng rồi in ra giá trị số của nó. Chúng ta xây dựng bắt đầu từ văn phạm sau : 
E → E + T | T 
T → T * F | F 
F → (E) | digit 
 Token digit là một ký hiệu số từ 0 đến 9. Một chương trình Yacc dành cho văn 
phạm này như sau : 
%{ 
# include 
%} 
% token DIGIT 
%% 
line : expr '\n' { print ("%d\n", $1); } 
 ; 
expr : expr '+' term { $$ = $1 + $3; } 
 | term 
 ; 
 term : term '* ' factor { $$ = $1 * $3; } 
 | factor 
 ; 
 factor: '(' expr ')' { $$ = $2 ; } 
 | DIGIT 
 ; 
 108
 %% 
 yylex ( ) 
 { int c 
 c = getchar ( ); 
 if (isdigit(c)) 
 { yyval = c -'0'; 
 return DIGIT; 
 } 
 return c; 
 } 
Phần khai báo có thể bao gồm 2 phần nhỏ: 
- Khai báo C đặt nằm trong cặp dấu %{ và }%. Những khai báo này sẽ được sử 
dụng trong phần 2 và phần 3. 
- Khai báo các token (DIGIT là một token). Các token khai báo ở đây sẽ được 
dùng trong phần 2 và phần 3. 
Phần luật dịch: Mỗi luật dịch là một luật sinh kết hợp với hành vi ngữ nghĩa. 
 Mỗi luật sinh có dạng 
 → | | ... 
 được mô tả trong Yacc : 
 : { hành vi ngữ nghĩa 1 } 
 | { hành vi ngữ nghĩa 2 } 
 ... 
 | { hành vi ngữ nghĩa n } 
 ; 
Trong luật sinh, các ký tự nằm trong cặp dấu nháy đơn. 'c' là một ký hiệu kết 
thúc c, một chuỗi chữ cái và chữ số không nằm trong cặp dấu nháy đơn và không được 
khai báo là token sẽ là ký hiệu chưa kết thúc. 
Hành vi ngữ nghĩa của Yacc là một chuỗi các lệnh C có dạng: 
ƒ $$ Giá trị thuộc tính kết hợp với ký hiệu chưa kết thúc bên vế trái. 
ƒ $I Giá trị thuộc tính kết hợp với ký hiệu văn phạm thứ i (kết thúc hoặc chưa) 
của vế phải. 
 109
 Phần thủ tục: Là các thủ tục viết bằng ngôn ngữ C 
Ở đây một bộ phân tích từ vựng yylex( ) sinh ra một cặp gồm token và giá trị 
thuộc tính kết hợp với nó. Các token được trả về phải được khai báo trong phần khai 
báo. Giá trị thuộc kết hợp với token giao tiếp với bộ phân tích cú pháp thông qua biến 
yylval (một biến được định nghĩa bởi yacc) 
 Chú ý: Chúng ta có thể kết hợp Lex và Yacc bằng cách dùng #include 
"lex.yy.c" thay cho thủ tục yylex( ) trong phần thứ 3. 
 110
 BÀI TẬP CHƯƠNG IV 
4.1. Cho văn phạm G chứa các luật sinh sau: 
 S → ( L)⏐ a 
 L → L , S | S 
a) Hãy chỉ ra các thành phần của văn phạm phi ngữ cảnh cho G. 
b) Viết văn phạm tương đương sau khi loại bỏ đệ quy trái . 
c) Xây dựng bộ phân tích cú pháp dự đoán cho văn phạm. 
d) Hãy dùng bộ phân tích cú pháp đã được xây dựng để vẽ cây phân tích cú pháp 
cho các câu nhập sau: 
i) (a, a) 
ii) (a, (a, a)) 
iii) (a, (a, a), (a, a))) 
e) Xây dựng dẫn xuất trái, dẫn xuất phải cho từng câu ở phần d 
f) Hãy cho biết ngôn ngữ do văn phạm G sinh ra ? 
4.2. Cho văn phạm G chứa các luật sinh sau: 
 S → aSbS⏐ bSaS | ε 
a) Chứng minh văn phạm này là mơ hồ bằng cách xây dựng 2 chuỗi dẫn xuất trái 
khác nhau cho cùng câu nhập abab. 
b) Xây dựng các chuỗi dẫn xuất phải tương ứng cho câu nhập abab. 
c) Vẽ các cây phân tích cú pháp tương ứng. 
d) Văn phạm này sinh ra ngôn ngữ gì ? 
e) Xây dựng bộ phân tích cú pháp đệ quy lùi cho văn phạm trên. Có thể xây dựng 
bộ phân tích cú pháp dự đoán cho văn phạm này không ? 
4.3. Cho văn phạm G chứa các luật sinh sau: 
 bexpr → bexpr or bterm | bterm 
 bterm → bterm and bfactor | bfactor 
 bfactor → not bfactor | (bexpr) | true | false 
a) Hãy xây dựng bộ phân tích cú pháp dự đoán cho văn phạm G. 
b) Xây dựng cây phân tích cú pháp cho câu : not ( true and false ) 
c) Chứng minh rằng văn phạm này sinh ra toàn bộ các biểu thức boole. 
 111
 d) Văn phạm G có là văn phạm mơ hồ không ? Tại sao ? 
e) Xây dựng bộ phân tích cú pháp SLR cho văn phạm. 
4.4. Cho văn phạm G chứa các luật sinh sau: 
 R → R + R | RR | R* | (R) | a | b 
a) Chứng minh rằng văn phạm này sinh ra mọi biểu thức chính quy trên các ký hiệu 
a và b. 
b) Chứng tỏ đây là văn phạm mơ hồ. 
c) Xây dựng văn phạm không mơ hồ tương đương với thứ tự ưu tiên của các phép 
tóan giảm dần như sau : phép bao đóng, phép nối kết, phép hợp. 
d) Vẽ cây phân tích cú pháp trong cả hai văn phạm trên cho câu nhập : a + b * c 
e) Xây dựng bộ phân tích cú pháp dự đoán từ văn phạm không mơ hồ. 
f) Xây dựng bảng phân tích cú pháp SLR cho văn phạm G. Ðề nghị một quy tắc 
giải quyết đụng độ sao cho các biểu thức chính quy được phân tích một cách bình 
thường. 
4.5. Văn phạm sau đây là một đề nghị điều chỉnh tính mơ hồ cho văn phạm chứa câu 
lệnh if - then - else: 
 Stmt → if expr then stmt 
 | matched_stmt 
 Matched_Stmt → if expr then matched_stmt else stmt 
 | other 
Chứng minh rằng văn phạm này vẫn mơ hồ. 
4.6. Thiết kế văn phạm cho các ngôn ngữ sau. Ngôn ngữ nào là chính quy? 
a) Tập tất cả các chuỗi 0 và 1 sao cho mỗi số 0 có ít nhất một số 1 ở ngay sau nó. 
b) Các chuỗi 0 và 1 với số số 0 bằng số số 1. 
c) Các chuỗi 0 và 1 với số số 0 không bằng số số 1. 
d) Các chuỗi 0 và 1 không chứa chuỗi 001 như chuỗi con. 
4.7. Cho văn phạm G chứa các luật sinh sau : 
 S → aSa | aa 
Xây dựng bộ phân tích cú pháp đệ quy lùi cho văn phạm với yêu cầu phải thử khả 
triển aSa trước aa. 
 112
 4.8. Cho văn phạm G chứa các luật sinh sau: 
 S → aAB 
 A → Abc | b 
 B → d 
a) Xây dựng bộ phân tích cú pháp dự đoán cho văn phạm . 
b) Hãy dùng bộ phân tích cú pháp đã được xây dựng để phát sinh cây phân tích cú 
pháp cho câu nhập: abbcd 
4.9. Cho văn phạm G chứa các luật sinh sau: 
 E → E or T | T 
 T → T and F | F 
 F → ( E) | not F | id 
a) Hãy xây dựng bộ phân tích cú pháp dự đoán cho văn phạm. 
b) Vẽ cây phân tích cú pháp cho câu nhập : id and not ( id or id ) 
4.10. Cho văn phạm G chứa các luật sinh sau: 
 S → AB 
 A → Ab | a 
 B → cB | d 
a) Xây dựng bộ phân tích cú pháp thứ tự ưu tiên cho văn phạm . 
b) Hãy dùng bộ phân tích cú pháp đã xây dựng để phát sinh cây phân tích cú pháp 
cho câu nhập: abccd 
4.11. Cho văn phạm G: 
 S → D • D | D 
 D → DB | B 
 B → 0 | 1 
a) Xây dựng bộ phân tích cú pháp thứ tự ưu tiên cho văn phạm . 
b) Hãy dùng bộ phân tích cú pháp đã xây dựng để phát sinh cây phân tích cú pháp 
cho câu nhập: 101•101 
4.12. Cho văn phạm G 
 Assign → id : = exp 
 Exp → Exp + Term | Term 
 113
 Term → Term * Factor | Factor 
 Factor → id | ( Exp ) 
a) Xây dựng bộ phân tích cú pháp thứ tự ưu tiên cho văn phạm . 
b) Hãy dùng bộ phân tích cú pháp đã được xây dựng để phát sinh cây phân tích cú 
pháp cho câu nhập: id : = id + id * id 
4.13. Cho văn phạm mơ hồ như sau: 
 S → AS | b 
 A → SA | a 
a) Xây dựng họ tập hợp mục LR(0) cho văn phạm này. 
b) Xây dựng bảng phân tích cú pháp SLR . 
 c) Thực hiện quá trình phân tích cú pháp SLR khả triển cho chuỗi nhập : abab 
d) Xây dựng bảng phân tích cú pháp chính tắc . 
e) Xây dựng bảng phân tích cú pháp LALR . 
4.14. Cho văn phạm G như sau: 
 E → E + T | T 
 T → TF | F 
 F → F * | a | b 
a) Xây dựng bảng phân tích cú pháp SLR cho văn phạm này. 
b) Thực hiện quá trình phân tích cú pháp SLR cho chuỗi nhập : b + ab* a 
c) Xây dựng bảng phân tích cú pháp LALR. 
4.15. Chứng tỏ rằng văn phạm sau đây: 
 S → Aa | bAc | dc | bda 
 A → d 
là LALR(1) nhưng không phải SLR(1). 
4.16. Cho văn phạm G như sau: 
 E → E sub R | E sup E | { E } | c 
 R → E sup E | E 
a) Xây dựng bảng phân tích cú pháp SLR cho văn phạm này. 
b) Ðề nghị một quy tắc giải quyết đụng độ để các biểu thức text có thể được phân 
tích một cách bình thường. 
 114
4.17. Viết một chương trình Yacc nhận chuỗi input là các biểu thức số học, sinh ra 
output là chuỗi biểu thức hậu tố tương ứng. 
4.18. Viết một chương trình Yacc nhận biểu thức chính quy làm chuỗi input và sinh ra 
output là cây phân tích cú pháp của nó. 
 115