Lý thuyết ngôn ngữ hình thức và ôtômát - Chương 3

ÔTÔMAT ĐẨY XUỐNG VÀ NGÔN NGỮ PHI NGỮ CẢNHĐối với các lớp văn phạm được phân loại theo Chomsky, lớp văn phạm phi ngữ cảnh có vai trò quan trọng nhất trong việc ứng dụng để xây dựng các ngôn ngữ lập trình và chương trình dịch. Trong quá trình dịch từ chương trình nguồn ra chương trình đích, người ta sử dụng cấu trúc cú pháp của văn phạm phi ngữ cảnh để phân tích các xâu vào. Cấu trúc cú pháp của một xâu vào được xác định từ dãy các quy tắc suy từ xâu đó....
Nội dung trích xuất từ tài liệu:
Lý thuyết ngôn ngữ hình thức và ôtômát - Chương 3 CHƯƠNG III: ÔTÔMAT ĐẨY XUỐNG VÀ NGÔN NGỮ PHI NGỮ CẢNH Đối với các lớp văn phạm được phân loại theo Chomsky, lớp văn phạm phingữ cảnh có vai trò quan trọng nhất trong việc ứng dụng để xây dựng các ngôn ngữlập trình và chương trình dịch. Trong quá trình dịch từ chương trình nguồn ra chương trình đích, người ta sửdụng cấu trúc cú pháp của văn phạm phi ngữ cảnh để phân tích các xâu vào. Cấutrúc cú pháp của một xâu vào được xác định từ dãy các quy tắc suy từ xâu đó. Dựavào dãy các quy tắc đó, bộ phân tích cú pháp của chương trình dịch sẽ cho biết xâuvào đang xét có thuộc vào xâu do văn phạm phi ngữ cảnh sinh ra hay không. Nóicách khác là với xâu vào ω và một văn phạm phi ngữ cảnh G, hỏi xem ω∈L(G)hay không? Nếu có thì hãy tìm cách biểu diễn ω bằng văn phạm, tức là tìm các quytắc sinh của văn phạm G để sinh ra xâu ω.3.1. VĂN PHẠM PHI NGỮ CẢNH VÀ CÂY SUY DẪN CỦA NÓ.3.1.1. Định nghĩa: Cho văn phạm phi ngữ cảnh G=. Cây suy dẫntrong văn phạm G là một cây có gốc thoả mãn bốn yêu cầu sau: 1. Ở mỗi đỉnh được gán một nhãn. Nhãn gán ở đỉnh là các ký hiệu trong tậpΣ∪∆. Gốc của cây được gán nhãn là S. 2. Mỗi đỉnh trong được gán nhãn là một ký hiệu nào đó trong ∆. 3. Mỗi đỉnh ngoài (lá của cây) được gán nhãn là một ký hiệu trong tập Σ. 4. Nếu đỉnh m được gán nhãn là A∈∆, còn các đỉnh n1, n2, …, nk là các concủa đỉnh m theo thứ tự từ trái sang phải và được gán nhãn B1, B2, …, Bk tương ứngthì A→B1B2…Bk là một quy tắc trong P của văn phạm G. Nếu đọc tất cả nhãn ở các lá theo thứ tự từ trái sang phải, ta sẽ nhận đượcmột từ nào đó. Từ đó sẽ là một phần tử trong L(G) và được gọi là kết quả của câysuy dẫn trong G.Thí dụ 1: Cho các văn phạm phi ngữ cảnh:G1=,G2=,G3=,G4=. Cây suy dẫn của từ b+(a+c)∗b trong G1 là: 43 S S + S ∗ b A A S ) b S + ( a cCây suy dẫn của từ anbnam trong G2 là: S S a m lần a S a A a A b a A b n lần A a b A a b A a bCây suy dẫn của từ ωωR=a1a2…anan…a2a1 trong G3 là: 44 S a1 S a1 a2 S a2 S S an-1 an-1 an an Hai cây suy dẫn của từ ω=if b then for c do if b then a else a trong G3 là: S Sif b A if b A else S then then c do S c do S for for a if b A else S if b A then then a a a3.1.2. Định lý: Cho G= là văn phạm phi ngữ cảnh và ω∈Σ* {ε}. Khiđó ω∈L(G) khi và chỉ khi tồn tại một cây suy dẫn trong G có kết quả là ω.Chứng minh: Do ω≠ε nên ta có thể giả thiết rằng S→ε∉P. Bây giờ với mọi A∈∆,đặt GA=, ta có GA là văn phạm phi ngữ cảnh. Ta sẽ chứng tỏ rằngω∈L(GA) khi và chỉ khi tồn tại một cây suy dẫn trong GA có kết quả là ω. Giả sử ω là kết quả của một cây suy dẫn trong GA và n là số ký hiệu khôngkết thúc trong cây. Bằng quy nạp theo n, ta sẽ chỉ ra rằng ω∈L(GA). Nếu tổng số ký hiệu không kết thúc trong cây là 1 ...