上下文无关文法CFG原理

可视化演示

上下文无关文法是语法分析的理论基础，通过产生式规则定义语言结构。本文详解CFG的四元组形式化定义、最左推导与最... 切换模式查看不同维度。

文法核心概念

想象你刚被乐高工厂录用为拼装员，工位前是一堆亮闪闪的基础砖块：红色 2×4 板、蓝色长轴、白色面板。这些砖块在车间里被称为“终端件”，因为任何工序都无法再拆分它们——在编译原理里，它们就叫终结符（Terminal）。而墙上贴着的“车身组件”“引擎组件”则不是实物，它们是工人们拼装过程中的半成品状态，最终都要被拆解成砖块——这就是非终结符（Nonterminal）。

把目光从车间拉回编译器。编译器要判断一段源代码 a + b * c 是不是“合法句子”，就需要一本“拼装手册”，也就是文法（Grammar）。文法由四条核心概念组成：终结符是句子里的最小原子（如 id、+、*、括号）；非终结符是“表达式”“项”这类待展开的半成品；开始符号（Start Symbol）是整本手册指定的唯一初始目标；而产生式（Production）就是手册上的一条条指令，比如“表达式可以拼成 表达式 加 表达式”。

形式化地说，一个上下文无关文法用一套产生式规则描述语言。看一个最简单的算术表达式文法：

在乐高车间里，这张文法就是《拼装手册》第 1 页的指令：一个“车身组件”可以是一块底盘加一个驾驶室，也可以是一块底盘加一个车斗，还可以直接就是一个现成的车壳。工人看着手册，按订单选择最合适的那条指令。

CFG四元组定义

乐高工厂为了规范化管理，会把《拼装手册》拆成四份台账：一份登记所有半成品夹具名（V），一份登记所有基础砖块类型（T），一份登记所有拼装指令（P），还有一份在封面标明最终产品名（S）。任何一本合法的拼装手册，都必须能装进这四个抽屉里——CFG 的形式化定义正是这“四个抽屉”。

这个定义叫做四元组：

正是这四个抽屉，把“拼装手册”变成机器可检索的数学对象。无论多复杂的语言规则，只要你能填满这四个抽屉，就得到了一个上下文无关文法。

推导与归约

拼装员拿到一张订单——目标串 id + id。他翻开手册，从封面上的“最终产品”E 出发，一路按指令把半成品拆成组件：E 先变成 E + T，再把左边的 E 变成 T，然后 T 变成 id……这种逐步展开的过程就叫推导（Derivation）。

推导就是反复用产生式的右部替换串中的某个非终结符。选择哪个非终结符替换，会带来不同的策略：最左推导（Leftmost Derivation）每步总替换当前串中最左边的非终结符；最右推导（Rightmost Derivation）每步替换最右边的非终结符；而归约（Reduction）是推导的逆过程——把一串符号“合并”回一个非终结符，这正是各类移进-归约分析器的核心动作。

考察文法 E → E + T | T、T → id，对串 id + id 做最左推导：

这就像流水线上永远先处理“最左边”的半成品工位。与之相对的最右推导则永远先处理最右边；对于无二义文法，两种策略最终会得到同一棵语法分析树——这个性质在后面讲 Yacc 时会成为“如何构造唯一语法树”的基石。

二义性判定

工厂收到一份特殊订单 id + id + id，两组工人各按手册拼装。A 组组长说“按左结合，从左往右加”；B 组组长说“按右结合，从右往左加”。两组都产出了合法产品，但内部装配关系完全不同——车间主任震怒了：同一张图纸怎么能有两种拼法？这就叫二义性（Ambiguity）。

一个 CFG 是二义的，如果存在某个由它生成的串，对应两棵不同的语法分析树。注意二义性是“文法”的性质，而不是“语言”的必然属性：同一个语言可以有一个二义文法，也可能存在无二义文法。考察文法 E → E + E | id 和串 id + id + id，可以构造两个不同的最左推导：

判定一个文法是否二义，理论上不可判定，但实践里只要找出一个具体的“双拼案例”就能敲定。在 Yacc 中，二义性会表现为 shift/reduce 冲突，工程师通常通过优先级声明或改写文法来消除它——就像组长开会统一“默认左结合”的规矩。

乔姆斯基范式

为了全工厂统一质量，品控部推出“标准件制度”：每一条拼装指令最多只能涉及“两个半成品”，或者直接使用“一个基础砖块”。任何复杂的手册都可以改造成这种标准格式，而产出的产品集合一字不差。这就是乔姆斯基范式（Chomsky Normal Form，CNF）。

CNF 规定每条产生式只能有两种形状：A → BC（右部恰为两个非终结符）或 A → a（右部恰为一个终结符）。另外允许 S → ε，但仅当空串属于该语言时才允许。把任意 CFG 转成 CNF 通常分三步：先消除 ε 产生式，再消除单元产生式（A → B 这种“直接改名”），最后把长度大于 2 的候选拆成二元链。

CNF 的意义不只是品控洁癖——CYK 动态规划算法就建立在这种“二元拆分”之上：一段字符串要归约成 A，就必须能拆成两段，分别归约成 B 和 C。这就像检验复杂拼装是否合规，只需递归检查每一个二元节点是否合规。

Greibach范式

如果说 CNF 是“标准件制度”，那么 Greibach 范式（Greibach Normal Form，GNF） 是更严格的新规：每条拼装指令的“第一步动作必须是拿起一个基础砖块”，后续才是继续拼半成品。也就是说，任何合法产品的拼装过程，第一个被放上去的永远是一片砖，而不是一个半成品。

GNF 规定每条产生式形如 A → aβ，其中 a 是终结符，β 是若干个非终结符组成的串（可以为空）。转换的核心难点是消除左递归：像 A → Aα 这样的规则会让最左推导永远卡在 A 上停不下来；标准做法是引入新非终结符 Z，把 A → Aα | β 改写成 A → βZ、Z → αZ | ε。

GNF 在理论上很优雅：它让“最左推导的每一步都消耗一个终结符”，从而与“下推自动机读入字母”形成一一对应。直观地说，GNF 相当于把每个半成品的拼装过程都规范成“第一块必然是砖头”，这让从文法到自动机的构造畅通无阻。

乔姆斯基分类

乐高总部发现世界上的拼装手册种类繁多，于是把手册按指令力度分成四个等级：最弱的手册只允许“把一个零件整体替换成另一个零件”（正则文法）；稍强的手册允许“按上下文情境替换”（上下文有关文法）；我们这本车间手册恰好属于第二强等级（上下文无关文法）；而最强的 0 型手册几乎不加限制，能描述图灵机的全部运算过程。这个分级就是乔姆斯基谱系（Chomsky Hierarchy）。

谱系把形式文法分为四型：0 型无限制文法（对应图灵机），1 型上下文有关文法（产生式形如 αAβ → αγβ，替换时要求 A 身边有 α 和 β），2 型上下文无关文法（即 CFG，左部只有一个非终结符），3 型正则文法（产生式形如 A → aB | a，对应有限自动机）。四种语言集合严格嵌套：

理解了这条谱系，你就明白为什么编译器前端选择 CFG 而非正则表达式——正则文法“记不住嵌套”，而 CFG 拥有“括号嵌套、表达式中套子表达式”的递归生成能力。这正是拼装手册被选为车间主手册的根本原因。

解析器应用

光有手册还不够，工厂里还需要一台“自动拼装机器人”。给机器人输入文法，它就能自动识别订单里的目标串并检查是否合规——这台机器就是解析器生成器（Parser Generator），最著名的当属 Yacc/Bison。工程师们写的不是分析算法，而是“手册的电子版”。

在 Yacc 的规则文件里，一条语法规则长这样：

其中 expression 是一个非终结符，冒号等价于产生式箭头 →，每个 | 分隔一种候选右部，分号收尾。Yacc 会根据这些产生式自动生成一个 LALR 分析器：它从左到右扫描输入串，把终结符“移进”栈里，当栈顶形成某个产生式右部时，将其“归约”成左部非终结符——这正是前面讲过的“归约”概念在工程中的直接体现。

当你在项目里用 Yacc/Bison 定义语法时，其实就是在填那四个抽屉：终结符是 token 声明，非终结符写在规则左侧，开始符号写在 %start 里，而 P 就是这一整段规则清单。从“乐高手册”到“自动拼装机”，CFG 理论就这样完整地落到了工程里。

expression : expression '+' expression           | expression '-' expression           | number           ;

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-def cyk_parse(grammar, start, string):    # CYK 算法: 判断 string 能否由 CNF 文法生成    n = len(string)    if n == 0:        return False  # 本示例文法不产生空串, 简化处理    # table[i][j] 是能推导出 string[i:j+1] 的非终结符集合    table = [[set() for _ in range(n)] for _ in range(n)]     # 第一步: 处理 A -> a 形式的终结符产生式    for i, ch in enumerate(string):        for A, prods in grammar.items():            for rhs in prods:                if len(rhs) == 1 and rhs[0] == ch:                    table[i][i].add(A)     # 第二步: 按子串长度从小到大填表    for length in range(2, n + 1):        for i in range(n - length + 1):            j = i + length - 1            for k in range(i, j):                for A, prods in grammar.items():                    for rhs in prods:                        if len(rhs) == 2 and rhs[0] in table[i][k] and rhs[1] in table[k + 1][j]:                            table[i][j].add(A)     return start in table[0][n - 1]  def main():    # 教材经典文法 G:    # S -> AB | BC    # A -> BA | a    # B -> CC | b    # C -> AB | a    grammar = {        'S': ['AB', 'BC'],        'A': ['BA', 'a'],        'B': ['CC', 'b'],        'C': ['AB', 'a']    }    for w in ['baaba', 'baa', 'abab']:        print("{} 属于 L(G): {}".format(w, cyk_parse(grammar, 'S', w)))  if __name__ == '__main__':    main()

1. table = [[set() for _ in range(n)] for _ in range(n)]建立 n×n 三角表，规则是“能推出 string[i:j+1] 的所有非终结符”。
2. if len(rhs) == 1 and rhs[0] == ch:先处理 A → a 这类终结符产生式，一个字符能被谁直接推出。
3. for k in range(i, j):枚举切分点 k，把子串 [i..j] 分成两段，这是 CYK 的“二元拆分”核心。
4. if len(rhs) == 2 and rhs[0] in table[i][k]只有当左半能归约成 B、右半能归约成 C，且存在 A → BC 时，整段才能归约成 A。
5. return start in table[0][n - 1]整串若能归约成开始符号 S，则该串属于文法语言。

常见误区

面试题