Bài giảng Chương trình dịch: Bài giảng 3 - Nguyễn Phương Thái

Bài giảng 3 trình bày về văn phạm phi ngữ cảnh trong chương trình dịch. Những nội dung chính sẽ được trình bày trong bài giảng gồm có: 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.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình dịch: Bài giảng 3 - Nguyễn Phương Thái Nguyễn Phương TháiBộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/ 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 15/11/15 2 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 15/11/15 3 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 15/11/15 4 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 15/11/15 5  Ví dụ phân tích văn phạm gàû m boì vaìng 15/11/15 Nguyễn Phương Thái - Coltech - coí non 6 Compiler 2009Địnhnghĩ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 đầ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 15/11/15 7Ví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 15/11/15 8Cácquiướ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 15/11/15 9 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 15/11/15 10 Đị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 15/11/15 11 Đị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 ...