语法

定义形式语言的语法是一个四元组 ，其中 是非终结符的有限集合， 是终结符的有限集合， 是产生式的有限集合，而 是 的一个元素。

终结符集合 是 的字母表。非终结符是表示语言构造的符号。集合 和 不应相交。 被称为起始符号。产生式是以下形式的规则：，其中 和 都是终结符和非终结符的字符串， 至少包含一个非终结符。

语法 的句型由以下规则定义： 是一个句型；如果 是一个句型，且产生式 属于 ，则 也是一个句型。

是由完全由终结符组成的句型构成的所有字符串的集合。对于由语法定义的语言，识别给定的字符串（表达式）是否属于该语言通常是一项非平凡的任务。所有由语法定义的语言都是递归可枚举集合。

1. 如果语法 的所有产生式都具有 或 的形式，其中 且 是终结符的字符串，则称该语法 为右线性语法。

2. 如果语法 的所有产生式都具有 的形式，其中 且 是终结符和非终结符的字符串，则称该语法 为上下文无关语法。

3. 如果语法 的所有产生式都具有 的形式，其中 和 都是终结符和非终结符的字符串，且 的长度不大于 的长度，则称该语法 为上下文相关语法。

4. 如果语法 不属于类别 1 到 3，则称其为无限制语法。

这种语法层次结构是由 N. 乔姆斯基引入的。由每个类别的语法定义的语言集合是前一个类别的真超集。由类别 1 到 3 的语法定义的语言是递归集合。一个语言可以通过类别 1 的语法定义，当且仅当它可以通过正则表达式定义时。