Giáo trình Xây dựng chương trình dịch - Chương IV: Phân tích cú pháp

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương IV: Phân tích cú pháp

1. Dạng câu phải Handle Luật thu gọn id1 + id2 * id3 id1 E → id E + id2 * id3 id2 E → id E + E * id3 id3 E → id E + E * E E * E E → E * E E + E E + E E → E + E E Thành công 4. Cài đặt bộ phân tích cú pháp Shift - Reduce Có hai vấn đề cần phải giải quyết nếu chúng ta dùng kỹ thuật phân tích cú pháp này. Thứ nhất là định vị chuỗi con cần thu gọn trong dạng câu dẫn phải, và thứ hai là xác định luật sinh nào sẽ được dùng nếu có nhiều luật sinh chứa chuỗi con đó ở vế phải. Cấu tạo: Dùng 1 Stack để lưu các ký hiệu văn phạm. Dùng 1 bộ đệm nhập INPUT để giữ chuỗi nhập cần phân tích w. Ta dùng ký hiệu $ để đánh dấu đáy Stack và xác định cuối chuỗi nhập. Hoạt động: 1. Khởi đầu thì Stack rỗng và w nằm trong bộ đệm input. 2. Bộ phân tích đẩy các ký hiệu nhập vào trong Stack cho đến khi một handle β nằm trên đỉnh Stack. 3. Thu gọn β thành vế trái của một luật sinh nào đó. 4. Lặp lại bước 2 và 3 cho đến khi gặp một lỗi hoặc Stack chứa ký hiệu bắt đầu và bộ đệm input rỗng (thông báo kết thúc thành công). Ví dụ 4.15: Với văn phạm E → E + E | E * E | (E) | id và câu nhập id1 + id2 * id3 Quá trình phân tích cú pháp sẽ thực hiện như sau: STACK INPUT ACTION $ id1 + id2 * id3 $ Đẩy $ id1 + id2 * id3 $ Thu gọn bởi E → id $ E + id2 * id3 $ Đẩy $ E + id2 * id3 $ Đẩy $ E + id2 * id3 $ Thu gọn bởi E → id $ E + E * id3 $ Đẩy $ E + E * id3 $ Đẩy $ E + E * id3 $ 85
2. Ta có bảng quan hệ thứ bậc các toán tử như sau : id + * $ id •> •> •> + * •> •> $ + * $ Chẳng hạn, đầu tiên (trong ví dụ của chúng ta là •> sau id đầu tiên). 2. Sau đó, duyệt ngược lại (hướng sang trái), vượt qua các =• (nếu có) cho đến khi gặp a đầu tiên và bên phải $ . Ðiều này chứng tỏ handle là E * E được thu gọn thành E. Vì các ký hiệu chưa kết thúc không ảnh hưởng gì đến việc phân tích cú pháp, nên chúng ta không cần phải phân biệt chúng. ‰ Giải thuật 4.5: Phân tích cú pháp thứ bậc toán tử Input: Chuỗi nhập w và bảng các quan hệ thứ bậc. Output: Nếu w là chuỗi chuẩn dạng đúng thì cho ra một cây phân tích cú pháp. Ngược lại, thông báo lỗi. Phương pháp: Khởi đầu, Stack chứa ký hiệu $ và bộ đệm chứa câu nhập dạng w$. Ðặt con trỏ ip trỏ tới ký hiệu đầu tiên của w$ ; Repeat forever If $ nằm ở đỉnh Stack và ip chỉ đến $ then return 87
3. 1. Thuật toán phân tích cú pháp LR INPUT a1 ai an $ STACK sm Chương trình phân OUTPUT Xm tích cú pháp LR sm-1 Xm-1 action goto . . . s0 Hình 4.12 - Mô hình bộ phân tích cú pháp LR • Stack lưu một chuỗi s0X1s1X2s2 Xmsm trong đó sm nằm trên đỉnh Stack. Xi là một ký hiệu văn phạm, si là một trạng thái tóm tắt thông tin chứa trong Stack bên dưới nó. • Bảng phân tích bao gồm 2 phần: hàm action và hàm goto. 9 action[sm, ai] có thể có một trong 4 giá trị : 1. shift s: đẩy s, trong đó s là một trạng thái. 2. reduce A→ β: thu gọn bằng luật sinh A→ β. 3. accept: Chấp nhận 4. error: Báo lỗi 9 Goto lấy 2 tham số là một trạng thái và một ký hiệu văn phạm, nó sinh ra một trạng thái. Cấu hình (configuration) của một bộ phân tích cú pháp LR là một cặp thành phần, trong đó, thành phần đầu là nội dung của Stack, phần sau là chuỗi nhập chưa phân tích: (s0X1s1X2s2 Xmsm, ai ai+1 an $) Với sm là ký hiệu trên đỉnh Stack, ai là ký hiệu nhập hiện tại, cấu hình có được sau mỗi dạng bước đẩy sẽ như sau : 1. Nếu action[sm, ai] = Shift s : Thực hiện phép đẩy để được cấu hình mới: (s0X1s1X2s2 Xmsm ais, ai +1 an $) Phép đẩy làm cho s nằm trên đỉnh Stack, ai+1 trở thành ký hiệu hiện hành. 2. Nếu action [sm, ai] = Reduce(A → β) thì thực hiện phép thu gọn để được cấu hình: (s0X1s1X2s2 Xm - ism - i As, ai ai +1 an $) 89
4. (5) F → (E) 2 r2 s7 r2 r2 (6) F → id 3 r4 r4 r4 r4 4 s5 s4 8 2 3 Ý nghĩa: 5 r6 r6 r6 r6 si : chuyển trạng thái i 6 s5 s4 9 3 ri : thu gọn bởi luật sinh 1 7 s s i 5 4 0 acc: accept (chấp nhận) 8 s6 s11 error : khoảng trống 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Hình 4.13 - Bảng phân tích cú pháp SLR cho văn phạm ví dụ Với chuỗi nhập id * id + id, các bước chuyển trạng thái trên Stack và nội dung bộ đệm nhập được trình bày như sau : STACK INPUT ACTION (1) 0 id * id + id $ Shift (2) 0 id 5 * id + id $ Reduce by F→ id (3) 0 F 3 * id + id $ Reduce by T → F (4) 0 T 2 * id + id $ Shift (5) 0 T 2 * 7 id + id $ Shift (6) 0 T 2 * 7 id 5 + id $ Reduce by F → id (7) 0 T 2 * 7 F 10 + id $ Reduce by T → T * F (8) 0 T 2 + id $ Reduce by E→ T (9) 0 E 1 + id $ Shift (10) 0 E 1 + 6 id $ Shift (11) 0 E 1 + 6 id 5 $ Reduce by F → id (12) 0 E 1 + 6 F 3 $ Reduce by T → F (13) 0 E 1 + 6 T 9 $ Reduce by E→ E + T (14) 0 E 1 $ Thành công 2. Văn phạm LR Làm thế nào để xây dựng được một bảng phân tích cú pháp LR cho một văn phạm đã cho? Một văn phạm có thể xây dựng được một bảng phân tích cú pháp cho nó được gọi là văn phạm LR. Có những văn phạm phi ngữ cảnh không thuộc lọai LR, nhưng 91
5. F → (E) | id Nếu I là tập hợp chỉ gồm văn phạm { E'→ • E } thì closure(I) bao gồm: E' → • E (Luật 1) E → • E + T (Luật 2) E → • T (Luật 2) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) Chú ý rằng: Nếu một B - luật sinh được đưa vào closure(I) với dấu chấm mục nằm ở đầu vế phải thì tất cả các B - luật sinh đều được đưa vào. d. Phép toán Goto Goto(I, X), trong đó I là một tập các mục và X là một ký hiệu văn phạm 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') Ví dụ 4.21: Giả sử I = { E' → E•, E → E • + T }. Tính goto (I, +) ? Ta có I' = { E→ E + • T } ( goto (I, +) = closure(I') bao gồm các mục : E → E + • T (Luật 1) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) e. Giải thuật xây dựng họ tập hợp các mục LR(0) của văn phạm G' Gọi C là họ tập hợp các mục LR(0) của văn phạm tăng cường G'. Ta có thủ tục xây dựng C như sau : Procedure Item (G') begin C := closure({ S' → •S}); 93
6. ‰ Giải thuật 4.7: Xây dựng bảng phân tích SLR Input: Một văn phạm tăng cường G' Output: Bảng phân tích SLR với hàm action và goto Phương pháp: 1. Xây dựng C = { I0, I1, , In }, họ tập hợp các mục LR(0) của G'. 2. Trạng thái i được xây dựng từ Ii .Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu A → α • aβ ∈ Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j". Ở đây a là ký hiệu kết thúc. 2.2. Nếu A → α• ∈ Ii thì action[i, a] = "reduce (A → α)", ∀a ∈ FOLLOW(A). Ở đây A không phải là S' 2.3. Nếu S' → S• ∈ Ii 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 sinh ra bộ phân tích cú pháp sẽ thất bại trong trường hợp này. 3. Với mọi ký hiệu chưa kết thúc A, nếu goto (Ii,A) = Ij thì goto [i, A] = j 4. Tất cả 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 Ví dụ 4.23: Ta xây dựng bảng phân tích cú pháp SLR cho văn phạm tăng cường G' trong ví dụ 4.20 trên. E' → E (0) E'→ E (4) T → F E → E + T | T (1) E → E + T (5) F → (E) T → T * F | F (2) E → T (6) F → id F → (E) | id (3) T → T * F 1. C = { I0, I1, I11 } 2. FOLLOW(E) = {+, ), $} FOLLOW(T) = {*, +, ), $} FOLLOW(F) = {*, +, ), $} Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 4.22, ta thấy: Trước tiên xét tập mục I0 : Mục F → • (E) cho ra action[0, (] = "shift 4", và mục F → • id cho action[0, id] = "shift 5". Các mục khác trong I0 không sinh được hành động nào. Bây giờ xét I1 : Mục E'→ E • cho action[1, $] = "accept", mục E → E • + T cho action[1, +] = "shift 6". Kế đến xét I2 : E → T • 95
7. Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I2 ta thấy mục đầu tiên trong tập này làm cho action[2, =] = "shift 6". Bởi vì = ∈ FOLLOW(R), nên mục thứ hai sẽ đặt action[2, =] = "reduce (R → L)" ⇒ Có sự đụng độ tại action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1). 4. Xây dựng bảng phân tích cú pháp LR chính tắc (Canonical LR Parsing Table) a. Mục LR(1) của văn phạm G là một cặp dạng [A → α•β, a], trong đó A → αβ là luật sinh, a là một ký hiệu kết thúc hoặc $. b. Thuật toán xây dựng họ tập hợp mục LR(1) ‰ Giải thuật 4.8: Xây dựng họ tập hợp các mục LR(1) Input : Văn phạm tăng cường G’ Output: Họ tập hợp các mục LR(1). Phương pháp: Các thủ tục closure, goto và thủ tục chính Items như sau: Function Closure (I); begin Repeat For Mỗi mục [A → α•Bβ,a] trong I, mỗi luật sinh B → γ trong G' và mỗi ký hiệu kết thúc b ∈ FIRST (βa) sao cho [B → • γ, b] ∉ I do Thêm [B → •γ, b] vào I; Until Không còn mục nào có thể thêm cho I được nữa; return I; end; Function goto (I, X); begin Gọi J là tập hợp các mục [A → αX•β, a] sao cho [A → α•Xβ, a]∈ I; return Closure(J); end; Procedure Items (G'); begin C := Closure ({[S' → •S, $]}) Repeat For Mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X sao cho goto(I, X) ≠ ∅ và goto(I, X) ∉ C do 97
8. Goto (I2,=) I6 : S → L = • R, $ Goto (I11,*) ≡ I11 R → • L, $ L → • * R, $ Goto (I11,id) ≡ I12 L → • id, $ c. Thuật toán xây dựng bảng phân tích cú pháp LR chính tắc ‰ Giải thuật 4.9: Xây dựng bảng phân tích LR chính tắc Input: Văn phạm tăng cường G' Output: Bảng LR với các hàm action và goto Phương pháp: 1. Xây dựng C = { I0, I1, In } là họ tập hợp mục LR(1) 2. Trạng thái thứ i được xây dựng từ Ii. Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu [A → α • aβ,b] ∈ Ii và goto(Ii,a) = Ij thì action[i, a]= "shift j". Ở đây a phải là ký hiệu kết thúc. 2.2. Nếu [A → α •, a]∈ Ii , A ∈ S' thì action[i, a] = " reduce (A → α)" 2.3. Nếu [S' → S•,$] ∈ Ii thì action[i, $] = "accept". Nếu có một sự đụng độ giữa các luật nói trên thì ta nói văn phạm không phải là LR(1) và giải thuật sẽ thất bại. 3. Nếu goto(Ii, A) = Ij thì goto[i,A] = j 4. Tất cả 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,$] Bảng phân tích xác định bởi giải thuật 4.9 gọi là bảng phân tích LR(1) chính tắc của văn phạm G, bộ phân tích LR sử dụng bảng LR(1) gọi là bộ phân tích LR(1) chính tắc và văn phạm có một bảng LR(1) không có các action đa trị thì được gọi là văn phạm LR(1). Ví dụ 4.26: Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên Trạng Action Goto thái = * id $ S L R 0 s4 s5 1 2 3 1 acc 2 s6 r5 3 r2 4 s4 s5 8 7 5 r4 99
9. 2. Với mỗi hạt nhân tồn tại trong tập các mục LR(1) tìm trên tất cả các tập hợp có cùng hạt nhân này và thay thế các tập hợp này bởi hợp của chúng. 3. Ðặt C' = { I0, I1, , Im } là kết quả thu được từ C bằng cách hợp các tập hợp có cùng hạt nhân. Action tương ứng với trạng thái i được xây dựng từ Ji theo cách thức như giải thuật 4.9. Nếu có một sự đụng độ giữa các action thì giải thuật xem như thất bại và ta nói văn phạm không phải là văn phạm LALR(1). 4. Bảng goto được xây dựng như sau Giả sử J = I1 ∪ I2 ∪ ∪ Ik. Vì I1, I2, Ik có chung một hạt nhân nên goto (I1,X), goto (I2,X), , goto (Ik,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) ⇒ goto(J, X) = K. Ví dụ 4.28: Với ví dụ trên, ta có họ tập hợp mục C' như sau C' = {I0, I1, I2, I3, I411, I512, I6, I713, I810, I9 } I0 : S' → • S, $ I512 = Goto (I0,id), Goto (I6,id) : closure (S' Æ •S, $) : S → • L = R, $ L → id •, = | $ S → • R, $ L → • * R, = I6 = Goto(I2,=) : L → • id, = S → L = • R,$ R → • L, $ R → • L, $ L → • * R, $ I1 = Goto (I0,S) : S' → S •, $ L → • id, $ I2 = Goto (I0, L) : S → L • = R, $ I713 = Goto(I411, R) : R → L •, $ L → * R•, = | $ I = Goto(I , L), Goto(I , L): I3 = Goto (I 0,R) : S → R • 810 411 6 R → L•, = | $ I411 = Goto (I0,*), Goto (I6,*) : L → * • R, = | $ I9 = Goto(I6, R) : R → • L, = | $ S → L = R•, $ L → • * R, = | $ R → • id, = | $ Ta có thể xây dựng bảng phân tích cú pháp LALR cho văn phạm như sau: 101
10. 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 Goto(I2,E) I6: E'→ (E •) E → • E + E E → E • + E E → • E * E E → E • * E E → • (E) Goto(I2,() ≡ I2 E → • id Goto(I2,id) ≡ I3 Goto(I0,E) I1: E'→ E • Goto(I4,E) I7: E → E + E • E → E • + E E → E • + E E → E • * E E → E • * E Goto(I4,( ) ≡ I2 Goto(I0,() I2: E → (• E) Goto(I4,id) ≡ I3 E → • E + E E → • E* E Goto(I5,E) I8: E → E * E • E → • (E) E → E • + E E → • id E → E • * E Goto(I5,() ≡ I2 Goto(I0,id) I3: E → id• Goto(I5,id) ≡ I3 Goto(I1,+ ) I4: E → E + • E Goto(I6,)) I9: E → (E) • E → • E + E E → • E * E Goto(I6,+) ≡ I4 E → • ( E) Goto(I6,*) ≡ I5 103
11. 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
12. Stack Input Output 0 i i a e a $ 0 i 2 i a e a $ Shift s2 0 i 2 i 2 a e a $ Shift s2 0 i 2 i 2 a 3 e a $ Shift s3 0 i 2 i 2 S 4 a $ Reduce by S Æ a 0 i 2 i 2 S 4 e 5 $ Shift s5 0 i 2 i 2 S 4 e 5 a 3 $ Shift s3 0 i 2 i 2 S 4 e 5 S 6 $ Reduce by S Æ a 0 i 2 S 4 $ Reduce by S Æ iS eS 0 s 1 $ 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 Yacc Y.tab.c Translate.y Compiler Y.tab.c a.out C Compiler Input 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
13. %% 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
14. 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
15. 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
16. 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