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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPT | Số trang:33

Thêm vào BST

Báo xấu

120
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ái Bộ 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
Đị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 15/11/15 7
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 15/11/15 8
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 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 | w * và w * S } Nguyễn Phương Thái - Coltech - Compiler 2009 15/11/15 12
 Đị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 15/11/15 13
Nguyễn Phương Thái - Coltech - Compiler 2009 15/11/15 14
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 15/11/15 15
 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 15/11/15 16
 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 15/11/15 17
 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 15/11/15 18
0 1 2 3 Nguyễn Phương Thái - Coltech - Compiler 2009 15/11/15 19
 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 15/11/15 20