Bài giảng Nguyên lý ngôn ngữ lập trình - Chương IV: Phân tích cú pháp

CHƯƠNG IV 
PHÂN TÍCH CÚ PHÁP 
Nội dung chính: 
Mỗi ngôn ngữ lập trình đều có các quy tắc diễn tả cấu trúc cú pháp của các chương 
trình có định dạng đúng. Các cấu trúc cú pháp này được mô tả bởi văn phạm phi ngữ 
cảnh. Phần đầu của chương nhắc lại khái niệm văn phạm phi ngữ cảnh, cách tìm một 
văn phạm tương đương không còn đệ quy trái và mơ hồ. Phần lớn nội dung của 
chương trình bày các phương pháp phân tích cú pháp thường được sử dụng trong các 
trình biên dịch: Phân tích cú pháp từ trên xuống (Top down) và Phân tích cú pháp từ 
dưới lên (Bottom up). Các chương trình nguồn có thể chứa các lỗi cú pháp. Trong quá 
trình phân tích cú pháp chương trình nguồn, sẽ rất bất tiện nếu chương trình dừng và 
thông báo lỗi khi gặp lỗi đầu tiên. Vì thế cần phải có kỹ thuật để vượt qua các lỗi cú 
pháp để tiếp tục quá trình dịch - Các kỹ thuật phục hồi lỗi. Từ văn phạm đặc tả ngôn 
ngữ lập trình và lựa chọn phương pháp phân tích cú pháp phù hợp, sinh viên có thể tự 
mình xây dựng một bộ phân tích cú pháp. Phần còn lại của chương giới thiệu công cụ 
Yacc. Sinh viên có thể sử dụng công cụ này để tạo bộ phân tích cú pháp thay vì phải tự 
cài đặt. Mô tả chi tiết về Yacc được tìm thấy ở phần phụ lục B. 
Mục tiêu cần đạt: 
Sau khi học xong chương này, sinh viên phải nắm được: 
• Các phương pháp phân tích cú pháp và các chiến lược phục hồi lỗi. 
• Cách tự cài đặt một bộ phân tích cú pháp từ một văn phạm phi ngữ cảnh xác 
định. 
• Cách sử dụng công cụ Yacc để sinh ra bộ phân tích cú pháp. 
Kiến thức cơ bản: 
Sinh viên phải có các kiến thức về: 
• Văn phạm phi ngữ cảnh (Context Free Grammar – CFG), Automat đẩy xuống 
(Pushdown Automata – PDA). 
• Cách biến đổi từ một CFG về một PDA. 
Tài liệu tham khảo: 
[1] Automata and Formal Language. An Introduction – Dean Kelley – Prentice 
Hall, Englewood Cliffs, New Jersey 07632. 
[2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey 
D.Ullman - Addison - Wesley Publishing Company, 1986. 
[3] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison - Wesley 
Publishing Company, 1996. 
[4] Design of Compilers : Techniques of Programming Language Translation 
- Karen A. Lemone - CRC Press, Inc, 1992. 
[5] Modern Compiler Implementation in C - Andrew W. Appel - Cambridge 
University Press, 1997. 
65 
I. VAI TRÒ CỦA BỘ PHÂN TÍCH CÚ PHÁP 
1. Vai trò của bộ phân tích cú pháp 
 Bộ phân tích cú pháp nhận chuỗi các token từ bộ phân tích từ vựng và xác nhận 
rằng chuỗi này có thể được sinh ra từ văn phạm của ngôn ngữ nguồn bằng cách tạo ra 
cây phân tích cú pháp cho chuỗi. Bộ phân tích cú pháp cũng có cơ chế ghi nhận các lỗi 
cú pháp theo một phương thức linh hoạt và có khả năng phục hồi được các lỗi thường 
gặp để có thể tiếp tục xử lý phần còn lại của chuỗi nhập. 
Chương 
trình 
nguồn 
token Cây 
phân tích 
cú pháp 
Bộ 
phân 
tích từ 
vựng 
Bộ phân 
tích cú 
pháp 
Phần 
còn lại 
của front 
end 
Lấy token 
tiếp 
Biểu diễn 
trung gian 
Bảng ký hiệu 
Hình 4.1 - Vị trí của bộ phân tích cú pháp trong mô hình trình biên dịch 
2. Xử lý lỗi cú pháp 
Chương trình nguồn có thể chứa các lỗi ở nhiều mức độ khác nhau: 
- Lỗi từ vựng như danh biểu, từ khóa, toán tử viết không đúng. 
- Lỗi cú pháp như ghi một biểu thức toán học với các dấu ngoặc đóng và mở 
không cân bằng. 
- Lỗi ngữ nghĩa như một toán tử áp dụng vào một toán hạng không tương thích. 
- Lỗi logic như thực hiện một lời gọi đệ qui không thể kết thúc. 
Phần lớn việc phát hiện và phục hồi lỗi trong một trình biện dịch tập trung vào giai 
đọan phân tích cú pháp. Vì thế, bộ xử lý lỗi (error handler) trong quá trình phân tích cú 
pháp phải đạt mục đích sau: 
ƒ Ghi nhận và thông báo lỗi một cách rõ ràng và chính xác. 
ƒ Phục hồi lỗi một cách nhanh chóng để có thể xác định các lỗi tiếp theo. 
ƒ Không làm chậm tiến trình của một chương trình đúng. 
3. Các chiến lược phục hồi lỗi 
Phục hồi lỗi là kỹ thuật vượt qua các lỗi để tiếp tục quá trình dịch. Nhiều chiến 
lược phục hồi lỗi có thể dùng trong bộ phân tích cú pháp. Mặc dù không có chiến lược 
nào được chấp nhận hoàn toàn, nhưng một số trong chúng đã được áp dụng rộng rãi. Ở 
đây, chúng ta giới thiệu một số chiến lược : 
a. Phương thức "hoảng sợ" (panic mode recovery): Ðây là phương pháp đơn 
giản nhất cho cài đặt và có thể dùng cho hầu hết các phương pháp phân tích. Khi một 
66 
lỗi được phát hiện thì bộ phân tích cú pháp bỏ qua từng ký hiệu một cho đến khi tìm 
thấy một tập hợp được chỉ định của các token đồng bộ (synchronizing tokens), các 
token đồng bộ thường là dấu chấm phẩy (;) hoặc end. 
 b. Chiến lược mức ngữ đoạn (phrase_level recovery): Khi phát hiện một lỗi, bộ 
phân tích cú pháp có thể thực hiện sự hiệu chỉnh cục bộ trên phần còn lại của dòng 
nhập. Cụ thể là thay thế phần đầu còn lại bằng một chuỗi ký tự có thể tiếp tục. Chẳng 
hạn, dấu phẩy (,) bởi dấu chấm phẩy (;), xóa một dấu phẩy lạ hoặc thêm vào một dấu 
chấm phẩy. 
 c. Chiến lược dùng các luật sinh sửa lỗi (error production): Thêm vào văn phạm 
của ngôn ngữ những luật sinh lỗi và sử dụng văn phạm này để xây dựng bộ phân tích 
cú pháp, chúng ta có thể sinh ra bộ đoán lỗi thích hợp để chỉ ra cấu trúc lỗi được nhận 
biết trong dòng nhập. 
 d. Chiến lược hiệu chỉnh toàn cục (global correction): Một cách lý tưởng là trình 
biên dịch tạo ra một số thay đổi trong khi xử lý một lỗi. Có những giải thuật để lựa 
chọn một số tối thiểu các thay đổi để đạt được một hiệu chỉnh có chi phí toàn cục nhỏ 
nhất. Cho một chuỗi nhập có lỗi x và một văn phạm G, các giải thuật này sẽ tìm được 
một cây phân tích cú pháp cho chuỗi y mà số lượng các thao tác chèn, xóa và thay đổi 
token cần thiết để chuyển x thành y là nhỏ nhất. Nói chung, hiện nay kỹ thuật này vẫn 
còn ở dạng nghiên cứu lý thuyết. 
II. BIẾN ÐỔI VĂN PHẠM PHI NGỮ CẢNH 
Nhiều ngôn ngữ lập trình có cấu trúc đệ quy mà nó có thể được định nghĩa bằng 
các văn phạm phi ngữ cảnh (context-free grammar) G với 4 thành phần G (V, T, P, S), 
trong đó: 
• V : là tập hữu hạn các ký hiệu chưa kết thúc hay các biến (variables) 
• T : là tập hữu hạn các ký hiệu kết thúc (terminals). 
• P : là tập luật sinh của văn phạm (productions). 
• S ∈ V: là ký hiệu bắt đầu của văn phạm (start symbol). 
Ví dụ 4.1: Văn phạm với các luật sinh sau cho phép định nghĩa các biểu thức số 
học đơn giản (với E là một biểu thức expression) : 
 E → E A E ⏐ (E) ⏐ - E ⏐ id 
 A → + ⏐ - ⏐ * ⏐ / ⏐ ↑ 
1. Cây phân tích cú pháp và dẫn xuất 
 Cây phân tích cú pháp có thể được xem như một dạng biểu diễn hình ảnh của một 
dẫn xuất. Ta nói rằng αAβ dẫn xuất ra αγβ (ký hiệu: αAβ ⇒ αγβ) nếu A → γ là một 
luật sinh, α và β là các chuỗi tùy ý các ký hiệu văn phạm. 
 Nếu α1 ⇒ α2 ⇒ .. .. ⇒ αn ta nói α1 dẫn xuất ra (suy ra) αn
 Ký hiệu ⇒ : dẫn xuất ra qua 1 bước 
 ⇒* : dẫn xuất ra qua 0 hoặc nhiều bước. 
67 
 ⇒ + : dẫn xuất ra qua 1 hoặc nhiều bước. 
 Ta có tính chất: 
1. α ⇒* α với ∀α 
 2. α ⇒* β và β ⇒* γ thì α ⇒* γ 
Cho một văn phạm G với ký hiệu bắt đầu S. Ta dùng quan hệ ⇒+ để định nghĩa 
L(G) một ngôn ngữ được sinh ra bởi G. Chuỗi trong L(G) có thể chỉ chứa một ký 
hiệu kết thúc của G. Chuỗi các ký hiệu kết thúc w thuộc L(G) nếu và chỉ nếu S ⇒+ w, 
chuỗi w được gọi là một câu của G. Một ngôn ngữ được sinh ra bởi một văn phạm gọi 
là ngôn ngữ phi ngữ cảnh. Nếu hai văn phạm cùng sinh ra cùng một ngôn ngữ thì 
chúng được gọi là hai văn phạm tương đương. 
 Nếu S ⇒* α, trong đó α có thể chứa một ký hiệu chưa kết thúc thì ta nói rằng α là 
một dạng câu (sentential form) của G. Một câu là một dạng câu có chứa toàn các ký 
hiệu kết thúc. 
 Một cây phân tích cú pháp có thể xem như một biểu diễn đồ thị cho một dẫn xuất. 
 Ðể hiểu được bộ phân tích cú pháp làm việc ta cần xét dẫn xuất trong đó chỉ có ký 
hiệu chưa kết thúc trái nhất trong bất kỳ dạng câu nào được thay thế tại mỗi bước, dẫn 
xuất như vậy được gọi là trái nhất. Nếu α ⇒ β trong đó ký hiệu chưa kết thúc trái nhất 
trong α được thay thế, ta viết α ⇒* lm β 
 Nếu S ⇒* lm α ta nói α là dạng câu trái của văn phạm. 
 Tương tự, ta có dẫn xuất phải nhất - còn gọi là dẫn xuất chính tắc (canonical 
derivations) 
 Ví dụ 4.2: Cây phân tích cú pháp cho chuỗi nhập : - (id + id) sinh từ văn phạm 
trong ví dụ 4.1 E 
E 
E 
- 
( ) 
+ E E 
idid
Hình 4.2 - Minh họa một cây phân tích cú pháp 
 Ðể thấy mối quan hệ giữa cây phân tích cú pháp và dẫn xuất, ta xét một dẫn xuất : 
α1 ⇒ α2⇒ .. .. ⇒ αn trong đó αi là một ký hiệu chưa kết thúc A. 
Với mỗi αi ta xây dựng một cây phân tích cú pháp. Ví dụ với dẫn xuất: 
 E ⇒ -E ⇒ - (E) ⇒ - (E + E) ⇒ - (id + E) ⇒ - (id + id) 
 Ta có quá trình xây dựng cây phân tích cú pháp như sau : 
68 
 E 
 - E 
E ⇒ 
_ 
E 
E 
( ) E
 - 
E 
E 
( ) E 
E E + 
⇒ ⇒ 
 - 
E 
E
( ) E 
E E + 
id 
E 
E 
( ) E 
E E + 
⇒ ⇒ 
id id 
_ 
Hình 4.3 - Xây dựng cây phân tích cú pháp từ dẫn xuất 
2. Loại bỏ sự mơ hồ 
 Một văn phạm tạo ra nhiều hơn một cây phân tích cú pháp cho cùng một chuỗi 
nhập được gọi là văn phạm mơ hồ. Nếu một văn phạm là mơ hồ, ta không thể xác định 
được cây phân tích cú pháp nào sẽ được chọn. Vì thế, ta phải viết lại một văn phạm 
nhằm tránh sự mơ hồ của nó. Một ví dụ, chúng ta sẽ loại bỏ sự mơ hồ trong văn phạm 
sau : 
 Stmt → if expr then stmt 
 ⏐ if expr then stmt else stmt 
 ⏐ other 
 Ðây là một văn phạm mơ hồ vì câu nhập if E1 then if E2 then S1 else S2 sẽ có hai 
cây phân tích cú pháp : 
Stmt 
if expr then Stmt 
if expr then Stmt elsem Stmt 
E2 S1 S2
E1 
69 
Hình 4.4 - Hai cây phân tích cú pháp cho một câu nhập 
Ðể tránh sự mơ hồ này ta đưa ra nguyên tắc "Khớp mỗi else với một then chưa 
khớp gần nhất trước đó". Với qui tắc này, ta viết lại văn phạm trên như sau : 
 Stmt → matched_stmt | unmatched_stmt 
matched_stmt → if expr then matched_stmt else matched_stmt 
 ⏐ other 
unmatched_stmt → if expr then Stmt 
 ⏐ if expr then matched_stmt else unmatched_stmt 
Văn phạm tương đương này sinh ra tập chuỗi giống như văn phạm mơ hồ trên, 
nhưng nó chỉ có một cách dẫn xuất ra cây phân tích cú pháp cho từng chuỗi nhập. 
3. Loại bỏ đệ qui trái 
 Một văn phạm là đệ qui trái (left recursive) nếu nó có một ký hiệu chưa kết thúc A 
sao cho có một dẫn xuất A ⇒+ Aα, với α là một chuỗi nào đó. Các phương pháp phân 
tích từ trên xuống không thể nào xử lý văn phạm đệ qui trái, do đó cần phải dùng một 
cơ chế biến đổi tương đương để loại bỏ các đệ qui trái. 
 Ðệ qui trái có hai loại : 
Loại trực tiếp: Dạng A → Aα 
Loại gián tiếp: A ⇒i Aα với i ≥ 2 
 Xét văn phạm như sau: 
 S → Aa | b 
 A→ Ac | Sd | ε 
 Biến S cũng là biến đệ qui trái vì S ⇒ Aa ⇒ Sda, nhưng đây không phải là đệ qui 
trái trực tiếp. 
 . Với đệ qui trái trực tiếp: Luật sinh có dạng: 
 A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn 
 Sẽ thay thế bởi : A → β1A’ | β2A’ | ... | βnA’ 
 A' → α1A'| α2A' | ... | αm A' | ε 
if expr then Stmt elsem
 S2E1 expr Stmt 
Stmt 
 E2 S1
if then 
Stmt 
 . Với đệ qui trái gián tiếp (và nói chung là đệ qui trái, ta sử dụng giải thuật sau) 
70 
‰ Giải thuật 4.1: Loại bỏ đệ qui trái 
 Input: Văn phạm không tuần hoàn và không có các luật sinh ε (nghĩa là văn phạm 
không chứa các dạng A ⇒ +A và A→ ε) 
 Output: Văn phạm tương đương không đệ qui trái 
 Phương pháp: 
1. Sắp xếp các ký hiệu không kết thúc theo thứ tự A1, A2, ..., An
2. For i:=1 to n do 
 Begin 
 for j:=1 to i -1 do 
 begin 
 Thay luật sinh dạng Ai → Ajγ bởi luật sinh Ai→ δ1γ | δ2γ | ... | δkγ 
 trong đó Aj → δ1 | δ2 | ... | δk là tất cả các Ai luật sinh hiện tại; 
 end; 
 Loại bỏ đệ qui trái trực tiếp trong số các Ai luật sinh; 
 End; 
 Ví dụ 4.3: Áp dụng thuật toán trên cho văn phạm ví dụ trên. Về lý thuyết, thuật 
toán 4.1 không bảo đảm sẽ hoạt động được trong trường hợp văn phạm có chứa các 
luật sinh ε, nhưng trong trường hợp này luật sinh A → ε rõ ràng là "vô hại". 
 1. Sắp xếp các ký hiệu chưa kết thúc theo thứ tự S, A. 
 2. Với i = 1, không có đệ qui trái trực tiếp nên không có điều gì xảy ra. 
 Với i = 2, thay các S - luật sinh vào A → Sd được: A→ Ac | Aad | bd | ε 
 Loại bỏ đệ qui trái trực tiếp cho các A luật sinh, ta được : 
 S→ Aa | b 
 A→ bdA' 
 A'→ cA' | adA | ε 
4. Tạo ra yếu tố trái 
 Tạo ra yếu tố trái (left factoring) là một phép biến đổi văn phạm rất có ích để có 
được một văn phạm thuận tiện cho việc phân tích dự đoán. Ý tưởng cơ bản là khi 
không rõ luật sinh nào trong hai luật sinh khả triển có thể dùng để khai triển một ký 
hiệu chưa kết thúc A, chúng ta có thể viết lại các A - luật sinh nhằm "hoãn" lại việc 
quyết định cho đến khi thấy đủ nguyên liệu cho một lựa chọn đúng. 
 Xét văn phạm cho câu lệnh if: 
stmt → if expr then stmt else stmt 
 | if expr then stmt 
71 
 Khi gặp token if, chúng ta không thể quyết định ngay cần chọn luật sinh nào để 
triển khai cho stmt. Ðể giải quyết vấn đề này, một cách tổng quát, khi có luật sinh 
dạng A → αβ1 | αβ2, ta biến đổi luật sinh thành dạng : 
 A → αA' 
A'→ β1 | β2
‰ Giải thuật 4.2 : Tạo yếu tố trái cho văn phạm 
 Input: Văn phạm G 
 Output: Văn phạm tương đương với yếu tố trái. 
 Phương pháp: 
 Với mỗi ký hiệu chưa kết thúc A, có các ký hiệu dẫn đầu các vế phải giống nhau, ta 
tìm một chuỗi α là chuỗi có độ dài lớn nhất chung cho tất cả các vế phải (α là yếu tố 
trái). Giả sử A → αβ1 | αβ2 | ... | αβn | γ, trong đó γ không có chuỗi dẫn đầu chung với 
các vế phải khác. Ta biến đổi luật sinh thành : 
 A → αA' | γ 
 A'→ β1 | β2 | ... | βn
Với A' là ký hiệu chưa kết thúc mới. Áp dụng lặp đi lặp lại phép biến đổi này cho 
đến khi không còn hai khả triển nào cho một ký hiệu chưa kết thúc có một tiền tố 
chung. 
Ví dụ 4.4: Áp dụng thuật toán 4.2 cho văn phạm sau: 
S → i E t S | i E t S eS | α 
E → b 
Ta có văn phạm tương đương có chứa yếu tố trái như sau : 
S → i E t S S' | α 
S' → eS | ε 
E → b 
III. PHÂN TÍCH CÚ PHÁP TỪ TRÊN XUỐNG 
 Trong mục này, chúng ta giới thiệu các ý niệm cơ bản về phương pháp phân tích 
cú pháp từ trên xuống (Top Down Parsing) và trình bày một dạng không quay lui 
hiệu quả của phương pháp phân tích từ trên xuống, gọi là phương pháp phân tích dự 
đoán (predictive parser). Chúng ta định nghĩa một lớp văn phạm LL(1) (viết tắt của 
Left-to-right parse, Leftmost-derivation, 1-symbol lockahead ), trong đó phân tích dự 
đoán có thể xây dựng một cách tự động. 
1. Phân tích cú pháp đệ qui lùi (Recursive Descent Parsing) 
 Phân tích cú pháp từ trên xuống có thể được xem như một nỗ lực tìm kiếm một dẫn 
xuất trái nhất cho chuỗi nhập. Nó cũng có thể xem như một nỗ lực xây dựng cây phân 
tích cú pháp bắt đầu từ nút gốc và phát sinh dần xuống lá. Một dạng tổng quát của kỹ 
thuật phân tích từ trên xuống, gọi là phân tích cú pháp đệ quy lùi, có thể quay lui để 
72 
quét lại chuỗi nhập. Tuy nhiên, dạng này thường rất ít gặp. Lý do là với các kết cấu 
ngôn ngữ lập trình, chúng ta hiếm khi dùng đến nó. 
2. Bộ phân tích cú pháp dự đoán (Predictive Parser) 
Trong nhiều trường hợp, bằng cách viết văn phạm một cách cẩn thận, loại bỏ đệ 
qui trái ra khỏi văn phạm rồi tạo ra yếu tố trái, chúng ta có thể thu được một văn phạm 
mà một bộ phân tích cú pháp đệ quy lùi phân tích được, nhưng không cần quay lui, gọi 
là phân tích cú pháp dự đoán. 
Xây dựng sơ ... ẽ đưa thêm các 
quy tắc khử mơ hồ (disambiguating rule), để chỉ cho phép chọn một cây phân tích cú 
pháp cho mỗi một câu nhập. Theo cách này, đặc tả ngôn ngữ về tổng thể vẫn là đơn 
nghĩa. 
1. Sử dụng độ ưu tiên và tính kết hợp của các toán tử để giải quyết đụng độ. 
 Xét văn phạm của biểu thức số học với hai toán tử + và * : 
E Æ E + E | E * E | (E) |id (1) 
 Ðây là một văn phạm mơ hồ vì nó không xác định độ ưu tiên và tính kết hợp của 
các tóan tử + và *. Trong khi đó ta có văn phạm tương đương không mơ hồ cho biểu 
thức có dạng như sau: 
 102
 E Æ E + T | T 
T Æ T * F | F (2) 
F Æ (E) | id 
 Văn phạm này xác định rằng + có độ ưu tiên thấp hơn * và cả hai toán tử đều kết 
hợp trái. Tuy nhiên có 2 lý do để chúng ta sử dụng văn phạm (1) chứ không phải là 
(2): 
1. Dễ dàng thay đổi tính kết hợp và độ ưu tiên của + và * mà không phá hủy các 
luật sinh và số các trạng thái của bộ phân tích (như ta sẽ thấy sau này). 
2. Bộ phân tích cho văn phạm (2) sẽ mất thời gian thu gọn bởi các luật sinh E Æ 
T và T Æ F. Hai luật sinh này không nói lên được tính kết hợp và độ ưu tiên. 
 Nhưng với văn phạm (1) thì làm thế nào để tránh sự đụng độ? Trước hết chúng ta 
hãy thành lập bộ sưu tập C các tập mục LR(0) của văn phạm tăng cường của nó. 
 I0: E'→ • E 
 E → • E + E 
 E → • E * E 
 E → • (E) 
 E → • id 
Goto(I0,E) I1: E'→ E • 
 E → E • + E 
 E → E • * E 
Goto(I0,() I2: E → (• E) 
 E → • E + E 
 E → • E* E 
 E → • (E) 
 E → • id 
Goto(I0,id) I3: E → id• 
Goto(I1,+ ) I4: E → E + • E 
E → • E + E 
E → • E * E 
E → • ( E) 
Goto(I2,E) I6: E'→ (E •) 
 E → E • + E 
 E → E • * E 
Goto(I2,() ≡ I2 
Goto(I2,id) ≡ I3
Goto(I4,E) I7: E → E + E • 
 E → E • + E 
 E → E • * E 
Goto(I4,( ) ≡ I2 
Goto(I4,id) ≡ I3
Goto(I5,E) I8: E → E * E • 
 E → E • + E 
 E → E • * E 
Goto(I5,() ≡ I2 
Goto(I5,id) ≡ I3
Goto(I6,)) I9: E → (E) • 
Goto(I6,+) ≡ I4 
Goto(I6,*) ≡ I5
 103
 E → • id 
Goto(I1,*) I5: E → E * • E 
E → • E + E 
E → • E * E 
E → • ( E) 
 E → • id 
Goto(I7,+) ≡ I4 
Goto(I7,*) ≡ I5
Goto(I8,+) ≡ I4 
Goto(I8,*) ≡ I5
Bảng phân tích SLR đụng độ được xây dựng như sau : 
Action Goto Trạng 
thái id + * ( ) $ E 
0 s3 s2 1 
1 s4 s5 acc 
2 s3 6 
3 r4 r4 r4 r4 
4 s3 s2 7 
5 s3 s2 8 
6 s4 s5 s9 
7 s4 / r1 s5 / r1 r1 r1 
8 s4 / r2 s5 / r2 r2 r2 
9 r3 r3 r3 r3 
Hình 4.16 - Bảng phân tích cú pháp SLR đụng độ 
 Nhìn vào bảng SLR trong hình trên, ta thấy có sụ đụng độ tại action [7, +] và 
action [7,*]; action [8, +] và action [8,*]. 
 Chúng ta sẽ giải quyết sự đụng độ này bằng quy tắc kết hợp và độ ưu tiên của các 
toán tử. Xét chuỗi nhập id + id * id 
Stack Input Output 
0 
0 id 3 
0 E 1 
0 E 1 + 4 
0 E 1 + 4 id 3 
0 E 1 + 4 E 7 
id + id * id $
+ id * id $
+ id * id $
id * id $
* id $
* id $
Shift s3 
Reduce by E Æ id 
Shift s4
Shift s3
Reduce by E Æ id 
 104
 Bây giờ đến ô đụng độ action[7, *] nên lấy r1 hay s5? Lúc này chúng ta đã phân 
tích qua phần chuỗi id * id. Nếu ta chọn r1 tức là thu gọn bởi luật sinh E Æ E + E, có 
nghĩa là chúng ta đã thực hiện phép cộng trước. Do vậy nếu ta muốn tóan tử * có độ 
ưu tiên cao hơn + thì phải chọn s5. 
 Nếu chuỗi nhập là id + id + id thì quá trình phân tích văn phạm dẫn đến hình 
trạng hiện tại là : 
 Stack Output 
 0 E 1 + 4 E 7 + id $ 
 Sẽ phải xét action [7, +] nên chọn r1 hay s4? Nếu ta chọn r1 tức là thu gọn bởi luật 
sinh E Æ E + E tức là + thực hiện trước hay toán tử + có kết hợp trái => action [7, +] 
= r1 
 Một cách tương tự nếu ta quy định phép * có độ ưu tiên cao hơn + và phép * kết 
hợp trái thì action [8, *] = r2 vì * kết hợp trái (xét chuỗi id * id * id). Action [8,+] = 
r2 vì toán tử * có độ ưu tiên cao hơn + (trường hợp xét chuỗi id * id + id) 
 Sau khi đã giải quyết được sự đụng độ đó ta có được bảng phân tích SLR đơn giản 
hơn bảng phân tích của văn phạm tương đương (2) (chỉ sử dụng 10 trạng thái thay vì 
12 trạng thái). Tương tự, ta có thể xây dựng bảng phân tích LR chính tắc và LALR cho 
văn phạm (1). 
2. Giải quyết trường hợp văn phạm mơ hồ IF THEN ELSE 
 Xét văn phạm cho lệnh điều kiện: 
 Stmt Æ if expr then stmt else stmt 
 | if expr then stmt 
 | other 
 Ðể đơn giản ta viết i thay cho if expr then, S thay cho stmt, e thay cho else và a 
thay cho other, ta có văn phạm viết lại như sau : 
S’ Æ S 
S Æ iS eS (1) 
S Æ iS (2) 
S Æ a (3) 
 Họ tập hợp mục C các tập mục LR(0) là: 
 105
 I0 : S' → • S, 
 S → • iSeS 
 S → • iS 
 S → • a 
Goto (I0,S) I1 : S' → S • 
Goto (I0,i) I2 : S → i • SeS 
 S → i • S 
 S → • iSeS 
 S → • iS 
 S → • a 
Goto (I0,a) I3: S → a • 
Goto (I2, S) I4: S → iS• eS 
 S → iS• 
Goto (I4,e) I5 : S → iSe• S 
 S → • iSeS 
 S → • iS 
 S → • a 
Goto (I5,S) I6 : S → iSeS• 
Goto(I2,i) ≡ I2 
Goto(I2,a) ≡ I3
Goto(I5,i) ≡ I2 
Goto(I5,a) ≡ I3
 Ta xây dựng bảng phân tích SLR đụng độ như sau: 
Action Goto Trạng 
thái 
i e a $ S 
0 s2 s3 1 
1 acc 
2 s2 s3 4 
3 r3 r3 
4 s5| r2 r2 
5 s2 s3 6 
6 r1 
Hình 4.17 - Bảng phân tích cú pháp LR cho văn phạm if - else 
 Ðể giải quyết đụng độ tại action[4, e]. Trường hợp này xảy ra trong tình trạng chuỗi 
ký hiệu if expr then stmt nằm trong Stack và else là ký hiệu nhập hiện hà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