Chuyển văn phạm phi ngữ cảnh về dạng chuẩn chomsky năm 2024

• Information
• AI Chat

Was this document helpful?

Was this document helpful?

Chương 4

OTOMAT ĐẨ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à các chương trình dịch.

Trong chương này, chúng ta sẽ nghiên cứu sâu hơn về ngôn ngữ phi ngữ cảnh

cùng với những cơ chế để sinh lớp ngôn ngữ này, đõ là các văn phạm phi ngữ cảnh và

các otomat có bộ nhớ đẩy xuống (pushdown otomata). Chương này gồm các nội dung

chủ yếu sau:

4.1. Cây suy dẫn trong văn phạm phi ngữ cảnh.

4.2. Rút gọn các văn phạm phi ngữ cảnh

4.3. Dạng chuẩn Chomsky và dạng chuẩn Greibach

4.4. Otomat đẩy xuống

• Home
• My Library
• Ask AI

Văn phạm phi ngữ cảnh

Bởi:

Huynh Tram Vo

VĂN PHẠM PHI NGỮ CẢNH

Nội dung chính :

Trong chương này, ta sẽ nghiên cứu một loại văn phạm khá quan trọng, gọi là văn phạm

phi ngữ cảnh (CFG) và lớp ngôn ngữ mà chúng mô tả - ngôn ngữ phi ngữ cảnh(CFL).

CFL, cũng như tập hợp chính quy, có nhiều ứng dụng thực tế rất quan trọng, đặc biệt

trong việc biểu diễn ngôn ngữ lập trình. Chẳng hạn, CFG dùng hữu ích để mô tả các

biểu thức số học trong các dấu ngoặc lồng nhau hay những cấu trúc khối trong ngôn ngữ

lập trình (cấu trúc khối begin-end). Sau khi định nghĩa văn phạm phi ngữ cảnh, một số

cách biến đổi văn phạm phi ngữ cảnh nhằm giản lược nó và đưa nó về một trong những

dạng chuẩn sẽ được trình bày. Cuối chương, bổ đề bơm cho ngôn ngữ CFL và một số

tính chất nhằm xác định tập ngôn ngữ này cũng sẽ được giới thiệu.

Mục tiêu cần đạt:

Cuối chương, sinh viên cần phải nắm vững:

Khái niệm CFG, xác định các thành phần của một CFG.

Nhận dạng được lớp ngôn ngữ mà một văn phạm CFG đặc tả.

Xây dựng các luật sinh cho một CFG đặc tả một lớp ngôn ngữ.

Các bước giản lược văn phạm CFG không chứa các giá trị vô ích.

Chuẩn hóa CFG về các dạng chuẩn Chomsky hoặc Greibach.

Ứng dụng bổ đề bơm cho CFL để chứng tỏ một ngôn ngữ không là ngôn ngữ phi ngữ

cảnh.

Xác định một ngôn ngữ có thuộc lớp ngôn ngữ phi ngữ cảnh hay không theo các tính

chất của CFL.

Văn phạm phi ngữ cảnh

1/12