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.
Kiểm tra tính rỗng, hữu hạn hoặc vô hạn của một CFL.Kiến thức cơ bản: Để tiếp thu tốt nội dung của chương này, trước hết sinh viên cần hiểu rõ cấu trúc cú pháp của một số ngôn ngữ lập trình cấp cao như Pascal, C; nắm vững lý thuyết đồ thị và cây; phương pháp chứng minh phản chứng và sự phân cấp các lớp văn phạm theo Noam Chomsky; …
Tài liệu tham khảo :[1] John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages and Computation – Addison – Wesley Publishing Company, Inc – 1979 (Chapter 4 : Context – Free Grammars).[2] V.J. Rayward-Smith – A First course in Formal Language Theory (Second Editor) – McGraw-Hill Book Company Europe – 1995 (Chapter 5: Context-Free Languages )[3] From Wikipedia, the free encyclopedia – Context-Free Grammar:http://en.wikipedia.org/wiki/Context-free_grammar
Văn phạm phi ngữ cảnh (cfg : context free grammar)
Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ như sau :
<câu đơn><chủ ngữ><vị ngữ>
<chủ ngữ><danh từ>
<vị ngữ><động từ><bổ ngữ>
<bổ ngữ><danh từ><tính từ>
<danh từ> An
<danh từ> sinh viên
<động từ> là
<tính từ> giỏi
Các từ trong dấu móc nhọn như<câu đơn>,<chủ ngữ>,<vị ngữ>, ... là các phạm trù cú pháp, cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu sinh ra qua các bước triển khai dần dần theo các quy tắc cú pháp. Đây cũng chính là dạng của các luật sinh trong văn phạm phi ngữ cảnh. Và như vậy, văn phạm phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự nhiên.
Tuy nhiên, trong khoa học máy tính, với nhu cầu biểu diễn các ngôn ngữ lập trình, văn phạm phi ngữ cảnh CFG còn được thiết kế thành một dạng tương đương gọi là văn phạm BNF (Backus - Naur Form). Đây cũng là văn phạm CFG với những thay đổi nhỏ về dạng thức và một số ký hiệu viết tắt mà các nhà khoa học máy tính thường ứng dụng trong việc diễn tả cú pháp của các ngôn ngữ lập trình cấp cao (như ALGOL, PASCAL, ... ). Trong dạng thức của văn phạm BNF, ký hiệu ::= được dùng thay cho ký hiệu . Chẳng hạn, để định nghĩa một biểu thức số học (expression) bao gồm các danh biểu (identifier) tham gia vào các phép toán +, * hoặc biểu thức con lồng trong dấu ngoặc đơn , ta viết :
