最近在做编译原理的课程设计花了两个通宵把 LL(1) 分析器从零写通顺便把语法树也建起来了。过程中踩了不少坑也把课本上那些“看懂了但没完全懂”的概念真正落到了 C 代码里。这篇文章想把整条链路完整讲清楚从文法改造、FIRST/FOLLOW 集合计算、预测分析表构造到表驱动分析主循环和语法树的同步构建最后附上我调试时的实测经验。适合正在学编译原理、准备期末或者要交课程设计的同学如果已经能背出 LL(1) 的定义但写不出代码那这篇正好是给你准备的。1. 先别急着敲代码LL(1) 分析的前置工作是把文法“伺候”舒服很多人打开 IDE 就想直接写parseE()、parseT()结果递归下降跑起来栈溢出或者表驱动分析行为完全不可控。归根结底不是代码写得不好而是原始文法根本不适合 LL(1) 分析。LL(1) 这个名字本身就代表约束从左到右扫描输入L、最左推导L、向前看 1 个符号1。能满足这种约束的文法必须没有左递归且任意非终结符的多个候选式之间不能出现“选择困难”。1.1 为什么原始算术表达式文法不能直接用课本上经典的算术表达式文法长这样E - E T | T T - T * F | F F - ( E ) | id这个文法能描述算术表达式但它是左递归的。直接拿去做递归下降分析parseE()一上来就要匹配E T于是内部再调用parseE()永远不消耗输入最终栈溢出。如果是表驱动分析问题同样致命预测分析表里M[E][id]这个格子既要填E - E T又要填E - T因为这两条产生式右侧都能以id开头。同一格子两条产生式这就是冲突。LL(1) 分析器面对这种冲突毫无办法所以第一步一定是消除左递归。1.2 消除左递归的具体操作直接左递归的模式很固定如果非终结符 A 有产生式A - A α | β其中 β 不以 A 开头那么可以改写成A - β A A - α A | ε注意看这个变换的精髓原本 A 在推导中最左边不断展开自己死后重生变成 AA 的作用是“把尾巴接完”。把 A 看成“剩余部分”它能推导出空串也就是尾巴没有了。应用到算术表达式文法上E - E T | T E - T E E - T E | ε T - T * F | F T - F T T - * F T | εF - ( E ) | id本身没有左递归保持不动。改造后的完整文法E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id消除左递归之后parseE()先调parseT()再调parseE()每次调用都会消耗至少一个终结符或者直接结束不会出现无限递归。1.3 提取左因子把“选择困难”杜绝掉左递归处理完之后还有一个问题同一个非终结符的多个候选式以相同符号开头。比如一个 if 语句的简化文法stmt - if ( expr ) stmt | if ( expr ) stmt else stmt当分析器看到stmt且当前输入是if时两条产生式都以if开头该选哪条LL(1) 没法选。解决办法是提取公共前缀stmt - if ( expr ) stmt opt_else opt_else - else stmt | ε这种变换叫提取左因子left factoring。它的思想是把“共同开头”单独拎出来剩下的选择推迟到后面用新引入的非终结符来表示。opt_else能推出else stmt也能推出空串实际上就是把“悬空 else”问题用文法结构消解掉了。1.4 改造完之后怎么自查动手写代码之前一定要先验证文法满足 LL(1) 条件。自查逻辑很简单没有左递归任何非终结符经过若干步推导都不能回到以自己开头的产生式。候选式 FIRST 集不相交同一个非终结符的任意两个产生式A - α和A - βFIRST(α) ∩ FIRST(β)必须为空。ε 产生式的附加条件如果某个候选式能推出空串那么FIRST(A)的其他元素和FOLLOW(A)不能有交集。用改造后的算术表达式文法逐条验一遍会发现全部满足。这一步一定不能跳我见过不少同学文法是临时想的结果费了半天劲把分析器写完一跑就冲突回头才发现是文法本身不满足 LL(1)。2. FIRST 与 FOLLOW 的计算与其背结论不如写一个固定点迭代FIRST 和 FOLLOW 是 LL(1) 分析的地基预测分析表全指望这两组集合。我建议别去背那些复杂的定义直接从直觉入手FIRST(A)是“A 能推出的串开头可能是哪些终结符”。FOLLOW(A)是“在推导过程中A 的后面可能紧跟哪些终结符”。如果你把它们当成集合运算来做代码写起来会非常顺。核心方法是固定点迭代不断应用规则往集合里加元素直到某一轮没有任何集合发生变化循环终止。2.1 先计算“可空集合”nullable为什么先算这个因为要判断“某个符号是否能推出空串 ε”。这直接影响 FIRST 和 FOLLOW 的迭代逻辑。可空集合的计算规则只有两条终结符永远不可空非终结符 A 可空当且仅当存在产生式A - ε或者存在A - X1 X2 ... Xn且每个Xi都可空。C 里的迭代写法// 判断产生式右侧是否全为空即 rhs 所有符号都可空 bool rhsAllNullable(const vectorstring rhs, const setstring nullable) { for (const auto sym : rhs) { if (sym EPS) continue; if (!nullable.count(sym)) return false; } return true; } setstring nullable; bool changed true; while (changed) { changed false; for (const auto prod : grammar) { if (rhsAllNullable(prod.rhs, nullable) !nullable.count(prod.lhs)) { nullable.insert(prod.lhs); changed true; } } }这里 EPS 我用#来表示空串避免和空字符串混淆。nullable一开始只包含那些能直接推导出 ε 的非终结符对应的产生式通过多轮迭代那些“间接可空”的非终结符也会被逐渐加进来。2.2 FIRST 集合的固定点迭代框架有了 nullable算 FIRST 就轻松多了。先说迭代思路初始化每个终结符 t 的FIRST[t] { t }。不断遍历每条产生式A - X1 X2 ... Xn把右侧符号串的 FIRST 加进FIRST[A]。直到某轮没有任何集合变大结束。这里的关键是“右侧符号串的 FIRST”怎么算我封装成一个函数firstOfSequencesetstring firstOfSequence(const vectorstring rhs, const setstring nullable, const mapstring, setstring first) { setstring result; bool allNullable true; for (const auto sym : rhs) { if (sym EPS) continue; if (isTerminal(sym)) { result.insert(sym); allNullable false; break; } // 非终结符把它的 FIRST 全部加进来 const auto fset first.at(sym); result.insert(fset.begin(), fset.end()); // 如果这个符号不能推出空就不用往后看了 if (!nullable.count(sym)) { allNullable false; break; } } if (allNullable) result.insert(EPS); return result; }注意isTerminal的判断我建议把所有终结符和非终结符统一放进setstring而不是靠“是否大写字母开头”这种规则硬判不然像id这种多字符终结符会出问题。主循环如下mapstring, setstring first; for (const auto t : terminals) first[t].insert(t); changed true; while (changed) { changed false; for (const auto prod : grammar) { auto seqFirst firstOfSequence(prod.rhs, nullable, first); for (const auto sym : seqFirst) { if (!first[prod.lhs].count(sym)) { first[prod.lhs].insert(sym); changed true; } } } }每次循环结束比较所有集合的大小有没有变化只要有一个集合变大了就说明还可以继续推直到稳定。这个思路在 FOLLOW 里同样用。2.3 FOLLOW 集合跟着产生式“向后看”FOLLOW 的计算比 FIRST 绕一点但代码结构几乎一样。规则有三条把$加入FOLLOW(开始符号)表示句子结束。对产生式A - α B β把FIRST(β)中除 ε 以外的符号加入FOLLOW(B)。如果 β 能推出空串包括 β 为空的情况把FOLLOW(A)整体加入FOLLOW(B)。第三条是大家最容易漏的。它的直觉是如果 B 后面跟着的那一串 β 最终能“消失”那么 A 后面能出现什么B 后面也能出现什么。代码实现mapstring, setstring follow; follow[startSymbol].insert(END); // END $ changed true; while (changed) { changed false; for (const auto prod : grammar) { const auto A prod.lhs; for (size_t i 0; i prod.rhs.size(); i) { const string B prod.rhs[i]; if (isTerminal(B)) continue; // 取 B 后面的符号串 beta vectorstring beta(prod.rhs.begin() i 1, prod.rhs.end()); auto fbeta firstOfSequence(beta, nullable, first); // 规则2FIRST(beta) 非 ε 部分加入 FOLLOW(B) for (const auto t : fbeta) { if (t ! EPS !follow[B].count(t)) { follow[B].insert(t); changed true; } } // 规则3beta 可空时FOLLOW(A) 加入 FOLLOW(B) if (fbeta.count(EPS)) { for (const auto t : follow[A]) { if (!follow[B].count(t)) { follow[B].insert(t); changed true; } } } } } }我排查过一个问题有些实现把规则 3 无条件执行了不判断 beta 是否可空这会导致 FOLLOW 被无脑放大分析表多出一堆错误条目。真正笔试题里也爱挖这个坑代码里更是要谨慎。2.4 很少被注意到的边界情况计算 FIRST/FOLLOW 时有几个边界情况值得提空产生式A - ε的firstOfSequence返回{ε}所以它会把自己的EPS加入FIRST(A)。开始符号的 FOLLOW必须包含$否则M[开始符号][$]会是空条目输入正确时反而报错。嵌套的可空链比如A - B CB可空C可空那么FIRST(A)一定包含所有FIRST(B)、FIRST(C)和EPS。firstOfSequence里通过“遍历到不可空符号就 break”的方式天然处理了这种情况。我第一次实现时为了省事把 FIRST 和 FOLLOW 硬编码在代码里结果换文法就得改源码非常痛苦。后来老老实实写成通用迭代算法整个项目一下活过来了。这一步值得花时间。3. 预测分析表把所有决策固化成一张查找表FIRST 和 FOLLOW 算完后下一步是构造预测分析表。表驱动分析的本质是把“遇到非终结符 A、看输入符号 a该用哪条产生式”这个决策提前算好运行时只查表不做任何推导。LL(1) 的“决定性”就体现在这张表里。3.1 表的数据结构设计表是二维的行是非终结符列是终结符包括$格子内容是产生式。C 里最直观的做法是mappairstring, string, intint是产生式的编号。mappairstring, string, int table; // key: (非终结符, 终结符)value: 产生式下标为什么不用二维vectorvectorint因为终结符不是连续的字符还要维护一套符号到下标映射代码可读性差。用map查起来直接后面调试打印也方便。3.2 填表的两条规则表不是凭空填的就两条规则对产生式A - α对FIRST(α)中每个非 ε 终结符a把M[A][a]填成A - α。如果 ε 属于FIRST(α)对FOLLOW(A)中每个终结符b把M[A][b]填成A - α。口诀是“开头符号直接填候选能空找后继”。这背后的逻辑很直白分析器看到栈顶 A、当前输入 a如果 a 有可能是 α 推出串的开头那么用 α 展开一定能匹配上如果 α 能推出空串那只有 a 属于 FOLLOW(A) 时才应选择 α相当于让 A 静悄悄消失把匹配的希望交给后面的符号。填表代码逻辑void buildTable() { for (size_t i 0; i grammar.size(); i) { const auto prod grammar[i]; auto fset firstOfSequence(prod.rhs, nullable, first); for (const auto t : fset) { if (t ! EPS) setEntry(prod.lhs, t, i); } if (fset.count(EPS)) { for (const auto t : follow[prod.lhs]) { setEntry(prod.lhs, t, i); } } } }setEntry里必须检查冲突void setEntry(const string A, const string a, int prodIndex) { auto key make_pair(A, a); if (table.count(key)) { cerr 分析表冲突: A 在输入 a 上同时匹配第 table[key] 和第 prodIndex 条产生式 endl; cerr 该文法不是 LL(1) 文法 endl; exit(1); } table[key] prodIndex; }很多同学填表时不检查冲突后面出现“这个输入明明该接受却报错”之类的问题根本没处查。一发现冲突就立刻暴露文法问题反而是最高效的调试方式。3.3 一张完整的预测分析表长什么样用前面改造后的算术表达式文法完整表如下数字是产生式编号1: E - T E 2: E - T E 3: E - ε 4: T - F T 5: T - * F T 6: T - ε 7: F - ( E ) 8: F - id非终结符id*()$E11E233T44T6566F87注意 E 行里)和$都填了产生式 3因为FOLLOW(E) {), $}。T 行同理、)、$都填了产生式 6。这张表就是后续分析器的“决策中枢”。4. 表驱动分析主循环与语法树的同步构建表造好之后分析器本身反而很简单了但“怎么边分析边建树”是另一个难点。我一开始只实现了分析器能输出产生式序列但不会建树。后来把语法树加上去才把整个流程盘活。4.1 为什么栈里存的是“符号 节点指针”如果把分析栈只设计成stackstring分析完成后你顶多知道用了哪些产生式但树形结构是丢的。要建树必须让每个栈元素既能表示符号又能追踪到内存中对应的树节点。我定义了两个结构体struct TreeNode { string symbol; vectorTreeNode* children; }; struct StackItem { string symbol; TreeNode* node; };每次往栈里压符号时同时创建一个TreeNode并挂到父节点上这样语法树就和分析过程同步生长。等分析结束根节点就是完整语法树。4.2 主循环的三分支结构分析循环的逻辑很固定每次看栈顶 X 和当前输入 aX 是终结符且 X a匹配成功弹出栈顶输入指针后移。这是“消耗”动作。X 是非终结符查表M[X][a]有产生式弹出 X取产生式X - Y1 Y2 ... Yn创建 Y1...Yn 的子节点挂到 X 的节点下然后把 Yn...Y1 逆序压栈。这是“展开”动作。其他情况报错进入错误恢复。核心代码结构如下bool analyze(const vectorstring input, TreeNode* root) { stackStackItem stk; root new TreeNode{startSymbol, {}}; stk.push({END, nullptr}); stk.push({startSymbol, root}); size_t ip 0; while (!stk.empty()) { StackItem top stk.top(); if (top.symbol END input[ip] END) return true; if (isTerminal(top.symbol)) { if (top.symbol input[ip]) { stk.pop(); ip; } else { reportError(终结符不匹配, top.symbol, input[ip]); return false; } } else { auto key make_pair(top.symbol, input[ip]); auto it table.find(key); if (it table.end()) { reportError(分析表无条目, top.symbol, input[ip]); return false; } const Production prod grammar[it-second]; stk.pop(); // 空产生式不创建子节点 if (prod.rhs.size() 1 prod.rhs[0] EPS) continue; vectorTreeNode* children; for (const auto sym : prod.rhs) { auto* child new TreeNode{sym, {}}; top.node-children.push_back(child); children.push_back(child); } // 逆序压栈保证下一个栈顶是产生式右侧第一个符号 for (int i (int)children.size() - 1; i 0; --i) { stk.push({prod.rhs[i], children[i]}); } } } return false; }一个容易被忽略的细节空产生式不创建子节点。因为ε在语法树中不产生叶子如果硬给E加一个 ε 孩子后面打印树的时候全是空节点很乱。4.3 手工追踪一个输入串id id * id纸上谈兵不如实际走一遍。用id id * id这个输入串初始栈是[ $ E ]栈顶在右初始输入是id id * id $步骤栈栈顶在右输入串动作1$ Eid id * id $E - T E2$ E Tid id * id $T - F T3$ E T Fid id * id $F - id4$ E T id * id $T - ε5$ E id * id $E - T E6$ E T id * id $终结符匹配7$ E Tid * id $T - F T8$ E T Fid * id $F - id9$ E T* id $T - * F T10$ E T F *id $终结符*匹配11$ E T Fid $F - id12$ E T$T - ε13$ E$E - ε14$$接受注意第 4 步和第 13 步T 和 E 通过 ε 产生式直接“消失”这正是 FOLLOW 集发挥作用的地方看到时知道T - ε可以接受看到$时知道E - ε可以接受。分析过程同步生成的语法树缩进展示E ├── T │ ├── F │ │ └── id │ └── T │ └── ε ├── E │ ├── │ ├── T │ │ ├── F │ │ │ └── id │ │ └── T │ │ ├── * │ │ ├── F │ │ │ └── id │ │ └── T │ │ └── ε │ └── E │ └── ε这里的 ε 节点我一般不打出来只保留实际参与匹配的叶子。打印时用递归缩进就行void printTree(TreeNode* node, int depth) { for (int i 0; i depth; i) cout ; cout node-symbol endl; for (auto* child : node-children) printTree(child, depth 1); }要不要打印 ε 节点可以根据需求决定但数据结构上保留空产生式的判断会更清晰。4.4 为什么说“产生式序列正确”不等于“树正确”这里提醒一个容易掉进去的误区分析器跑出“接受”不代表语法树一定对。树建错的情况往往出在子节点顺序或逆序压栈环节。我曾经在压栈时用for (int i 0; i n; i)压栈结果第一个符号跑到栈底去了整棵树兄弟节点顺序颠倒还得回头调。后来养成的习惯是先在纸上画出期望的树再让程序打印出来跟预期比对。尤其是id id * id这种能验证结合优先级的用例比一句“程序跑通了”靠谱得多。5. 联调与踩坑为什么你的分析器“误判”表驱动分析看着简单实际联调时问题集中在几个地方。我把自己踩过和帮同学排查过的坑整理成了一份问题清单按出现频率排序。5.1 最容易翻车的三个技术细节终结符/非终结符判断我用了一个isTerminal(string)函数判断方法是看符号是否在terminals集合里。这个集合初始化时要包含所有终结符包括id、、*、(、)、$。有人偷懒用isupper(s[0])判断非终结符一旦遇到id这种多字符终结符就废了。集合迭代的终止条件FIRST/FOLLOW 的迭代循环如果忘了写“没有变化就退出”可能会死循环。尤其是文法里有A - B和B - A这种互相引用的产生式时集合不会无限变大但循环要一直跑。每次迭代后比较集合大小或直接比较整个map是否相等都可以。FOLLOW 的可空判断A - α B β中只有β可空时才能把FOLLOW(A)加入FOLLOW(B)。这个条件漏掉会导致 FOLLOW 集合偏大分析表多填条目但程序不会直接崩而是接受了一些本不该接受的输入。这种 bug 最难查因为输出看起来“还挺正常”。5.2 用测试用例验证分析器正确性我总结了这样一组用例每条都对应不同的文法路径输入串预期结果验证点id接受最简单路径id id接受运算符id id * id接受优先级*比高( id id ) * id接受括号表达式id * id拒绝或报错恢复*后面紧跟非法 id拒绝或报错恢复表达式不能以开头( id拒绝或报错恢复缺右括号测试时我建议每一步都打印“栈 | 输入 | 动作”这个输出能直接和论文里的分析过程对照也是答辩/报告里最好用的演示材料。5.3 错误恢复想拿高分不能只报“语法错误”LL(1) 分析器的错误恢复在课程设计里是加分项考试中也喜欢考。常见策略有三种panic mode恐慌模式遇到空表项或终结符不匹配直接丢掉当前输入符号直到遇到同步符号为止。实现最简单但不考虑上下文可能跳过一些本不该跳的 token。同步符号法利用 FOLLOW 集。每个非终结符 A 对应的表行里把FOLLOW(A)中的终结符标记为同步synch。当栈顶是非终结符 A、但查表无条目且当前输入属于FOLLOW(A)时直接弹出 A等于让 A “消失”继续分析后续符号。插入法当发现缺失某个符号时把它当作虚拟 token 插入输入流不弹栈继续分析。适合交互式环境但实现复杂。同步符号法在 LL(1) 分析器里最常用因为它不需要大改代码在填表时多加一步for (const auto t : follow[A]) { syncTable[{A, t}] true; }注意错误恢复和语法树构建之间存在冲突。一旦报告错误后续展开的树节点实际上已经不可信了。我处理的方式是分析出错时只打印错误信息不再继续建树返回 false 退出。如果你需要“恢复后继续分析”建议在语法树层面做一个标记把错误点之后的子树隔离避免误用。5.4 过来人的几个实在建议第一把 FIRST、FOLLOW 和分析表作为独立模块先跑通。不要一上来就写主循环而是先把这三样输出打印出来和书上/作业答案对一遍。集合不对后面全白搭。第二符号统一用常量。const string ID id; const string EPS #; const string END $;都放在全局或命名空间里代码里不要出现裸字符串。我见过同学因为大小写不一致查错查了一下午最后发现是Id和id的问题。第三代码模块化。分析器和建树分开看先确保产生式序列正确再让树节点跟着搭起来。如果一开始就把树逻辑塞进主循环bug 会加倍因为你要同时排查“分析错”和“建树错”两件事。第四可视化输出很加分。语法树用缩进打印是最低要求如果再进一步导出成括号表达式比如(E (T (F id)) (E ( ...)))后面做语义分析时也很顺手。最后再分享一个小技巧如果你调试时发现某个输入串的行为不对先别急着看代码拿笔在纸上模拟一遍表驱动分析把每一步的栈和输入写出来。分析器本质上就是一台状态机纸上的轨迹和程序输出一对偏差位置马上就能定位到是集合算错了、表填错了还是主循环写错了。这个方法救了我至少两次通宵。