Văn phạm và sự phân lớp văn phạm

Với mục đích sản sinh (hay đoán nhận) ngôn ngữ, văn phạm được dùng như một cách thức hiệu quả để biểu diễn ngôn ngữ.

Định nghĩa văn phạm cấu trúc (Grammar)

Theo từ điển, văn phạm, một cách không chính xác, là một tập các quy tắc về cấu tạo từ và các quy tắc về cách thức liên kết từ lại thành câu.

Để hiểu rõ hơn khái niệm này, ta xét ví dụ cây minh họa cấu trúc cú pháp của một câu đơn trong ngôn ngữ tiếng Việt "An là sinh viên giỏi" ở thí dụ 1.5 của chương 1. Xuất phát từ nút gốc theo dần đến nút lá, ta nhận thấy các từ ở những nút lá của cây như “An”, “sinh viên”, “giỏi”, … là những từ tạo thành câu được sản sinh. Ta gọi đó là các ký hiệu kết thúc bởi vì chúng không còn phát sinh thêm nút nào trên cây và câu được hoàn thành. Trái lại, các nút trong của cây như “câu đơn”, “chủ ngữ”, “danh từ”, … sẽ không có mặt trong dạng câu sản sinh, chúng chỉ giữ vai trò trung gian trong việc sinh chuỗi, dùng diễn tả cấu trúc câu. Ta gọi đó là các ký hiệu chưa kết thúc.

Quá trình sản sinh câu như trên thực chất là sự diễn tả thông qua cấu trúc cây cho một quá trình phát sinh chuỗi. Các chuỗi được phát sinh bắt đầu từ một ký hiệu chưa kết thúc đặc biệt, sau mỗi bước thay thế một ký hiệu chưa kết thúc nào đó trong chuỗi thành một chuỗi lẫn lộn gồm các ký hiệu kết thúc và chưa, cho đến khi không còn một ký hiệu chưa kết thúc nào nữa thì hoàn thành. Quá trình này chính là phương thức phát sinh chuỗi của một văn phạm, được định nghĩa hình thức như sau:

Định nghĩa : Văn phạm cấu trúc G là một hệ thống gồm bốn thành phần xác định như sau G (V, T, P, S), trong đó:

. V : tập hợp các biến (variables) hay các ký hiệu chưa kết thúc (non terminal)

. T : tập hợp các ký hiệu kết thúc (terminal) (với V size 12{ intersection } {} T = ∅)

. P : tập hữu hạn các quy tắc ngữ pháp được gọi là các luật sinh (production), mỗi luật sinh được biểu diễn dưới dạng α → β, với α, β là các chuỗi ∈ (V size 12{ union } {} T)^*.

. S ⊂ V: ký hiệu chưa kết thúc dùng làm ký hiệu bắt đầu (start)

Người ta thường dùng các chữ cái Latinh viết hoa (A, B, C, ...) để chỉ các ký hiệu trong tập biến V; các chữ cái Latinh đầu bảng viết thường (a, b, c, ...) dùng chỉ các ký hiệu kết thúc thuộc tập T. Chuỗi các ký hiệu kết thúc thường được biểu diễn bằng các chữ cái Latinh cuối bảng viết thường (x, y, z, ...).

Nhận xét : Bằng quy ước này chúng ta có thể suy ra các biến, các ký hiệu kết thúc và ký hiệu bắt đầu của văn phạm một cách xác định và duy nhất bằng cách xem xét các luật sinh. Vì vậy, để biểu diễn văn phạm, một cách đơn giản người ta chỉ cần liệt kê tập luật sinh của chúng.

Từ văn phạm, để sinh ra được các câu (từ), ta định nghĩa khái niệm “dẫn xuất” như sau :

Nếu α → β là một luật sinh thì γ size 12{γ} {}αδ ⇒ γ size 12{γ} {}βδ gọi là một dẫn xuất trực tiếp, có nghĩa là áp dụng luật sinh α → β vào chuỗi γ size 12{γ} {}αδ để sinh ra chuỗi γ size 12{γ} {}βδ.

Nếu các chuỗi α₁, α₂, ...., α_m ∈ Σ^* và α₁ ⇒ α₂, α₂ ⇒ α₃, ..., α_m-1 ⇒ α_m thì ta nói α_m có thể được dẫn ra từ α₁ thông qua chuỗi dẫn xuất α₁ ⇒ α₂, α₂ ⇒ α₃, ..., α_m-1 ⇒ α_m hay α₁ dẫn xuất (gián tiếp) ra α_m, viết tắt là α₁ ⇒^* α_m.

Ngôn ngữ của văn phạm G (V, T, P, S) là tập hợp các chuỗi ký hiệu kết thúc w ∈ T^* được sinh ra từ ký hiệu bắt đầu S của văn phạm bởi các luật sinh thuộc tập P, ký hiệu là L(G) :

L (G) = {w | w ∈ T ^* và S ⇒^* w}

Một ngôn ngữ có thể có nhiều cách đặc tả, do đó cũng có thể có nhiều văn phạm khác nhau sinh ra cùng một ngôn ngữ. Hai văn phạm sinh ra cùng một ngôn ngữ thì gọi là tương đương.

G₁ tương đương G₂ ⇔ L (G₁) = L (G₂)