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

1. Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
Ø  Văn phạm ưu tiên toán tử
            Văn phạm phi ngữ cảnh thỏa mãn các ĐK:
-          Không có 2 sản xuất có cùng vế phải
-          Không có vế phải là e
-          Không có 2 ký hiệu chưa kết thúc đứng liền nhau
Ø  Mối quan hệ ưu tiên giữa các ký hiệu
                        Với a, b ÎΣ có:
-          a < b : a kém ưu tiên hơn b
-          a= b: a ưu tiên bằng b
-          a > b: a ưu tiên hơn b
-          a và b : không có quan hệ ưu tiên
-          Qui tắc xác định mối quan hệ
(1) $ Sx mà vế phải có dạng aabb hay aaCbb    => a=b
(2) $ Sx mà vế phải có dạng aaBb mà BÞ+ bg hay BÞ+Cbg     => a<.b
(3) $ Sx mà vế phải có dạng aAbb mà AÞ+ ga hay AÞ+ gaC   => a .>b
(4)        SÞ+ga hay SÞ+gaC      hay SÞ+ ag hay SÞ+Cag   => a .>$
            Với a, bÎΣ; A,B,CÎΔ; a, b, g Î (ΣÈΔ)*
v  Lưu ý:
-     Cán:<. .>
-          a <.  b
-          b <. c
ð  a <. c (Không có tính chất bắc cầu)
Ø  Thuật toán
Sử dụng: 1 stack và 1 Buffer
Khởi tạo:                - stack:             $
                                    - Buffer:            x$
Lặp: If  (Stack là $S) và (Buffer là $) Then
                        - x đúng cú pháp của vp G
                        - Dừng vòng lặp
Else     {giả sử k/h kết thúc gần đỉnh stack nhất là a và buffer là b}
                        If  (a>b) Then
                         - Tìm cán b ở đỉnh stack(vị trí mở cán <)
                        - Lấy cán b ra khỏi stack
                        - Đẩy A vào stack với Aàb
                        Else
                                    If  (a<b) or (a=b)Then
                                    D/c b từ Bufferà Stack
                                    Else
                                    - Báo lỗi x không đúng cú pháp G
                                    - Dừng vòng lặp          
Ø  Ví dụ:   Sàif  DK then L ;
                                    DK à true | false
                                    L à write(ID) | read(ID)
                                    ID àa | b
            Xâu x: if true then read(a); có đúng cú pháp vp trên?
Gợi ý giải:
-          Xác định tất cả các mối quan hệ
            Xét vế phải của từng sản xuất
      -    Phân tích 
Giải 1:



Giải 2:












Bài tập:
(1)   Cho văn phạm G:
                        S àC ; H                                  H àtype ID=A;B
                        Càconst ID = N                       A à byte | real
                        IDàa | b | c                              Bà var ID : A;
                        N à 5                          
            Xâu x: const a=5; type b=byte; var c:real;
(2)   Cho văn phạm G:
            S àC ; H                      H àtype ID=A var B
            Càconst ID = N           A à byte; | real;
            IDàa | b | c                  Bà ID : A
            N à 5                          
            Xâu x: const a=5; type b=byte; var c:real;
Bài tập:
(1)   Cho văn phạm G:
                        S àC ; H                                  H àtype ID=A;B
                        Càconst ID = N                       A à byte | real
                        IDàa | b | c                              Bà var ID : A;
                        N à 5                          
            Xâu x: const a=5; type b=byte; var c:real;
(2)   Cho văn phạm G:
            S àC ; H                      H àtype ID=A var B
            Càconst ID = N           A à byte; | real;
            IDàa | b | c                  Bà ID : A
            N à 5                          
            Xâu x: const a=5; type b=byte; var c:real;
Giải:














Ø  Cấu tạo:
-          Xi Î (ΣÈΔ)
-          yi Î Σ
-          S_R: ma trận có:
          Chỉ số hàng xi Î (ΣÈΔ)
          Chỉ số cột yi Î Σ
          S_R[xi,yi]: có các giá trị
-          S_R[xi,yi]=S
-          S_R[xi,yi]=R
-          S_R[xi,yi]=R*
-          S_R[xi,yi]=rỗng
ØØ Hoạt động:
-          Tại một thời điểm nào đó k/h ở đỉnh của stack là XiÎ(ΣÈΔ), ở đỉnh buffer là yiÎΣ. Bộ phân tích sẽ xác định hành động thông qua bảng S_R:
          S_R[xi,yi]: xác định hành động
-          S_R[xi,yi]=S: dịch chuyển k/h đỉnh buffer à stack
-          S_R[xi,yi]=R: rút gọn
-          S_R[xi,yi]=R*: chấp nhận x đúng cp G
-          S_R[xi,yi]=rỗng: báo lỗi x k0 đúng cp G
Ø  Thuật toán
Sử dụng: 1 stack và 1 Buffer
Khởi tạo:          - stack:             $
                                    - Buffer:            x$
Lặp:
                        {g/sử k/h ở đỉnh stack là x, ở đỉnh buffer là y}
If  (S_R[x,y]=R*) Then
                        - x đúng cú pháp của vp G
                        - Dừng vòng lặp           
Else   If  (S_R[x,y]=rỗng) Then
                        Báo lỗi và dừng vòng lặp
Else   If (S_R[x,y]=S) then
                                    D/c y từ buffer àstack
Else   {S_R[x,y]=R}
                                    If (Có vế phải b dài nhất ở đỉnh stack) then
                                                - Lấy b ra khỏi stack
                                                - Đẩy A vào stack với Aàb
Else
                                          - Báo lỗi và dừng vòng lặp
Ø  Ví dụ: Cho G : Sàid=A
                  AàA+B | B
                  BàB*C | C
                  Càid | (A)
Xâu x: id=id+id*id

 Giải:















Ø  Ví dụ: cho G như sau:
          SàA C D                       Aà const ID=N;
          Cà var ID: K;               Dà begin L end.
          Là write(ID) |read(ID)  IDà a|b
          Nà5                              Kàbyte|real
Xâu x: const a=5;var b:byte;begin read(b) end.

Giải:















Ø  Văn phạm thứ tự yếu
Văn phạm phi ngữ cảnh thỏa mãn các ĐK:
-          Không có 2 sản xuất có cùng vế phải
-          Không có vế phải là e
-          Không có phần tử S_R[x,y] có cả trị S và R
-         Nếu $Aàx1x2…xn và Bàxixi+1…xn thì không $ xi-1<=B
Nếu $ xi-1<=B thì có nghĩa $ Càx1x2…xi-1B và như vậy để thu gọn x1x2…xn, thì sẽ thu gọn xixi+1…xn về B rồi mới thu gọn x1x2…xi-1B về C. Như vậy mâu thuẫn với tính chất luôn luôn thay thế vế phải dài nhất.

Ø  Cấu tạo:
-          Stack: $s0x0 s1x1…si-1xi-1si
                        st: trạng thái; xtÎ(ΣÈΔ)
-          Buffer: aiai-1…a0$  ; với at ÎΣ
-          Bảng SLR gồm 2 phần: action và goto
          Chỉ số hàng: trạng thái St
          Chỉ số cột
-          Phần action: aiÎΣ
-          Phần goto: XÎΔ
          Action[Si,ai]=Shift j (Sj)
          Action[Si,ai]=Reduce Aàa (RJ)
          Action[Si,ai]=Accept
          Action[Si,ai]=rỗng
          Goto[Si,X]=j
Ø  Hoạt động:
Tại một thời điểm bộ phân tích đọc trạng thái Si ở đỉnh stack và ký hiệu vào ai ở đỉnh buffer và tra trong bảng SLR ở phần Action một giá trị. Nếu:
-           Action[Si,ai]=Shift j (Sj)
-           D/c ai từ Buffer àStack
-          Đẩy j vào stack
-          Action[Si,ai]=Reduce Aàa (RJ)
-           Lấy 2*r phần tử ra khỏi stack. Với r=|a|
-          Đẩy A vào stack
-          Đẩy j vào stack với j=goto[Si-r,A]
-          Action[Si,ai]=Accept
-           Xâu x đúng cp của vpG
-           Action[Si,ai]=rỗng
-          Báo lỗi x không cú pháp của vpG
Ø  Thuật toán:
Sử dụng: 1 stack, 1 buffer, bảng SLR
Khởi tạo:          - stack: $0
                                    - Buffer: x$
Lặp: {g/sử ở đỉnh stack là Si, đỉnh buffer là a}
If (Action[Si,a]=accept) then
x đúng cp và dừng vòng lặp
Else If (Action[Si,a]=Sj) then
-          D/c a từ buffer à stack
-          Đẩy j vào stack
Else IF (Action[Si,a]=Reduce Aàa) then
Lấy 2*r phần tử ra khỏi stack
-          Đẩy A vào stack
-          Đẩy j vào stack. Với j=goto[Si-r,A]
Else {Action[Si,a]=rỗng}
-          Báo lỗi x không đúng cp của G
-          Dừng vòng lặp






















Ø  Xây dựng bảng SLR

-          Văn phạm gia tố G’

            G’=G È {S’àS}

            Ví dụ:   G:         S à 0S | 1S|0|1

                                    G’:        S’ à S
                                                S à 0S | 1S|0|1
-          Thực thể: Sx thêm dấu chấm ở bất kỳ vị trí của vế phải.
            Ví dụ:   A àxyz
                        thì         A à.xyz            Aàx.yz Aàxy.z
                                    A à xyz.  là các thực thể
-          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ứ mỗi thực thể có dạng Aàa.BbÎclosure(Ii) mà Bàg thì thêm Bà.g vào closure(Ii)với Bà.g Ï closure(Ii)
(3)   Ví dụ: Xác định tập closure(I) của VP G’
                                    E’à E
                                    E à E + T | T
                                    T à T * F | F
                                    F à (E) | id
I={E’à.E}
-          Hàm tính goto
            Goto(Ii,x)=closure({Aàax.b})
                        với {Aàa.xb} Ì Ii ; xÎ(ΣÈΔ)
Ø  Ví dụ: Tìm tất cả các tập goto(I,X) có thể của VP G
I={        E’à.E
Eà.E+T
            Eà.T
            Tà.T*F }
X: E, T
Goto(I,E) và Goto(I,T)
E’à E  
E à E + T | T
T à T * F | F
F à (E) | id
Goto(I,E)=closure({E’àE. ; EàE.+T})
Goto(I,T)=closure({EàT. ; TàT.*F})
-          Tập thực thể LR(0)
            I0=closure({S’à.S})
-          Tính tất cả các goto(Ii,x) của tất cả các tập thực thể ta sẽ được tập LR(0).
-          Tính hết goto(Ii,x) mà không sinh được Ii+1 thì dừng.
Ø  Qui tắc xác định hành động
(1)   $ Aàa.ab Î Ii và goto(Ii,a)=Ij  với a ÎΣ    thì: Action[i,a]= Sj
(2)   $ Aàa.Xb Î 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. Î Ii thì Action[i,a]= Reduce Aàa với aÎ Follow(A); A<>S’
-          Qui tắc xác định Follow Follow(A)={(tÎΣ|SÞ+aAtb)È(t=$|SÞ+ aA)}
Ví dụ: Cho vp G
      E à E + T | T
      T à T * F | F
      F à (E) | id
      Xây dựng bảng SLR cho VP G
Gợi ý giải:
-          Xác định G’
-          Tạo tập thực thể LR(0)
-          Xác định các hành động
Giải:
-          VP gia tố G’
      E’ à E
      E à E + T | T
      T à T * F | F
      F à (E) | id
-                     -        Tạo tập thực thể LR(0)
I0=closure({E’à.E})
E’à.E
Eà.E+T
Eà.T
            Tà.T*F
Tà.F
Fà.(E)
Fà.id
I1=goto(I0,E)
E’àE.
EàE.+T
-                    -           Xác định các hành động
Bài tập:
(1)   cho VPG:          A àA or B | B
                                                B à B and C | C
                                                C à not C | (A) | true | false
Hỏi xâu x: true and false or (not true) có được sinh ra từ VPG? c/m bằng PP SLR
(2)   Cho VPG:         S àAS| b
                                                A à SA| a
            Xây dựng bảng SLR cho VP G?









Post a Comment