上下文无关文法与下推自动机

比正则高一级的语言类：上下文无关（CFL）——大多数编程语法的层次。本章讲 CFG 的推导与语法树、歧义性、Chomsky 范式、下推自动机与 CFL 的泵引理，以及 LR 解析器的位置（→ 语法与语义）。

CFG 与语法树

上下文无关文法：产生式左端是单个非终结符（ $A \to \alpha$ ）——"一个符号展开成什么"，与上下文无关（这正是名字的来源）：

\begin{aligned} S &\to (S) \mid SS \mid \epsilon &\text{(配对括号)} \\ E &\to E + T \mid T, \quad T \to T \times F \mid F, \quad F \to (E) \mid \text{id} &\text{(表达式)} \end{aligned}

推导（从 S 出发反复应用产生式）对应语法树（parse tree）——叶子连起来是串。语法分析 = 给定串，重建语法树（或证明不存在）。

歧义文法：同一串有两个不同的语法树——语义随之不明。经典例子悬空 else：

S \to \text{if } E \text{ then } S \text{ else } S \mid \text{if } E \text{ then } S \mid \cdots

if a then if b then x else y 中 else 归属哪个 if？两个语法树都合法。歧义文法是语言设计的常见问题：解决靠改文法（无歧义版本，配对结构化）或语义约定（"最近 if"）。注意：有些语言天生无歧义文法不存在（固有歧义），但多数实用语言可以消除。

给 NFA 加一个栈：转移可以读写栈顶。PDA 与 CFG 等价（识别同样的语言）：

Chomsky 范式（CNF）：产生式只允许 $A \to BC$ 与 $A \to a$ ——任何 CFG 都能转换（可能引入新符号）。CNF 的回报：CYK 算法用动态规划判定成员资格与重建语法树：

dp[i][j][A] = \bigvee_{k} dp[i][k][B] \land dp[k+1][j][C] \quad (A \to BC)

$O(n^3 |G|)$ ——CYK 算法 O(n³) 判定成员资格，是 CFL 解析的理论基线（工程解析器更快，见下）。

通用 CFL 解析（CYK、Earley）太慢。LR(k) 解析器处理确定性 CFL（每一步看 k 个前瞻符号就能定）：

自底向上：从叶子向根归约，用栈 + 状态机（LALR 表）；
线性时间 $O(n)$ ；LR 解析器处理确定性 CFL——yacc/bison 的 LALR(1) 与多数编译器（递归下降）处理的都是这个类；
CFG 的实用子集：编程语言的语法几乎都在确定性 CFL 里——上下文无关够用（表达嵌套），确定性够快（线性）。

而语义不是上下文无关：类型检查、变量声明先于使用——这些是上下文相关的约束，由语义分析（符号表）处理，不塞进文法（→ 语法与语义）。