CSCI3130 L05 Part 2 解析与歧义

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L05 Part 2 解析与歧义 · 原件 L05-上下文无关文法-资料包.pdf（本地课件） p.39–79 定位：把成员问题转成解析，并区分搜索效率、文法歧义与固有歧义。前后：上一份 L05-P1-上下文无关文法.md · 下一份 L05-P3-程序语言.md

p.39 Outline，进入解析与歧义。

解析是从结果找生成过程（p.40–42）【新】

p.40 Parsing describes finding a sequence of productions by which a w ϵ L(G) is derived.

p.40 以前给规则问能生成什么，现在给终结串问能否生成、怎么生成。p.41 parser 的输入为文法与串，成功时输出推导。p.42 用 $S\to SS\mid aSb\mid bSa\mid\lambda$ 解析 aabb，朴素思路是从 S 展开所有可能，逐层搜索。

穷举搜索如何找到 aabb（p.43–45）

p.43 第一轮有 SS、aSb、bSa、空串四候选。p.44 第二轮展开其中的变量，例如 aSb 可变 aaSbb。p.45 第三轮用 S→空串，得到 aabb，找到完整推导。搜索不能只沿第一分支无限递归；按推导步数逐层枚举，才能保证有限深度的成功路径最终被看到。已输出的终结符位置若和目标冲突，可剪去该候选，但剪枝须有不会漏解的理由。

p.44 的第二轮候选完整展开：固定最左变量后，SS 分别变成 SSS、aSbS、bSaS、S；aSb 分别变成 aSSb、aaSbb、abSab、ab。第一支 bSa 从首字符 b 起就与目标 aabb 冲突，可以剪去；第二轮的 bSaS 同理，abSab 的第二个终结符已经是 b，而目标第二位要 a，也可剪去。这就是 p.45 留下的 SSS、aSbS、S、aSSb、aaSbb。然后 aaSbb 用空规则得到 aabb。剪枝只利用已经固定的终结符次序，不把暂时未展开的 S 当作空串。

找得到不代表能判定找不到（p.46–48）

p.46 返回 $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ 。p.47 若输入 abb，不在等量 a、b 的语言中，但 SS 可以无限增多再消去，朴素搜索没有自然停止界。p.48 去掉空产生式、以 ab 与 ba 作结束，文法为 $S\to SS\mid aSb\mid bSa\mid ab\mid ba$ ，生成原语言中的非空串。每一步句型总符号数至少增加1，目标长 n 时超过 n 的候选不可能缩回，因此至多搜索 n 轮即可停止；空串例外不能悄悄说两文法语言完全相同。

没有空规则、单位规则后的界（p.49–51）

p.49 排除 $A\to\lambda$ 和 $A\to B$ ，穷举就能成为总停机算法。p.50 一次替换要么使句型长度增加至少1，要么是 $A\to a$ ，长度不变但终结符数增加1。成功推导的这两个数都不能超过目标长度 n，所以总步数有2n的安全上界。p.51 若固定最左展开位置，每步最多有 $\lvert P\rvert$ 个规则选择，第 k 层候选数至多 $\lvert P\rvert^k$ ；不固定展开位置时还要另计位置分支，不能原样照抄这个界。

可判定不等于高效（p.52–54）

p.52 总候选数上界为 $\sum_{k=1}^{2n}\lvert P\rvert^k$ ，对固定文法仍随 n 指数增长。p.53 提到 CYK，可对固定文法在立方时间内解析，具体算法以后讲。p.54 另一条路径是限制文法形状：s-grammar 每条规则 $A\to ax$ ，a 是终结符，x 是变量串，并且同一对(A,a)最多出现一次。因此“当前变量＋下一个输入字符”就能唯一决定规则。

s-grammar 的确定解析（p.55–56）

p.55 左文法 $S\to aS\mid bSS\mid c$ 满足条件；右文法多了 $S\to aSS$ ，同一(S,a)出现两次，就不满足。左文法解析 abcc： $S\Rightarrow aS\Rightarrow abSS\Rightarrow abcS\Rightarrow abcc$ 。第一位 a 选 aS，第二位 b 选 bSS，接着两个 c 依次消去两个待处理 S。

p.56 每步恰消耗一个输入字符且规则唯一，固定文法下共 n 步。这里的“唯一推导”应放在固定最左处理约定下理解；不同独立变量的一般展开顺序仍可不同，不影响唯一树。

p.57 Ambiguity 分节页。

同一字符串有两棵树（p.58–60）【新】

p.58 的 $S\to aSb\mid SS\mid\lambda$ 对 aabb，一棵树直接嵌套两层；另一棵先 S→SS，左支空、右支嵌套。根的孩子数已经不同，因此是结构歧义，不只是访问次序。

题面（本讲 · Example 5.11 · p.59–60；公式按讲义重排）

p.59 $E\to E+E\mid E\ast E\mid(E)\mid a$ .

$a+a\ast a$ .

p.59 第一种最左推导先 E→E+E，得到 $a+(a\ast a)$ 的树： $E\Rightarrow E+E\Rightarrow a+E\Rightarrow a+E\ast E\Rightarrow a+a\ast E\Rightarrow a+a\ast a$ 。p.60 第二种先 E→E∗E，左子树再加法： $E\Rightarrow E\ast E\Rightarrow E+E\ast E\Rightarrow a+E\ast E\Rightarrow a+a\ast E\Rightarrow a+a\ast a$ 。输出字面相同，根运算却不同。

歧义的等价判据（p.61–63）

p.61 并排两树，左根加号、右根乘号；p.62 用这个单一见证串证明文法歧义。p.63 给两条最左推导作为同样有效的证据。关键是“两条最左”而非随便两条推导；固定展开顺序排除了独立变量先后顺序造成的表面差异。

存在一个反例就够（p.64–66）

p.64 A context-free grammar G is ambiguous if some string w∈L(G) has: two or more derivation trees

p.64 是存在量词：只需一个串有两树；不要求所有串都这样。p.65 可等价用两条最左或两条最右推导。p.66 让 a=2，演示结构不同会改变解释，不只是图画不同。

两棵树分别算出什么（p.67–69）

p.67 把三个 a 全替成2。p.68 左树先算 $2\times2=4$ ，再算 $2+4=6$ ；右树先算 $2+2=4$ ，再算 $4\times2=8$ 。p.69 按课程要求乘法优先，加法后算，选结果6的那棵。原 CFG 没有把这个优先级写进结构，因此单靠这个文法不能决定唯一解释。

用层级强制优先级（p.70–72）

p.70 希望移除程序语言中的歧义。p.71 用

E\to E+T\mid T,\quad T\to T\ast F\mid F,\quad F\to(E)\mid a.

E 管加法层，T 管乘法层，F 管原子或括号。T 内不能无括号地产生加号，所以一次加法的操作数必须先完成乘法。p.72 对 $a+a\ast a$ ： $E\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T\Rightarrow a+T\Rightarrow a+T\ast F\Rightarrow a+F\ast F\Rightarrow a+a\ast F\Rightarrow a+a\ast a$ 。每个换层步骤都保留，才能检查是否真按规则展开。

优先级与结合方向是两项不同承诺（补充自取实例）：层级 E/T/F 使 $a+a\ast a$ 的根只能是加号，因此乘法先算；但只有这句话还没说明 $a+a+a$ 如何分组。正文的 $E\to E+T$ 把剩余加法放在左边 E，右边 T 不能继续产生未括起的加号，所以结构为 $(a+a)+a$ ，即左结合。若改为 $E\to T+E$ ，则会变成 $a+(a+a)$ 。

加法在普通整数上两种分组数值相同，不能靠数值相同断言树相同。若同样结构用于减法，自取 $8-3-1$ ：左结合为 $(8-3)-1=4$ ，右结合为 $8-(3-1)=6$ ，差别立刻可见。这个例子只解释结合规则，不声称原文法已包含减号。

唯一结构与悬空 else（p.73–75）

p.73 给唯一树，p.74 宣布该文法无歧义。理由是最高层未被括号包住的加号把表达式分成 T；没有这种加号时下沉到 T，由乘号分成 F；括号内重新递归处理。规则左递归也固定了同优先级的结合方向。观察一个串只有一树本身不足以证明所有串唯一，结构约束才是普遍理由。

p.75 的 if 可有 else 也可无 else：一个嵌套 if 后只有一个 else 时，不加额外规则便无法决定它属于哪层。

文法歧义与语言固有歧义（p.76–78）

图（p.76）：同一串 if expr1 then if expr2 then stmt1 else stmt2。上树将 else 与内层 if 配对，下树将 else 与外层 if 配对；两种控制流可能不同。补充：语言可规定 else 绑定最近未匹配 if，或用块界定来消除歧义；原图本身尚未规定这个选择。

p.77 给语言 $\{a^nb^nc^m\}\cup\{a^nb^mc^m\}$ ，讲义称它固有歧义，即不存在任何无歧义 CFG 生成它。p.78 的 $a^nb^nc^n$ 在展示的文法里两支都能生成，说明这份文法歧义；要推出“所有可能文法都歧义”需要更强证明。讲义仅列外部证明归因，没有给出完整证明，本伴读不把两棵树当成固有歧义定理的充分证明。

p.77–78 展示的文法不能省去：

\begin{aligned} S&\to S_1\mid S_2,\\ S_1&\to S_1c\mid A,& A&\to aAb\mid\lambda,\\ S_2&\to aS_2\mid B,& B&\to bBc\mid\lambda. \end{aligned}

第一支先留下任意个尾部 c，再由 A 配对 a、b；第二支先留下任意个头部 a，再由 B 配对 b、c。对 abc，两条最左推导分别为 $S\Rightarrow S_1\Rightarrow S_1c\Rightarrow Ac\Rightarrow aAbc\Rightarrow abc$ 与 $S\Rightarrow S_2\Rightarrow aS_2\Rightarrow aB\Rightarrow abBc\Rightarrow abc$ 。这具体落实了课件的两树见证；课件将更强的固有歧义定理归于 Harrison（1978），该归因在这里按课件保留，并非本次独立查阅该著作。

用两条最左推导证明歧义（p.79）

题面（本讲 · Exercise 5.3.6 · p.79；公式按讲义重排）

p.79 Show that the following grammar is ambiguous.

$S\to AB\mid aaB,\quad A\to a\mid Aa,\quad B\to b$ .

选讲义的 aab。第一条 $S\Rightarrow aaB\Rightarrow aab$ ；第二条 $S\Rightarrow AB\Rightarrow AaB\Rightarrow aaB\Rightarrow aab$ 。每步替换的确是当前最左变量；两条第一步已不同，一条根下为 a、a、B，另一条根下为 A、B，因此对应不同树。结论是该文法歧义，不能据此声称其语言固有歧义。

考试角度：（C 级通识）常见考法是给两条最左推导作歧义见证，或用 E/T/F 层级解释运算符优先级。

考试角度：（A 级：HW03-2025T1-题目.pdf Q4，考的是简单文法拆分。）见附录 A1。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q5(2)；期末-2022T1-资料包.pdf Q5，对应歧义见证与LR零项集；扫描件视觉读取。）见附录 A2。

自检：两个不同文法都生成某个串，能证明文法歧义吗？

歧义的两个见证必须在哪个对象内部？

展开推理与答案

不能。两个不同文法生成同一个串很常见。要证明某份 G 歧义，必须在同一个 G 中找到同一个终结串的两棵不同推导树，或两条不同最左推导。证明语言固有歧义还要对所有生成它的 CFG 作更强论证。

本讲核心考点

穷举的终止界及指数复杂度（p.43–53，C 级）。
s-grammar 的规则唯一性（p.54–56，C 级）。
两棵树或两条最左推导证明歧义（p.58–65、79，C 级）。
优先级和固有歧义的量词区别（p.71–78，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：简单文法拆分

题面块（HW03-2025T1-题目.pdf（本地课件） · Q4 · p.1）：

p.1 (20pts) Find a simple grammar for:

p.1 $S\to abS\mid bc\mid d\mid cdS$ .

引入B→b、C→c、D→d，改S→aBS或bC或d或cDS。每条规则恰以一个终结符开头，后面全变量；S的四种首符号a/b/d/c各自唯一，辅助变量也唯一。因此是s-grammar。把B/C/D展开就得到原右侧，所以语言不变。原S⇒abS⇒abcdS⇒abcdd，在新文法中S⇒aBS⇒abS⇒abcDS⇒abcdS⇒abcdd；只增加中间展开步，不改变叶串。

回到正文：简单文法拆分

A2 作业/往年题演练（非讲义内容）：歧义见证与LR零项集

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q5(2) · p.5）：

p.5 Let G be the context-free grammar over {a, b} with productions

S→E或O；E→AB或BA；A→aA或a；B→bB或b；O→XXO或X；X→a或b。

p.5 Decide whether G is ambiguous or not. If it is ambiguous, give a word w ∈ L(G) that has two different parse trees (or two different leftmost derivations). Otherwise, prove that G is unambiguous.

E生成正a段接正b段或反过来；O生成任意奇数长串。aab同时属于两类。最左推导一：S⇒E⇒AB⇒aAB⇒aaB⇒aab。最左推导二：S⇒O⇒XXO⇒aXO⇒aaO⇒aaX⇒aab。根用的规则已经不同，故两棵树不同，文法歧义。仅说规则多不够，必须有同一终结串的两个推导。

题面块（期末-2022T1-资料包.pdf（本地课件） · Q5 · p.4，扫描件视觉读取）：

p.4 Is the grammar $S\to bS\mid b$ LR(0)? Explain your answer with a DFA.

这是往年卷额外的LR(0)题，原讲解析部分未完整教项集构造，以下仅补到本题所需。增广S′→S，“点”表示已读到规则右侧的位置。初项集I0={S′→·S,S→·bS,S→·b}；I1={S′→S·}；I2={S→b·S,S→b·,S→·bS,S→·b}；I3={S→bS·}。全部非空转移：I0—S→I1，I0—b→I2，I2—b→I2，I2—S→I3。

在I2，完成项S→b·要求无向前看条件地归约，同时S→·bS、S→·b又可读b移进，形成shift/reduce冲突，所以不是LR(0)。它生成b正闭包是正则语言，但语言正则不保证这份具体文法是LR(0)；不能以语言简单替代项集检查。

回到正文：歧义见证与LR零项集

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

原件：L05-上下文无关文法-资料包.pdf（本地课件），PDF p.39–79。
本次独立学习修订：核对本讲90页的文本，视觉复核 p.36、58、76、78、81–82、84、88–90；补全原规则、程序示意、推导树结构和搜索候选。