Kĩ thuật lập trình - Văn phạm phi ngữ cảnh

Nguyễn Phương TháiBộ môn Khoa học Máy tínhú phápLà khuôn dạng hay cấu trúc của chương trìnhKhông liên quan đến ý nghĩa chương trìnhĐược mô tả bằng văn phạm phi ngữ cảnhTại sao chúng ta sử dụng văn phạm phi ngữ cảnh (VPPNC) cho phân tích cú phápCho phép mô tả rõ ràng và dễ hiểu cú pháp một ngôn ngữ lập trìnhDễ sửa đổi và mở rộng ngôn ngữ lập trìnhDễ tạo ra các bộ parserCho phép dịch dựa vào cú pháp**Nguyễn Phương Thái - Coltech - Compiler 2009Văn phạmPhân loại văn phạm của ChomskyCây phân tích, dẫn xuất, và văn phạm nhập nhằngÔtômát đẩy xuống**Nguyễn Phương Thái - Coltech - Compiler 2009Một ngôn ngữ L trên bộ chữ Σ là một tập con của Σ*.Bài toán đối với L:Cho một xâu w, xâu w có thuộc L?Làm thế nào để sinh ra w trong L?**Nguyễn Phương Thái - Coltech - Compiler 2009Thường dùng: văn phạmLà một công cụ mô tả hữu hạn ngôn ngữ rất hiệu quảLà công cụ có định nghĩa toán học chặt chẽ, đã được nghiên cứu kỹvăn phạm = ngữ pháp = cú pháp**Nguyễn Phương Thái - Coltech - Compiler 2009Ví dụ phân tích văn phạm**Nguyễn Phương Thái - Coltech - Compiler 2009Định nghĩaMột văn phạm là một hệ thống G = (, , P, S) trong đó: là tập hữu hạn các ký hiệu, gọi là ký hiệu kết thúc (terminal) là tập hữu hạn các ký hiệu, gọi là ký hiệu không kết thúc (nonterminal)S gọi là ký hiệu khởi đầuP là tập hữu hạn các cặp xâu (,) được gọi là các sản xuất hay luật cú pháp (→)**Nguyễn Phương Thái - Coltech - Compiler 2009Ví dụ: = {“bò”, “vàng”, “gặm”, “cỏ”, “non”} = {,, , , , , , }S =P=→;→;→;→ →; →”bò”|”cỏ”; →”vàng”|”non”; →”gặm”;**Nguyễn Phương Thái - Coltech - Compiler 2009Các qui ước:Dùng các chữ in hoa A, B, C, D, E... hoặc cụm từ trong cặp ngoặc nhọn (như ) để trỏ các ký hiệu không kết thúc;Dùng các chữ thường a, b, c, d, e... và các con số, các phép toán +, -, *, /, cặp ngoặc đơn để trỏ các ký hiệu kết thúc. Trong một số trường hợp dùng qui ước là một từ được in đậm (như số và chữ) hoặc cụm từ trong cặp ngoặc kép (như "bò");Dùng các chữ in hoa X, Y, Z để trỏ các ký hiệu có thể là kết thúc hoặc không kết thúc;Dùng các chữ thường u, v, w, x, y, z để trỏ các xâu ký hiệu cuối;Dùng các chữ thường Hy lạp , ,  để trỏ các xâu gồm các biến và ký hiệu cuối;Nếu có các sản xuất cùng vế trái A   và A   thì ta viết gộp lại cho gọn thành A   | . Các sản xuất có cùng một kí hiệu không kết thúc vế trái có thể gọi chung bằng tên kí hiệu vế trái. Ví dụ, sản xuất-A.**Nguyễn Phương Thái - Coltech - Compiler 2009V = (  )* là một xâu (có thể rỗng) bao gồm cả ký hiệu không kết thúc và ký hiệu kết thúc;V* là tập tất cả các xâu V có thể có;V+ cũng như vậy trừ xâu rỗng;| | là ký hiệu độ dài xâu (ví dụ |  | là độ dài của xâu );Ký hiệu  là một kí hiệu đặc biệt, chỉ xâu rỗng hoặc kí hiệu rỗng**Nguyễn Phương Thái - Coltech - Compiler 2009Định nghĩa suy dẫn (derivation): Cho văn phạm G = (,  , P, S) như trên, ta gọi suy dẫn trực tiếp là một quan hệ hai ngôi ký hiệu  trên tập V* nếu  là một xâu thuộc V* và  là một sản xuất trong P, thì   .Suy dẫn k bước kXâu  suy dẫn xâu :  * Suy dẫn không tầm thường: +**Nguyễn Phương Thái - Coltech - Compiler 2009Định nghĩa: Ngôn ngữ của văn phạm G là tập hợp các xâu ký hiệu kết thúc, ta ký hiệu là L(G), được sinh ra từ S, hoặc được phân tích (đoán nhận) về S: L(G) = { w | w  * và S * w }hoặc: L(G) = { w | w  * và w * S }**Nguyễn Phương Thái - Coltech - Compiler 2009Định nghĩa: Hai văn phạm G1 và G2 (sản sinh hoặc đoán nhận) là tương đương khi và chỉ khi L(G1) = L(G2).**Nguyễn Phương Thái - Coltech - Compiler 2009**Nguyễn Phương Thái - Coltech - Compiler 2009Cho văn phạm G = (, , P, S), ta gọi nó là văn phạm:Lớp 0, văn phạm ngữ cấu (phrase - structure) nếu sản xuất có dạng:   trong đó   V+, V*hoặc cũng có thể nói, lớp văn phạm này không bị ràng buộc gì.**Nguyễn Phương Thái - Coltech - Compiler 2009Lớp 1, văn phạm cảm ngữ cảnh (context - sensitive) nếu sản xuất có dạng:   thỏa mãn điều kiện |  |  |  | **Nguyễn Phương Thái - Coltech - Compiler 2009Lớp 2, văn phạm phi ngữ cảnh (context free - viết tắt là VPPNC) nếu sản xuất có dạng:A   trong đó A  ,  V***Nguyễn Phương Thái - Coltech - Compiler 2009Lớp 3, văn phạm chính quy (regular - viết tắt là VPCQ) nếu sản xuất có dạng: A  a, A  Ba trong đó A, B  , a   hoặc tương tự A  a, A  aB với A, B  , a  **Nguyễn Phương Thái - Coltech - Compiler 2009**Nguyễn Phương Thái - Coltech - Compiler 2009Ngôn ngữ loại 0 được đoán nhận bởi một máy Turing;Ngôn ngữ loại 1 (cảm ngữ cảnh) được đoán nhận bởi một ôtômát tuyến tính giới nội (sai khác xâu rỗng);Ngôn ngữ loại 2 (phi ngữ cảnh - viết tắt là NNPNC) đoán nhận bởi một ôtômát đẩy xuống (không đơn định);Ngôn ngữ loại 3 (chính qui - viết tắt là NNCQ) được đoán nhận bởi một ôtômát hữu hạn (sai khác xâu rỗng).**Nguyễn Phương Thái - Coltech - Compiler 2009Dạng BNF (Backus - Naur Form): thực chất chỉ là một cách biểu diễn khác của VPPNC. Quy ước:Các ký tự viết hoa biểu diễn các ký hiệu không kết thúc (nonterninal), cũng có thể thay bằng một xâu đặt trong cặp dấu hoặc một từ in nghiêng;Các ký tự viết chữ nhỏ và dấu toán học biểu diễn các ký hiệu kết thúc (terninal), cũng có thể thay bằng một xâu đặt trong cặp dấu nháy kép " " hoặc một từ in đậm;Ký hiệu  hoặc = là ký hiệu chỉ phạm trù cú pháp ở vế trái được giải thích bởi vế phải;Ký hiệu | chỉ sự lựa chọn.**Nguyễn Phương Thái - Coltech - Compiler 2009Định nghĩa toán hạng: có thể là một biến (tên), số hoặc một biểu thức ở trong cặp dấu ngoặc đơnViết dưới dạng BNF: = | | "(" ")"HoặcToánHạng  Tên | số | ( BiểuThức )**Nguyễn Phương Thái - Coltech - Compiler 2009Định nghĩa: Cây phân tích trong một VPPNC G = (, , P, S) :Mọi nút có một nhãn, là một ký hiệu trong(    {  })Nhãn của gốc là SNếu một nút có nhãn X là một nút trong thì X  Nếu nút n có nhãn là X và các nút n1, n2,..., nk là các con của nút n, theo thứ tự từ trái sang phải, và lần lượt mang các nhãn X1,X2,... Xk thì XX1X2Xk phải là một sản xuất trong P**Nguyễn Phương Thái - Coltech - Compiler 2009Ví dụ: Cho VPPNCG =({a, b}, {S, A}, P, S) P gồm: S aAS | a, A SbA|SS|baKết quả: xâu aabbaa **Nguyễn Phương Thái - Coltech - Compiler 2009Bắt đầu từ SSử dụng dẫn xuất để tạo nên dãy các kí hiệu kết thúcVới các xâu α, β và γ bất kì và một sản xuất A →βMột dẫn xuất là αAγ  αβγThay β vào vị trí của A ở vế tráiThứ tự dẫn xuất tùy ý, có thể chọn bất cứ một kí hiệu không kết thúc nào để áp dụng sản xuấtHai thứ tự dẫn xuất thường dùng: Suy dẫn trái: chọn kí hiệu bên trái nhấtSuy dẫn phải: chọn kí hiệu bên phải nhấtVí dụ: Dẫn xuất trái nhất và dẫn xuất phải nhất của cây cú pháp trên**Nguyễn Phương Thái - Coltech - Compiler 2009Ký hiệu không kết thúc A của văn phạm G = (, , P, S) gọi là đệ quy nếu: A + A với  ,   V* Nếu  =  , A gọi là đệ quy trái.Nếu  = , A gọi là đệ quy phải.Nếu    và   , A gọi là đệ quy trong. **Nguyễn Phương Thái - Coltech - Compiler 2009Một VPPNC G gọi là văn phạm nhập nhằng nếu có một xâu là kết quả của hai cây suy dẫn khác nhau trong G. Ngôn ngữ do văn phạm này sinh ra gọi là ngôn ngữ nhập nhằng.Một NNPNC L được gọi là ngôn ngữ nhập nhằng cố hữu nếu mọi VPPNC sản sinh ra L đều nhập nhằng.**Nguyễn Phương Thái - Coltech - Compiler 2009S  S + S | S * S | ( S ) | a **Nguyễn Phương Thái - Coltech - Compiler 2009Viết lại văn phạm để nó không nhập nhằng nữaSử dụng qui tắc xử lý nhập nhằng**Nguyễn Phương Thái - Coltech - Compiler 2009Định lý: Tồn tại giải thuật để xác định, với mỗi văn phạm phi ngữ cảnh bất kỳ G = (, , P, S) và một xâu bất kỳ w  *, xác định được w  L(G) hay không.Chứng minh được định lý này bằng cách đưa ra các giải thuật cài đặt trên thực tế:Thuật toán phân tích Top - Down.Thuật toán phân tích Bottom - Up.Thuật toán phân tích CYK (Coke-Younger-Kasami).Thuật toán phân tích Earley.**Nguyễn Phương Thái - Coltech - Compiler 2009Ôtômát đẩy xuống dùng để đoán nhận một xâu vào có thuộc một NN PNC cho trước hay khôngLà một cái “máy” trừu tượng**Nguyễn Phương Thái - Coltech - Compiler 2009**Nguyễn Phương Thái - Coltech - Compiler 2009Có hai cách khác nhau để thừa nhận xâu vào:Xâu vào được đọc xong và ôtômát đến được một trong các trạng thái cuối mong muốn.Xâu vào được đọc xong và ngăn xếp trở thành rỗng.Hai cách thừa nhận xâu vào như trên là tương đương với nhau**Nguyễn Phương Thái - Coltech - Compiler 2009