做这个实验之前我原以为LL(1)语法分析就是把课本上的First集、Follow集公式抄一遍然后照猫画虎写个表驱动的程序。真到了实验三才发现从文法到可运行的代码之间隔着整整一条“把形式化定义翻译成程序逻辑”的河。这篇博文就记录我自己从读题、推导集合、设计数据结构、调通分析器到应付检查的全过程重点是那些课本上不会写、但一跑就炸的细节。内容围绕经典表达式文法展开适合正在被LL(1)语法分析实验折磨的同学参考也适合想重新梳理一遍表驱动分析原理的人。1. 实验要求拆解一个LL(1)分析器到底要交什么1.1 读懂指导书背后的真实考核点很多实验指导书写得比较抽象通常只给一句话“构造LL(1)分析程序对输入串进行语法分析并输出分析过程。”这句话看着简单实际上包含四个隐藏交付项。第一文法需要自己设计或给定。如果是给定文法那你的第一步不是写代码而是先做文法等价变换。经典表达式文法一般含有左递归比如E - E T | T直接拿来算First、Follow集没问题但构造预测分析表时必然出现多重入口因为它根本不是LL(1)文法。所以实验的第一步其实是“改造文法”。第二必须计算First集、Follow集和预测分析表。这是实验报告的重点区域也是老师检查时问你“为什么表里这一格是空的”的根源。多数同学会选择程序自动计算但我建议哪怕程序能算自己也手工推一遍否则报错的时候完全看不懂查表过程。第三实现表驱动的预测分析过程。也就是用栈输入缓冲区预测分析表三者配合模拟最左推导。程序要能处理匹配成功、匹配失败、栈空接受等状态并且最好能输出每一步的栈内容和剩余输入串。第四测试用例设计。只拿一个ii*i试通就交差的同学往往在课堂检查时被老师当场用(ii)*i或ii*之类输入问住。所以实验要求拆解下来本质上是“集合计算 查表 栈模拟 健壮性”四件事。注意LL(1)的“1”指的是向前看一个输入符号就能决定用哪条产生式。实验考核的不仅是编码能力更是你能否解释“为什么这个文法可以LL(1)分析而另一个不能”。1.2 为什么实验选LL(1)而不是LR(1)有的同学会问现在实际编译器里Yacc/Bison用的都是LALR(1)为什么课程实验偏偏要做LL(1)我一开始也觉得这实验有点“过时”但做完之后发现LL(1)是理解自顶向下语法分析的最佳切片。LL(1)分析器是表驱动、无回溯的它的核心矛盾集中在“怎么根据当前非终结符和当前输入符号立刻决定用哪条产生式”。这个决策如果手工构造预测分析表你会被迫把First集、Follow集的关系彻底想清楚。而LR(1)分析器虽然功能更强但它的状态机来自项目集规范族包含大量状态迁移对初学者来说信息量太大容易被状态转移表淹没。从实验角度讲LL(1)的代码量适中。一个合法的LL(1)分析器核心逻辑也就三四个函数集合计算、建表、查表、栈驱动。它既能考验你对文法理论的掌握又不至于像LR那样需要动辄几百行的自动机构造。另外LL(1)的“预测分析错误恢复”也比LR直观适合用来教学。所以不要觉得这个实验“太简单”或者“太老”。真正写一遍以后你会对递归下降和表驱动之间的等价性有很深的体会。后文讲代码时会提到很多同学把表驱动写成了递归下降的味道那就是没理解栈模拟的本质。2. 前置计算全流程First集、Follow集和预测分析表是怎么推出来的2.1 先改造文法消除左递归与提取左因子实验里最常用的示例文法是E - E T | T T - T * F | F F - ( E ) | id这个文法描述四则运算优先级很自然但直接用于LL(1)的话E和T都有直接左递归。左递归会让预测分析进入死循环要推导E先得用E - E T可最左符号还是E永远无法往下推进。标准改法是消除左递归。对形如A - Aα | β的产生式改成A - β A A - α A | ε套到表达式文法上得到E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这里E和T就是新的非终结符很多人叫它们“尾巴”。注意提取左因子也要顺手检查比如如果文法里有A - ab | ac就需要提取成A - aA否则预测分析表里同一个格子会出现两个产生式不是LL(1)。本例文法没有公共左因子所以不需要做这一步。我建议改造完文法后用编号记下每条产生式。后面程序里用整数编号管理比直接存字符串方便得多。2.2 First集合的计算顺序与常见误区First集合的定义是从某个符号出发通过零步或多步推导能得到的首个终结符的集合。这里的“多步推导”是关键它决定了计算需要迭代不能只扫一遍。对终结符aFirst(a) {a}。对非终结符A要扫描所有形如A - X1 X2 ... Xn的产生式先把First(X1)中除ε外的所有元素加入First(A)。如果X1能推出空串那么继续看X2把First(X2)中除ε外的元素也加入First(A)。一直往后推直到遇到某个符号不能推出空串为止。如果所有Xi都能推出空串则把ε加入First(A)。手工计算上面的表达式文法结果如下非终结符First集合E{ (, id }E{ , ε }T{ (, id }T{ *, ε }F{ (, id }我踩过的第一个坑是只处理了右部首符号没有处理“第一个符号可空时继续往后看”的情况。比如T - * F T | ε右部首符号是终结符*没问题但假设文法里有A - B a且ε ∈ First(B)这时候必须继续把First(a)加进去很多同学在这里漏算。另一个容易错的是ε的归属。比如E - T E | ε它的First集里既有又有ε这是正常的。可当你用First(E)去填预测分析表时一定要注意ε不能直接作为输入符号出现在表头表头只放真正的终结符和结束符#。2.3 Follow集合计算记住三条规则Follow集合的定义是在推导过程中可能出现在非终结符A之后的终结符集合。对开始符号我们规定#一定属于它的Follow集。计算Follow集合时别按集合定义去“推导”直接记规则效率最高。对于产生式A - αBβ规则1把First(β) - {ε}加入Follow(B)。规则2如果β可以推出空串或β本身就是空串那么把Follow(A)加入Follow(B)。规则3对开始符号S把#加入Follow(S)。注意区分“First是向后看右部”而“Follow是向前看左部”。计算的时候需要反复迭代直到所有集合不再变化。手工计算表达式文法的Follow集如下非终结符Follow集合E{ #, ) }E{ #, ) }T{ , #, ) }T{ , #, ) }F{ *, , #, ) }这里特别容易漏的是Follow(E)里的)。为什么会有)因为产生式F - ( E )中非终结符E后面跟着终结符)所以)必须加入Follow(E)。同理Follow(E)里也有)因为E处于E的尾巴位置Follow(E)中的符号都会传递给它。我建议在程序里用工作列表法实现维护一个“集合发生变化”的队列每处理完一条产生式如果某个Follow集合变大就把相关产生式重新加入队列。比单纯线性扫描所有产生式直到完全收敛要高效也更容易写对。2.4 Select集合和预测分析表构建有了First、Follow集还不能直接写程序得先把每个产生式的Select集合算出来。Select集合表示“选择这条产生式时当前输入符号允许是哪些”。对产生式A - α如果α不能推出空串则Select(A - α) First(α)。如果α可以推出空串则Select(A - α) (First(α) - {ε}) ∪ Follow(A)。实际上预测分析表就是Select集合的“按行存储”行是左部非终结符列是输入终结符。以表达式文法为例预测分析表如下id*()#EE - T EE - T EEE - T EE - εE - εTT - F TT - F TTT - εT - * F TT - εT - εFF - idF - ( E )注意“空表项”表示遇到这种情况语法错误。如果是LL(1)文法表里每个格子最多只能有一条产生式——如果出现了两条就是文法冲突必须回头检查改造是否正确。我在调试时遇到过一次冲突原因是程序里把ε也算进列名了导致表多出一列查表时永远匹配不到。手工填表的技巧遇到右部以非终结符开头的产生式先看这个非终结符的First集如果包含ε还要再看左部的Follow集。每次填完表最好用“每个格子里有没有重复项”做一次LL(1)验证。3. 代码骨架怎么写从文法数据结构到栈模拟分析3.1 文法存储与终结符/非终结符划分拿到改造后的文法先别急着写集合计算数据结构设计直接影响后面的调试体验。我第一版用一个字符串数组存产生式解析的时候反复做字符串匹配代码写得很乱。后来改成结构体存储清爽很多。一个实用的做法是给每个终结符、非终结符、ε和#都分配整数编号。#作为特殊的输入结束符ε作为特殊的空符号。然后const int MAXN 100; int terminalCount, nonTerminalCount; string symbolName[MAXN]; // 符号名到编号的映射 mapstring, int symbolId; struct Production { int left; // 左部非终结符编号 vectorint right; // 右部符号序列包含空串符号 eps setint selectSet; // 该产生式的Select集合 }; vectorProduction prods;symbolName和symbolId构成双向映射。扫描文法时每遇到一个新符号先判断它是大写字母开头还是小写字母开头还是特殊符号以此划分非终结符和终结符。在表达式文法里E, E, T, T, F是非终结符, *, (, ), id是终结符ε是特殊符号。我建议把id当做一个整体的终结符而不是拆成i和d两个字符。很多输入串是用空格分割token的所以读取输入串前先做个简单分词不然分析器会对“id”产生歧义。3.2 集合计算的迭代算法实现First集计算可以用一个vectorsetint first(nonTerminalCount)来存加上一个布尔数组表示“该非终结符是否能推出空串”。最基本的迭代伪代码如下bool changed true; while (changed) { changed false; for (auto p : prods) { int A p.left; bool canDeriveEps true; for (int sym : p.right) { if (isTerminal(sym)) { if (!first[A].count(sym)) { first[A].insert(sym); changed true; } canDeriveEps false; break; } else { // 非终结符加入其First集除空串 for (int x : first[sym]) { if (x ! epsSymbol !first[A].count(x)) { first[A].insert(x); changed true; } } if (epsNotInFirst[sym]) { canDeriveEps false; break; } // 如果继续扫描下一个符号说明当前符号可空 } } if (canDeriveEps !epsNotInFirst[A]) { epsNotInFirst[A] true; changed true; } } }这里最需要提防的是“中途改集合导致同一轮扫描结果不稳定”。事实上这种循环会一直迭代到不动点才停止所以一轮内改了后面的集合并影响前面也没有关系反正算法保证最终收敛。不过效率一般课程实验规模下完全够用。Follow集计算同理注意初始先把#加进开始符号的Follow集然后反复遍历产生式应用三条规则bool changed true; while (changed) { changed false; for (auto p : prods) { int A p.left; vectorint beta; // 表示A右部中某个符号后面的部分? // 对右部从右向左扫描更方便 setint followA follow[A]; // 从右向左扫描 setint suffixFirst; // 当前符号后面的符号串的First集(含空?) suffixFirst.insert(epsSymbol); for (int i p.right.size() - 1; i 0; --i) { int B p.right[i]; if (isNonTerminal(B)) { // suffixFirst 就是 First(β)其中β是B后面的符号串 for (int x : suffixFirst) { if (x ! epsSymbol !follow[B].count(x)) { follow[B].insert(x); changed true; } } if (suffixFirst.count(epsSymbol)) { for (int x : followA) { if (!follow[B].count(x)) { follow[B].insert(x); changed true; } } } } // 更新suffixFirst: 把First(B)并入 if (isTerminal(B)) { suffixFirst {B}; } else { setint newSuffix; for (int x : first[B]) { if (x epsSymbol) { newSuffix.insert(epsSymbol); // 保留空如果后面还有更多符号 } else { newSuffix.insert(x); } } if (!epsNotInFirst[B]) { newSuffix.erase(epsSymbol); } // 实际要把newSuffix并入suffixFirst但注意规则要把First(B)并入原先的suffixFirst // 并且原suffixFirst中的终结符保留因为它们是B后面的符号产生的 setint merged suffixFirst; for (int x : first[B]) { if (x epsSymbol) { // 空串不能直接留需要视情况决定但可以保留标记 // 这里简化为如果B可空保留eps标记 } else { merged.insert(x); } } if (!epsNotInFirst[B]) { merged.erase(epsSymbol); } else { merged.insert(epsSymbol); } suffixFirst merged; } } } }从右往左扫是经验之谈它能自然实现“如果后面符号串可空就把Follow(A)加给当前B”的规则比从左往右扫好理解得多。上面的代码逻辑稍微复杂但实际写的时候可以先用朴素的“针对每个非终结符对每个产生式匹配”的方式性能不差正确性更重要。3.3 预测分析表生成与冲突检测预测分析表可以定义成二维数组或mappairint,int, int最后一项存产生式编号。生成流程很简单for (int i 0; i prods.size(); i) { int A prods[i].left; setint se prods[i].selectSet; // 已算好的Select集合 for (int a : se) { if (a epsSymbol) continue; // ε不填表 if (table[{A, a}] ! -1) { // 冲突这个格子里已经有一条产生式 cout 文法不是LL(1)文法冲突在: symbolName[A] , symbolName[a] endl; } else { table[{A, a}] i; } } }Select集合的计算可以直接复用前面算好的First和Follow对每个产生式A - α模拟一遍First(α)的推导如果α能推出空串再加上Follow(A)。我当时在这里掉过一次链子把ε也当成了列名表格列数多了一列然后查表时输入的终结符永远进不了ε列导致每次遇到E和)的时候都报错。后来打印表格时发现列名有ε才意识到“预测分析表列名只能是终结符结束符ε只是计算中间量”。建议程序里增加一个printTable()函数把预测分析表按行列打印出来。一来方便人工核对二来写实验报告时可以直接截图。表格打印格式对齐算个小坑但加上宽度控制很快就能解决。3.4 分析栈驱动的语法分析流程表驱动分析的核心是一个栈和一个输入缓冲区。栈底先放#再放开始符号E。输入串token化后末尾加上#。每次循环取出栈顶符号X和当前输入符号a。如果X a匹配成功弹出栈顶输入指针前进。若两者都是#则接受。如果X是终结符且不等于a报错并进入错误恢复。如果X是非终结符查表table[{X, a}]无表项报错当前输入符号需要跳过或采取同步操作。有表项弹出X若产生式右部不是ε就逆序压栈。输出当前栈内容、剩余输入、使用的产生式。核心代码很简洁void parse(const vectorint tokens) { stackint st; st.push(hashSymbol); st.push(startSymbol); int idx 0; while (!st.empty()) { int X st.top(); int a tokens[idx]; printf(栈: ); printStack(st); printf(输入: ); printRemain(tokens, idx); if (X a) { st.pop(); idx; if (X hashSymbol a hashSymbol) { cout 接受 endl; return; } } else if (isTerminal(X)) { cout 错误: 栈顶终结符不匹配 endl; // 错误恢复 } else { int pId table[{X, a}]; if (pId -1) { cout 错误: 预测分析表无表项 endl; // 错误恢复 } else { st.pop(); auto p prods[pId]; printf(用产生式 %s - , symbolName[X].c_str()); for (int s : p.right) printf(%s , symbolName[s].c_str()); printf(\n); for (int i p.right.size() - 1; i 0; --i) { if (p.right[i] ! epsSymbol) st.push(p.right[i]); } } } } }注意压栈顺序产生式右部X - α β γ在推导时α最先被展开所以压栈时要先压γ再压β最后压α保证α在栈顶。很多人第一次会写反导致推导顺序完全错乱输出的分析树也很奇怪。4. 实测最容易翻车的五个地方和排查思路4.1 把表驱动写成了隐式递归下降我第一版代码写完自以为逻辑正确但跑测试时发现输出里完全没有“预测分析表”的参与只是顺着输入串递归调用函数。仔细一查发现我在外层循环里用了一个全局指针然后每个非终结符的处理函数内部又循环消费token互相调用。这本质上是递归下降分析器只不过披了一层表驱动的外壳。它也能工作但实验要求的是“栈模拟”两者的输出形式根本不同而且无法体现预测分析表的动态查表过程。要分清楚在表驱动里所有推导步骤都必须由查表驱动而不是由函数调用驱动。我把每个非终结符的分析函数都删掉统一改成“查表压栈”代码量一下少了一半逻辑也清晰多了。写之前一定要想明白“谁在驱动循环”——是栈顶符号和输入符号而不是当前非终结符函数。4.2 空串符号带来的连锁问题ε是实验里最大的隐形杀手。它有三个表现集合计算时ε的存在让“First(α)可能为空”的判断变得复杂。预测分析表不包含ε列但Select集里又必须保留ε用来决定是否加入Follow集。代码里如果用string存产生式很容易把空串判断写成if (right.substr(0,1) ε)结果在C字符串比较时踩编码坑。很多同学的实验环境默认用GBK编码而编辑器里存的是UTF-8字符串一比较就失败报错完全莫名其妙。我的建议是不要用中文字符“ε”作为内部符号直接用一个整数常量epsSymbol -1表示空串输出的时候再转成字符串“ε”用于展示。这样既能避免编码问题也让逻辑判断更加清晰。4.3 构造表达式文法时预览表的冲突现场有一次为了复杂化实验我加了一条产生式E - T E | T想着多一种选择。结果预测分析表里E行、列同时出现了两条产生式程序直接报“文法不是LL(1)”。这种冲突不是程序bug而是文法本身的问题。我当时花了不少时间检查代码最后回头看文法发现就是自己画蛇添足。这也提醒我预测分析表的冲突就是LL(1)判定的最终标准与其手工分析不如靠程序输出冲突位置。针对这种情况正确的做法是保留 T E放弃 T因为后者只是前者的一个特例E继续推导成ε而已。观察E的递归结构会发现 T作为独立产生式时First( T) {}而Select(E - T E) {}两者重合必然冲突。这也能看出提取左因子的重要性——如果提前把 T提取成公共前缀就不会有这个问题。4.4 错误恢复的同步符号设计实验要求里通常不强制要求错误恢复但老师检查时十有八九会输入类似i*i这样的非法串。如果你只做“报错并停止”会显得不够完善。LL(1)错误恢复有一种简单的方式是用Follow集做同步符号。核心思想是当栈顶非终结符A遇到无法匹配的输入符号a时如果a ∈ Follow(A)我们可以弹出A因为“在推导中A之后出现a是合理的A可以推导结束”否则跳过输入符号a。不过这属于扩展功能我建议至少实现一个版本遇到错误时打印错误位置和期望的符号集合然后选择跳过当前输入符号继续分析下去。例如输入i*i经过E - T E、T - F T、F - id后栈里为T E输入符号查表T遇应该用T - ε然后E遇用E - T E正确。再往后T期望F但遇到*则报错。如果同步符号设计合理程序可以恢复并报告“第4个token处出现错误”。4.5 循环不收敛和打印死循环集合计算的循环如果判断条件写错经常出现死循环。我遇到的一次是epsNotInFirst数组初始值全为false然后迭代时没有初始的“终结符不能推空串”标记导致所有非终结符最终都变成可空First集爆掉产生式无限生成。调试办法是在循环体里打印迭代轮数和每个集合大小如果两三轮后大小还在涨基本就是空串传播出现逻辑漏洞。栈驱动的循环也有死循环风险如果预测分析表里存在A - A这种产生式压栈后栈顶还是A永远无法推进。正常文法不会有这种产生式但程序里要加一个“步骤上限”保护比如超过100步就强制终止避免失控输出。我调试时遇到过因为终态判断错误栈空了还在查表程序崩溃的情况——正确做法是把#也放在栈里和输入末尾只有两者同时相遇才接受。5. 测试用例怎么设计覆盖正例、反例和边界5.1 基础表达式测试用例实验报告里至少要列一组正例展示分析过程。我常用的测试串如下id - 单个标识符 id id - 加法 id * id - 乘法 (id) - 括号 (id id) * id - 括号与优先级 id id * id - 验证乘法的优先级 id (id * id) - 括号改变优先级每一个正例程序应该输出完整的栈变化序列和使用的产生式。以id id * id为例它是最能展示“乘法比加法更紧密”的过程分析时E先推导成T ET又推导成F TF匹配id然后T遇到时选择空产生式把控制权交回EE再推导成 T E。这一连串动作能把T - ε和E - T E这两条最容易混淆的产生式完整暴露出来。我强烈建议手动推一遍id id * id的分析过程再和程序输出核对。因为很多人的程序输出看着“每一步都对”但stack弹出的顺序和实际最左推导不一致只是碰巧结果正确。5.2 非法输入的定位与报错反例至少要准备以下几类完全无法开始的输入* id在第一步查表E遇到*就无表项。中间出错id * id在T遇到*时出错。括号不匹配(id id栈里出现)但输入已经结束。多token粘连id id)多了一个右括号。对于(id id这种输入因为输入末尾的#不等于期待中的)程序应该在某个节点报错。如果没有错误恢复机制直接停机也算正常如果做了同步就要输出错误后把残余的栈清掉。测试时重点关注报错信息是否包含“位置”和“期望符号”老师往往会看这一项。我自己的错误信息格式类似[第3个token附近] 栈顶非终结符 T 遇到 * 在预测分析表中无表项。 期望输入可能来自: First(T) 中的终结符集合。有了这个信息调试和写报告都很方便。5.3 扩展测试改变文法后回归实验要求如果只写“对给定文法”那只要上面测试过就行。但如果你想多得一点分可以额外测试改造后的文法能否处理更复杂的产生式。比如把F扩展为支持数字和负数F - ( E ) | id | num | - F加上- F之后First(F)变成{ (, id, num, - }Follow集和预测分析表都会变。你要重新计算集合、重新建表再回归之前的正例。这个过程能测试程序的可复用性如果集合计算是自动的那么只需要改文法定义就能生成新表。如果之前你把First、Follow、表全部硬编码在代码里那么改起来会非常痛苦。我后来把实验架构改成了“文法驱动”启动时从一个文本文件读文法程序自动算集合、建表、开始分析。这样换文法不需要改代码缺点是文件读取和解析多了一堆代码。如果实验时间紧张还是用硬编码文法加自动计算集合的折中方案比较好。6. 答辩和报告里那些容易被追问的点6.1 报告里必须写清楚的三张表实验报告通常要求包含文法改造前后对比、First集、Follow集、预测分析表。但很多同学只贴程序输出没有展示“怎么算出来的”。我建议至少画一张手工推导的表格比如列举Follow(F)的计算过程产生式T - * F T中F后面是TFirst(T) {*, ε}所以*加入Follow(F)。由于ε ∈ First(T)还需要把Follow(T)加入Follow(F)。由T - F TFollow(T)加入Follow(T)而Follow(T) {, #, )}等等。这种“推导链路”比直接写最终结果有价值的多。老师看报告时最反感的就是结果正确但过程残缺会怀疑你是不是抄代码算出来的。6.2 老师最爱问的几个问题我参加课堂检查时被问到最多的几个问题为什么这个文法要消除左递归不消除会怎样——要答出“左递归会导致分析器无限递归或预测分析表多重入口”。First集和Follow集各有什么用——First管“可能以什么开头”Follow管“后面允许跟什么”二者共同决定Select集。栈里为什么要放#——作为唯一的结束标志当栈顶和输入同时为#时表示整个输入串恰好被最左推导完成。如果预测分析表有冲突代码会怎样——程序应该暴露冲突并拒绝生成表而不要静默覆盖。错误恢复里的同步符号为什么用Follow集——因为当非终结符A在栈顶却无法匹配时弹出A意味着“认为A到此结束”此时只有Follow(A)中的符号才是合理的后续输入。不要背答案最好现场用表达式文法举例说明。我当时的回答方式是拿出打印好的预测分析表指着E和)那一格说“这里填了E - ε因为)在Follow(E)里所以当E分析完括号内的表达式遇到)时它能安全退出”。6.3 一个小技巧打印输出带上产生式编号不管是调试还是截图写报告所有输出都带上产生式编号会方便很多。比如输出步骤 3: 栈顶 E输入 查表得到产生式 (2) E - T E这样老师和 TA 能一眼看出你的分析器每一步在做什么。我甚至在程序里加了一个traceMode开关测试时开着交付时关掉最终输出简洁一些。另外实验目录里最好保留一个testcases.txt文件把几十个正反例都放进去写一个批处理脚本跑一遍输出结果存成日志。这样就算临时答辩打断你的思路你也能立刻拿出“全部测试通过”的证据比现场敲命令稳得多。最后再分享一点个人体会LL(1)实验是我整个编译原理课程里投入产出比最高的一个它逼着我把形式语言理论和实际代码串成一条线。如果你正在做这个实验不要急着找现成代码先自己手工推一整套First、Follow、预测分析表再去写程序。推完之后你会发现程序里的每个分支都有据可依报错信息也能一眼看懂。等你把栈驱动的输出跑通那一刻回头看课本上的那些定义会突然觉得它们不再是公式而是一个个具体的动作。