CSCI3130 T05 · Part 4 文法清理

课程：CSCI3130 · 2025T1 本讲：第4部分 / 共4部分 · T05-2025T1.pdf（本地课件） p.12–14 定位：文法清理的原题、完整推导与边界核对。 前后：上一份 简单文法 · 下一单元 T06 承接：#L06-04 无用变量、#L06-02 可空变量、#L06-03 单位产生式

空规则、单位规则和无用变量（p.12–14）【已会】

p.12导航，p.13出题，p.14给清理结果。

题面块（T05 · Problem 4 · PDF p.13）：

p.13 Remove all unit-productions, all useless productions, and all λ-productions from the grammar:

原题规则逐条为S→aA或aBB；A→aaA或λ；B→bB或bbC；C→B。

先求nullable集合：A能直接变λ；B/C每条继续保留B或C且还产生b，不能空；S每条含a也不能空。删除A→λ时，对S→aA补S→a，对A→aaA补A→aa，保留未删A的原分支。得到S→aA或a或aBB，A→aaA或aa，B→bB或bbC，C→B。

消单位C→B，将B的非单位右侧复制到C：C→bB或bbC。原页p.14中间把B→bB误写为B→bC；正文保留原题B→bB后正确展开，两者最终都会因不生成终结串而删除，但中间变换不能凭空换变量。

最后求能生成全终结串的变量：A能，S能；B与C始终互相留下一个变量，无规则结束，所以都不能。删去含B/C的规则后，最终S→aA或a，A→aaA或aa。所有剩余变量可达且可生成，没有λ或单位规则。

算一遍：原S⇒aA⇒aaaA⇒aaaaaA⇒aaaaa生成5个a；新S⇒aA⇒aaaA⇒aaaaa也生成5个a。最终语言是全部正奇数个a，最短a由S→a，其他为a加A产生的正偶数个a。原aBB分支不可能终结，因此删它没有丢失合法串。

用最小不动点识别“能结束”，不用可达性代替（补充）

生成性可逐轮求：第一轮先收有全终结符右侧的变量，清空规则后可直接看到 A→aa 与 S→a，故加入 A、S；再加入右侧所有变量已经在集合中的左变量，直到不再增长。B→bB、B→bbC、C 的继承规则都至少依赖 B 或 C，自始至终没有一个可作为终结基础，故两者不能被加入。相互引用形成环，不会凭空创造一个结束出口。

B、C 虽然从 S→aBB 可达，仍然不能生成全终结串；这说明“可达”与“可生成”是不同判据。删去非生成变量后，再从 S 检查可达性，最终保留下来的 A 既可达又能结束。以最终语言验证清理结果也是独立检查：最短串 a 必须保留，全部长度为1+2k，而含 b 的串一个也不应出现。

三次清理后的检查

最终规则 S→aA或a、A→aaA或aa：右侧全都非空，所以无λ规则；右侧没有单个变量，所以无单位规则；S为开始变量，A由S可达且能出aa，所以没有无用变量。形状检查与前面的语言保持论证合在一起，才完成题目要求。

本讲核心考点

• 先求nullable与单位闭包，再排除不能生成终结串的变量（p.12–14，C 级）。

附录

本Part完整演练的是辅导课原题，推导与原页问题已在正文给出；不新建Tutorial知识条目。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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：无

• 原件：T05-2025T1.pdf（本地课件），PDF p.12–14。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页5、8、11、14。