CFG的应用与文法的二义性

官官方信息技术老师·9 页·深入（追求细节与边界）·0 次浏览·2 天前

✦ CFG的应用与文法的二义性信息技术 CFG的应用与文法的二义性 CFG的应用

二义性推导树语法分析歧义消除

CFG的应用与文法的二义性

从一棵语句的两棵推导树，看清二义性本质与消除路径

按空格/→ 演示下一步

1 / 9 页

全部页面点击任意一页，跳回舞台从这页播放

二义性推导树语法分析歧义消除

CFG的应用与文法的二义性

从一棵语句的两棵推导树，看清二义性本质与消除路径

1第 1 页 · CFG的应用与文法的二义性

CFG的应用

你写代码时 IDE 实时提示语法错误——这背后 CFG 在工作。它用一套产生式规则告诉机器「什么样的字符串算合法」。

程序语言的语法骨架

C、Java、Python 等都用 CFG（多以 BNF 书写）规定合法语句结构

结构化文档的规范

HTML、XML、JSON 的格式本质都是 CFG 描述的语言

自然语言的近似模型

可刻画短语递归嵌套，但对上下文敏感现象（如代词指代）无能为力

语法分析器的输入

YACC/Bison 等工具直接吃 CFG，自动生成 LR/LALR 解析器

建筑施工规范对应 →CFG 产生式规则

规范规定墙体、门窗怎么合法拼接；产生式规定终结符、非终结符怎么合法组合

2第 2 页 · CFG的应用

CFG的转化

一个文法写出来就能用吗？往往不能——里面藏着推不出终结符的符号、空串产生式、绕弯的单产生式。得按特定顺序一步步收拾成 Chomsky 范式这种标准形状，算法才能稳定工作。

消除无用符号

永远推不出终结符串、或者从开始符永远到不了的符号，可以直接删掉

消除ε产生式

把 A→ε 这类产生式替换掉，可空变量显式展开成多种情形

消除单产生式

A→B 这种绕一道的产生式会拉长推导链，合并展开掉

化为Chomsky范式

产生式只允许 A→BC 或 A→a 两种形式，结构最规整

搬家分类打包对应 →CFG化简流水线

先按类分拣再统一装箱，顺序反了后面的箱子就装不下

3第 3 页 · CFG的转化

文法二义性

接上页CFG转化——即便改写后文法等价，文法本身的二义性仍会埋雷。本页拆解定义、文法与语言二义的差别、不可判定的深度，以及工程中最常遇到的陷阱。

定义

存在某个串对应两棵或更多不同的语法树（推导树）

文法≠语言

文法二义不代表该语言二义——语言可能存在无二义文法

不可判定

不存在通用算法判定任意 CFG 是否二义（经典不可判定问题）

典型陷阱

算术优先级未固定、dangling else、同一前缀的多种分支

解决路径

改写文法引入优先级/结合性，或在 parser 层消歧

算式 a−b−c 的两种括号对应 →文法二义性

同一字符串两种语法树，对应不同语义——文法只问能否这样拆

G\text{ 二义} \iff \exists w \in L(G),\ |T_w| \geq 2

4第 4 页 · 文法二义性

二义性的消除方法

上一页我们看到，文法二义性会让同一字符串对应多棵语法树。这一页介绍四种消除方法，从工程实践到理论边界。

引入优先级与结合性

为不同运算层级建立分层产生式，同层再规定左或右结合方向

改写文法结构

把扁平的产生式改写成嵌套分层结构，从源头消除多棵语法树

附加限制规则

针对悬挂else这类结构，规定匹配语句不得以未闭合的if结尾

本质二义不可消

存在先天二义语言（如aⁿbⁿcᵐ∪aⁿbᵐcⁿ），任何等价文法都二义

算术运算优先级约定对应 →文法分层产生式

约定×比+先算，高优先级放更深层，对应先归约

E \to E+T \mid T \\ T \to T \times F \mid F \\ F \to (E) \mid id

5第 5 页 · 二义性的消除方法

CFG的构造方法

无论设计JSON解析器还是定义SQL语法，第一步都是写出CFG。但CFG不会凭空冒出来，它有一套系统的构造方法。

构造目标

对给定语言L，找到G使L(G)=L

构造起点

可从正则式、语言描述、BNF规范出发

核心思想

非终结符划分子语言，递归刻画嵌套结构

双向验证

证明L(G)⊆L且L⊆L(G)，缺一不可

典型应用

程序语言、协议格式、查询语言的语法定义

正式信函模板对应 →CFG

固定措辞(终结符)、段落槽位(非终结符)、格式规则(产生式)

6第 6 页 · CFG的构造方法

CFG的构造实例

上一页给了几条构造套路——这一页挑一个语言跑一遍，看每一步怎么落地。

例题语言

先圈定要识别的语言集合，如回文串或算术表达式

终结符识别

从语料中找最小不可分符号，如数字、字母、运算符

非终结符设计

为语法结构层级命名，如 Expr 代表整个表达式

产生式拼装

用箭头把非终结符和终结符连起来，逐层展开句型

积木拼装规则对应 →CFG产生式

小块拼成大块，对应终结符拼出非终结符，每层规则都可被复用

E \rightarrow E + T \mid T \\ T \rightarrow T \times F \mid F \\ F \rightarrow (E) \mid \text{id}

7第 7 页 · CFG的构造实例

本节要点

✓CFG 是程序语言语法的形式化骨架
✓文法转化不改语言，只为适配分析器
✓二义性是文法的属性，不是语言的属性
✓消除二义性常借助优先级与结合性约束
✓构造 CFG 先定句子骨架，再细化规则

延伸主题：自顶向下与自底向上语法分析LL(1) 与 LR(0) 分析表构造算符优先文法

8第 8 页 · 本节要点

课后思考

先凭记忆回答，再翻看参考答案对照思路——重点不在对错，而在思考路径。

1为什么无歧义文法对编译器至关重要？文法若有二义性，编译器会遇到什么具体困难？

参考答案编译器要为每个句子生成唯一的语法树。无歧义文法保证任意串只有一棵树；二义性文法让同一句子对应多棵树，编译器无法确定该走哪条推导路径，导致语义歧义甚至报错。

2对于一个具体文法，有没有系统性的步骤判定它是否二义？为什么往往很难？

参考答案理论上要构造两个不同语法树的句子，但不存在通用算法。实践靠试探：尝试找两棵不同的推导树，或归纳证明所有句子唯一。后者往往非常繁琐。

3是否存在一类语言，无论用什么 CFG 描述都注定二义？这反映了什么边界？

参考答案有的，叫本质二义语言——任何 CFG 描述它都必有二义。直觉上：语言层「句-义」本身多对一，换任何文法都榨不出唯一性。这是 CFG 表达力的理论边界。

9第 9 页 · 课后思考