tailieunhanh - Giáo trình Ôtômát và ngôn ngữ hình thức: Phần 2
Mời các bạn tham khảo tiếp phần 2 sách gồm 3 chương: Chương 5,6 nghiên cứu các khái niệm cơ sở, mối quan hệ giữa các lớp ngôn ngữ và các tính chất rất quan trọng của ngôn ngữ phi ngữ cảnh, ôtômát đẩy xuống. Lớp các ngôn ngữ phi ngữ cảnh loại LR(k) có nhiều ứng dụng trong chương trình dịch, chương trình phân tích cú pháp được trình bày trong chương 7. Giáo trình này giới thiệu một cách hệ thống những khái niệm cơ bản và các tính chất chung của ôtômát và ngôn ngữ hình thức. | Ôtômát và ngôn ngữ hình thức CHƢƠNG V Các ngôn ngữ phi ngữ cảnh Nội dung của chương năm đề cập đến: Cây dẫn xuất và các phương pháp xác định văn phạm phi ngữ cảnh, Tính nhập nhằng và quá trình giản lược văn phạm phi ngữ cảnh, Các dạng chuẩn: dạng chuẩn Chomsky và dạng chuẩn Greibach, Bổ đề Bơm (điều kiện cần) cho các ngôn ngữ phi ngữ cảnh và một số thuật toán quyết định được. Các ngôn ngữ phi ngữ cảnh và các cây dẫn xuất Ngôn ngữ phi ngữ cảnh thường được sử dụng trong thiết kế các bộ chương trình phân tích cú pháp. Nó cũng được sử dụng để mô tả các khối cấu trúc trong các ngôn ngữ lập trình. Trong phần này chúng ta sử dụng cây dẫn xuất để biểu diễn cho ngôn ngữ phi ngữ cảnh. Trước tiên chúng ta nhắc lại định nghĩa của văn phạm phi ngữ cảnh. G là phi ngữ cảnh nếu mọi qui tắc dẫn xuất đều có dạng: A , trong đó A VN và (VN )* Ví dụ Xây dựng một văn phạm phi ngữ cảnh G để sinh ra tất cả các số nguyên. Giải. Giả sử G = (VN, , P, S), trong đó VN = {S, , , } = {0, 1, 2, . . ., 9, +, - } P bao gồm các qui tắc: S , + | -, | 0 | 1 | 2 | . . .| 9. Dễ dàng kiểm chứng được là L(G) là tập tất cả các số nguyên. Mỗi dẫn xuất của một văn phạm có thể biểu diễn dưới dạng một cây, dc gọi là cây dẫn xuất. Định nghĩa Cây dẫn xuất (còn gọi là cây phân tích cú pháp) cho văn phạm phi ngữ cảnh G = (VN, , P, S) là cây thoả mãn các tính chất sau: (i) Các đỉnh đều được gán nhãn là biến, ký tự kết thúc hoặc , - 109 - Ôtômát và ngôn ngữ hình thức (ii) Gốc có nhãn S, (iii) Nhãn các đỉnh bên trong (không phải là lá) là các biến, (iv) Nếu các đỉnh n1, n2, ., nk được viết với các nhãn X1, X2, ., Xk là các con của đỉnh n có nhãn A thì trong P có tương ứng qui tắc A X1X2 .Xk (v) Đỉnh n là lá nếu nhãn của nó là a hoặc là ký hiệu rỗng . Ví dụ Cho trước văn phạm G = ({S, A}, {a, b}, P, S), trong đó P gồm: S aAS | a | SS, A SbA | ba Cây dẫn xuất của G để sinh ra xâu w = aabaa sẽ .
đang nạp các trang xem trước
