語法

定義形式語言的語法是一個四元組 ，其中 是非終結符的有限集合， 是終結符的有限集合， 是產生式的有限集合，而 是 的一個元素。

終結符集合 是 的字母表。非終結符是表示語言構造的符號。集合 和 不應相交。 被稱為起始符號。產生式是以下形式的規則：，其中 和 都是終結符和非終結符的字串， 至少包含一個非終結符。

語法 的句型由以下規則定義： 是一個句型；如果 是一個句型，且產生式 屬於 ，則 也是一個句型。

是由完全由終結符組成的句型構成的所有字串的集合。對於由語法定義的語言，識別給定的字串（表示式）是否屬於該語言通常是一項非平凡的任務。所有由語法定義的語言都是遞迴可列舉集合。

1. 如果語法 的所有產生式都具有 或 的形式，其中 且 是終結符的字串，則稱該語法 為右線性語法。

2. 如果語法 的所有產生式都具有 的形式，其中 且 是終結符和非終結符的字串，則稱該語法 為上下文無關語法。

3. 如果語法 的所有產生式都具有 的形式，其中 和 都是終結符和非終結符的字串，且 的長度不大於 的長度，則稱該語法 為上下文相關語法。

4. 如果語法 不屬於類別 1 到 3，則稱其為無限制語法。

這種語法層次結構是由 N. 喬姆斯基引入的。由每個類別的語法定義的語言集合是前一個類別的真超集。由類別 1 到 3 的語法定義的語言是遞迴集合。一個語言可以透過類別 1 的語法定義，當且僅當它可以透過正則表示式定義時。