Chương 3: Các vấn đề cơ bản về phân tích cú pháp

Sinh viên học tiếp chương 3 như đã trao đổi ở lớp học.

2. Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Ø  Cây suy dẫn: cây thoả mãn các điều kiện:
-          Mỗi nút có 1 nhãn: ký hiệu kết thúc hoặc chưa kết thúc
-          Nhãn của nút gốc: ký hiệu bắt đầu
-          Nhãn của nút lá: ký hiệu kết thúc
-          Nếu một nút có nhãn A có các nút con của nó từ trái sang phải có nhãn x1, x2, x3, …xn thì Aàx1x2x3…xn Î p
Ø  Cây suy dẫn
-          Suy dẫn trái tạo cây suy dẫn trái.
-          Suy dẫn phải tạo cây suy dẫn phải.
-          Ví dụ: cho văn phạm phi ngữ cảnh sau:
                                    EàE+E | E*E | (E) | a
                        Vẽ cây suy dẫn trái, phải sinh xâu: a+a*a
Ø  Văn phạm đơn nghĩa
Văn phạm G=(Σ, Δ, s, p) sản sinh ra ngôn ngữ L(G)={wÎΣ*}. Ta nói G là văn phạm đơn nghĩa (không nhập nhằng) nếu với mỗi xâu wÎL(G) chỉ có một cây suy dẫn duy nhất, trái lại thì G là văn phạm nhập nhằng.
Ø  Văn phạm tương đương
Văn phạm G1 và G2 được gọi là tương đương Û bất kỳ xâu x được sinh ra từ G1 thì G2 cũng sinh ra được và ngược lại
Ø  Văn phạm đệ qui
Cho văn phạm PNC G, với A ÎΔ$AÞ+aAb thì A gọi là ký hiệu đệ qui, G gọi là văn phạm đệ qui. Với a, b Î (ΣÈΔ)*
-          Nếu a=e: đệ qui trái
-          Nếu b=e: đệ qui phải
Ø  Văn phạm đệ qui
            Ví dụ:  SàS0 | S1 | 0 | 1
Bài tập
(1)   Xác định ngôn ngữ được sản sinh bởi Văn phạm:
            a. SàS(S)S | e
            b. SàaSb | bSa| e
            c. Sà+ S S | * S S | a
            d. Sà0S1 | e
(2) Xây dựng văn phạm sản sinh ra ngôn ngữ:
            a. Số nhị phân lẻ
            b. Số nguyên k0 dấu
            c. Số nguyên có dấu
            d. Số thực, số nguyên k0 và có dấu
(2) Xây dựng văn phạm sản sinh ra ngôn ngữ:
            a. Sà0S |1S |1
            b. Sà0S| 1S|..|9S|0|..|9
            c.         NCDà D S
                        D à+ | -
                        Sà0S| 1S|..|9S|0|..|9
d. SOàNCD.S | S.S | S |NCD
                        NCDà D S
                        D à+ | -
                        Sà0S| 1S|..|9S|0|..|9
3. Đại cương về phân tích cú pháp
3.1. Mục đích
            Cho G=(Σ, Δ, s, p)
            Một xâu vào xÎΣ*
ð   x có viết đúng cú pháp của văn phạm G?
3.2. Phương pháp giải quyết
Ø  Bắt đầu từ S áp dụng các sản xuất để tìm x: PTCP từ trên xuống
-          Nếu tìm được x: x viết đúng cú pháp của văn phạm G
-          Nếu k0 tìm được x: x viết không đúng cú pháp của văn phạm G
Ø  Bắt đầu từ x áp dụng các suy dẫn ngược 1 sản xuất để thu S: PTCP từ dưới lên
-          Nếu thu được S: x viết dúng cú pháp của văn phạm G
-          Nếu k0 thu được S: x viết k0 đúng cú pháp của văn phạm G
Ví dụ: Cho văn phạm PNC G sau:
                                    SàB
                                    BàR | (B)
                                    Rà E=E
                                    Eà a | b | (E+E)
                        Xâu x: (a=(b+a))
                        Hỏi xâu x có viết đúng cú pháp của G k0?









Giải:





















Ø  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
                        If  (cán b xuất hiện ở đỉnh stack) Then
                     - Lấy cán b ra khỏi stack
                             - Đẩy A vào stack với Aàb
Else
                             If  (Buffer<>$) Then
                                 D/c k/h ở đỉnh của Bufferà Stack
                             Else
                                -Báo lỗi x không đúng cú pháp VP 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?
Giải:



















Ø  Thuật toán:
Sử dụng: 1 stack và 1 buffer
Khởi tạo: - stack: S$
                               - Buffer: x$
Lặp: If (Stack là $) và (Buffer là $) Then
                        - x đúng cú pháp của VP G
- Dừng vòng lặp
             Else
                        If  (AÎΔ) xuất hiện ở đỉnh Stack Then
                            Chọn sx thích hợp Aàb
                            Triển khai A bằng b ở đỉnh Stack
Else
                             If  (aÎΣ) xuất hiện ở đỉnh Stack và Buffer Then 
                                    Lấy a ra khỏi Stack và Buffer {đối sánh}
    Else
                                - Báo lỗi x không đúng cú pháp của G
                                - Dừng vòng lặp
Ø  Ví dụ:   SàaA
                        AàbA | c
            Xâu x: abbc có đúng cú pháp của VP trên ?
Giải:













Bài tập:
(1)   Cho văn phạm G:         S àvar ID:K;T
                                 ID àa | b | c
                                 K àbyte | integer | real
                                 T à begin L end.
                                 L à read(ID) | write(ID)
            Xâu x: var a : byte; begin read(a) end.
            Xâu x có đúng cp của G? ch/m?
(2)   Cho văn phạm G:         S àaA | bA
                                 A àcA | bA | d
            Xâu x: abbcbd 
            Xâu x có đúng cp của G? ch/m?
4. Các phương pháp phân tích  pháp
4.1. Từ trên xuống
-          Phương pháp tiên đoán
-          Phương pháp đệ qui không quay lui
4.2. Từ dưới lên
-          Phương pháp ưu tiên toán tử
-          Phương pháp thứ tự yếu
-          Phương pháp LR(k)

(Sinh viên theo dõi tiếp chương 4 để củng cố kiến thức thi hết môn học)

Post a Comment