(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp

1.4. Phương pháp Canonical LR (LR(1))
-          Trong PP SLR xung đột chỉ xảy ra ở những thực thể Aàa .
-          Khi xảy ra xung đột ta có thể sử dụng PP Canonical LR
-          Cấu tạo: như SLR
-          Hoạt động: như SLR
-          Thuật toán: như SLR
-          Xây dựng bảng Canonical LR
Ø  Xây dựng bảng Canonical LR
-          Văn phạm gia tố: như SLR
-          Thực thể: gồm có 2 phần
+          Phần nhân: giống thực thể trong SLR
+          Ký hiệu nhìn trước: aÎΣ
            Ví dụ: AàX.YZ, a
-          Hàm tính bao đóng closure(Ii): 2 qui tắc
(1)   Đưa tất cả các thực thể trong Ii vào closure(Ii)
(2)   Cứ thực thể [Aàa.Bb,a]Îclosure(Ii) mà Bàg thì thêm [Bà.g, b] vào closure(Ii) với [Bà.g, b]Ïclosure(Ii) và bÎfirst(ba)
-          Qui tắc xác định First(a)
                        First(a)={(aÎΣ|aÞ+ab)È(a=$|aÞ+e )}
-          Hàm tính goto(Ii,X)
            Goto(Ii,X)=Closure({AàaX.b, a}) với {Aàa.Xb, a}Ì Ii và XÎ(ΣÈΔ)
-                     -           I0=closure({S’à.S, $})



(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp


 -          Qui tắc xác định hành động
(1)   $ [Aàa.ab,b]Î Ii và goto(Ii,a)=Ij  với a ÎΣ    thì: Action[i,a]= Sj
(2)   $ [Aàa.Xb,b] Î Ii và goto(Ii,X)=Ij  với X ÎΔ    thì: goto[i,X]= j
(3)   $ [S’àS.,$] Î Ii thì: Action[i,$]= accept
(4)   $ [Aàa.,a]ÎIi thì Action[i,a]= Reduce Aàa với A<>S’
-          -         Trộn các tập thực thể
            Với các tập thực thể có chung phần nhân, khác nhau phần ký hiệu nhìn trước, ta có thể trộn chúng lại với         nhau để  được một tập thực thể mới có:
+ phần nhân: phần giống nhau
+ ký hiệu nhìn trước: hợp các k/h nhìn trước
Ví dụ:   Sà AA
            Aà aA | d
-          Xây dựng văn phạm gia tố G’
-          Tính I0=closure({S’à.S, $} và tất cả các Ii
-          Xác định hành động
Ví dụ:   Sà AA
            Aà aA | d
I0=closure({S’à.S, $}
(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp

(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp

(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp
Bài tập: xây dựng bảng Canonical LR
                                                SàAS | b
                                                Aà SA | a
(I0àI10) trộn I2 và I10, I3 và I7, I8 và I9

2. Phương pháp phân tích cú pháp trên xuống 
-          PTCP từ trên xuống: thay vế trái bằng vế phải. Một vấn đề đặt ra khi có 2 sx có vế trái giống nhau thì chọn sx nào?
-          Chọn một sx nếu không được thì quay lui, chọn sx khác
-          Hạn chế văn phạm.
    2.1. Văn phạm LL(1)
-          VP cho phép PTCP bằng cách triển khai dần dần suy dẫn trái từ trên xuống.
-          Thăm dò xâu vào từ trái sang phải
-          Nhìn trước 1 ký hiệu
Ø  Định nghĩa:
VP PNC G=(Σ, Δ, S, p) được gọi là LL(1) nếu nó thỏa mãn 2 điều kiện sau:
(1)   "sx có dạng Aàb1 | b2 | b3 |… | bn thì phải có first(bi) Ç first(bj) = f với i¹j
            (2)   AÎΔ mà AÞ+ e thì phải có: first(A) Ç follow(A)=f
Ø  Ví dụ:
(1)                           SàA | B
                                    AàaA | b
                                    BàaB | c
            Xét: SàA | B    First(A)={a,b} First(B)={a,c}
            First(A) Ç first(B)={a}¹f (vi phạm ĐK1) nên vp trên không phải là LL(1)
(2)   AàAa
                                    Aàa | e
Xét: AÎΔ mà AÞ+ e có: first(A)={a,$}, follow(A)={a} nên first(A)Çfollow(A)={a}¹f (vi pham đk2)
VP trên không phải là LL(1)
2.2. Vài phép biến đổi về VP LL(1)
Ø  Khử đệ qui trái:
            Dạng (1): AàAab
            Dạng (2): AàAa | e      
Xét (1) có: first(Aa)=first(b) nên first(Aa)Çfirst(b)=first(b)¹f (vi pham đk1) VP đệ qui trái không phải là LL(1)
Xét (2): AÎΔ mà AÞ+ e có:  first(A)=first(Aa)=first(a), follow(A)=first(a) nên first(A)Çfollow(A)=first(a)¹f (vi pham đk2)     VP đệ qui trái không phải là LL(1)

(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp

(Tiếp) Chương 4: Các phương pháp Phân tích cú pháp

 Ø  Đặt thừa số chung:
            Dạng (3): Aàab | ag
            Có: first(ab)=first(ag)=first(a) nên first(ab)Çfirst(ag)=first(a)¹f     (vi phạm đk1)
Dạng (3):          Aàab | ag
            Thay bởi:          Aàa A’
                                    A’àb





Ø  Bài tập: Biến đổi các VP sau thành LL(1)
(1)               E à E + T | T
                        T à T * F | F
                        F à (E) | id
(2)               A àA T | T
            T à0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(3)   AàA S | A C | C
                        C àa
                        S à 0
     (4)   Xây dựng VP LL(1) sản sinh ra danh định của một ngôn ngữ.
Ø  giải
(1)    E à TE’
            E’à+TE’ | e
            T à FT’
            T’à*FT’ | e
            Fà(E) | id
(2)   Aà TA | T                     AàTA’
            Tà 0 | .. | 9                   A’àA |e
                                                Tà 0|..|9
(3)   Sx(1) và (2) biến đổi:     A àAA’            A’àS | C
                                                AàAA’|C          AàCA”             AàCA” A’àS | C           A”àA’A”|e                                                         A”àSA”            Cà a                A’àS|C             A”àCA”|e                                                          Sà 0                Càa                 Càa                                                                                                     Sà0                 Sà0
(4)   ID à ID CC | ID CS |ID_ | CC| _ID|
            CCà a | b
            CS à 0 | 1
            AàCC A’ | _B
            BàCCA’ | CS A’| _B
            A’àCCA’| CSA’ | _A’| e
            CCàa
            CSà0





Ø  Cấu tạo:
-          Stack: xixi-1…x0$ với xt Î (ΣÈΔ)
-          Buffer: aiai-1…a0$ với at Î Σ
-          Bảng tiên đoán M:
ü  Chỉ số hàng: A Î Δ
ü  Chỉ số cột: a Î Σ
ü  M[A,a]: Aàa hoặc rỗng
Ø  Hoạt động:  Tại một thời điểm nếu:
-          Ở stack là $ và buffer là $: x đúng CP VPG
-          Ở đỉnh stack và buffer aÎΣ: đối sánh a
-          Ở đỉnh stack là AÎΔ thì nếu:
          M[A,a]=Aàa : triển khai Aàa ở đỉnh stack
          M[A,a]=rỗng: xâu x không đúng CP VPG
Ø  Giải thuật:
Sử dụng: 1 stack và 1 buffer
Khởi tạo:          - stack là S$
                                    - Buffer là x$
Lặp:
                        If (stack là $) và (buffer là $) then
                                    x đúng cp và dừng vòng lặp
Else if (aÎΣ ở đỉnh stack và buffer) then            
đối sánh a ở đỉnh stack và buffer
Else if (AÎΔ ở đỉnh stack) và (a ÎΣ ở đỉnh buffer) then                          
if (M[A,a]=Aàa) then
triển khai A ở đỉnh stack            
Else  x k0 đúng CP VPG, dừng vòng lặp
Ø  Ví dụ:   SàaA
                                    AàbA | c
            Xâu x: abbc có đúng CP của VP trên ?












Ø  Xây dựng bảng tiên đoán M: 2 qui tắc
(1)   " sx Aàa thì M[A,a]=Aàa với aÎfirst(a)
            a ¹ e
(2)   " sx Aàe thì M[A,a]=Aàe với a Îfollow(A)










-          Xét sx: E à TE’ có First(TE’)={ (, id }

            M[E,(]=M[E,id]=EàTE’
-          Xét sx: E’à+TE’ có First(+TE’)={+}
            M[E’,+]=E’à+TE’
-          Xét sx: TàFT’ có First(FT’)={(, id}
            M[T,(]=M[T,id]=TàFT’
-          Xét sx: T’à*FT’ có First(*FT’)={*}
            M[T’,*]=T’à*FT’
-          Xét sx: Fà(E) có First((E))={(}
            M[F,(]=Fà(E)
-          Xét sx: Fàid có First(id)={id}
            M[F,id]=Fàid
-          Xét sx: E’àe có follow(E’)={), $}
            M[E’,)]=M[E’,$]=E’àe
-          Xét sx: T’àe có follow(T’)={),$,+}
            M[T’,)]=M[T’,$]=M[T’,+]=T’àe
            EÞTE’ÞTÞFT’Þ FÞ(E)Þ(TE’)Þ(T)Þ(FT’)
            E Þ TE’ Þ T+TE’ Þ FT’+TE’

Bài tập:

      xây dựng bảng tiên đoán M cho các vp LL(1) trong phần vài phép biến đổi về LL(1). Tự cho xâu vào và phân tích theo PP tiên đoán
2.4. Phương pháp đệ qui không quay lui
-          Về mặt nguyên lý giống pp tiên đoán.
-          Khác về lập trình: không tra bảng tiên đoán M mà mô phỏng trực tiếp.
-          Thay stack bằng sự đệ qui trong chương trình.
-          Một k/h chưa kết thúc: bdiễn bằng 1 biểu đồ cú pháp
-          Một biểu đồ cú pháp: bdiễn bằng 1 CT con













Ø  Thuật toán:

k/htiep: ký hiệu kết thúc;
function  Dockh:ký hiệu kết thúc; {đọc k/hiệu tiếp trong x}
Procedure Baoloi; {đưa thông báo lỗi, dừng}
Procedure bI;{các Ctcon biểu diễn AÎΔ}
Procedure PTCP;
            Begin    k/htiep:=Dockh;
                                    S;
                                    if k/htiep=$ then x đúng CP
                                    else baoloi;
            End.
Ví dụ:   E à TE’
            E’à+TE’ | e
            T à FT’
            T’à*FT’ | e
            Fà(E) | id














Ví dụ: giải thuật các ctcon tương ứng
k/htiep: ký hiệu kết thúc;
function  Dockh:ký hiệu kết thúc; {đọc k/hiệu tiếp trong x}
Procedure Baoloi; {đưa thông báo lỗi, dừng}
Procedure E;
            Begin   
                        T; Ephay;
            End;
Procedure Ephay;
            Begin
                        If k/htiep=+ Then                                                                                 
Begin    k/htiep:=Dockh;
                                                T;
                                                Ephay;                                                   
 End;                                                        
End;
Procedure T;
            Begin   
                        F;
                        Tphay;
            End;
Procedure Tphay;
            Begin
                        If k/htiep=* Then                                                                                     
Begin    k/htiep:=Dockh;
                                                F;
                                                Tphay;                                       
 End;                                                                  
End;
Procedure F;                                                                   
Begin                                                                           
If k/htiep=id Then
k/htiep:=Dockh                                    
Else
                                    If k/htiep=( Then                                                      
Begin    k/htiep:=Dockh;                                                
E;
if k/htiep=) Then
k/htiep:=Dock                           
Else baoloi;                                                            
End                                                                      
Else baoloi;           
End;
Procedure PTCP;
            Begin    k/htiep:=Dockh;
                                    E;
                                    if k/htiep=$ then x đúng CP
                                    else baoloi;
            End.
Bài tập:            
            Xây dựng giải thuật đệ qui không quay lui cho các VP LL(1) trong phần bài tập vài phép biến đổi về VP LL(1)


Post a Comment