Bài giảng Ngôn ngữ hình thức và Ôtômát: Chương 4 - Văn phạm và ngôn ngữ phi ngữ cảnh

Văn phạm phi ngữ cảnh và ngôn ngữ phi ngữ cảnh đóng vai trò nền tảng trong lĩnh vực khoa học máy tính lý thuyết, đặc biệt là trong thiết kế trình biên dịch và xử lý ngôn ngữ tự nhiên. Sự hiểu biết sâu sắc về các khái niệm này là thiết yếu để phân tích và mô tả cấu trúc cú pháp của các ngôn ngữ lập trình cũng như các hệ thống ngôn ngữ hình thức khác. Chương này cung cấp một cái nhìn tổng quan về định nghĩa, các thành phần cơ bản và cơ chế hoạt động của văn phạm phi ngữ cảnh, đồng thời khám phá các thách thức phát sinh từ sự nhập nhằng trong ngữ pháp và cách giải quyết chúng.

Sinh viên ngành Khoa học Máy tính, Kỹ thuật Phần mềm, hoặc các chuyên ngành liên quan đang nghiên cứu về lý thuyết ngôn ngữ hình thức, lý thuyết biên dịch và phân tích cú pháp.

Tài liệu này đi sâu vào "Văn phạm phi ngữ cảnh" (Context-Free Grammars – CFGs) và "Ngôn ngữ phi ngữ cảnh" (Context-Free Languages – CFLs), những khái niệm cốt lõi trong lý thuyết ngôn ngữ hình thức. Chương trình bày định nghĩa một văn phạm phi ngữ cảnh G dưới dạng một bộ bốn (Σ, Δ, s, p), nơi Σ là tập hợp các "ký hiệu kết thúc", Δ là các "ký hiệu chưa kết thúc", s là ký hiệu bắt đầu, và p là tập hợp các "luật sản xuất". Các cơ chế suy dẫn như suy dẫn trái và suy dẫn phải được minh họa, dẫn đến việc xây dựng "cây suy dẫn" – một cấu trúc cây trực quan mô tả quá trình suy dẫn các xâu. Một khía cạnh quan trọng khác được đề cập là "sự nhập nhằng trong văn phạm phi ngữ cảnh", xảy ra khi một xâu có thể được sinh ra bởi nhiều hơn một cây suy dẫn khác nhau. Tài liệu giới thiệu các phương pháp "khử sự nhập nhằng" bằng cách áp dụng luật ưu tiên và kỹ thuật đặt thừa số chung, giúp đảm bảo tính nhất quán trong phân tích cú pháp. Cuối cùng, "ngôn ngữ phi ngữ cảnh" được định nghĩa là tập hợp tất cả các xâu được sinh ra từ một văn phạm phi ngữ cảnh nhất định. Những kiến thức này là cơ sở không thể thiếu cho việc thiết kế trình biên dịch, phân tích cú pháp và nghiên cứu cấu trúc ngôn ngữ.