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

文法用产生式描述语言，下推自动机（PDA）用一个栈识别语言。 下面亲手操控一台 PDA：看它如何把非终结符逐层展开成推导树、把符号压栈、再和输入串一格一格地匹配。

上下文无关文法 CFG 下推自动机 PDA 最左推导 推导树 栈操作

1公式与参数

一个上下文无关文法（Context-Free Grammar, CFG）由四元组 $G = (V, \Sigma, P, S)$ 定义。 它的核心是产生式集合 $P$，每条产生式左边必须是一个非终结符，与上下文无关：

$$G = (V,\ \Sigma,\ P,\ S), \qquad A \;\rightarrow\; \alpha \quad (A \in V,\ \alpha \in (V \cup \Sigma)^{*})$$

$V$ 是非终结符集合，$\Sigma$ 是终结符集合，$S \in V$ 是起始符号，$P$ 是产生式集合。

从起始符号出发，每一步把串中最左边的非终结符替换成某条产生式的右部，就得到一次最左推导：

$$S \;\Rightarrow\; \alpha_1 \;\Rightarrow\; \alpha_2 \;\Rightarrow\; \cdots \;\Rightarrow\; w, \qquad w \in \Sigma^{*}$$

若存在这样的推导序列，就说串 $w$ 属于该文法生成的语言 $L(G)$。

与之等价的下推自动机（PDA）把推导过程"倒过来"执行： 它用栈保存待展开的符号，栈顶是非终结符就展开，栈顶是终结符就与输入匹配并弹出。

$$\delta:\ Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \;\longrightarrow\; \mathcal{P}\big(Q \times \Gamma^{*}\big)$$

本页演示的是最简形式：状态集只有一个"展开/匹配"循环，转移完全由栈顶符号决定。

符号 数学含义 通俗解释
V 非终结符集合 还要继续展开的"占位符"，例如 S、E、T。它们在栈中显示为蓝色。
Σ 终结符集合 最终出现在输入串里的"实际字符"，例如 a、b、(、+。它们在栈中显示为灰色。
P 产生式集合 改写规则，形如 S → aSb。读作"把 S 换成 a S b"。
S 起始符号 一切推导的起点。PDA 启动时，栈里只放这一个符号。
Γ 栈字母表 栈里允许出现的符号集合，这里是 $V \cup \Sigma$。
w 输入串 你希望被识别的那串字符，例如 aabb。
ε 空串 / 空动作 产生式右部为 ε 表示"什么都不生成"；匹配时表示不消耗输入。

2交互模拟：最左推导与栈操作

左侧选择文法、输入串并调节参数，右侧会实时显示栈的压入/弹出、 输入串的匹配进度和推导树的生长过程。 每一步只有两种可能：栈顶是非终结符 → 展开；栈顶是终结符 → 与输入匹配。

推导步数上限。设太小会在还没推完时就停下并报告"未完成"。
数值越小，每一步的栈变化看得越清楚。
已执行步数
0
栈深度
1
已读输入
0 / 4
模拟进度
0.00%
待运行
栈 Stack
↑ 栈顶
输入串 Input
灰色删除线 = 已匹配并消费；蓝色高亮 = 当前待匹配字符
等待开始…
推导树 Parse Tree
栈深度变化

3深入理解

标准介绍

上下文无关文法（CFG）是乔姆斯基层级中的2 型文法，其产生式左部恒为单个非终结符。 它生成的语言称为上下文无关语言（CFL）。 与之等价的识别装置是下推自动机（PDA）——一个带"后进先出"栈的非确定有限自动机。 这一对等价关系是可计算理论中最漂亮的对应之一： 文法负责"生成"，自动机负责"识别"，两者描述的是同一类语言。

通俗介绍

把文法想成一套搭积木的规则。比如 S → a S b 是说： 想搭一个 S，就拿一块 a 放在左边、一块 b 放在右边， 中间再塞一个 S。一直套用规则，最后把所有 S 都换成 ε，就得到一串 aabb 这样的字符。 而 PDA 是反过来玩的：它手上有一个便签本（栈），先写下"S"，看到栈顶是 S 就照着规则把它拆开、把子零件叠上去； 看到栈顶是 a 就翻到输入串的下一格对一对，对上了就丢掉。便签本清空、输入串也读完，就说明这串字符合法。

解决了什么问题

  • 给出了自然语言与编程语言语法的严格数学描述：BNF 范式就是 CFG 的直接工业应用。
  • 明确了有限自动机能力的边界：正则语言搞不定括号配对、aⁿbⁿ 这类"需要计数"的结构，CFG 可以。
  • 提供了可机械执行的解析算法框架：递归下降、LL(1)、LR(1) 全部建立在 CFG 之上。
  • 把"生成"和"识别"统一起来，使语法分析与自动机理论可以互相翻译。

为什么重要

  • 它是编译原理的骨架：从词法分析（正则）到语法分析（CFG），构成了现代编译器的前半程。
  • 它精确地刻画了"递归嵌套结构"这一类计算能力，而这是编程语言表达力的关键来源。
  • 它揭示了栈这种数据结构的计算本质：一个 LIFO 栈恰好把有限自动机提升到上下文无关的层次。
  • 它是乔姆斯基谱系的中间一环：正则 ⊂ 上下文无关 ⊂ 上下文有关 ⊂ 递归可枚举，层层递进。

应用场景

  • 编译器前端：用 Yacc / ANTLR / Bison 描述语言语法，自动生成语法分析器。
  • JSON / XML / HTML 解析：嵌套结构天然属于上下文无关语言。
  • 表达式求值与括号匹配：计算器、公式编辑器、模板引擎的核心逻辑。
  • 编程语言设计：通过文法定义语法的二义性、结合性与优先级。
  • 自然语言处理：句法分析树（parse tree）的历史源头之一。
  • 协议与格式校验：配置文件、报文格式的合法性验证。

缺陷与局限

  • 无法描述上下文相关约束：比如"变量必须先声明后使用""类型必须匹配"，CFG 无能为力。
  • 歧义性不可判定：判断任意 CFG 是否有二义性，本身就是一个不可判定问题。
  • 部分子类才可高效解析：一般 CFG 的解析是 $O(n^3)$（CYK 算法），只有 LL(k)、LR(k) 等受限子类才线性可解。
  • 左递归需要改写：预测分析（如本页演示）要求文法不是左递归，需要手工改写为等价格式。
  • 栈的容量是理想的：PDA 假设栈可以无限增长，物理机器的栈深度始终有限。

动手建议

试试把文法切到 ① aⁿbⁿ 匹配，输入 aaabbb 和 aabbb： 前者会一路展开到栈空并被接受，后者会在某个时刻栈顶是 b 却读到了输入结束，于是被拒绝。 再切到 ④ 算术表达式，输入 (i+i)*i 并放慢速度： 你会看到 E → T E1 → F T1 E1 → ( E ) T1 E1 这一串最左推导如何在栈上一层层铺开， 右边的推导树也同步长出新分支。栈的内容 = 推导树的"待办清单"，这就是 CFG 与 PDA 等价关系的直观含义。