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 BA → aB → C b而C没有任何产生式。如果你先做可达性分析你会发现S能到达A和BB能到达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 → CB和D同时去掉。这三种情况一个都不能漏。漏掉任何一种文法描述的语言就悄悄变了后面推导某些句子时会发现怎么都推不出来特别难排查。3.2 单产生式的消除闭包计算与循环依赖处理单产生式也叫单位产生式指的是形如A → B这种右部只有一个非终结符的产生式。这类产生式在文法里其实代表一种“改名”操作——从A直接跳到B。有些算法能容忍它但在化简到Chomsky范式CNF时必须把所有单产生式消掉因为CNF要求产生式右部要么是一个终结符要么是两个非终结符单个非终结符是不被允许的。消除单产生式的核心思路是计算“单产生式闭包”。对每个非终结符A我要找到所有能通过一连串单产生式到达的非终结符集合。比如A → BB → C那A的闭包就是{B, C}。这个过程可以写成类似图搜索的算法把每个非终结符看作图的节点单产生式A → B看作从A指向B的一条边然后对每个节点做可达性搜索。闭包算好后原本的单产生式A → B可以直接删掉取而代之的是“A → 所有从B出发的非单产生式”。为什么这么做因为A和B在推导能力上是等价的——既然A只换成B那B能推出的东西A也一定能推出。直接复制过来既保住了推导能力又消掉了“间接跳转”整个文法链条就缩短了。这里有一个实际中非常常见的问题就是循环单产生式比如A → BB → 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开始符号为SS → 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的两个产生式里根本没有CC从来不会被任何非终结符引用。所以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只到达BA已经不可达了应该再删一次最终得到S → a B B → c这个例子看着简单但它很好地演示了“删完一轮还要再检查一轮”的坑。如果你只做一遍可达性就收工A这条“孤悬在外”的产生式就会残留下来。实际项目中这种“删了一个连带另一个也变成孤岛”的情况非常普遍务必迭代处理。5.2 常见问题与排查技巧实录问题一做可终止性分析时把“部分可终止”的算成可终止。比如产生式X → Y zY还没确认可终止有人就先把X放进去。这是错的必须等Y确认了X才能确认。我的建议是先在纸上把所有产生式列出来每轮迭代结束拿笔勾掉已确认的做到“眼见为实”。问题二删除不可达产生式后忘了检查空产生式残留。空产生式消除和可达性消除经常是配合使用的。比如本例中的C → ε如果C可达那ε就影响着整个文法。最常见的情况是先消除空产生式再删除不可达最后再做一次全局复查。我习惯把复查作为固定动作做完一遍化简就整体重读一遍文法问自己两个问题每个非终结符还能推导出句子吗每个非终结符还能从S到达吗问题三做单产生式闭包时忘记了自反性。处理A → B | C这种多候选时要把每个候选都展开并且特别注意A自身算不算闭包成员。虽然从定义上说零步推导也构成闭包的一部分但在替换单产生式时不要把“A → A”这种无聊的自循环加入替换不然会出现无限递归的灾难。5.3 化简完成后的自查清单总结我这些年做文法化简和编译实验的经验我给自己定了一份自查清单每次做完都对着过一遍分享给你参考是否所有非终结符都能推出至少一个终结符串是否所有非终结符都能从开始符号到达文法中是否还有形如A → ε的空产生式除非特意保留是否还有右部只含单个非终结符的单产生式除非特意保留化简前后随机挑几个句子确认推导路径依然存在且唯一最后一条特别重要。化简最大的风险就是改着改着把语言给“改没了”。你永远要记住化简的目的是让文法更干净不是让它表达能力变弱。每次改完拿几个代表性句子手工推导一遍确认句子依然能被推导出来。我在实际工作中这个验证步骤即使再忙也不会省——因为一旦被语言本身吞掉一个合法句子后面所有的工作都建立在错误的地基上。