四种文法类型

文法分类

文法类型分为0型、1型、2型、3型，他们都由四部分组成，即 ，其中 为终结符（Terminal）集合， 为非终结符（Nonterminal）集合， 为文法的开始符号， 为产生式集合。这四种文法对产生式的限制不同。

0型

• 短语文法、图灵机

• 产生式为 ，其中 且至少含有一个 非终结符 ， 。（集合右上角加星号表示该集合的闭包）

1型

• 上下文有关文法、线性界限自动机

• 产生式为 ，其中 ，仅 例外。（ 表示空字）。

2型

• 上下文无关文法、非确定下推自动机

• 产生式为 ，其中 ， 。

• 采用栈式工作结构

3型

• 正规文法、有限自动机

• 产生式为 或 ，其中 ， 。

• 产生式右边要么没有非终结符，要么非终结符在最右边，称为右线性文法。

• 类似地，也有左线性文法，这两种文法是等价的。

四种文法的比较

从0型到3型，描述能力越来越低。

• 不能由正规文法产生，但可由上下文无关文法产生：

  $$S\rightarrow aSb|ab$$

• 不能由上下文无关文法产生，但可由上下文有关文法产生：

  $$S\rightarrow aSBC|aBC$$

$$CB\rightarrow BC$$ $$aB\rightarrow ab$$ $$bB\rightarrow bb$$ $$bC\rightarrow bc$$ $$cC\rightarrow cc$$

可以看到，这种文法的处理方法与上下文有关。

程序设计语言的文法

程序设计语言不是上下文无关语言，甚至不是上下文有关语言，只能由0型文法产生。

但是对于编译程序，仍然使用 上下文无关文法 来描述其语言结构，不能用上下文无关文法描述的部分，一般放在语义分析阶段进行，而不是在语法分析阶段。