1. 文法的化简改造：为什么非做不可
1.1 从一次实际调试说起：冗余产生式带来的麻烦
先讲个我早年做编译器实验时踩过的坑。当时为了应付一个简单的表达式语法，我随手写了一堆产生式，结果在构造递归下降分析器的时候，怎么调都出现莫名其妙的回溯和死循环。后来耐着性子把文法从头到尾捋了一遍才发现，里面有好几条产生式根本走不到——有一个非终结符从开始符号出发永远无法到达，还有两个非终结符无论怎么替换都会回到自身，根本推不出任何终结符串。
这件事给我留下一个非常深的印象：文法不是“能表达语言就行”，它内部的结构是否干净，直接决定了后续所有工具（分析器生成器、语法树构造、错误恢复）好不好写。编译原理第二章之所以要把“文法的化简改造”单独拿出来讲，不是为了考试凑知识点，而是因为真实的编译器前端开发里，第一步就是把你手写或自动生成的文法“打扫干净”。
那什么是化简改造？一句话概括：在保证文法描述的语言不变的前提下，把文法中冗余、有害、拐弯抹角的部分删掉或改写成更直接的形式。注意关键词是“语言不变”——化简不是改语言，而是去掉语言描述中的无效表达。这有点像代码重构：功能不变量，只是把代码写得更干净、更可维护。
1.2 化简改造的三个核心方向
我习惯把整个化简过程拆成三个方向来理解，这样不管是做题还是实际用，脑子里都有一张地图：
- 删除无用产生式：文法里有些产生式永远用不上，留着只会干扰分析器的构造。这相当于代码里的死变量、不可达分支。
- 删除不可终止的产生式：有些非终结符看起来能推导，但永远绕不到终结符上，等于一个无限递归的循环，走到这里整个分析就卡死了。
- 转换为规范形式：把空产生式、单产生式这些“特殊形态”消除掉，变成更规整的范式，方便后续算法（比如CYK算法、LR分析表构造）统一处理。
这里需要特别强调一个常见的认知误区：很多人觉得“文法能推出语言就行，干嘛多此一举”。但实际开发中，一个带无用产生式的文法直接喂给yacc、bison这类工具，轻则生成的分析表异常膨胀，重则产生shift/reduce冲突还特别难排查。我记得有个朋友的项目里，就因为一条看似无害的冗余产生式，让他调试了整整一个下午的reduce冲突。所以，化简不是学院派的洁癖，是工程上的刚需。
2. 无用产生式的识别与消除：动手前的思路准备
2.1 什么叫“无用产生式”：两类情况要分清
无用产生式这个概念，表面看很简单，就是“推导中永远用不到的产生式”，但它其实可以细分成两种独立的情况，很多人第一次学的时候会混为一谈。
第一种叫不可终止的非终结符。这种非终结符参加推导，但你永远等不到它变成终结符的那一天。比如有非终结符A，产生式只有A → A b，那无论替换多少次，A后面总有A，始终跳不出终结符串。这种情况下，任何一个包含A的产生式都是“没结果”的，属于典型的僵尸代码。
第二种叫不可达的非终结符。这种非终结符从文法的开始符号出发，根本没有路径能走到它。比如开始符号是S，但某条产生式里有个非终结符B，而S的推导过程中从来不涉及B，那B定义的这一整块就是“孤岛”，怎么走都走不到。
这两种情况经常同时出现，但它们本质不同：前者是“推导没有终点”，后者是“起点到不了”。在消除的时候，顺序很重要，我通常先说结论——先删不可终止的，再删不可达的。为什么是这个顺序？后面详细讲，但你先记着，这个顺序反了会出问题。
2.2 第一步：找出所有能推出终结符串的非终结符
消除不可终止产生式的算法，本质上是一个“逐步逼近”的迭代过程，在编译原理里这叫不动点算法，听着玄乎，其实思路特别朴素。
我先维护一个集合，专门放“已经被确认能推出终结符串的非终结符”。初始的时候，我先扫一遍所有的产生式，凡是右部全是终结符的（比如A → a、B → 1），就把左部A、B加进集合。这就好比先找到那些一上来就能直接产出成品的生产线。
接下来是迭代。每一轮，我看剩下的产生式里，有没有哪条的右部全部由终结符，或者已经在集合里的非终结符构成。如果有，就把这条产生式的左部也加进集合。反复循环，直到某一轮结束集合完全没变化，算法就停了。这个“没变化”的时刻，就是不动点——你再也找不出新成员了。
有个特别容易踩的坑：注意是“右部全部由集合内的元素或终结符组成”，只要还有任意一个非终结符不在集合里，这条产生式就不能算数。我见过很多初学者在这里出错，看到一条产生式右部大部分都推进了，剩下一个还没确认的，就心急把它也算进去，结果整个化简就废了。
迭代结束后，凡是左部不在集合里的产生式，全部删掉。因为这些非终结符永远推导不到终结符串——它们代表的是一类无法终止的递归。这时候你再看整个文法，所有剩下的非终结符，至少都能推导出某个具体句子了。
2.3 第二步：从开始符号出发找出所有可达非终结符
处理完不可终止的，接着处理不可达的。这一步的思路更直观：从开始符号S出发，像做广度优先搜索一样，一层一层往外遍历。
初始先把开始符号S放进“可达集合”。然后看S的所有产生式，右部出现了哪些非终结符，把第一次见到的都加进可达集合。接着，对集合里新加入的每个非终结符，重复上面的操作，看它的产生式右部又引出了哪些新的非终结符。循环往复，直到可达集合不再变大。
这时候注意了，所有左部不在可达集合里的产生式，全部是孤岛代码，直接删除。这些产生式定义了从开始符号永远访问不到的非终结符规则，它们对语言没有任何贡献，只会让文法变得臃肿。
为什么必须先把不可终止的删掉再处理不可达的？我给你举个反例就明白了。假设有文法：S → A B，A → a，B → C b，而C没有任何产生式。如果你先做可达性分析，你会发现S能到达A和B，B能到达C，所以S、A、B、C都可达，什么都不会删。但你再看可终止性，C推不出任何终结符串，B也推不出（因为依赖C），所以B这条产生式是废的，最终语言其实只有A能产生的串。如果你不先删不可终止的，那里的C就会一直留着，成为一颗永远长不出来的叶子。顺序反了，终归要再回头删一遍，还可能看漏。
2.4 第三步：删除无用产生式的完整操作流程
把前面两步讲透了，第三步其实就是收尾。我直接给一个可以照着做的完整清单：
- 先一趟扫描，找出所有右部全是终结符的产生式，把它们的左部加入集合T（可终止集合）。
- 迭代扩充T：只要某产生式的右部全部由终结符或T中的非终结符构成，就把左部加入T；一直循环到T不再变化。
- 删除所有左部不在T中的产生式。
- 重新以开始符号S为根，进行可达性遍历：把S加入集合R，不断查看R中非终结符的所有产生式，将右部出现的非终结符加入R，直到R稳定。
- 删除所有左部不在R中的产生式。
做完这五步，文法里就不再有无用产生式了。我把这个流程做成表格，方便你对着自查：
| 步骤 | 操作内容 | 删除对象 | 终止条件 |
|---|---|---|---|
| 1 | 初始化可终止集合T | — | 找出所有右部全终结符的产生式 |
| 2 | 迭代扩充T | — | T不再变化 |
| 3 | 删除不可终止的产生式 | 左部不在T中的产生式 | — |
| 4 | 从S出发做可达性遍历 | — | R不再变化 |
| 5 | 删除不可达的产生式 | 左部不在R中的产生式 | — |
实际操作的时候，我建议每做一步就在纸上把当前文法的产生式重新抄一遍，这样不容易乱。尤其是考试或者手写作业的时候，很多人习惯在原来那张纸上涂涂改改，结果越涂越看不清，反而失分。
3. 产生式的“特型消除”：空产生式和单产生式
3.1 空产生式的消除：可空非终结符与生成规则
聊完无用产生式，接下来是另一类需要改造的产生式——空产生式，也就是形如A → ε的规则。在正规文法里，空产生式有时是必要的，比如要描述一个可选的声明列表时，空串就是一个合理的句子。但在很多后续算法里，空产生式会变成麻烦制造者——比如在构造预测分析表的时候，空产生式会导致表项出现多个候选，增加冲突概率。
消除空产生式的核心是找到所有“可空非终结符”——即能推导出ε的非终结符。怎么找？还是不动点迭代：先找形如A → ε的直接空产生式，把这些A标记为可空；然后看有没有产生式右部全部由可空非终结符组成，比如B → C D，而C和D都可空，那B也可空。反复推，直到集合稳定。
找出所有可空非终结符之后，关键操作来了：对每个含有可空非终结符的产生式，我们要生成“去掉部分可空项”的新变体。这里最容易出错的点是遗漏组合情况，我给你一个不会漏的方法：假设一条产生式右部有n个符号，其中k个是可空的，那么能够生成的变体数量是2的k次方减1（去掉全都不去的情况，因为原始产生式要保留）。每一个可空的符号都同时面临两个选择：保留还是不保留，你要把所有组合都遍历一遍。
举个例子，产生式A → B C D，其中B和D可空，C不可空，那么原始产生式保留的同时，还要生成：A → B C（去掉D）、A → C D（去掉B）、A → C（B和D同时去掉）。这三种情况一个都不能漏。漏掉任何一种，文法描述的语言就悄悄变了，后面推导某些句子时会发现怎么都推不出来，特别难排查。
3.2 单产生式的消除：闭包计算与循环依赖处理
单产生式也叫单位产生式，指的是形如A → B这种右部只有一个非终结符的产生式。这类产生式在文法里其实代表一种“改名”操作——从A直接跳到B。有些算法能容忍它，但在化简到Chomsky范式（CNF）时，必须把所有单产生式消掉，因为CNF要求产生式右部要么是一个终结符，要么是两个非终结符，单个非终结符是不被允许的。
消除单产生式的核心思路是计算“单产生式闭包”。对每个非终结符A，我要找到所有能通过一连串单产生式到达的非终结符集合。比如A → B，B → C，那A的闭包就是{B, C}。这个过程可以写成类似图搜索的算法：把每个非终结符看作图的节点，单产生式A → B看作从A指向B的一条边，然后对每个节点做可达性搜索。
闭包算好后，原本的单产生式A → B可以直接删掉，取而代之的是“A → 所有从B出发的非单产生式”。为什么这么做？因为A和B在推导能力上是等价的——既然A只换成B，那B能推出的东西A也一定能推出。直接复制过来，既保住了推导能力，又消掉了“间接跳转”，整个文法链条就缩短了。
这里有一个实际中非常常见的问题，就是循环单产生式，比如A → B，B → A。遇到这种循环依赖，闭包算法要小心死循环。我自己的习惯是用一个visited集合来记录已经处理过的节点，避免重复遍历。如果你用递归写，务必在函数入口先做检查，否则栈溢出是分分钟的事。
4. 文法的其他表示方法：不仅仅是产生式
4.1 扩展巴科斯范式（EBNF）：让文法更贴近真实工程
聊完化简和消除，再来说说文法的“表达方式”问题。前面讲的都是产生式这种标准写法，但实际工程里，我们还会用到不少更高级的表示手段。最典型的就是扩展巴科斯范式，也就是EBNF。
EBNF在BNF的基础上加了三类元符号：花括号{}表示“重复零次或多次”，方括号[]表示“可选”，圆括号()加竖线|表示“分组和选择”。这三样东西，本质上是对正则表达式思想的借镜，目的是让文法描述更紧凑、更贴近人的阅读习惯。
举个最经典的例子。标准BNF描述“标识符”经常要写成一组递归产生式：
<标识符> ::= <字母> | <标识符> <字母> | <标识符> <数字>这个写法没错，但读起来绕，而且直接拿去做递归下降分析还会引入左递归问题。同样的语言用EBNF写，就清爽得多：
<标识符> ::= <字母> { <字母> | <数字> }这一行摆在那里，意思一目了然：先来一个字母，后面随便接字母或数字，接多少都行。我个人在实际写语法规范的时候，几乎都是用EBNF先写一版给人看，确认设计合理后，再手工或借助工具转成标准产生式去实现。这一步“先设计后实现”的顺序，能省下不少返工时间。
4.2 语法图：把文法画出来，比看公式快十倍
比EBNF更直观的表示方法是语法图，也叫铁路图。它把产生式画成一张带箭头的流程图：矩形框代表非终结符，圆形或椭圆代表终结符，箭头表示匹配顺序，分支和循环用路径的汇合与回头来表示。
我记得大学那会儿学Pascal语法，老师发了一本手册，里面全是语法图。当时年轻，觉得这算什么正经知识，后来真去写语言解析器才明白，对人来说，语法图是理解文法最快的媒介。比如描述一个if语句，你用产生式写可能有三四行，还要注意各种嵌套和else的匹配。但画成语法图，分支结构一眼就清楚，哪里是必经路径、哪里是可选的，全都写在图上。
这里有个实操心得：当你要为一个新语言设计文法，先用语法图把结构画出来，再转成产生式，比反过来顺得多。因为画图的过程会逼迫你把“可选”“循环”“分支”这些结构都想清楚，而直接写产生式很容易漏掉边界情况。很多开源项目里，语法规范文档其实就是一组语法图，原因就在这里。
4.3 文法与正则表达式的关系：什么时候用哪个
除了EBNF和语法图，还有一种“表示”手段经常被拿来和文法对比，就是正则表达式。很多人学到这里会疑惑：这些东西到底有什么区别？我用一句话概括：正则表达式描述的是正规语言，对应的是3型文法（正规文法）；文法描述的范围更广，包含了上下文无关语言甚至更高级语言。
实际选型的时候，判断标准很简单。如果一种语言的句子结构足够规则，没有嵌套、没有递归匹配的需求，那用正则表达式就够了，词法分析器里的标识符、关键字、数字常量全部属于此类。但如果结构里出现括号匹配、嵌套块、表达式递归求值这类“自身包含自身”的模式，正则就不够用了，必须交给上下文无关文法来处理。
我见过不少初学者喜欢拿正则去解析HTML或表达式，结果写出一堆极其脆弱的匹配规则，稍微变一变格式就全盘崩溃。这种场景下，应该直接用文法描述，再用分析器生成器去构造解析器。记住这个经验，能给你未来省下大量调试时间。
5. 综合例题演练与避坑指南
5.1 例题：一个典型文法的完整化简过程
把上面的知识点串起来，我们完整做一道例题。给定文法G，开始符号为S：
S → a B | A C A → a | A b B → c C → d | ε第一步，先删除不可终止的产生式。先找右部全是终结符的：A → a满足，D？这里没有D，那就先只有A。B → c也满足，B入集合。C → d也满足，C入集合。现在集合里有{A, B, C}。再看迭代：S → a B，右部有B在集合里，整条右部合法，S入集合。S → A C，右部A、C都在集合里，S已经在集合里了，不影响。现在集合稳定：{S, A, B, C}，所有非终结符都可终止，这一步不需要删。
第二步，删除不可达的产生式。从S出发，S的产生式右部出现了A、B，所以A、B入可达集合。查看A的产生式A → a | A b，右部只涉及终结符和A（自身已在集合），没有新成员。查看B的产生式B → c，没有新成员。等等，C呢？S的两个产生式里根本没有C，C从来不会被任何非终结符引用。所以C是不可达的，包含C的产生式S → A C要删掉，C → d | ε也要删掉。
删完之后文法变成：
S → a B A → a | A b B → c这时候你再看，A虽然还保留着，但它已经没有任何被引用的地方了？等等，这里要注意——A在S → a B里没有出现，所以A也是不可达的了。因为一开始我们从S出发找不到A，这就是为什么可达性检查要迭代到稳定。其实在第一步检查完后应该重新做一遍完整可达性。我更正一下这个例题的处理，让它更严谨。
重新严谨地走一遍：原文法中C不可达，删除后得到：
S → a B A → a | A b B → c此时从S出发，S → a B只到达B，A已经不可达了，应该再删一次，最终得到：
S → a B B → c这个例子看着简单，但它很好地演示了“删完一轮还要再检查一轮”的坑。如果你只做一遍可达性就收工，A这条“孤悬在外”的产生式就会残留下来。实际项目中这种“删了一个，连带另一个也变成孤岛”的情况非常普遍，务必迭代处理。
5.2 常见问题与排查技巧实录
问题一：做可终止性分析时，把“部分可终止”的算成可终止。比如产生式X → Y z，Y还没确认可终止，有人就先把X放进去。这是错的，必须等Y确认了X才能确认。我的建议是先在纸上把所有产生式列出来，每轮迭代结束拿笔勾掉已确认的，做到“眼见为实”。
问题二：删除不可达产生式后忘了检查空产生式残留。空产生式消除和可达性消除经常是配合使用的。比如本例中的C → ε，如果C可达，那ε就影响着整个文法。最常见的情况是，先消除空产生式，再删除不可达，最后再做一次全局复查。我习惯把复查作为固定动作，做完一遍化简就整体重读一遍文法，问自己两个问题：每个非终结符还能推导出句子吗？每个非终结符还能从S到达吗？
问题三：做单产生式闭包时忘记了自反性。处理A → B | C这种多候选时，要把每个候选都展开，并且特别注意A自身算不算闭包成员。虽然从定义上说，零步推导也构成闭包的一部分，但在替换单产生式时，不要把“A → A”这种无聊的自循环加入替换，不然会出现无限递归的灾难。
5.3 化简完成后的自查清单
总结我这些年做文法化简和编译实验的经验，我给自己定了一份自查清单，每次做完都对着过一遍，分享给你参考：
- 是否所有非终结符都能推出至少一个终结符串？
- 是否所有非终结符都能从开始符号到达？
- 文法中是否还有形如A → ε的空产生式（除非特意保留）？
- 是否还有右部只含单个非终结符的单产生式（除非特意保留）？
- 化简前后，随机挑几个句子，确认推导路径依然存在且唯一？
最后一条特别重要。化简最大的风险就是改着改着，把语言给“改没了”。你永远要记住，化简的目的是让文法更干净，不是让它表达能力变弱。每次改完，拿几个代表性句子手工推导一遍，确认句子依然能被推导出来。我在实际工作中，这个验证步骤即使再忙也不会省——因为一旦被语言本身吞掉一个合法句子，后面所有的工作都建立在错误的地基上。
