第2章：上下文无关语言（Context-Free Languages）

一、导读

1.1 本章学习目标

第2章从正则语言扩展到上下文无关语言。上下文无关语言由上下文无关文法（CFG）生成，由下推自动机（PDA）识别。这一章建立了程序设计语言理论的基础。

本章核心学习目标：理解 CFG、下推自动机、歧义性和泵引理。

1.2 为什么第二章如此重要

上下文无关语言是编程语言理论的基础。几乎所有编程语言的语法都可以用 CFG 描述。理解 CFG 是理解编译器、解析器和形式语言理论的关键。

1.3 核心问题引导

上下文无关文法比正则表达式强大在哪里？

下推自动机如何识别上下文无关语言？

什么是歧义性？为什么它是个问题？

如何证明一个语言不是上下文无关的？

二、核心概念详解

2.1 上下文无关文法（CFG）

CFG 是一个四元组 $(V, \Sigma, R, S)$：

• $V$：变量（非终结符）的有限集
• $\Sigma$：终结符的有限集
• $R$：产生式规则的有限集
• $S \in V$：起始变量

示例：生成回文串的 CFG
V = {S}
Σ = {0, 1}
R = {
    S → 0S0
    S → 1S1
    S → 0
    S → 1
    S → ε
}

推导：S ⇒ 0S0 ⇒ 01S10 ⇒ 01110

2.2 下推自动机（PDA）

PDA = 有限自动机 + 栈。栈提供了额外的存储能力，使 PDA 能识别 CFG 生成的语言。

PDA 识别 {0^n 1^n | n ≥ 0}：
1. 读 0 时压栈
2. 读 1 时弹栈
3. 如果栈为空且输入结束，接受

2.3 歧义性

如果一个文法对某个字符串有两棵不同的语法树，则该文法是歧义的。

歧义文法：
E → E + E | E * E | a

字符串 a + a * a 有两棵语法树：
(a + a) * a  和  a + (a * a)

解决方案：使用无歧义文法
E → E + T | T
T → T * F | F
F → a

2.4 泵引理

泵引理：如果 $L$ 是 CFL，则存在泵长度 $p$，使得任意 $s \in L$（$|s| \geq p$）可以分解为 $s = uvxyz$，满足：

$uv^ixy^iz \in L$，对所有 $i \geq 0$

$|vy| > 0$

$|vxy| \leq p$

证明：$\{a^n b^n c^n \mid n \geq 0\}$ 不是 CFL。

三、实战案例

3.1 构造 CFG

设计 CFG 生成 $\{a^i b^j \mid i \geq j \geq 0\}$：

S → aSb | A
A → aA | ε

3.2 消除歧义

为算术表达式构造无歧义文法：

E → E + T | T
T → T * F | F
F → ( E ) | id

四、本章小结

CFG 比正则表达式更强大，能描述编程语言的语法。PDA 通过栈增强了有限自动机的能力。歧义性是 CFG 的重要问题，需要通过文法设计来避免。

五、思考与练习

CFG 能描述哪些正则语言不能描述的语言？

如何将 CFG 转换为 PDA？

如何判断一个文法是否歧义？

为什么编程语言的语法需要无歧义？

如何用泵引理证明 $\{a^n b^n c^n\}$ 不是 CFL？