第3章：上下文无关文法与下推自动机

元数据卡

前置知识：第1章（形式语言概述）、第2章（DFA/NFA）
预计时间：50 分钟
核心难度：进阶
阅读模式：高度专注（建议 50 分钟+）
完成标志：能写出简单表达式的文法，能判断并消去文法的二义性，理解 PDA 如何用栈匹配括号

第三层的墙上刻着这样一个咒语："abracadabra"——但奇怪的是，它嵌套了多层括号，像 (ab(ra(ca)dab)ra)。你尝试用上一层的 DFA 去匹配，发现做不到；不管怎么画状态图，都没有办法记住"当前打开了多少个括号"。你需要一种有记忆的装置——一个栈。

你的进度

正则语言和 DFA 只能处理"平坦"的规则——字符序列的局部模式。但编程语言普遍有嵌套结构：括号、表达式、语句块、作用域——这些都嵌套。你需要从 3 型文法升级到 2 型。

你的任务

这一章让你掌握第二层计算能力的武器：上下文无关文法（CFG）和下推自动机（PDA）。你会学会如何用 CFG 描述括号匹配、算术表达式、甚至一小段语言，然后看到为什么 PDA（DFA + 一个栈）恰好可以识别这类文法。你还会见识到"二义性文法"这个实战中频繁遇到但容易被忽视的问题。

破局 · 溯源

你试着用正则表达式匹配括号——\(.*\) 只能匹配最外层的一对括号，却无法保证括号的嵌套层次正确。为了让每层括号正确配对，你需要记住"当前读到第几层了"。正则语言是无记忆的——它只关心当前字符和当前状态，不关心"过去读到过几个左括号"。

你需要一个栈。

CFG：上下文无关文法

CFG 比正则文法多了一样东西：产生式的右边可以是任意长度的终结符和非终结符混合。

算术表达式三层的层级分解：

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

这个文法描述了算术表达式的层次结构：加号最低优先级，乘号中间，括号最内层。你从 E（Expression）开始展开，最终得到一串终结符——就是合法的算术表达式。

推导示例：id + id * id

E -> E + T
  -> T + T        (因为 E -> T)
  -> F + T        (T -> F)
  -> id + T       (F -> id)
  -> id + T * F   (T -> T * F)
  -> id + F * F   (T -> F)
  -> id + id * F  (F -> id)
  -> id + id * id (F -> id)

注意推导的每一步只替换一个非终结符。这种"最左推导"是语法分析时最常用的展开方式。

PDA：下推自动机

PDA = DFA + 栈。栈提供了无限容量的记忆（但只限于 LIFO 访问）。

一个 PDA 的定义：

状态集合 Q
输入字母表 ∑
栈字母表 Γ
转移函数 δ: Q × (∑ U {ε}) × Γ -> Q × Γ* 的子集
起始状态 q0
起始栈符号 Z0
接受状态集合 F

转移函数的三元组意思是：(当前状态, 下一个输入字符或 ε, 栈顶符号) -> (新状态, 栈替换串)

以匹配 a^n b^n 的语言为例——a 和 b 的个数相等且 a 在前：

PDA 运作过程：
读到 a 时：把 a 压入栈
读到 b 时：从栈中弹出一个 a
读完所有输入后：检查栈是否为空

具体转移（简化记号）： 
δ(q0, a, Z) -> (q0, aZ)    // 第一个 a，压栈
δ(q0, a, a) -> (q0, aa)    // 更多的 a，继续压栈
δ(q0, b, a) -> (q1, ε)     // 遇到 b，弹出一个 a，进入 q1
δ(q1, b, a) -> (q1, ε)     // 继续弹出 a
δ(q1, ε, Z) -> (q2, ε)     // 栈回到起始符号，进入接受状态

这个例子很直观：栈就是你的"括号计数器"。

二义性文法

一个文法如果能对同一个句子产生多棵不同的推导树（或称语法分析树），就是二义的。

G: E -> E + E | E * E | id

对输入 id + id * id，可以有两棵分析树：
  1. 先展开加法（id + (id * id)）
  2. 先展开乘法（(id + id) * id）

一个产生了两种不同的解释方式——这在编译器中意味着你无法确定运算符优先级。

解决方法是分解优先级：把优先级信息编码在文法结构里。上面的 E -> E + T | T 三层文法就是标准解法。另一种解法是使用算符优先分析器，但不太常用。

第一层：够用——为一个小语言写 CFG

假设你要为一个迷你语言写文法，它支持变量声明、赋值和过程调用：

Program -> Statement*
Statement -> VarDecl | Assign | Call
VarDecl -> type id ;
Assign -> id = Exp ;
Call -> id ( Args ) ;
Args -> Exp ( , Exp )* | ε
Exp -> id | num | Exp + Exp | Exp * Exp | ( Exp )

这个文法虽小，但已经覆盖了大多数编程语言的关键语法结构。你写出来，就可以喂给解析器生成器（如 Yacc/Bison）来生成语法分析器。

第二层：深入——CFG 的解析复杂度

CFG 的通用解析算法（如 CYK 算法）复杂度为 O(n^3)，其中 n 是输入长度。这在实际工程中不可接受。所以编译器不解析任意 CFG——它们限定文法的子集，用更快的算法来解析：

LL 文法：自顶向下（递归下降），O(n)。适合手写。要求无左递归。
LR 文法：自底向上（Shift-Reduce），O(n)。可以处理更多文法（包括所有 LL 文法）。Yacc/Bison 就用 LR 变体 LALR(1)。

所以实际编译器中用的文法都不是"通用 CFG"，而是经过设计的、可高效解析的子集。设计语言和文法时就要考虑可解析性，而不是随意写 CFG。

常见陷阱

陷阱1：左递归导致递归下降分析器无限循环。 如果你写 A -> Aα | β，递归下降的 parseA 函数会在第一行直接调用 parseA，形成无限递归。解决方案是消除左递归：将 A -> Aα | β 改写为 A -> βA' 和 A' -> αA' | ε。

陷阱2：公因子导致 FIRST 集冲突。 A -> αβ | αγ 的两个分支都以 α 开头，递归下降解析器看一眼 α 不知道走哪条。需要提取公因子：A -> αA' 和 A' -> β | γ。

陷阱3：混淆"下推自动机"和"双栈自动机"。 PDA 只有一个栈。双栈自动机的计算能力等价于图灵机（TM），远远超过 PDA。加一个栈就让计算能力跳升到下一个层次。

通关挑战

热身（5分钟）： 写出匹配 { 和 } 嵌套括号（C 语言的花括号块）的 CFG。不必考虑花括号内部的具体语法，只写括号匹配本身。
挑战（30分钟）： 写一个包含 if-else 匹配的 CFG。注意：if-else 的"悬空 else"问题是经典二义性问题——if (c1) if (c2) s1 else s2 中，else 应该匹配哪个 if？规则是"最近的未匹配 if"。修改你的文法，让这种匹配唯一。提示：使用"强制性匹配"策略，即内部 if 必须有 else。
观察： 找一个 ANSI C 语法文件的 BNF（比如 man yacc 的 C 示例），找出其中用了哪几类 CFG 模式来解决运算符优先级的问题。

旅人笔记

上下文无关文法（CFG）描述嵌套结构，下推自动机（PDA）用栈实现识别；编译器实际使用 LL/LR 等受限子集来换取线性解析时间。

下一站预告

CFG + PDA 能描述几乎所有编程语言的语法了。但"语法"只是"程序的形式"——下一层你要面对的问题是：有没有一些问题是任何计算模型都解决不了的？