二义性与Chomsky分类

二义性

若文法 $G$ 中存在某个句子对应两棵不同的语法树（或有两个不同的最左/最右推导），则称 $G$ 是二义性的。

二义性示例

$E\to I\mid E+E\mid E\ast E\mid (E)$ $I\to a\mid b$

句子 $I\ast I+I$ 存在两棵不同的语法树：

1. $((I)\ast (I+I))$：先乘后加
2. $((I\ast I)+I)$：先加后乘

重点 二义性概念及 $I\ast I+I$ 示例

运算符优先级消除二义性

二义性消除不存在形式化方法，依赖人工理解和设计。

通过引入优先级和结合性消除：

$E\to E+T\mid T$ $T\to T\ast F\mid F$ $F\to (E)\mid I$

• 优先级：* 高于 +
• 结合性：左结合（递归在左边）

Chomsky 文法分类

0 型文法（短语结构文法）

产生式形如 $\alpha \to \beta$，$\alpha \in (V_N\cup V_T{)}^{+}$ 且至少含一个非终结符。

对应的自动机：图灵机

1 型文法（上下文有关文法）

产生式形如 $\alpha A\beta \to \alpha \gamma \beta$，$|\alpha A\beta |\le |\alpha \gamma \beta |$（$\gamma \ne \epsilon$，$S\to \epsilon$ 除外）。

对应的自动机：线性界限自动机

2 型文法（上下文无关文法）

产生式形如 $A\to \beta$，$A\in V_N$，$\beta \in V^{\ast }$。

对应的自动机：下推自动机

3 型文法（正规文法）

产生式形如 $A\to aB$ 或 $A\to a$（右线性），或 $A\to Ba$（左线性）。

对应的自动机：有限自动机

类型	名称	产生式约束	对应自动机
0 型	短语结构文法	无限制	图灵机
1 型	上下文有关	$\alpha A\beta \to \alpha \gamma \beta$	线性界限自动机
2 型	上下文无关	$A\to \beta$	下推自动机
3 型	正规文法	$A\to aB\mid a$	有限自动机

$3\subset 2\subset 1\subset 0$（包含关系）

Chomsky 语言分类

每种文法定义一类语言，语言类型与文法类型一一对应：

语言类型	名称	由何种文法产生	对应自动机	封闭性
0 型语言	递归可枚举语言	0 型文法（短语结构文法）	图灵机	对并、连接、闭包封闭
1 型语言	上下文有关语言	1 型文法（上下文有关文法）	线性界限自动机	对并、交、连接、闭包封闭
2 型语言	上下文无关语言	2 型文法（上下文无关文法）	下推自动机	对并、连接、闭包封闭，对交不封闭
3 型语言	正规语言	3 型文法（正规文法）	有限自动机	对并、交、补、连接、闭包封闭

语言类型的包含关系：$3\subset 2\subset 1\subset 0$

• 正规语言（3 型）⊂ 上下文无关语言（2 型）
• $a^n{b}^n$ 是上下文无关语言（2 型），但不是正规语言（3 型）
• 上下文有关语言（1 型）可描述 $a^n{b}^n{c}^n$ 等需多个等长序列匹配的语言

重点 语言类型与文法类型对应关系、各类型包含关系和封闭性质。

文法 $\leftrightarrow$ 语言设计

重点 根据语言设计文法是考试常考题型。

示例：

• $L=\{a^n{b}^n\mid n\ge 1\}$：$S\to aSb\mid ab$（2 型，非 3 型）
• $L=\{\omega \in \{0,1{\}}^{\ast }\mid \text{0 和 1 数量相等}\}$：$S\to 0S1\mid 1S0\mid SS\mid \epsilon$（2 型）
• 奇整数文法设计

重点 各类型对应自动机需记忆，0 型→3 型递进关系。