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

Nội dung text: Bài giảng Xây dựng chương trình dịch - Chương 3: Phân tích cú pháp

1. CHƯƠNG III Phân tích cú pháp Mục tiêu: -Nắm được vai trò của giai đoạn phân tích cú pháp - Văn phạm phi ngữ cảnh (context- free grammar),cách phân tích cú pháp từ dưới lên- từ trên xuống (top-down and bottom-up parsing) -Bộ phân tích cú pháp LR 1
2. • Các phương pháp phân tích cú pháp (PTCP) chia làm hai loại: Phân tích từ trên xuống (top- down parsing) và phân tích từ dưới lên (bottom- up parsing) • Trong quá trình biên dịch xuất hiện nhiều lỗi trong giai đoạn PTCP do đó bộ phân tích cú pháp phải phát hiện và thông báo lỗi chính xác cho người lập trình đồng thơi không làm chậm những chương trình được viết đúng 3
3. Ví dụ 3.1: Văn phạm sau định nghĩa các biểu thức số học đơn giản E → E A E | (E) | -E | id A → + | - | * | / |  Trong đó E, A là các kí tự chưa kết thúc (E còn là kí tự bắt đầu), các kí tự còn lại là các kí tự kết thúc 5
4. • Ta nói một xâu w L(G) nếu và chỉ nếu S + w, w được gọi là một câu (sentence) của văn phạm G • Một ngôn ngữ được sinh bởi văn phạm phi ngữ cảnh được gọi là ngôn ngữ phi ngữ cảnh (context- free language) • Hai văn phạm được gọi là tương đương nếu sinh ra cùng một ngôn ngữ • Nếu S * ( có thể chứa kí hiệu chưa kết thúc) thí ta nói là một dạng câu (sentence form) của G. Một câu là một dạng câu không chứa kí hiệu chưa kết thúc 7
5. • Cây phân tích cú pháp (parse tree) là dạng biểu diễn hình học của dẫn xuất. Ví dụ parse tree cho biểu thức –(id+id) là: E - E ( E ) E + E | | id id 9
6. • Văn phạm trên là mơ hồ vì với cùng một câu lệnh "if E1 then if E2 then S1 else S2" sẽ có hai parse tree: 11
7. • Loại bỏ đệ qui trái: Một văn phạm được gọi là đệ qui trái (left recursion) nếu tồn tại một dẫn xuất có dạng A + A (A là 1 kí hiệu chưa kết thúc, là một xâu). • Các phương pháp phân tích từ trên xuống không thể xử lí văn phạm đệ qui trái, do đó cần phải biến đổi văn phạm để loại bỏ các đệ qui trái • Ðệ qui trái có hai loại : Loại trực tiếp: Có dạng A + A Loại gián tiếp: Gây ra do dẫn xuất của hai hoặc nhiều bước 13
8. • Với đệ qui trái gián tiếp: Ta dùng thuật toán sau 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 luật sinh hiện tại end; 15 Loại bỏ đệ qui trái trực tiếp trong số các luật sinh Ai
9. Ví dụ 3.3: Ta có hai luật sinh stmt → if expr then stmt else stmt | if expr then stmt Sau khi đọc token if, ta không thể ngay lập tức quyết định sẽ dùng luật sinh nào để mở rộng stmt • Cách tạo nhân tố trái: Giả sử có luật sinh A → 1 | 2 | | n |  ( là tiền tố chung dài nhất của các luật sinh,  không bắt đầu bởi ) Luật sinh trên được biến đổi thành: A → A' |  17 A' →  |  | | 
10. • PTCP đoán trước không đệ qui (nonrecursive predictive parsing) hoạt động theo mô hình sau: INPUT a + b $ Predictive parsing OUTPUT X program STACK Y Z $ Parsing table M 19
11. • Predictive parsing program hoạt động như sau: Chương trình xét ký hiệu X trên đỉnh Stack và ký hiệu nhập hiện hành a 1. Nếu X = a = $ thì quá trình PTCP kết thúc thành công 2. Nếu X = a $, đẩy X ra khỏi Stack và đọc ký hiệu nhập tiếp theo. 3. Nếu X là ký hiệu chưa kết thúc thì chương trình truy xuất đến phần tử M[X,a] trong Parsing table M: - Nếu M[X,a] là một luật sinh có dạng X → UYV thì đẩy X ra khỏi đỉnh Stack và đẩy V, Y, U vào Stack (với U trên đỉnh Stack), đồng thời bộ xuất ra OUTPUT luật sinh X → UYV 21 - Nếu M[X,a] = error, gọi chương trình phục hồi lỗi.
12. • Parsing table M cho văn phạm trên như Nonsau- Input symbol termin al id + * ( ) $ E E → TE' E → TE' E' E' E' →  E' →  →+TE' T T → FT' T → FT' T' T' →  T' → T' →  T' →  *FT' F F → id F → (E) 23
13. • Hàm FIRST và FOLLOW: Là các hàm xác định các tập hợp cho phép xây dựng bảng phân tích M và phục hồi lỗi • Nếu là một xâu thì FIRST( ) là tập hợp các ký hiệu kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ . Nếu *  thì  thuộc FIRST( ) • Nếu A là một kí hiệu chưa kết thúc thì FOLLOW(A) là tập các kí hiệu kết thúc mà nó xuất hiện ngay bên phải A trong một dạng câu . Nếu S * A thì $ thuộc FOLLOW(A) 25
14. Ví dụ 3.5: Xét văn phạm E → TE' E' → +TE' |  T → FT' T' → *FT' |  F → (E) | id Khi đó: FIRST(E) = FIRST(T) = FIRST(F) = { (, id } FIRST(E') = {+,  } FIRST(T') = {*,  } FOLLOW(E) = FOLLOW(E') = { $, ) } FOLLOW(T) = FOLLOW(T') = { +, ), $ } FOLLOW(F) = {*,+, ), $ } 27
15. Phân tích cú pháp từ dưới lên • Giới thiệu một kiểu phân tích cú pháp từ dưới lên tổng quát gọi là phân tích cú pháp Shift –Reduce • Một phương pháp tổng quát hơn của kỹ thuật Shift - Reduce là phân tích cú pháp LR (LR parsing) sẽ được thảo luận • Shift –Reduce parsing sẽ cố gắng xây dựng một parse tree cho một xâu nhập vào từ nút lá lên nút gốc. Nói cách khác ta "reducing" từng bước xâu nhập vào đến khi thu được kí hiệu bắt đầu của văn 29 phạm
16. • Handles: Handle của một right-sentential form  là một luật sinh A→, một xâu * sao cho =  và S rm A rm . Đôi khi ta còn gọi  là một handle, xâu  bên phải  chỉ chứa các kí hiệu kết thúc • Nếu một văn phạm là không mơ hồ thì với mỗi right-sentential form có duy nhất một handle của nó Ví dụ 3.7: Trong dẫn xuất S rm aABe rm aAde rm aAbcde rm abbcde các handle được gạch chân 31
17. • Biểu diễn stack của shift- reduce parsing STACK INPUT ACTION $ id1 + id2 * id3 shift $ id1 $ reduce by E → id $ E + id2 * id3 $ shift $ E + + id2 * id3 $ shift $ E + id2 id2 * id3 $ reduce by E → id $ E + E * id3 $ shift $ E + E * * id3 $ shift $ E + E id3 $ reduce by E → id * id3 $ reduce by E → E * $ E + E * E $ E $ E + E $ reduce by E → E + $ E $ E 33 accept
18. • Ưu điểm của LR: - Có thể nhận biết hầu như tất cả các ngôn ngữ lập trình được tạo ra bởi văn phạm phi ngữ cảnh - Phương pháp phân tích cú pháp LR là phương pháp tổng quát của phương pháp shift-reduce không quay lui - Lớp văn phạm có thể dùng phương pháp LR là một lớp rộng lớn hơn lớp văn phạm có thể sử dụng phương pháp dự đoán - Có thể xác định lỗi cú pháp nhanh ngay trong khi duyệt dòng nhập từ trái sang phải • Nhược điểm của LR: - Xây dựng LR parser khá phức tạp 35
19. • STACK lưu chuỗi s0 X1 s1 X2 s2 Xm sm trong đó sm nằm trên đỉnh STACK 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ó • Parsing table bao gồm 2 phần : Hàm action và hàm goto - 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: Thu gọn bằng luật sinh A →  37 3. accept: Chấp nhận
20. Ví dụ 3.9: Xét văn phạm cho các phép toán số học + và * (1) E → E + T Stat Action Goto (2) E → T e id + * ( ) $ E T F (3) T → T * F 0 s5 S4 1 2 3 (4) T → F 1 s6 acc (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 : shift si 6 s5 s4 9 3 rj : reduce by 7 s5 s4 10 production j acc: accept 8 s6 s11 blank: error 9 r1 s7 r1 r1 10 r3 r3 r3 r3 39 11 r5 r5 r5 r5
21. 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 41 parser được gọi là một văn phạm SLR
22. • 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ể43 thêm vào closure(I) được nữa
23. • 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
24. • 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; 47 end;
25. • 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 = { I0, I1, , In } 2. Trạng thái i được xây dựng từ Ii .Các action tương ứng trạng thái i xác định như sau: a) Nếu A → .a Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j", a là ký hiệu kết thúc b) Nếu A → . Ii thì action[i, a] = "reduce (A → )", với mọi a FOLLOW(A), A S' c) 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 thất bại 49
26. • 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 51 → X., a] sao cho [A → .X, a] I
27. 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 closure({S' → S}) S' → · S, $ goto (I0, d C → d ·, c/d I0: S → · CC, $ ) I4: C → · cC, c/d S → CC ·, $ C → · d, c/d goto (I2, S' → S ·, $ C) I5: C → c · C, $ goto (I0, C → · cC, $ S) I1: S → C ·C, $ goto (I2, C → · d, $ C → · cC, $ c) I6: goto (I0, C → · d, $ C → d ·, $ C) I2: C → c ·C, c/d C → cC ·, c/d C → · cC, c/d goto (I2, C → · d, c/d d) I7: C → cC ·, $ 53 goto (I0, c) I : goto (I ,
28. • Canonical LR parsing table cho văn phạm trong ví dụ 3.14 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 55
29. • 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 = {I0, I1, , In } 2. Nhóm các mục có cùng core trong C được C' = {J0, J1, , Jm } 3. Trạng thái i được xây dựng từ Ji .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 = I1 I2 .  Ik . Vì I1, I2, Ik có chung hạt nhân nên goto (I1,X), goto (I ,X), , goto (I ,X) cũng có chung hạt nhân. 2 k 57 Ðặt K bằng hợp tất cả các tập hợp có chung hạt
30. 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