编译原理课程里LR(0)分析器绝对是一座绕不开的山。严格来说它算是所有自底向上语法分析技术的起点后面SLR(1)、LR(1)、LALR都跟它有直接的血缘关系。可惜很多学校的实验题只给一句话“用C实现LR(0)文法分析器”剩下全靠自己摸索。我当年在这个实验上折腾了整整两天网上找的代码要么编译不过要么生成的分析表全是冲突最后干脆从零手写边写边把项集、闭包、自动机、分析表生成的整条逻辑彻底捋通了。这篇就把我踩过的坑和总结出来的完整实现方法整理出来适合正在做编译原理实验的同学也适合想真正吃透自底向上分析原理的读者参考。1. 为什么非要手写LR(0)分析器1.1 从文法到查表LR(0)解决的是最后一公里LR(0)所做的工作可以概括成一句话给定一个文法自动生成一张驱动表然后用一个简单的栈机去匹配输入串。在编译器的整体架构里这部分属于语法分析阶段它要解决的核心问题是“如何根据当前已经读入的内容决定下一步是继续读入还是回头规约”。用手写C实现它的价值不光是交个实验而是能把“文法 - 项目 - 项目集 - 自动机 - 分析表 - 驱动程序”这条链路用代码完整走一遍。以后你在课本上看到的一堆记号才有了真正对应的实物。LR这个名字的含义是L表示从左往右扫描输入串R表示构造最右推导的逆过程0表示向前看0个符号。这个“0”既是优点也是缺点。构造分析表的时候完全不需要参考当前输入符号逻辑简单、实现直接但正因为不看很多日常使用的文法在它看来都带冲突。理解了这一点就理解了为什么教材紧接着就讲SLR(1)——LR(0)更像是为了铺垫而存在的一个精简模型。1.2 这套C方案适合谁、能解决什么问题这套方案适合三类人。第一类是正在做编译原理实验的本科生需要一份能读懂、能改、能通过验收的代码第二类是准备考研或者面试前自检LR分析原理的人亲手构造一遍比死记硬背强得多第三类是喜欢折腾开发工具的人想自己搞一个小型语法分析器生成器。方案本身不依赖第三方库核心代码全部用C17就能编译随便哪个开发环境都能跑起来。你只需要准备一个文法文件程序会依次输出项集规范族、ACTION表、GOTO表再输入一个句子就能看到完整的移进、归约过程。如果文法存在冲突程序会明确指出冲突发生在哪个状态、哪个终结符上。这样一套东西做完LR(0)分析对你来说就不再是抽象概念而是一个随手能改、能跑的工具。2. LR(0)的核心原理先弄懂词再动手2.1 项与项集分析器的最小积木块产生式右边打上一个圆点就是项。比如产生式E - E T一共有四个项E - .E T还没读入任何右部符号E - E . T已经读入了E接下来期望看到E - E . T已经读入E和等待TE - E T .整个右部都已读入可以考虑按这条产生式归约圆点的位置记录了分析器在某条产生式上推进到了哪一步。一个状态对应一组项称为项集。构造初始项集时必须执行闭包操作如果某个项的圆点后面是非终结符B那就把以B为左部的所有产生式以圆点在开头的形式加入当前项集直到集合不再变化为止。这相当于说我当前期望看到B那么所有可能推导出B的开始符号都有可能出现自然要把它们的起点都纳入进来。用个玩游戏类比来理解圆点就是任务进度条当前位置表示任务做到哪一步closure操作则是把所有“可能在后面接续发生的支线任务”一并加载进当前场景。这套逻辑后面写代码时几乎原样翻译理解透了代码就是体力活。2.2 两个核心表ACTION和GOTO状态机和项集都构造好之后下一步是把它转换为分析驱动表。这里有两张表ACTION表以当前状态和当前输入终结符为索引决定动作。动作一共有四类SHIFT表示移进并把下一状态压栈REDUCE表示按某条产生式归约ACC表示接受即分析成功ERROR表示出错。GOTO表规约之后根据归约后的新栈顶状态和左部非终结符决定跳转到哪个状态。Driver本质上是一个状态栈加符号栈的联动循环。可以把它理解为下棋时查规则表当前局面栈顶状态和看到的棋子输入符号决定这一步怎么走走完之后棋盘局面变了再查下一手怎么走。理解了这个查表机制后面写驱动循环就会非常清晰。2.3 移进-归约冲突LR(0)分析表的边界在哪构造LR(0)分析表时有一条非常“蛮横”的规则只要某个状态里存在归约项例如A - α .那么该状态对所有终结符都填写REDUCE动作。如果这个状态同时还有带移进动作的项比如B - β . a γ那在终结符a对应的格子里就会同时出现SHIFT和REDUCE这就是移进-归约冲突。如果同一个状态里有两个不同的归约项那就是归约-归约冲突。这两类冲突是LR(0)分析表生成中最核心的检测点也是判断一个文法是否属于LR(0)直接依据。需要特别说明一个容易误解的地方LR(0)的“0”不代表没有冲突而是指归约时不参考任何向前看符号。所以几乎所有常规文法在LR(0)分析表里都会摔跤。经典表达式文法E - ET | TT - TF | FF - (E) | id就不是LR(0)文法。构造流程中会出现状态{E - T . , T - T . * F}归约项E - T .要求对符号也执行归约可同一个状态里又有移进项T - T . * F要求在*上移进两者撞在同一个格子里。这就是LR(0)处理不了它的直接原因也是后文SLR(1)登场的动机。3. C实现的数据结构与整体架构3.1 文法表示一切从符号表开始先用一个结构体Production存产生式用int枚举符号id。我建议把所有非终结符和终结符统一编号非终结符编成0到nonTermCnt-1终结符从nonTermCnt编到total-1最后一个特殊终结符$代表输入结束。符号名存到一个全局vector里编号就是下标打印调试非常方便。符号名到编号的映射用std::map或unordered_map都行。struct Production { int lhs; // 左部非终结符id std::vectorint rhs; // 右部符号id列表 }; std::vectorstd::string symbolNames; std::mapstd::string, int symbolId; int nonTermCnt 0, termCnt 0, dollarId -1; std::vectorProduction prods;项直接用std::pairint,int表示first是产生式下标second是圆点位置。这个组合在C里天然就能放进set和map非常适合做集合运算。很多人会嫌pair不够“工程化”想自定义结构体再写相等比较结果只是给自己找麻烦。我实际测试过pair配合std::set做项集去重效率和正确性都非常稳。3.2 项集族的构造从CLOSURE和GO开始closure函数用反复扫描直到集合不再变化的写法也就是不动点思想。圆点后面的符号如果不是终结符就把所有以它为左部的产生式以圆点在位置0的形式加进集合。因为每次加入新项可能又引入新的非终结符所以必须反复循环直到集合稳定。go(I, X)是状态转移函数先找出所有圆点后面恰好是X的项把圆点右移一位形成集合J再对J做closure。两个函数是整个实现的心脏代码很短但几乎所有表构造逻辑都建立在它们之上。ItemSet closure(ItemSet I) { bool changed true; while (changed) { changed false; for (auto [pid, dot] : I) { auto p prods[pid]; if (dot (int)p.rhs.size() !isTerminal(p.rhs[dot])) { int B p.rhs[dot]; for (int i 0; i (int)prods.size(); i) { if (prods[i].lhs B) { if (I.insert({i, 0}).second) changed true; } } } } } return I; } ItemSet go(const ItemSet I, int X) { ItemSet J; for (auto [pid, dot] : I) { auto p prods[pid]; if (dot (int)p.rhs.size() p.rhs[dot] X) J.insert({pid, dot 1}); } return closure(J); }建议先拿一个小文法手动算一遍closure和go再把代码输出结果对一遍。我在做实验时就是这么对比的很快就能发现自己对“圆点位置”和“非终结符展开”的理解有没有偏差。3.3 状态机落地用队列BFS构造规范族构造项集规范族的标准做法是BFS。先定义增广产生式也就是新开始符号S加上S - S把它作为0号产生式。用closure得到初始状态0放进队列然后对队列里的每个状态枚举所有出现在文法右部的符号X计算go结果。如果结果非空而且从未出现过就分配新状态号并加入队列否则就把转移边接到已存在的状态上。为了快速判断“是否出现过”需要维护一个项集到状态号的映射。我推荐用std::mapItemSet,int因为ItemSet是有序集合天然可以作为map的key不需要自己写哈希函数。std::vectorItemSet states; std::mapItemSet, int stateMap; std::dequeint worklist; states.push_back(closure({{augProdIdx, 0}})); stateMap[states[0]] 0; worklist.push_back(0); while (!worklist.empty()) { int s worklist.front(); worklist.pop_front(); for (int X 0; X (int)symbolNames.size(); X) { ItemSet nxt go(states[s], X); if (nxt.empty()) continue; if (!stateMap.count(nxt)) { int id (int)states.size(); states.push_back(nxt); stateMap[nxt] id; worklist.push_back(id); } edges[s][X] stateMap[nxt]; } }这里的潜规则是打开边的枚举范围时最好只针对“实际出现在文法右部的符号”而不是全符号表。否则一旦符号表里混入了没有初始化的编号go函数反复计算空状态虽然不影响结果但白白浪费时间输出也不好看。4. 实操完整代码与关键步骤4.1 Action结构设计与冲突检测不建议直接用二维int数组存动作因为动作类型和动作编号混在一起很容易出错。我习惯定义一个结构体把动作类型和参数分开enum ActType { SHIFT, REDUCE, ACC, ERROR }; struct Action { ActType type ERROR; int num -1; }; std::vectorstd::vectorAction ACTION; std::vectorstd::vectorint GOTO;构建分析表时逐状态扫描每个项按三种情况分别处理圆点后是终结符a在ACTION[s][a]填SHIFT参数是go到达的状态号。圆点在最右端且不是增广产生式对全部终结符包括$填写REDUCE参数是产生式下标。如果对应格子已经不是初始的ERROR就说明出现了LR(0)冲突记录冲突现场。圆点在最右端且是增广产生式S - S .在ACTION[s][$]填ACC。圆点后是非终结符B的情况对应GOTO表格填写。GOTO和ACTION最大的区别在于GOTO不产生冲突因为同一条边只会被同一个状态转移填一次而ACTION里的REDUCE是“赔上全部位置”的最容易出冲突。4.2 打印项集规范族和分析表的小技巧实验验收往往要求输出项集、ACTION/GOTO表。打印项集时建议输出文字形式而不是光打印数字编号。给每个符号id维护一个名字打印时拼成“E - E . T”这种易读格式。表格输出则用固定宽度左对齐看起来就像教材上的表验收老师一眼就能确认你确实实现了分析过程。我在实验报告里就是这么打印的避免了大量口头解释。冲突检测也需要明确的输出。我的做法是发现冲突时打印冲突发生的状态编号、产生式、终结符以及冲突类型是移进-归约还是归约-归约。这样即使文法不是LR(0)的也能清楚地看到问题根源而不是只得到一个“失败”的结论。4.3 Driver状态栈和符号栈的双栈联动驱动循环的主体是状态栈加符号栈。初始状态栈只有0符号栈为空输入串末尾是$。每一步执行循环查ACTION[栈顶状态][当前输入符号]如果是SHIFT把当前符号压入符号栈把ACTION的num压入状态栈然后读下一个输入符号如果是REDUCE先把prods[p].rhs.size()个符号和同样数量的状态弹出记此时栈顶状态为st查GOTO[st][prods[p].lhs]把左部符号和跳转状态压栈如果是ACC接受输入串分析成功如果是ERROR打印错误和当前输入位置。一个特别容易翻车的地方是归约时弹出的状态个数必须和产生式右部符号个数一致符号栈和状态栈严格同步。如果文法里有epsilon产生式也就是右部为空归约时不弹任何符号但依然要查GOTO做一次状态跳转。我见过好几个同学在这个边界上栽跟头驱动循环写了好几版才调对。while (!statusStack.empty()) { int cur statusStack.back(); Action act ACTION[cur][input.front()]; if (act.type SHIFT) { statusStack.push_back(act.num); symbolStack.push_back(input.front()); input.pop_front(); } else if (act.type REDUCE) { auto p prods[act.num]; for (int i 0; i (int)p.rhs.size(); i) { statusStack.pop_back(); symbolStack.pop_back(); } int next GOTO[statusStack.back()][p.lhs]; statusStack.push_back(next); symbolStack.push_back(p.lhs); } else if (act.type ACC) { return true; } else { return false; } }这段代码写完后记得加一行调试打印把每一步的状态栈、符号栈、剩余输入都打出来。这一步能把抽象的执行过程变成肉眼可见的轨迹排查问题效率直接翻倍。5. 调试技巧与常见坑5.1 项集去重不稳定多半是closure的锅如果出现go返回的项集明明“见过”但stateMap却查不到第一个要怀疑的是closure实现不严格。比如圆点后面的符号判断错位或者插入新项后没有再次触发扫描导致项集内容漏项。项集一旦漏项两个状态看起来差不多实际上却不相等map自然找不到。还有一个隐藏较深的问题在set遍历过程中直接插入新元素。虽然C标准里set迭代器不会因为插入操作失效但是否立刻又能被循环变量看到取决于实现细节。稳妥做法是每次循环重扫整个集合或者用do-while配合一个独立的newItems列表去积累本轮新增项最后再统一合并。5.2 冲突太多先查文法有没有增广LR(0)分析表的构造要求先对文法做增广也就是加入新的开始符号S和产生式S - S。没有这一步初始项集就少了“整个分析结束”的锚点ACC状态永远无法正确产生。我见过不少实验代码直接拿用户输入的起始符去构造初始项集结果各种奇奇怪怪的冲突全都冒出来。更常见的问题是把产生式编号从0还是从1开始搞混。归约动作里存的编号必须和prods数组下标完全对应否则分析表打印出来后REDUCE后面跟着的产生式内容是错的但又不报编译错误极难排查。我建议所有内部编号都从0开始展示和打印时统一加1既能避免下标错位又方便对照教材里的表格。5.3 Driver循环里几个致命bug输入串读取和$的处理。很多初版代码读到文件末尾就报错但LR分析器必须把$当成一个正常终结符读进去否则ACC动作永远不会触发所有合法输入都会以ERROR结尾。移进之后忘记读下一个符号。有些同学在SHIFT分支里把状态和符号都压栈了却忘了把输入指针前移于是同一个字符被反复移进栈越来越长也没有任何报错。归约时查GOTO用错了状态。归约之后应该用新的栈顶状态去查GOTO而不是用归约之前的状态。这个错误在只有一两条产生式的小文法上不太明显一旦右部符号多起来立刻表现为“归约后状态越界”。这类问题单看代码很难发现。我的调试经验是拿课本上最简单的可分析句子比如idid*id一步一步人工推导再和程序的调试输出对照。只要前十个状态转移都一样基本就能确定driver没有问题。6. 扩展玩法从LR(0)到SLR(1)只需要几步6.1 为什么教材总把LR(0)和SLR(1)放在一起讲LR(0)表的问题在于“宁可错杀也不聪明”状态里只要有归约项就不分青红皂白地对所有终结符填REDUCE。SLR(1)的改进非常直观——归约动作只填在左部非终结符的FOLLOW集合包含的那些终结符上。这样一来那些用不到的归约条目就不会白白占据格子很多移进-归约冲突自然就消失了。拿前面提到过的表达式文法来说状态{E - T . , T - T . * F}里E - T .的归约动作在LR(0)下会覆盖所有终结符包括*导致冲突。但在SLR(1)下FOLLOW(E)里只有$和没有*所以*这个格子里只留下T - T . * F的移进动作冲突被干净利落地消除了。这就是SLR(1)名字里带着FOLLOW的原因。6.2 C代码上实现FOLLOW集和改动第一步计算所有非终结符的FOLLOW集合。三条基本规则开始符号S的FOLLOW集合里一定有$对产生式A - αBβ把FIRST(β)中除ε外的终结符加入FOLLOW(B)对产生式A - αB或者A - αBβ且β能推导出ε时把FOLLOW(A)整体加入FOLLOW(B)。计算时同样用到不动点循环结构和closure非常像。用set存每个非终结符的FOLLOW集合反复扫描所有产生式直到全部集合不再变化为止。第二步修改构建ACTION表的地方。把“对所有终结符填REDUCE(p)”这一句改成“只对FOLLOW[prods[p].lhs]里的终结符填REDUCE”。冲突检测逻辑完全复用只是填表范围收窄了。第三步把原来写好的Driver原封不动拿来继续跑。Driver只认表里的动作不关心表是怎么生成的。我当时把LR(0)代码改成SLR(1)只花了不到一小时效果立竿见影。改良后表达式文法所有状态全部无冲突能正确分析出idid*id的归约过程。这一步做完你会对FOLLOW集合存在的意义产生非常深的记忆。6.3 再往后走LR(1)和LALR的基本方向如果SLR(1)还有冲突就要上LR(1)文法。LR(1)把向前看符号也纳入项的定义项变成“产生式圆点位置 向前看符号”的二元结构状态数量会膨胀但冲突消除得更加彻底。LALR则在LR(1)基础上做状态合并兼顾表达能力和状态规模。理解了LR(0)的C实现之后再上手LR(1)其实就是把项从二元组改成结构体其他架构完全一致。这条扩展路径非常值得自己亲手写一遍写完之后对语法分析器的理解会上一个台阶。我个人在做完LR(0)实验之后的体会是千万不要急着抄完整代码先把closure和go两个函数手动算通再慢慢往上搭。代码本身不算长难的在于你是否真的相信那些抽象集合运算能变成分析表以及遇到冲突时敢不敢对照定义一项项排查。等看到自己的Driver正确归约出一个句子那种踏实感是很真实的。