›

Bài giảng cấu trúc dữ liệu và thuật toán - Chương 3: Phân tích cú pháp

ppt 60 trang huongle 2790
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng cấu trúc dữ liệu và thuật toán - Chương 3: Phân tích cú pháp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_3_phan_tich.ppt

Nội dung text: Bài giảng cấu trúc dữ liệu và thuật toán - 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. Vai trò của bộ phân tích cú pháp • Đây là giai đoạn thứ 2 của quá trình biên dịch • Nhiệm vụ chính: Nhận chuỗi các token từ bộ phân tích từ vựng và xác định chuỗi đó có được sinh ra bởi văn phạm của ngôn ngữ nguồn không Token Source Lexical Parser Parse Rest of program analyzer Get next tree front end token Symbol table 2
  3. • 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
  4. Văn phạm phi ngữ cảnh • Để định nghĩa cấu trúc của ngôn ngữ lập trình ta dùng văn phạm phi ngữ cảnh (Context-free grammars) hay gọi tắt là một văn phạm • Một văn phạm bao gồm: - Các kí hiệu kết thúc (Các kí hiệu kết thúc (terminalsterminals): Chính là các ): Chính là các tokentoken - Các kí hiệu chưa kết thúc (Các kí hiệu chưa kết thúc (nonterminalsnonterminals): Là các ): Là các biến kí hiệu tập các xâu kí tựbiến kí hiệu tập các xâu kí tự - Các luật sinh (Các luật sinh (productionsproductions): Xác định cách thức ): Xác định cách thức hình thành các xâu từ các kí hiệu kết thúc và hình thành các xâu từ các kí hiệu kết thúc và chưa kết thúcchưa kết thúc 4 - Một kí tự bắt đầu (Một kí tự bắt đầu (start symbolstart symbol))
  5. 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
  6. • Dẫn xuất (derivation): Ta nói A  nếu A  là một luật sinh ( đọc là dẫn xuất hoặc suy ra) • Nếu 1 2 n thì ta nói rằng 1 dẫn xuất n • Kí hiệu: * là dẫn xuất 0 bước, + là dẫn xuất 1 bước • Cho văn phạm G với kí tự bắt đầu là S, L(G) là ngôn ngữ được sinh bởi G. Mọi xâu trong L(G) chỉ chứa các kí hiệu kết thúc của G 6
  7. • 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
  8. Ví dụ 3.2: Xâu –(id+id) là một câu của văn phạm trong ví dụ 3.1 vì E -E -(E) -(E+E) -(id+E) (id+id) • Một dẫn xuất được gọi là trái nhất (leftmost) nếu tại mỗi bước kí hiệu chưa kết thúc ngoài cùng bên trái được thay thế, kí hiệu lm. Nếu S *lm thì được gọi là dạng câu trái • Tương tự ta có dẫn xuất phải nhất (rightmost) hay còn gọi là dẫn xuất chính tắc, kí hiệu rm 8
  9. • 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
  10. • Tính mơ hồ của văn phạm (ambiguity): Một văn phạm sinh ra nhiều hơn một parse tree cho một câu được gọi là văn phạm mơ hồ. Nói cách khác một văn phạm mơ hồ sẽ sinh ra nhiều hơn một dẫn xuất trái nhất hoặc dẫn xuất phải nhất cho cùng một câu. • Loại bỏ sự mơ hồ của văn phạm: Ta xét ví dụ văn phạm sau Stmt Stmt ifif expr expr thenthen stmt stmt | | ifif expr expr thenthen stmt stmt elseelse stmt stmt | | otherother 10
  11. • 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
  12. • Ðể loại bỏ sự mơ hồ này ta đưa ra qui 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 Stmt matched_stmt | unmatched_stmt matched_stmt | unmatched_stmt matched_stmt matched_stmt ifif expr expr thenthen matched_stmt matched_stmt elseelse matched_stmtmatched_stmt | | otherother unmatched_stmt unmatched_stmt if if expr expr then then Stmt Stmt | | if if expr expr thenthen matched_stmt matched_stmt elseelse unmatched_stmt unmatched_stmt 12
  13. • 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
  14. • Với đệ qui trái trực tiếp: Ta nhóm các luật sinh thành A A 1 | A 2 | | A m | 1 | 2 | | n Thay luật sinh trên bởi các luật sinh sau: A 1A' | 2A' | | nA' A' 1A' | 2A' | | mA' |  Ví dụ 3.3: Thay luật sinh A A |  bởi A A' A' A' |  14
  15. • 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ự Sắp xếp các ký hiệu không kết thúc theo thứ tự A1, A2, , AnA1, A2, , An 22. . forfor i:=1 i:=1 toto n n dodo begin begin forfor j:=1 j:=1 toto i -1 i -1 dodo beginbegin Thay luật sinh dạng Thay luật sinh dạng Ai Aj bởi luật sinh bởi luật sinh Ai 1 | 2 | | k trong đó trong đó Aj 1 | 2 | | k là tất cả các luật là tất cả các luật sinh hiện tạisinh hiện tại end;end; 15 Loại bỏ đệ qui trái trực tiếp trong số các luật Loại bỏ đệ qui trái trực tiếp trong số các luật sinh Aisinh Ai end; end;
  16. • Tạo ra nhân 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 đủ yếu tố cho một lựa chọn đúng. 16
  17. 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' 1 | 2 | | n
  18. Phân tích cú pháp từ trên xuống • Phân tích cú pháp (PTCP) từ trên xuống được xem như một cố gắng 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 cố gắng 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á • PTCP từ trên xuống đơn giản hơn PTCP từ dưới lên nhưng bị giới hạn về mặt hiệu quả • Có một số kĩ thuật PTCP từ trên xuống như: PTCP đệ qui lùi, PTCP đoán trước, 18 PTCP đoán trước đệ qui. Ta sẽ xét trường hợp PTCP đoán trước đệ qui
  19. • PTCP đoán trước không đệ qui (nonrecursive predictive parsing) hoạt động theo mô hình sau: INPUT aa ++ bb $$ Predictive parsing OUTPUT XX program STACK YY ZZ $$ Parsing table M 19
  20. • INPUT là bộ đệm chứa chuỗi cần phân tích, kết thúc bởi ký hiệu $ • STACK chứa một chuỗi các ký hiệu văn phạm với ký hiệu $ nằm ở đáy STACK. Khởi đầu STACK chứa kí hiệu bắt đầu S trên đỉnh • Parsing table M là một mảng hai chiều dạng M[A,a], trong đó A là ký hiệu chưa kết thúc, a là ký hiệu kết thúc hoặc $. • Bộ phân tích cú pháp được điều khiển bởi Predictive parsing program 20
  21. • 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 1. Nếu X = a = $ thì quá trình PTCP kết thúc thành côngcông 2. Nếu X = a 2. Nếu X = a $, đẩy X ra khỏi Stack và đọc ký hiệu $, đẩy X ra khỏi Stack và đọc ký hiệu nhập tiếp theo.nhập tiếp theo. 3. Nếu X là ký hiệu chưa kết thúc thì chương trình 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 truy xuất đến phần tử M[X,a] trong Parsing table Parsing table MM:: - Nếu M[X,a] là một luật sinh có dạng X - Nếu M[X,a] là một luật sinh có dạng X UYV thì UYV thì đẩy X ra khỏi đỉnh Stack và đẩy V, Y, U vào Stack đẩ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 (với U trên đỉnh Stack), đồng thời bộ xuất ra OUTPUT luật sinh X OUTPUT luật sinh X UYV UYV 21 - Nếu M[X,a] = error, gọi chương trình phục hồi lỗi.- Nếu M[X,a] = error, gọi chương trình phục hồi lỗi.
  22. Ví dụ 3.4: Xét văn phạm E E+T | T T T*F | F F (E) | id Loại bỏ đệ qui trái ta thu được E TE' E' +TE' |  T FT' T' *FT' |  F (E) | id Giả sử xâu input nhập vào là id+id*id 22
  23. • Parsing table M cho văn phạm trên như Non- sau 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
  24. STACK INPUT OUTPUT $ E id + id * id $ $ E' T id + id * id $ E T E' $ E' T' F id + id * id $ T F T' $ E' T' id id + id * id $ F id $ E' T' + id * id $ $ E' + id * id $ T'  $ E' T + + id * id $ E' + T E' $ E' T id * id $ $ E' T' F id * id $ T F T' $ E' T' id id * id $ F id $ E' T' * id $ $ E' T' F * * id $ T' * F T' $ E' T' F id $ $ E' T' id id $ F id $ E' T' $ 24 $ E' $ T'  $ $ E' 
  25. • 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
  26. • Qui tắc tính các tập hợp FOLLOW 1. Đặt $ vào FOLLOW(S) (S là kí hiệu bắt đầu) 2. Nếu A B thì mọi phần tử thuộc FIRST() ngoại trừ  đều thuộc FOLLOW(B) 3. Nếu A B hoặc A B và  *  thì mọi phần tử thuộc FOLLOW(A) đều thuộc FOLLOW(B) 26
  27. Ví dụ 3.5: Xét văn phạm E E TE' TE' E' E' +TE' | +TE' |  T T FT' FT' T' T' *FT' | *FT' |  F F (E) | id (E) | id Khi đó: FIRST(E) = FIRST(T) = FIRST(F) = { (, id }FIRST(E) = FIRST(T) = FIRST(F) = { (, id } FIRST(E') = {+, FIRST(E') = {+,  } } FIRST(T') = {FIRST(T') = { , ,  } } FOLLOW(E) = FOLLOW(E') = { $, ) }FOLLOW(E) = FOLLOW(E') = { $, ) } FOLLOW(T) = FOLLOW(T') = { +, ), $ }FOLLOW(T) = FOLLOW(T') = { +, ), $ } FOLLOW(F) = {FOLLOW(F) = { ,+, ), $ },+, ), $ } 27
  28. • Thuật giải xây dựng Parsing table M của văn phạm G: 1. Với mỗi luật sinh A 1. Với mỗi luật sinh A của văn phạm, thực của văn phạm, thực hiện bước 2 và 3hiện bước 2 và 3 2. Với mỗi ký hiệu kết thúc a 2. Với mỗi ký hiệu kết thúc a FIRST(FIRST( ), thêm A ), thêm A vào M[A,a] vào M[A,a] 3. Nếu 3. Nếu   FIRST(FIRST( ) thì đưa luật sinh A ) thì đưa luật sinh A vào vào M[A,b] với mỗi ký hiệu kết thúc bM[A,b] với mỗi ký hiệu kết thúc b FOLLOW(A). FOLLOW(A). Nếu Nếu   FIRST(FIRST( ) và $) và $ FOLLOW(A) thì đưa luật FOLLOW(A) thì đưa luật sinh A sinh A vào M[A,$]. vào M[A,$]. 4. Ô còn trống trong bảng tương ứng với lỗi 4. Ô còn trống trong bảng tương ứng với lỗi (error).(error). 28
  29. 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
  30. Ví dụ 3.6: Cho văn phạm : S a A B e A A b c | b B d Câu abbcde có thể thu gọn về S theo các bước sau: a b b c d e a A b c d e a A d e a A B e S Đảo ngược lại quá trình trên ta thu được dẫn xuất phải nhất: 30 S rm aABe rm aAde rm aAbcde rm abbcde
  31. • 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
  32. Ví dụ 3.8: Xét văn phạm mơ hồ E E + E | E * E | (E) | id Với cùng một biểu thức id+id*id sẽ có hai dẫn xuất phải nhất (các handle được gạch chân). Cùng một right sentence form E+E*id3 trong trường hợp đầu id3 là handle còn trường hợp thứ 2 handle là E+E E E rm rm E + EE + E E E rm rm E * EE * E rm rm E + E + E * EE * E rm rm E * E * id3 id3 rm rm E + E E + E id3id3 rm rm E + EE + E id3 id3 rm rm E + E + id2id2 id3 id3 rm rm E + E + id2id2 id3 id3 rm rm id1id1 + id2 + id2 id3 id3 rm rm id1id1 + id2 + id2 id3 id3 32
  33. • Biểu diễn stack của shift- reduce parsing STACKSTACK INPUTINPUT ACTIONACTION $$ idid11 + id + id22 id id33 shiftshift $ id$ id11 $$ reduce by E reduce by E idid $ E$ E + id+ id22 id id33 $ $ shift shift $ E +$ E + + id+ id22 id id33 $ $ shiftshift $ E + id$ E + id22 id id22 id id33 $ $ reduce by reduce by E E idid $ E + E$ E + E id id33 $ $ shiftshift $ E + E $ E + E id id33 $ $ shiftshift $ $ E E + + E E idid33 $ $ reduce by reduce by E E idid idid33 $ $ reduce reduce by by E E E E * * $ E + E $ E + E E E $ $ EE $ E + E$ E + E $ $ reduce reduce byby E E E E + + $ E $ E $$ EE 33 acceptaccept
  34. Phân tích cú pháp LR (LR parser) • LR(k) là một kỹ thuật phân tích cú pháp từ dưới lên hiệu quả, có thể sử dụng để phân tích một lớp rộng các văn phạm phi ngữ cảnh. - L(Left-to-right): Duyệt chuỗi nhập từ trái sang phải - R(Rightmost derivation): Xây dựng chuỗi dẫn xuất phải nhất đảo ngược - k:Số lượng ký hiệu lookahead tại mỗi thời điểm, dùng để đưa ra quyết định phân tích. Khi không đề cập đến k, chúng ta hiểu 34 ngầm là k = 1
  35. • Ưu điểm của LR: - Có thể nhận biết hầu như tất cả các ngôn ngữ 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ảnhlậ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ươ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 pháp tổng quát của phương pháp shift-reduce không quay luikhông quay lui - Lớp văn phạm có thể dùng phương pháp LR là - 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ử 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ándụng phương pháp dự đoán - Có thể xác định lỗi cú pháp nhanh ngay trong 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ảikhi 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- Xây dựng LR parser khá phức tạp 35
  36. • Mô hình của LR parser INPUT aa11 aaii aann $$ LR parsing OUTPUT ssmm program XXmm STACK ssm-1m-1 XXm-1m-1 actionaction gotogoto Parsing table ssoo 36
  37. • 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. 1. shift sshift s: Đẩy s, trong đó s là một trạng : Đẩy s, trong đó s là một trạng tháithái 2. 2. reducereduce: Thu gọn bằng luật sinh A : Thu gọn bằng luật sinh A  37 3. 3. acceptaccept: Chấp nhận: Chấp nhận 4. 4. errorerror: Báo lỗi: Báo lỗi - 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
  38. • 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 (s0 X1 s1 X2 s2 Xm sm, ai ai+1 an $). Cấu hình biểu diễn right- sentential form X1 X2 Xmai ai+1 an • Sự thay đổi cấu hình theo hàm action như sau: - Nếu action[s- Nếu action[smm, a, aii] = shift s, cấu hình chuyển thành ] = shift s, cấu hình chuyển thành (s(s0 0 XX1 1 ss1 1 XX2 2 ss22 X Xm m ssmm a ai i s, as, ai+1i+1 a ann $), trong đó $), trong đó s=action[ss=action[smm, a, aii]] - Nếu action[s- Nếu action[smm, a, aii] = reduce A] = reduce A  , , cấu hình chuyển cấu hình chuyển thành thành 38 (s(s0 0 XX1 1 ss1 1 XX2 2 ss22 X Xm-r m-r ssm-rm-r A A s, as, aii a ai+1i+1 a ann $), trong đó s=goto $), trong đó s=goto [s[sm-rm-r, A], r=|, A], r=||=|X|=|Xm-r+1m-r+1 X Xmm|| - Nếu action[s- Nếu action[smm, a, aii] = accept, quá trình phân tích ] = accept, quá trình phân tích thành côngthành công - Nếu action[s- Nếu action[smm, a, aii] = error, gọi thủ tục phục hồi lỗi] = error, gọi thủ tục phục hồi lỗi
  39. 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 sii : shift sii 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
  40. • Với chuỗi nhập id*id+id quá trình phân tích như sau: STACKSTACK INPUTINPUT ACTIONACTION (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 + id $ reduce by F id (7) 5 + id $ reduce by T T * F (8) 0 T 2 * 7 F + id $ reduce by E T (9) 10 + id $ shift (10) 0 T 2 id $ shift (11) 0 E 1 $ reduce by F id (12) 0 E 1 + 6 $ reduce by T F (13) 0 E 1 + 6 id 5 $ reduce by E E + T (14) 0 E 1 + 6 F $ accept 40 3 0 E 1 + 6 T 9 0 E 1
  41. 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
  42. • 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
  43. • 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).1. Tất cả các mục của I được thêm vào closure(I). 2. Nếu A 2. Nếu A .B.B  closure(I) và B closure(I) và B  là một luật là một luật sinh thì thêm B sinh thì thêm B . . vào closure(I) nếu nó chưa vào closure(I) nếu nó chưa có trong đó. Lặp lại bước này cho đến khi không có trong đó. Lặp lại bước này cho đến khi không 43 thể thêm vào closure(I) được nữathể thêm vào closure(I) được nữa
  44. Ví dụ 3.11: Xét văn phạm tăng cường E' E' E E E E E + T | T E + T | T T T T T F | F F | F F F (E) | id (E) | id Nếu I= {E' · E} thì closure(I) bao gồm các mục sau: E'E' · E · E E E · E + T · E + T E E · T · T T T · T · T F F T T · F · F F F · (E) · (E) 44 F F · id · id
  45. • 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' = 1. Tạo một tập I' =  2. Nếu A 2. Nếu A XX  I I thì đưa A thì đưa A X.X. vào I', vào I', tiếp tục quá trình này cho đến khi xét hết tập 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')3. goto(I, X) = closure(I') 45
  46. Ví dụ 3.12: Giả sử I = {E' E' E., E E., E E . + T E . + T} Ta có I' = { E E E + . T E + . T} goto (I, +) = closure(I') bao gồm các mục : E E E + . T E + . T T T . T * F . T * F T T . F . F F F . (E) . (E) F F . id . id 46
  47. • 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' procedureprocedure Item (G') Item (G') beginbegin C := {closure({ S' C := {closure({ S' . .S}) };S}) }; repeatrepeat For For Với mỗi tập các mục I Với mỗi tập các mục I C và mỗi ký C và mỗi ký hiệu hiệu văn phạm X sao cho goto (I, văn phạm X sao cho goto (I, X)X)   và và goto(I, X)goto(I, X) C thì thêm goto(I, X) vào C; C thì thêm goto(I, X) vào C; until until Không còn tập hợp mục nào có thể thêm Không còn tập hợp mục nào có thể thêm vào C;vào C; 47 end;end;
  48. 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}) E' · E goto (I0, id) F id · I0: E · E + T I5: E E + · T E · T goto (I1, +) T · T * F T · T * F I6: T · F T · F F · (E) F · (E) F · id F · id T T* · F E' E · F · (E) goto (I0, E) E E · + T goto (I2, *) F · id I1: E T · I7: F (E ·) T T · * F E E · + T goto (I0, T) T F · E E + T · I2: F (· E) goto (I4, E) T T · * F E · E + T I8: T T * F · goto (I0,F) E · T F (E) · I3: T · T * F goto (I6,T) goto (I0, ( ) T · F I9: I4: F · (E) goto (I7,F) 48 F · id I10: goto (I8,) ) I11:
  49. • 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 = { I1. Xây dựng họ tập hợp các mục của G': C = { I00, I, I11, , , I , Inn } } 2. Trạng thái i được xây dựng từ I2. Trạng thái i được xây dựng từ Iii .Các action tương .Các action tương ứng trạng thái i xác định như sau:ứng trạng thái i xác định như sau: a) Nếu A a) Nếu A .a.a  IIii và goto (I và goto (Iii, a) = I, a) = Ijj thì action[i, a] thì action[i, a] = "shift j", = "shift j", a là ký hiệu kết thúca là ký hiệu kết thúc b) Nếu A b) Nếu A . . IIii thì action[i, a] = "reduce (A thì action[i, a] = "reduce (A ))", với mọi a ", với mọi a FOLLOW(A), A FOLLOW(A), A S'S' c) Nếu S' c) Nếu S' S · S · IIii thì action[i, $] = "accept". thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi các luật 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 trên, ta nói văn phạm không phải là SLR(1). Giải thuật thất bạithuật thất bại 49 3. Nếu goto (I3. Nếu goto (Iii,A)=I,A)=Ijj thì goto [i, A] = j, A là kí hiệu thì goto [i, A] = j, A là kí hiệu chưa kết thúcchưa kết thúc 4. Các ô không xác định được bởi 2 và 3 đều là 4. Các ô không xác định được bởi 2 và 3 đều là “error”“error” 5. Trạng thái khởi đầu của bộ phân tích cú pháp được 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’ xây dựng từ tập các mục chứa S’ · S · S
  50. 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
  51. • 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).1. Tất cả các mục của I được thêm vào closure(I). 2. Nếu [A 2. Nếu [A .B.B, a], a] closure(I), B closure(I), B  là một là một luật sinh và b luật sinh và b FIRST( FIRST(a) thì thêm [B a) thì thêm [B . ., , b]b] vào closure(I) nếu nó chưa có trong đó. Lặp 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 lại bước này cho đến khi không thể thêm vào closure(I) được nữaclosure(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
  52. • 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' procedureprocedure Item (G') Item (G') beginbegin C := {closure({[ S' C := {closure({[ S' . .S, S, $$]})};]})}; repeatrepeat For For Với mỗi tập các mục I Với mỗi tập các mục I C và mỗi ký C và mỗi ký hiệu hiệu văn phạm X sao cho goto (I, văn phạm X sao cho goto (I, X)X)   và và goto(I, X)goto(I, X) C thì thêm goto(I, X) vào C; C thì thêm goto(I, X) vào C; until until Không còn tập hợp mục nào có thể thêm Không còn tập hợp mục nào có thể thêm vào C;vào C; 52 end;end;
  53. 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' S S (1) S (1) S CC CC (2) C (2) C cC cC (3) C (3) C d 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, C) S' S ·, $ I5: C c · C, $ goto (I0, S) C · cC, $ I1: S C ·C, $ goto (I2, c) C · d, $ C · cC, $ I6: goto (I0, C) C · d, $ C d ·, $ I2: C c ·C, c/d C cC ·, c/d C · cC, c/d goto (I2, d) C · d, c/d I7: C cC ·, $ 53 goto (I0, c) I3: goto (I3, C) I8: goto (I6,C) I9:
  54. • 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 = 1. Xây dựng họ tập hợp các mục LR(1) của G': C = {I{I00, I, I11, , I, , Inn } } 2. Trạng thái i được xây dựng từ I2. Trạng thái i được xây dựng từ Iii .Các action tương .Các action tương ứng trạng thái i xác định như sau:ứng trạng thái i xác định như sau: a) Nếu [A a) Nếu [A .a.a, b], b] IIii và goto (I và goto (Iii, a) = I, a) = Ijj thì thì action[i, a] = "shift j", a là ký hiệu kết thúcaction[i, a] = "shift j", a là ký hiệu kết thúc b) Nếu [A b) Nếu [A ., a] ., a] IIii thì action[i, a] = "reduce (A thì action[i, a] = "reduce (A .).)", A", A S'S' c) Nếu [S' c) Nếu [S' S ·, $] S ·, $] IIii thì action[i, $] = "accept". thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi các luật 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 trên, ta nói văn phạm không phải là LR(1). Giải thuật thất bạithuật thất bại 54 3. Nếu goto (I3. Nếu goto (Iii,A)=I,A)=Ijj thì goto [i, A] = j, A là kí hiệu thì goto [i, A] = j, A là kí hiệu chưa kết thúcchưa kết thúc 4. Các ô không xác định được bởi 2 và 3 đều là 4. Các ô không xác định được bởi 2 và 3 đều là “error”“error” 5. Trạng thái khởi đầu của bộ phân tích cú pháp được 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’ xây dựng từ tập các mục chứa [S’ · S, $] · S, $]
  55. • 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
  56. Xây dựng bảng phân tích LALR • 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 = {I0, I1, , In} có thể có các tập hợp các mục có chung một hạt nhân. 56
  57. • 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 = {I1. Xây dựng họ tập hợp các mục LR(1) của G': C = {I00, , II11, , I, , Inn } } 2. Nhóm các mục có cùng core trong C được C' = {J2. Nhóm các mục có cùng core trong C được C' = {J00, , JJ11, , J, , Jmm } } 3. Trạng thái i được xây dựng từ J3. Trạng thái i được xây dựng từ Jii .Các action tương .Các action tương ứng trạng thái i xác định tương tự như canonical LRứ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 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 trên, ta nói văn phạm không phải là LALR(1). Giải thuật thất bạithuật thất bại 3. Xây dựng bảng goto : Giả sử J = I3. Xây dựng bảng goto : Giả sử J = I11 I I22 . .  I Ikk . Vì . Vì II11, I, I22, I, Ikk có chung hạt nhân nên goto (I có chung hạt nhân nên goto (I11,X), goto ,X), goto (I(I ,X), , goto (I,X), , goto (I ,X) cũng có chung hạt nhân. ,X) cũng có chung hạt nhân. 22 kk 57 Ðặt K bằng hợp tất cả các tập hợp có chung hạt Ðặ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.nhân với goto (I1,X) khi đó goto(J, X) =K.
  58. • LALR parsing table cho văn phạm trong ví dụ 3.14 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 58
  59. 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
  60. Yacc Yacc specification y.tab.c compiler translate.y C y.tab.c a.out compiler input a.out output 60