Bài giảng Chương trình dịch - Văn phạm phi ngữ cảnh

Nguyễn Phương Thái Bộ môn Khoa học Máy tính  Cú pháp Là khuôn dạng hay cấu trúc của chương trình Không liên quan đến ý nghĩa chương trình Được mô tả bằng văn phạm phi ngữ cảnh Tại sao chúng ta sử dụng văn phạm phi ngữ cảnh (VPPNC) cho phân tích cú pháp Cho phép mô tả rõ ràng và dễ hiểu cú pháp một ngôn ngữ lập trình Dễ sửa đổi và mở rộng ngôn ngữ lập trình Dễ tạo ra các bộ parser Cho phép dịch dựa vào cú pháp * * Nguyễn Phương Thái - Coltech - Compiler 2009 Văn phạm Phân loại văn phạm của Chomsky Câ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 2009 Mộ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 2009 Thường dùng: văn phạm Là 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 2009 Ví dụ phân tích văn phạm * * Nguyễn Phương Thái - Coltech - Compiler 2009 Định nghĩa Mộ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 đầu P 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 2009 Ví 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 2009 Cá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 2009 V = (  )* 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 k Xâ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 2009 Cho 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 2009 Lớ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 2009 Lớ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 2009 Lớ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 2009 Ngô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 2009 Dạ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 đơn Viết dưới dạng BNF: = | | "(" ")" Hoặc Toá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à S Nế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X1X2…Xk phải là một sản xuất trong P * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ: Cho VPPNCG =({a, b}, {S, A}, P, S) P gồm: S aAS | a, A SbA|SS|ba Kết quả: xâu aabbaa * * Nguyễn Phương Thái - Coltech - Compiler 2009 Bắt đầu từ S Sử dụng dẫn xuất để tạo nên dãy các kí hiệu kết thúc Vớ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ái Thứ 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ất Hai 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ất Suy dẫn phải: chọn kí hiệu bên phải nhất Ví 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 2009 Ký 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 2009 Mộ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 2009 S  S + S | S * S | ( S ) | a * * Nguyễn Phương Thái - Coltech - Compiler 2009 Viết lại văn phạm để nó không nhập nhằng nữa Sử 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ông Là 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 2009 Có 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