tailieunhanh - 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 đó | 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 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 đó. Dựa và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âu và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ói cách khác là với xâu vào 0 và một văn phạm phi ngữ cảnh G hỏi xem 0eL G hay không Nếu có thì hãy tìm cách biểu diễn 0 bằng văn phạm tức là tìm các quy tắc sinh của văn phạm G để sinh ra xâu 0. . VĂN PHẠM PHI NGỮ CẢNH VÀ CÂY SUY DẪN CỦA NÓ. . Định nghĩa Cho văn phạm phi ngữ cảnh G A a S P . Cây suy dẫn trong 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 XoA. 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 A. 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 s. 4. Nếu đỉnh m được gán nhãn là AeA còn các đỉnh n1 n2 . nk là các con của đỉnh m theo thứ tự từ trái sang phải và được gán nhãn B1 B2 . Bk tương ứng thì 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 được mộ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ây suy dẫn trong G. Thí dụ 1 Cho các văn phạm phi ngữ cảnh Gi a b c S A S S S S A A a b c A S S a b c G2 a b S A S S Sa Aa A aAb ab G2 S ai a2 . an S S S aSa S aa asS G4 if then else for do a b c S A S S if b then A if b then A else S S a A for c do S a . Cây suy dẫn của từ b a c b trong G1 là 43 S S b S J a 0 b c a J Cây suy dẫn của từ anbnam trong G2 là n lần Cây suy dẫn của từ a1a2. anan. .