4.4 CNF、CFG 与 PDA
上下文无关文法是一种生成模型：它描述开始符号如何展开成合法句子。下推自动机（pushdown automaton，PDA）是一种识别模型：它一边读取输入，一边使用一个可无限增长的栈。两者之间有一个核心定理：
上下文无关语言，恰好等于非确定性下推自动机能够识别的语言。这不代表生产级语法分析器（parser）就是一个教科书 PDA，而是精确说明了：为什么栈足以处理嵌套和匹配结构，而有限自动机不够。
乔姆斯基范式（Chomsky normal form，CNF）是另一种形式化工具。它限制 CFG 产生式的形状，让 CYK 这类算法可以系统地处理子串。CNF 主要服务于证明和通用算法，并不是你通常会直接维护或直接交给用户的源语言文法风格。
乔姆斯基范式
当每条产生式都满足以下之一时，文法处于 CNF：
A -> B C
A -> a其中 A、B、C 都是非终结符，a 是终结符。如果语言包含空串，通常允许开始符号在受控条件下产生 ε。
CNF 不允许：
- 长右部，例如
A -> B C D。
- 混合右部，例如
A -> a B。
- unit production（单元产生式），例如
A -> B。
- 任意位置的空产生式（epsilon production）。
为什么要接受这种看似不自然的限制？因为它使每个非终结符要么产生一个终结符，要么产生恰好两个较小的非终结符跨度。动态规划语法分析器可以据此填表：
A 能否推导 token i 到 token j？
枚举中间切分点 k。
若 A -> B C，那么 B 是否推导 i..k，且 C 是否推导 k+1..j？这种规则形状给 CYK 提供了清晰的复杂度边界，常见写法是 O(n^3 * |G|)。
典型转换流程
具体步骤会有变体，但常见流程是：
1. 如果旧开始符号出现在右部，或构造需要保护开始符号，则增加新的开始符号。
2. 消除空产生式，同时在语言确实包含空串时保留受控的开始符号例外。
3. 消除单元产生式，例如 A -> B。
4. 删除无用符号，包括不可达符号和不能推出终结符串的符号。
5. 用辅助非终结符替换长右部中混入的终结符。
6. 把超过两个符号的右部拆成二元产生式。
例如：
S -> A B C | b
A -> a A | ε
B -> C
C -> b可以变为：
S -> A X | B C | b
X -> B C
A -> X_a A | a
B -> b
C -> b
X_a -> aX、X_a 都不是用户可见的语言特性，而是变换过程中引入的记账辅助符号。
PDA：有限控制器加一个栈
PDA 在有限自动机基础上增加栈。概念上，一次转移可以：
- 查看下一个输入符号，也可以选择空转移（epsilon move）。
- 查看栈顶。
- 切换状态。
- 压入零个或多个栈符号。
- 弹出一个栈符号。
对于平衡括号，PDA 可以遵循：
读到 "("：push "("
读到 ")"：pop "("
读到 EOF：仅当栈只剩底标记时接受栈深度代表目前还有多少左括号没有匹配。这个数量可以无限增长，正是有限自动机无法保存的记忆。
对于：
{ a^n b^n | n >= 0 }PDA 可以对每个 a 压入一个标记，再对每个 b 弹出一个标记。只有输入从 a 正确转到 b，并且刚好在输入结束时清空栈，才接受。
但一个栈仍无法表达一切。例如：
{ a^n b^n c^n | n >= 0 }通常不属于上下文无关语言，因为它需要以 CFG/PDA 无法做到的方式比较三个无界计数。这个边界有助于区分哪些约束适合放在语法中，哪些应该交给语义分析，哪些甚至需要更强的计算模型。
CFG 与 PDA 如何互相对应
等价定理背后有很直观的构造思路。
从 CFG 构造 PDA：
1. 先把开始符号压入栈。
2. 当栈顶是非终结符时，非确定地选择其一条产生式，并把右部按逆序压栈。
3. 当栈顶是终结符且与下一个输入词法单元（token）匹配时，弹栈并消费输入。
4. 当输入读完且栈回到底标记时接受。
其中的非确定性表示：在尚未读到足够输入前，自动机可能要猜测使用哪条产生式。实际语法分析器通过向前看、分析表、语法分析器状态或广义分析算法，把这种选择变得可控。
反过来，也能把一个 PDA 编码为 CFG：非终结符描述状态与栈之间的关系。构造更技术化，但它确立了 CFG 与非确定性 PDA 识别能力相同。
确定性 PDA 与非确定性 PDA
每个确定性 PDA 识别的都是上下文无关语言，但并非每个上下文无关语言都有确定性 PDA。这也是语法分析器设计有趣的原因。为了让 LL、LR 等确定性算法能稳定决策，实际编程语言常把语法限制或设计成特定形状。一份文法在理论上是 CFG，不代表它对任意一种确定性语法分析器都容易处理。
为正确任务使用正确形式工具
CNF 的价值是单词法单元跨度是基本情形，较长跨度总能分成两个更小跨度。对 id + id，CYK 风格算法逐一尝试切分点，再问两段能否由对应非终结符推出。这适合证明/动态规划，不适合让人维护满是辅助名字的源文法。
PDA 栈记录的是嵌套义务：它能记住最近未匹配分隔符，却不能普遍比较 a^n b^n c^n 这类三个独立无界区域。这个边界帮助判断规则应留在语法还是放到后续语义分析。