0型文法

0型文法是一个四元组$(V_N, V_T, R, S)$(各部分分别表示非终结符号、终结符号、规则和起始符号)，且满足：

1) $V_N$和$V_T$是符号的有限集

2) $V_N \cap V_T = \oslash$

3) R是(P, Q)的集合，且

    a) $P \in (V_N \cup V_T)^+$  (这里表示不严谨，P至少包含一个非终结符号)

    b) $Q \in (V_N \cup V_T)^*$

4) $S \in V_N$

0型文法相当于图灵机，都是递归可枚举的。

1型文法

分为两种

1) 单调(monotonic)1型文法： 不存在任何一个左侧符号比右侧符号多

2) 上下文相关(context-sensitive)1型文法: 所有的规则都是上下文相关的

2型文法

2型文法是上下文无关(context-free)文法： 所有规则左侧只有一个非终结符号。

左递归: $A \to Aa$

右递归: $A \to aA$

自嵌入(self-embedding): $A \to \alpha A\beta$ 。用于处理嵌套(nesting)，$\alpha$在进入一层嵌套时产生，$\beta$在退出一层嵌套时产生。

上下文无关文法的规则只有一种可能会是非单调的(non-monotonic)：右侧为空。这种规则被称为$\epsilon-rule$。没有$\epsilon-rule$的文法被称为$\epsilon-free$文法。

3型文法

3型文法是正则(regular)文法/有限状态(finite-state)文法，即：规则右侧只能有一个非终结符号，且必须在最后。(right-regular grammars)

正则文法是非嵌套文法(non-nesting grammars)，无法处理嵌套

4型文法

4型文法的规则右侧不得有非终结符号，所以又称为有限选择(finite-choice)文法。它不在乔姆斯基谱系中，但它也是有用的，可以用来处理编程语言的keywords之类的东西。