Bài giảng Các phương pháp phân tích hiệu quả

*Bài giảng 5 – Các phương pháp phân tích hiệu quảNguyễn Phương TháiBộ môn Khoa học Máy tínhân tích Top-Down, Bottom-upƯu điểm:Đơn giảnPhân tích được cho toàn bộ lớp VPPNCPhân tích được ngôn ngữ nhập nhằngNhược điểm:Quá chậm (cn) do phải quay lui*Tìm đường*Phân tích hiệu quả (tất định)Hi sinh (nhược điểm):Lớp ngôn ngữ bé hơn PNCBắt buộc không nhập nhằngƯu điểm:Rất nhanh (cn)*Đặc điểm phân tích tất địnhQuét xâu vào từ phải sang tráiQuá trình phân tích là hoàn toàn xác địnhKhông dùng quay luiDựa vào trạng thái hiện tại và ký hiệu kết thúc để xác định luật duy nhấtCác luật phải được thiết kế đặc biệt*Các lớp văn phạmVăn phạm LL(k) - văn phạm cho phép xây dựng các bộ phân tích làm việc tất định nếu bộ phân tích này được phép nhìn k ký hiệu vào nằm ngay ở bên phải của vị trí vào hiện thời.Văn phạm LR(k) - văn phạm cho phép xây dựng các bộ phân tích làm việc tất định nếu bộ phân tích này được phép nhìn k ký hiệu vào nằm vượt quá vị trí vào hiện thời.*Phân tích LL*Chương trình điều khiểnX ký hiệu đỉnh ngăn xếp, a ký hiệu vào hiện tạiNếu X = a = $: dừng và tuyên bố thành công (cả xâu vào lẫn ngăn xếp đều rỗng).Nếu X = a  $: lấy X khỏi ngăn xếp, dịch con trỏ vào sang ký hiệu vào tiếp theo (đã khai triển đến lá khớp với xâu vào).Nếu X là một biến: xét ô M [X, a]. Nếu:Nếu M[X, a] = {XUVW} thay X đang nằm trên đỉnh ngăn xếp bằng WVU (U sẽ nằm trên đỉnh) (thực hiện một phép mở rộng cây)Nếu M[X, a] = lỗi (vị trí lỗi), gọi hàm khôi phục lỗi.*Thuật toánĐặt con trỏ ip chỉ đến ký tự đầu tiên của xâu w$ repeat Giả sử X là ký hiệu đỉnh của ngăn xếp và a là ký hiệu vào tiếp theo; if X là một ký hiệu kết thúc hoặc $ then if X = a then pop X từ đỉnh ngăn xếp và loại bỏ a khỏi xâu vào else ERROR( ); else { X không phải là ký hiệu kết thúc } if M[X, a] = X  Y1Y2 ...Yk then begin pop X từ ngăn xếp; push Yk,Yk-1,...Y1 vào ngăn xếp, với Y1 ở đỉnh; đưa ra sản xuất X Y1Y2 ...Yk end else ERROR( ); until X = $; { ngăn xếp rỗng }*Tìm đường*Ví dụ*Ví dụ - phân tích: a+a*a*Ví dụ*Nhận xétM[A, a] đóng vai trò “cẩm nang” tìm đườngChương trình đơn giảnHoạt động nhanhCần xây dựng M[A, a]?First, Follow*Tính First và FollowTính dựa vào bộ luật PTừ First và Follow có thể xây dựng được bảng M[A, a]*Định nghĩaFIRST(): là tập các ký hiệu kết thúc bắt đầu các xâu được suy dẫn từ .FOLLOW(A): là tập các ký hiệu kết thúc a mà chúng có thể xuất hiện ngay bên phải của A ở trong một số dạng câu, tức là tập các ký hiệu kết thúc a sao cho tồn tại một suy dẫn dạng E + Aa đối với ,  bất kỳ. Nếu A là ký hiệu bên phải nhất trong một số dạng câu thì ta thêm $ vào FOLLOW(A).*Hàm FIRST() cho biết một xâu hiện tại có thể suy dẫn đến tận cùng thành một xâu bắt đầu bằng các kí hiệu kết thúc nào.Hàm FOLLOW(A) cho biết các kí hiệu kết thúc ở đầu phần câu do các phần tử sau A tạo ra.*Tính First()Hai bước:Tính First(A)Tính First()*Tính First(A)Lặp cho đến khi không còn thêm:Nếu X là ký hiệu kết thúc thì FIRST(X) = {X};Nếu X là một sản xuất thì thêm  vào FIRST(X);Nếu XY1Y2 ...Yk là một sản xuất:Nếu với một i nào đó thì  có trong mọi FIRST(Y1), FIRST(Y2),... FIRST(Yi-1) (nghĩa là Y1Y2 ...Yi-1 *) thì ta thêm mọi ký hiệu kết thúc có trong FIRST(Yi) vào FIRST(X).Nếu i = k (tức là  có trong mọi FIRST(Yi) với i = 1, 2, ..., k) thì thêm  vào FIRST(X).*Tính First()Tính FIRST() với  có dạng X1X2 ... Xn:Thêm vào FIRST(X1X2 ... Xn) tất cả các ký hiệu không phải  của FIRST(X1).Thêm các ký hiệu không phải  của FIRST(X2) nếu  thuộc FIRST(X1)Thêm các ký hiệu không phải  của FIRST(X3) nếu  thuộc cả FIRST(X1) và FIRST(X2)...Thêm  vào FIRST(X1X2...Xn) nếu với mọi i mà FIRST(Xi) có chứa , hoặc nếu n = 0.*Tính FOLLOW(A)Lặp cho đến khi không thể thêm gì vào tập FOLLOW:Đặt $ vào FOLLOW(A), với A là ký hiệu bắt đầu (đỉnh cây con), $ là ký hiệu đánh dấu kết thúc xâu vào (chú ý là A không nhất thiết phải trùng với S do ta đang tính FOLLOW cho cây con);Nếu có một sản xuất dạng BA (với   ), thì mọi phần tử thuộc FIRST() trừ  đều được cho vào FOLLOW(A);Nếu có một sản xuất dạng BA (hoặc một sản xuất BA với FIRST() chứa , nghĩa là  * ), thì mọi phần tử của FOLLOW(B) cũng cho vào FOLLOW(A).*Ví dụCho văn phạm:ETE’E’+TE’ | TFT’T’*FT’ | F(E) | a*Ví dụ tính FirstTính FIRST(F):Áp dụng qui tắc 3 của cách tính FIRST(X) vào các sản xuất F (E) và Fa ta có:FIRST(F) = { (, a}.Tính FIRST(T):Từ sản xuất TFT' ta thấy không có  trong FIRST của phần tử đầu tiên vế phải (tức là FIRST(F)), do đó theo qui tắc 3 ta cóFIRST(T) = FIRST(F) = { (, a }. *FIRST(E):Đối với sản xuất ETE', ta có:FIRST(E) = FIRST(T) = { (, a }FIRST(E’):Từ sản xuất E'+TE' áp dụng qui tắc 3, sản xuất E' áp dụng qui tắc 2 ta có:FIRST(E') = {+,  }.FIRST(T’) : đối với hai sản xuất T'*FT' và T' ,FIRST(T') = {*,  }.*Tính FOLLOWTính FOLLOW(E):$ thuộc tập này theo qui tắc 1 (qui tắc này sẽ không được áp dụng cho bất kì kí hiệu nào khác nữa).Áp dụng qui tắc 2 vào sản xuất F(E), (sản xuất này có dạng BA thu được:FOLLOW(E) = FIRST( ) ) = { ) }Không còn luật nào có E vế phải nữa nên FOLLOW(E) dừng.Tổng hợp kết quả: FOLLOW(E) = { ), $}.Tính FOLLOW(E'):Theo qui tắc 3 áp dụng cho luật ETE' ta nhận được FOLLOW(E') = FOLLOW(E) = { ), $}.Cũng qui tắc này có thể áp dụng cho luật 2 nhưng ta không thu thêm được gì mới...*Kết quả:FIRST(E)=FIRST(T)=FIRST(F) ={ (, a}FIRST(E’) = {+, }FIRST(T’) = {*, }FOLLOW(E) = FOLLOW(E’) = { ), $}FOLLOW(T) = FOLLOW(T’) = { +, ), $}FOLLOW(F) = { +, *, ), $}*Lập bảng phân tíchCho một văn phạm GGiả sử A là một sản xuất với a thuộc FIRST().Mỗi khi bộ phân tích gặp A ở trên đỉnh của ngăn xếp và a là ký hiệu vào hiện tại thì bộ phân tích sẽ mở rộng A bằng  (bảng M[A, a] = A).Rắc rối: khi = hoặc *. Mở rộng A bằng  nếu:ký hiệu vào hiện tại thuộc FOLLOW(A), hoặcký hiệu vào hiện tại là $ và $ thuộc FOLLOW(A).*Thuật toán 5.2Thuật toán 5.2. Xây dựng bảng phân tích tất định LL.Vào: Văn phạm G.Ra: Bảng phân tích M.*Thuật toán 5.2Đối với mỗi sản xuất A, thực hiện bước 2 và bước 3.Đối với mỗi ký hiệu kết thúc a thuộc FIRST(), thêm A vào ô M[A, a].Nếu  thuộc FIRST(), thêm A vào M[A, b] đối với mỗi b thuộc FOLLOW(A). Nếu  thuộc FIRST() và $ là thuộc FOLLOW(A), thêm A vào M[A, $].Đặt tất cả các vị trí chưa được định nghĩa còn lại của bảng là lỗi.*Ví dụLuật ETE’ :FIRST(TE') = FIRST(T) = {(, a}Cả hai ô M[E, (] và M[E, a] đều được đặt là ETE’ (theo mục 2, thuật toán 5.2)Luật E’+TE’FIRST(+TE’) = { + }Ô M[E', +] được đặt là E'+TE'*Ví dụ (tiếp)Luật E’ FIRST () = { }Phải dùng FOLLOW (E’) thay thếFOLLOW (E’) = { ), $} Cả hai ô M[E’, )] và M[E, $] được đặt là E’ Cuối cùng bảng phân tích như ví dụ 5.1.*Văn phạm LL(k) và LL(1)Chữ "L" đầu tiên: quét từ trái sang phải (left-to-right)Chữ "L" tiếp theo: chỉ suy dẫn đưa ra là suy dẫn trái nhất (leftmost derivation)k là một số chỉ việc nhìn trước k ký tự để quyết định hành động phân tích ở mỗi bước.Thực tế hay dùng k = 1, bộ phân tích là LL(1) và thường được viết tắt là LL nếu không sợ hiểu nhầm.*Văn phạm LL(1)Khi áp dụng thuật toán 5.2 cho một số văn phạm, có thể có một số vị trí trong bảng phân tích có trên một giá trị (tức là số sản xuất nhiều hơn 1). Ví dụ, nếu văn phạm G là đệ quy trái hoặc nhập nhằng thì ít nhất phải có một vị trí trong bảng như vậy.Định nghĩa 5.3: Văn phạm LL(1) là các văn phạm xây dựng được bảng phân tích theo thuật toán 5.2 có các ô chỉ được định nghĩa nhiều nhất là một lần.Văn phạm LL(1) không bị nhập nhằng và không có đệ quy trái.*Điều kiện để một VP là LL(1)Nếu A |  là hai sản xuất phân biệt của G thì các điều kiện sau phải thỏa mãn:Không có một ký hiệu kết thúc a nào mà cả  và  có thể suy dẫn các xâu bắt đầu bằng a.Nhiều nhất là chỉ một trong  hoặc  có thể suy dẫn ra xâu rỗng.Nếu *  thì  không suy dẫn được một xâu nào bắt đầu bằng một ký hiệu kết thúc b thuộc FOLLOW(A).*Điều kiện để một VP là LL(1)Các điều kiện trên tương đương với biểu thức dưới đây:FIRST( )  FOLLOW(A)  FIRST ()  FOLLOW(A) =  Cách đơn giản: lập bảng phân tích và dựa vào định nghĩa 5.3 kiểm tra.*Khôi phục lỗiMột lỗi sẽ được phát hiện trong quá trình phân tích tất định khi:Ký hiệu kết thúc ở trên đỉnh ngăn xếp không đúng với ký hiệu vào tiếp theo;Vị trí trong bảng phân tích là M[A, a] với biến A ở trên đỉnh ngăn xếp và ký hiệu vào tiếp theo a, lại là rỗng hay đã điền dấu hiệu báo lỗi (error).*Chiến lược khôi phục lỗiThường theo kiểu trừng phạt: bỏ qua các ký hiệu trên xâu vào cho đến khi xuất hiện một từ tố thuộc tập từ khoá đã được xác định trước (gọi là tập từ khoá đồng bộ).Tính hiệu quả của phương pháp này phụ thuộc vào việc chọn tập đồng bộ. Các tập này được chọn sao cho bộ phân tích vượt qua được lỗi nhanh chóng.*Chọn tập đồng bộ synch(A)Khởi đầu: đưa FOLLOW(A) vào synch(A). Nếu khi có lỗi chúng ta bỏ qua các từ tố cho đến khi một phần tử của FOLLOW(A) xuất hiện và lấy A khỏi ngăn xếp, lúc này quá trình phân tích có thể tiếp tục.Tăng cường: thêm các từ khoá bắt đầu các câu lệnh vào các tập đồng bộ của các ký hiệu không kết thúc sinh ra các biểu thức.Thêm các ký hiệu trong FIRST(A) nhằm có thể tiếp tục phân tích theo A nếu một ký hiệu trong FIRST(A) xuất hiện ở đầu vào.Nếu một ký hiệu không kết thúc có thể sinh ra một xâu rỗng thì sản xuất suy dẫn ra có thể được sử dụng như ngầm định. Dùng để giảm số lượng các ký hiệu không kết thúc phải xem xét trong lúc khắc phục lỗi.Nếu một ký hiệu kết thúc nằm trên đỉnh ngăn xếp không đúng: loại bỏ ký hiệu kết thúc này, đưa ra một thông báo và tiếp tục phân tích. Phương pháp này tạo nên tập đồng bộ của một từ tố có chứa tất cả các từ tố khác.*Ví dụ:synch = {+, *, ), $ } *Ví dụ:Xâu vào:) a * + a *Bài tập1. Cho một văn phạm với các luật sản xuất như sau: EaEbE | bEaE |  Văn phạm này có là văn phạm LL(1) không? Tại sao?2. Cho một văn phạm với các luật sản xuất như sau:ETE’; E'+E | ; TFT’; T’T|;FPF’; F’*F’| ; P( E ) | a | b |  trong đó, P là đỉnh của cây con.Tính các FIRST và FOLLOW;Văn phạm này là LL(1) ?Xây dựng bảng phân tích nếu nó là LL1.