企业官网建设流程全解析

简介：这份编译原理语法分析实验资料面向正在学习编译原理、需要完成递归下降语法分析课程实验的高校学生，重点解决如何基于已有词法分析结果识别各类语法成分的问题。资料对应C++实现，要求按文法规则用递归子程序法逐一分析语法成分，并处理testfile.txt输入与output.txt输出，按单词顺序输出词法信息，在指定语法成分结束前另起一行输出形如“<常量说明>”的名称，适合用来对照实验要求理解分析流程。压缩包共2个文件，包含1个doc问题说明文档与1个cpp源码文件，整体约17KB，体积轻便，便于直接查看和编译调试。该实现已在CG实验平台满分通过，已有6110人学习，可作为课程实验的参考方案，帮助读者梳理递归子程序的组织方式、输出格式细节与评测要点，并在此基础上完成自己的语法分析程序。

1. 从「能跑通的 parser」到「知道它为什么不会崩」

写一个能跑通的语法分析器，是整个编译原理实验里最快的一步；真正耗时间的是它在你以为完工之后的第一次翻车——输入一个少了右括号的表达式，程序既不报错也不退出，而是原地打转、调用栈越压越深，最后直接崩掉。C++ 版的语法分析实验之所以值得认真拆一遍，是因为它把「词法 Token 流 → 文法产生式 → 分析表 → 归约动作」这条链路完整摊开了：递归下降里的每一次前瞻、FIRST/FOLLOW 的不动点迭代、LR 项目集的闭包运算，全都是可以单步跟到底的确定性过程。搞懂这条链路，你才分得清错误出在哪一层，也才明白为什么两种构造路线给出的错误信息差得那么远。

2. Token 流与文法：语法分析的输入契约

任何语法分析器都不直接读源码字符，它读的是两样东西：一条已经被词法器规整过的 Token 序列，以及一份用产生式写死的文法。这两样东西构成了分析器的全部输入契约——契约定得糙，后面所有算法都会跟着糙。血泪经验是，很多人把注意力全放在 LL(1) 或 LR(1) 的算法本身上，结果真正让程序行为诡异的，是 Token 里没带行号、产生式里拿字符串当符号比较这类看起来无关紧要的表示问题。

2.1 Token 结构：哪些字段必须从扫描器一路带进分析器

Token 是词法器和语法分析器之间唯一的交接物，它的字段设计直接决定了后面错误报告能做到多细。最小值是一个类型枚举，但要真正可用，必须把源码位置和原始词素一起带过去。

enum class TokenKind { ID, NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, LBRACE, RBRACE, ASSIGN, SEMI, KW_IF, KW_WHILE, END_OF_FILE, INVALID }; struct Token { TokenKind kind; // 分派用，必须是枚举而不是字符串 std::string lexeme; // 原始词素，"x1" 和 "x2" 都是 ID，但它们不是同一个标识符 int line; // 扫描器填，分析器只读 int column; // 报错时定位到列，比只有行号好用得多 double numValue; // NUMBER 时预先把字面量转好，parser 里不再做字符串转数字 };

kind是分析器做分支判断的唯一依据，用枚举是因为后面的预测分析表、LR 动作表都是拿它当二维数组的下标，用字符串查表会让整个循环慢一个数量级。lexeme看起来冗余，但它是变量声明和变量引用能被认成同一个符号的前提——两个ID类型的 Token，只有靠lexeme才能判断是不是同一个名字，语法分析阶段可以不做这个判断，但一旦你顺手建符号表，它就是唯一来源。

line和column必须由扫描器在消费字符时填好，不能让分析器事后去猜。原因是词法器在跳过空白和注释的时候，位置信息是它唯一知道而分析器永远不知道的东西；分析器手里只有一条 Token 序列，它已经看不到原始换行符了。新手最常犯的错是只保留line，报错时输出「第 17 行附近有语法错误」，而实际上 17 行可能是一整个函数体，定位到列才能让人一眼看出问题。

numValue属于可选项，但它体现了一个更普遍的设计取舍：能在前面做完的转换不要留到后面。分析器一次运行可能对同一个 Token 做多次前瞻比较，如果每次都拿字符串重新解析数字，这部分开销会白白叠在分析热路径上。

2.2 产生式的内存表示：为什么符号要 id 化而不是比字符串

如果说 Token 是输入侧的契约，产生式就是文法侧的契约。实验里最常见的做法是从一个文本文件里读 BNF，每行一条产生式。读进来之后怎么存，决定了后面所有集合运算的性能和正确性。

struct Symbol { enum Type { Terminal, NonTerminal } type; int id; // 全局符号表下标，所有比较、查表都用它 std::string name; // 只用于打印和调试 }; struct Production { int lhs; // 左部非终结符的 id std::vector<int> rhs; // 右部符号 id 序列，空 vector 表示 ε int index; // 产生式编号，分析表里存的就是它 }; // 全局符号表：读文法时统一分配 id，终结符和非终结符共用一张表但 id 区间分开 class Grammar { std::vector<Symbol> symbols; std::vector<Production> productions; std::vector<int> prodsOf; // 按非终结符 id 索引，快速拿到它的所有产生式 };

符号id化这件事，在文法规模只有二三十条产生式的时候看不出好处，但 LR 项目集构造里，闭包运算要对每个项目反复查「点后面这个符号是不是非终结符」、再取出它的所有产生式。如果每次都是字符串比较加哈希查找，一个中等规模的文法能让你等上十几秒，而用整数下标就是 O(1) 数组访问。更要命的是正确性：字符串比较容易出现「同一个名字被分配了两个不同符号对象」的情况，这在打印调试时完全看不出来，但会导致 FIRST 集算出来缺元素。

rhs用std::vector<int>而不是std::string，还有一个隐性好处：空 vector 天然表示 ε，不需要额外用一个特殊字符串去约定。很多人用空串或者"ε"当占位符，结果在后面判断「这个产生式能不能推出空」的时候到处漏判。

index字段也不是可有可无的。分析表里不管是 LL(1) 的table[非终结符][终结符]还是 LR 的动作表，存的值都应该是产生式编号，而不是产生式对象的指针或拷贝。编号是稳定的、可序列化的，调试时把它打印出来就能直接对应到文法文件的第几行。

2.3 词法错误与语法错误的分界线，以及各自的恢复策略

这两类错误的边界经常被搞混，但它们从定义到处理方式都应该完全分开。

词法错误是「字符不在字母表里」——比如出现了一个@，而你的语言里没有这个符号。这类错误的判断不依赖任何上下文，扫描器在读到这个字符的瞬间就可以确定。处理方式是跳过该字符、记录一条错误、继续扫描下一个 Token。原因是词法器没有能力做上下文推断，它唯一能做的就是保证输出一条尽可能长的、合法的 Token 流。

语法错误是「Token 序列不符合文法」——比如if ( x > 0 { ... }，少了一个右括号。这类错误必须由分析器判断，因为它取决于当前处在哪个非终结符的展开过程中。处理方式通常是 panic mode：报错之后丢弃输入，直到遇到一个能重新同步的 Token，最常见的选择是当前非终结符的 FOLLOW 集里的符号，或者分号、右花括号这种天然的分隔符。

// LL(1) 预测分析表命中空项时的 panic 恢复 void recoverLL(int nonTerminal, Token cur) { reportError(cur.line, cur.column, "unexpected token"); // 同步集：该非终结符的 FOLLOW 集 + 语句结束符 const auto& sync = followSet[nonTerminal]; while (cur.kind != TokenKind::END_OF_FILE && !sync.count(cur.kind)) { cur = nextToken(); // 关键：必须推进输入，否则死循环 } // 栈同步：弹出栈顶符号，直到栈顶也是同步符 while (!stack.empty() && !sync.count(stack.back())) stack.pop_back(); }

这段代码里有两处推进动作，缺一不可。第一处是消费输入直到遇到同步符，第二处是弹栈直到栈顶也是同步符。只做其中一处，分析器就会在原地反复报同一个错误。这是语法分析实验里最典型的死循环成因，后面避坑那章还会展开。

分界线划清楚之后有个额外收益：错误信息可以做到准确。词法错误报「第 3 行第 12 列出现非法字符 @」，语法错误报「第 3 行第 20 列，期望 ) 实际遇到 {」，两条信息指向的是不同层的问题，排查时不用再猜。

3. 自顶向下：递归下降、FIRST/FOLLOW 与预测分析表

自顶向下的本质是「从开始符号出发，不断用产生式右部替换左部，试图拼出输入序列」。这句话听起来抽象，但落到实现上有两种完全等价、写法却差别很大的形式：一种是把推导过程写成互相调用的函数，也就是递归下降；另一种是把函数调用栈换成显式的符号栈，用一张预先算好的表来决定每步该用哪条产生式，也就是 LL(1) 预测分析。理解这两种形式的关系，比单独会写其中一种重要得多。

3.1 递归下降的形态：每个非终结符一个函数

递归下降的结构极其直白：文法里每个非终结符对应一个函数，函数体就是该非终结符所有产生式的分支判断，用当前前瞻的 Token 决定走哪一支。

// 文法： // E -> T E' // E' -> + T E' | ε // T -> F T' // T' -> * F T' | ε // F -> ( E ) | id bool parseE() { if (!parseT()) return false; return parseEPrime(); // E' 可以为空，所以这里总是调用 } bool parseEPrime() { if (peek().kind == TokenKind::PLUS) { advance(); // 消费 '+' if (!parseT()) return false; return parseEPrime(); // 右递归：栈深与加号的个数成正比 } return true; // ε 分支：一个 token 都不消费，直接成功返回 }

peek()返回当前 Token 但不推进，advance()消费并前进。整个分析器只靠一个 Token 的前瞻就能决定分支，这就是「LL(1)」里那个 1 的含义。

注意parseEPrime里那个 ε 分支：它不消费任何 Token 就返回 true。这个设计初看很奇怪，但它恰恰是递归下降能正确工作的关键——调用方拿到 true 之后会继续走自己的流程，如果输入里确实有+，下一个peek()就会看到它。换成「先探测有没有+，没有再返回」的写法，就变成了一次额外的前瞻，等价但啰嗦。

parseEPrime是右递归的，每一层+都会压一次栈。这意味着一个一百项相加的表达式会产生一百层调用。这在实验规模的输入上没问题，但如果有人拿它去解析几千项的表达式，栈溢出是迟早的事。真正的编译器前端在这一点上通常会把二元运算改写成循环而不是右递归，原因就在这里。

3.2 左递归为什么会让递归下降直接爆栈

上面那段文法里，E -> T E'这种形式不是随手写的，它是从E -> E + T | T改写来的。原始写法叫直接左递归，如果照着它直译成递归下降函数，结果是灾难性的。

// 错误示范：直接照抄左递归文法 bool parseE() { // E -> E + T 分支 if (parseE()) { // 一进来就无条件调用自己 if (peek().kind == TokenKind::PLUS) { advance(); return parseT(); } } return parseT(); // E -> T 分支 }

调用parseE的第一件事就是再调用parseE，而这一次调用没有消费任何输入，于是它又调用parseE，如此往复。栈帧一路压下去，直到栈空间耗尽。这不是「跑得慢」，而是几毫秒内直接崩掉。

标准解法是改写文法，把左递归消掉：

A -> A α | β 改写成 A -> β A' A' -> α A' | ε

代入到加法上就是E -> T E'、E' -> + T E' | ε，也就是 3.1 里那段代码。改写后的语言完全等价，但推导方向从「先递归再匹配」变成了「先匹配再递归」，递归下降就能正常工作了。

还有一类更隐蔽的情况叫间接左递归：A -> B x、B -> A y，单独看每条产生式都不左递归，但展开两步之后A又回到了A开头。这类文法需要先做一次代入消元，把间接左递归转成直接左递归，再套上面的公式。实验里如果文法规模小，很多人会手动改；但如果是程序读文法自动处理，就得老老实实实现这个代入过程，否则一旦文法里藏了环，分析器会以一种极其难查的方式崩掉。

3.3 FIRST 与 FOLLOW：不动点迭代到底在迭代什么

消除左递归只是让递归下降能跑，要让它跑对，还得知道「遇到某个 Token 时该选哪条产生式」。这个判断依据就是 FIRST 集：一个符号串能推导出的所有可能的首终结符。

FIRST 的定义是递归的——一个非终结符的 FIRST 集依赖于它所有产生式右部第一个符号的 FIRST 集，而那些符号又可能是别的非终结符。所以计算方式不是一次遍历，而是反复扫描直到不再变化，这就是不动点迭代。

// FIRST 集的不动点计算 void computeFirst(Grammar& g) { bool changed = true; while (changed) { changed = false; for (const auto& p : g.productions) { // 逐个扫描右部符号，只要前一个符号能推出 ε 就继续往后看 bool allNullable = true; for (int sym : p.rhs) { if (g.isTerminal(sym)) { changed |= g.first[p.lhs].insert(sym).second; allNullable = false; break; // 终结符之后不可能再贡献 FIRST } // 非终结符：把它的 FIRST 集（去掉 ε）并入左部 for (int t : g.first[sym]) { if (t != EPSILON) changed |= g.first[p.lhs].insert(t).second; } if (!g.first[sym].count(EPSILON)) { allNullable = false; break; // 这个符号推不出空，后面的符号够不着 } } // 整个右部都能推出空，左部才能推出空 if (allNullable) changed |= g.first[p.lhs].insert(EPSILON).second; } } }

changed是这段代码的核心。每一轮扫描都可能给某个 FIRST 集加入新元素，而新加入的元素又可能让依赖它的其他非终结符在下一轮获得新元素。只有某一轮完全没有任何insert成功，才能确定到达了不动点。

这里有两个极易漏掉的点。第一个是EPSILON的传播：只有当一个产生式的整个右部都能推出空串时，左部才能推出空。很多人写成「右部第一个符号能推出空就给左部加 ε」，这是错的，因为后面还有符号。第二个是去 ε 后并入：把其他符号的 FIRST 集并进来时要排除 ε，不然会凭空造出一堆本不该为空的非终结符。

FOLLOW 集的计算依赖 FIRST，并且同样是不动点迭代。它的语义是「某个非终结符后面可能紧跟哪些终结符」，构造规则有三条：开始符号的 FOLLOW 里放$；对A -> α B β，把 FIRST(β) 去掉 ε 后放进 FOLLOW(B)；如果 β 能推出空，把 FOLLOW(A) 整个放进 FOLLOW(B)。第三条是递归的，也是必须迭代的原因。

3.4 预测分析表：把递归调用栈搬到显式栈上

有了 FIRST 和 FOLLOW，就能填出 LL(1) 预测分析表。表是二维的，行是非终结符，列是终结符，格子里存产生式编号。

填表规则只有两句：对产生式A -> α，把 FIRST(α) 里每个终结符 a 对应的M[A][a]填成这条产生式；如果 α 能推出 ε，那么对 FOLLOW(A) 里每个终结符 b，也把M[A][b]填成这条产生式。

一旦某个格子在填的时候发现已经有值且不同，就说明这个文法不是 LL(1) 的——同一对（非终结符，前瞻符号）导出了两条不同的产生式，分析器无从选择。这就是 LL(1) 冲突的判定方式，比在代码里到处加断言靠谱得多。

填完表之后，运行逻辑就不再需要递归了，改用显式的符号栈：

// LL(1) 表驱动主循环 std::vector<int> stack; // 符号 id 栈，栈顶在 back() stack.push_back(EOF_SYMBOL); // 先压结束符，它永远不会被弹出 stack.push_back(g.startSymbol); Token cur = lexer.nextToken(); while (!stack.empty()) { int X = stack.back(); if (g.isTerminal(X)) { if (X == static_cast<int>(cur.kind)) { stack.pop_back(); // 匹配成功，同时推进两边 cur = lexer.nextToken(); } else { recoverLL(X, cur); // 终结符对不上，进入错误恢复 } continue; } int prod = table[X][static_cast<int>(cur.kind)]; if (prod < 0) { // 空项意味着没有任何产生式可用 recoverLL(X, cur); continue; } stack.pop_back(); const auto& rhs = g.productions[prod].rhs; // 逆序压栈：保证右部最左边的符号最后压入，从而位于栈顶 for (int i = static_cast<int>(rhs.size()) - 1; i >= 0; --i) { if (rhs[i] != EPSILON) stack.push_back(rhs[i]); } }

两个参数细节值得单独说。第一，EOF_SYMBOL必须在最开始就压在栈底，它负责在输入耗尽时给出一个确定的行为，否则循环结束条件会变得含糊。第二，右部符号必须逆序压栈——栈是后进先出，要让最左符号先被展开，就得让它最后进去。这个逆序如果写反了，语法稍微复杂一点的输入就会立刻错位，而且报错位置会很诡异。

这套显式栈写法和 3.1 的递归写法在语义上完全等价：递归下降的调用栈和这里的符号栈是同一个东西，只不过一个由编译器管理、一个由你管理。但显式栈有个隐性优势——栈的内容是可打印的。出错的时候把整个栈 dump 出来，你立刻能看到当前正处在哪条推导路径上；递归写法就只能靠调试器看调用栈。

3.5 LL(1) 的表达力天花板与左公因子提取

LL(1) 的那个「1」是硬约束：只看一个 Token 就必须决定用哪条产生式。这意味着两条产生式如果右部有公共前缀，就一定冲突。

比如stmt -> id = expr ;和stmt -> id ( args ) ;，两个右部都以id开头，遇到id的时候分析器不知道该走哪条。解法是提取左公因子，改写成一个中间非终结符：

stmt -> id suffix ; suffix -> = expr | ( args )

改写之后，stmt遇到id只有唯一选择，把决策推迟到suffix那一层再做。这个手法在写递归下降分析器的时候几乎是必需的，而且和手写 parser 的经验直接对应——你看那些手写的声明解析函数，为什么会先读出标识符再看下一个 Token，这就是左公因子提取的人工版本。

但提取左公因子有代价：它改变了文法的形状，也就改变了语法树的结构。如果不做额外处理，suffix会成为一个多余的中间节点挂在树上，AST 里凭空多出一层。常见做法是在建树阶段把这种纯转发节点折叠掉，而不是为了树形好看去改文法。

更根本的限制在于，有些语言结构天生不是 LL(1) 的。比如「同一个标识符，后面跟着(是函数调用，否则是变量引用」，这在某些文法里需要看两个 Token 才能决定。这类问题在自顶向下框架里只能靠改文法或者加有限的前瞻来绕，绕不过去的时候就得换到自底向上。这也解释了为什么真实的编译器前端更多用 LR 系而不是 LL 系——不是因为 LL 不好写，而是因为 LL(1) 装不下真实语言的文法。

4. 自底向上：LR 项目集、冲突消解与表驱动循环

自底向上的思路和自顶向下正好反过来：它不预测该用哪条产生式，而是一路把输入符号移进栈里，等到栈顶的符号串凑够某条产生式的右部，就把它归约成左部。这个「凑够就归约」的判断，靠的是一张预先构造好的动作表。LR 分析器之所以强大，是因为它在构造表的时候已经把「什么时候该移进、什么时候该归约」这个问题在图层面推演清楚了，运行时只是查表。

4.1 LR(0) 项目与闭包：一个状态到底代表什么

LR 分析器的核心概念是「项目」：一条产生式加上一个圆点，表示「这条产生式我已经匹配到哪了」。比如E -> E · + T表示我已经识别出了E，期待接下来看到+ T。

圆点在最右端（E -> E + T ·）的项目叫归约项目，意思是这条产生式已经完整匹配，可以归约了。

状态是一组项目的集合，也就是项目集。构造项目集的关键运算是闭包：如果项目里圆点后面是一个非终结符，那么该非终结符的所有产生式都要以圆点在开头的形式加入这个集合。

struct Item { int prodIndex; // 产生式编号 int dotPos; // 圆点位置，取值 0..rhs.size() int lookahead; // LR(1) 才用；LR(0) 里统一置 -1 bool operator==(const Item& o) const { return prodIndex == o.prodIndex && dotPos == o.dotPos && lookahead == o.lookahead; } }; // 闭包运算：把圆点后面的非终结符展开 std::set<Item> closure(std::set<Item> I, const Grammar& g) { bool changed = true; while (changed) { changed = false; for (const Item& it : std::vector<Item>(I.begin(), I.end())) { const auto& rhs = g.productions[it.prodIndex].rhs; if (it.dotPos >= static_cast<int>(rhs.size())) continue; // 归约项目，无需展开 int next = rhs[it.dotPos]; if (!g.isNonTerminal(next)) continue; // 圆点后是终结符，不展开 for (int p : g.prodsOf[next]) { Item ni{p, 0, it.lookahead}; if (I.insert(ni).second) changed = true; } } } return I; }

这是一个典型的不动点循环，和 FIRST 集的计算同构。之所以需要循环而不是一轮遍历，是因为展开出来的新项目可能圆点后面还是非终结符，需要继续展开，一层套一层。用insert().second判断是否真的插入了新元素，是控制循环收敛的标准写法。

GOTO函数在此基础上再走一步：给定项目集 I 和一个符号 X，把所有圆点后面是 X 的项目圆点右移一位，然后对新集合求闭包。从初始项目集出发，对每个可能符号反复求 GOTO，就能构造出完整的项目集规范族，也就是 LR 自动机的全部状态。

4.2 从 SLR(1) 到 LR(1) 到 LALR(1)：冲突消解的三级跳

最朴素的 LR(0) 只看项目本身，不看后续输入，所以遇到归约项目就无脑填归约动作，产生的冲突非常多。后面三级演化，本质是在「什么条件下才允许归约」这件事上不断收紧判断。

SLR(1) 的改进点是引入 FOLLOW 集做过滤：只有当当前输入 Token 落在这个非终结符的 FOLLOW 集里，归约才合法。这个判断是上下文无关的，所以实现起来极简单——填表的时候查一下集合就行。但它的问题也在于「上下文无关」：FOLLOW 集把某个非终结符在所有位置后面可能出现的符号都混在了一起，而实际上在某个特定状态下，能跟在它后面的符号远比这少。

LR(1) 解决这个问题的方式是给每个项目加一个展望符，记录「在这个特定状态下，归约之后期待看到什么」。这个信息精确，但代价是状态爆炸——同一个项目因为展望符不同会被算成不同的项目，项目集规范族的规模可能翻好几倍。对于真实语言的文法，内存占用会到一个不太能接受的程度。

LALR(1) 是工程上的折中：把 LR(1) 里「核心项目相同、只有展望符不同」的那些状态合并成一个，展望符取并集。这样状态数回到 SLR 的量级，但判断精度比 SLR 高得多。代价是合并可能把本来不冲突的两个状态并出冲突来，产生归约-归约冲突——这是 LALR 唯一的固有缺陷，也是几乎所有解析器生成工具默认用 LALR 而不是纯 LR(1) 时唯一需要留意的风险。

从实验角度说，这三级的差异只有在特定文法上才能体现出来。如果你的文法足够简单，SLR 和 LALR 给出的表完全一样；只有当你构造出一个 FOLLOW 集明显过宽的文法，才能看到 SLR 报冲突而 LALR 正常工作的场景。想在报告里体现深度，造这样的对比用例比堆一堆代码有用得多。

4.3 移进-归约冲突的本质：悬空 else 与优先级覆盖

移进-归约冲突的形式是：某个状态下，当前 Token 既能触发一次移进，也能触发一次归约，动作表那一格填不下两个动作。

最经典的例子是悬空 else：

stmt -> if ( expr ) stmt | if ( expr ) stmt else stmt | other

当分析器读完if ( expr ) stmt之后，如果下一个 Token 是else，它既可以把这个stmt归约完（对应没有 else 的分支），也可以继续移进else（对应有 else 的分支）。两种选择都合法，文法本身是二义的。

默认解法是移进优先，也叫「就近匹配」：else属于最近的那个if。这个选择不是从文法里推导出来的，而是额外约定的一条规则。几乎所有工具都默认这么做，因为大部分语言的语义就是这么规定的。

另一类冲突来自运算符优先级。E -> E + E | E * E这种写法天然二义，分析器在读完E + E之后遇到*，不知道该先归约加法还是先移进乘法。正规解法有两个：一是把文法改写成多层非终结符（E -> E + T、T -> T * F），把优先级编码进文法结构；二是在表构造阶段用优先级声明覆盖冲突，读到*就强制移进。

// 冲突解决：用优先级表覆盖默认的移进优先 Action resolve(Action shift, Action reduce, const Grammar& g) { int precShift = g.precOf(shift.token); int precReduce = g.precOf(g.productions[reduce.prod].rhs); if (precShift > precReduce) return shift; // 当前符号优先级高，先算它 if (precShift < precReduce) return reduce; // 栈上的运算优先级高，先归约 // 优先级相同时看结合性：左结合归约，右结合移进 return g.assocOf(shift.token) == LEFT ? reduce : shift; }

precShift取自待移进的那个终结符，precReduce取自被归约产生式右部最外层的运算符——也就是这条产生式「最后算」的那个操作符。优先级相同时靠结合性决断：左结合运算符让栈上的先算（归约），右结合让新来的先算（移进）。

这套机制看起来像补丁，但它是解析器生成工具的标准做法，因为把优先级写进文法会使产生式数量成倍增长，而用优先级声明只需要几行配置。实验里如果只实现文法改写那一条路，也不影响正确性，只是体会不到「表构造阶段还能被外部规则干预」这层设计。

4.4 表驱动的运行循环：状态栈与符号栈必须同步

LR 分析器的运行时结构比 LL 复杂一点，它有两个栈：状态栈和符号栈。状态栈记录自动机走到哪，符号栈记录已经识别出的文法符号，两者长度必须始终一致。

// LR 分析主循环 std::vector<int> states{0}; // 初始状态 0 std::vector<Symbol> symbols; // 对应的文法符号 Token cur = lexer.nextToken(); while (true) { int s = states.back(); const Action& act = action[s][static_cast<int>(cur.kind)]; if (act.type == Action::Shift) { states.push_back(act.target); symbols.push_back(symbolOf(cur)); // 终结符压符号栈 cur = lexer.nextToken(); } else if (act.type == Action::Reduce) { const Production& p = grammars.productions[act.target]; // 先弹：弹出 |rhs| 个状态和符号 for (size_t i = 0; i < p.rhs.size(); ++i) { states.pop_back(); symbols.pop_back(); } // 再查 GOTO：用弹完之后的新栈顶状态和左部非终结符 int g = goTo[states.back()][p.lhs]; if (g < 0) { reportError(cur, "no goto entry"); break; } states.push_back(g); symbols.push_back(Symbol{Symbol::NonTerminal, p.lhs, g.nameOf(p.lhs)}); } else if (act.type == Action::Accept) { break; // 输入耗尽且归约到开始符号 } else { recoverLR(states, cur); // 空项 = 语法错误 } }

这里有个顺序细节必须严格：归约时先弹出右部长度的状态和符号，再用弹出后的栈顶状态去查 GOTO，最后把新状态和左部符号压回去。如果先查 GOTO 再弹，拿到的是旧栈顶，跳转全错。这个 bug 的表现非常有欺骗性——程序不崩，只是会在某个特定的输入上给出错误结果，而且是那种「多加一个符号就正常」的玄学现象。

Accept动作只在状态 0 里的一次归约完成后才会出现，它对应「输入已耗尽 + 已经归约出开始符号」这个终局条件。很多人把循环终止条件写成「输入读到 EOF 就退出」，这样会在最后一个非终结符还没归约完的时候就提前结束，语法树缺一块。

recoverLR和 LL 那边的恢复逻辑本质相同：报错、丢弃 Token 直到能重新同步、保持两个栈长度一致。区别在于 LR 的错误恢复多一个选择——可以直接弹状态栈，模拟「放弃当前部分构造」的行为，这在某些文法上比丢弃输入更容易恢复到一个一致状态。

4.5 语法树在归约动作里生长

LR 分析器有一个天然优势：每次归约恰好对应一棵子树的完成。移进的时候把叶子节点压进符号栈，归约的时候把栈顶的若干个节点取出来，作为新节点的子节点，再把新节点压回去。

// 在 Reduce 分支里顺手建树 std::vector<AstNode*> children; for (size_t i = 0; i < p.rhs.size(); ++i) { children.push_back(astStack.back()); // 弹出顺序是逆序的 astStack.pop_back(); } std::reverse(children.begin(), children.end()); // 翻转回源码顺序 AstNode* node = makeNode(p.lhs, children); astStack.push_back(node);

std::reverse这一步是必须的。符号栈的弹出顺序天然是从右往左，而语法树的子节点顺序必须从左往右。漏掉这一行，程序不会报任何错，但生成的树是完全镜像的——它看起来还挺像个树，只有当你拿它去做求值或者代码生成的时候，才会发现a - b算成了b - a。这种 bug 在没有可视化工具的情况下极难定位，因为中间结果看起来都「合理」。

astStack和symbols是两个平行栈，长度应该同步变化。把它们合成一个结构体是个好习惯，这样压弹的时候不可能只动一个不动另一个。

5. 避坑与排查：五处最容易翻车的地方

语法分析的代码有个共同特点：写错的时候很少是编译不过，更多是「能跑、结果不对、或者干脆卡死」。这一章记录五个常见故障，每个都按现象、原因、解决三段的顺序写，因为这类问题的排查路径比结论本身更有价值。

5.1 现象：程序卡死不动，CPU 跑满但没有任何输出

原因几乎总是错误恢复路径里没有推进输入。分析器遇到语法错误之后进入恢复逻辑，丢弃 Token 直到遇到同步符，但如果同步符恰好就是当前这个 Token，循环条件立刻不成立，一个 Token 都没丢，于是回到主循环，又遇到同一个错误，再进恢复逻辑——如此往复。

更隐蔽的一种情况是符号栈没有被同步弹出。LL(1) 里如果只跳过了输入 Token，但栈顶还是那个无法展开的非终结符，下一次循环表查出来还是空项，于是又调一次恢复。

解决方式是把恢复逻辑里的两个推进动作都写死：输入侧必须至少前进一个 Token（哪怕是advance()一次），栈侧必须弹到栈顶落在同步集里。如果担心误伤，可以在恢复函数里加一个断言，检查调用前后的cur和栈深度至少有一个变了，不变就直接抛异常而不是继续跑。这种「防御性断言」在实验阶段比事后调试省时间得多。

5.2 现象：FIRST 集算出来是空的，或者明显少了一批终结符

原因通常是两件事之一。第一种是不动点迭代只跑了一遍——扫一次产生式就把结果拿去用了。这在文法层次较深的时候必然出错，因为某个非终结符的 FIRST 集可能要靠三轮传播才能凑齐。

第二种是 ε 的传播写错了。A -> B C，如果B能推出空，那么C的 FIRST 集也应该进入A的 FIRST 集；如果B、C都能推出空，A才能推出空。常见的错误写法是「只要右部有任何一个符号能推出空就给左部加 ε」，这会造出一堆假的空产生式，进而让 FOLLOW 集和预测表全部错位。

解决方式是严格按 3.3 里那个allNullable标志的写法来：顺序扫描右部，遇到终结符就停，遇到推不出空的非终结符也停，只有扫完整个右部时allNullable还是 true 才加 ε。排查时可以在每轮迭代后打印各集合的大小，如果某轮之后大小不再变化但明显偏小，说明传播逻辑有断点。

5.3 现象：LR 项目集构造跑不完，状态数远超预期

标准的 LR(0) 文法，状态数一般在几十到一两百之间。如果你的程序跑出了上千个状态还停不下来，多半是项目集的比较出了问题。

根本原因在于项目集是一个集合的集合，判断两个项目集是否相等时必须按内容比较，而不是按对象地址或者插入顺序。如果用std::vector<Item>存项目集，两个内容相同但插入顺序不同的 vector 会被判成不同状态，于是同一个状态被反复重新生成、重新求闭包，状态数指数增长。

解决方式是把每个项目集规范化：内部项目排序，然后映射到一个唯一的整数 id。之后所有状态转移都记这个 id，判断是否已有状态时用 id 查哈希表。这个规范化步骤在任何 LR 实现里都是必需的，少了它，SLR(1) 还能在小文法上侥幸跑完，LALR(1) 基本必然超时。

5.4 现象：文法检查过没问题，但构造分析表时报冲突

有一种冲突不是文法本身造成的，而是符号编号系统的 bug。终结符和非终结符如果共用同一段 id 空间，而某些判断又只看 id 不做类型检查，就会出现「把非终结符当成终结符去查表」的情况，表现是莫名其妙的空项或者冲突。

另一个来源是 ε 产生式处理不一致。有的地方把空右部当成「长度 0 的 vector」，有的地方用了一个特殊的EPSILON符号占位，两种表示混用的时候，闭包运算会把EPSILON当成一个正常的非终结符去展开，凭空造出一批错误项目。

解决方式是把符号空间彻底分开：用type字段明确区分，并且在所有查表入口做一次断言。至于 ε，统一约定「空 vector 表示 ε」，不要引入占位符；确实需要在打印时显示，就在输出层做转换而不是在数据结构里塞一个假符号。

5.5 现象：程序完整跑完了，生成的语法树结构不对

这类问题最难查，因为没有任何错误信号。典型表现是某个二元表达式的结果反了，或者函数调用的实参顺序颠倒了。

原因在 4.5 已经提过：归约时从栈上弹出的子节点是逆序的，必须翻转回来。还有一个相关的问题发生在 LL 那边——递归下降建树时，如果中途某个分支失败返回了，已经建好的部分节点必须回收掉，否则会留下一批挂着半棵子树的孤儿节点，最终树的根节点看起来正常，但某个分支上多出了不该存在的兄弟节点。

解决方式是给建树逻辑加一个自检：每次归约完成后，检查新节点的子节点数量和产生式右部长度（排除 ε 后）是否一致，不一致就直接报错停机。这个检查成本极低，但能在问题扩散成「结果不对」之前把它拦住。另外，给 AST 写一个打印函数，把树按缩进输出，比在调试器里点开指针高效得多。

6. 设计取舍：为什么两条路线都要自己写一遍

把递归下降和 LR 表驱动都实现一遍，看起来像是重复劳动，实际上它们回答的是两个不同的问题。自顶向下的版本让你理解「一个非终结符的展开过程是什么样的」，这个视角和人类阅读文法的方式一致，错误信息也天然友好——你知道自己正期待什么，所以能报出「期望)实际遇到{」。自底向上的版本让你理解「归约时机是怎么被预先计算出来的」，它把文法中所有的决策点都压缩进了一张表，运行时不再有任何推理。

这个差异直接体现在工程选择上。手写的一次性解析器，尤其是需要精细错误提示的场景，几乎都选自顶向下：改一行文法就是改一个函数，加一条错误恢复规则就是加一个分支。而需要支持大量语法变体、或者文法本身频繁变动的场景，会选表驱动：改文法只需要改输入文件，重新生成表即可，代码一行不动。所谓「解析器生成器」，卖的就是这个分离。

另一个常被忽略的取舍是内存和可调试性。递归下降的中间状态全在调用栈上，出错时你只能看到当前函数的局部变量；LR 的状态栈和符号栈是你自己管理的，可以随时打印完整快照。这也是为什么在排查一个复杂文法的问题时，很多人会临时把 LR 版本的分析器当调试工具用——它能告诉你走到了自动机的哪个状态，而这正是理解冲突的关键信息。

最后是验证方法。写完两个版本之后，别只拿教科书上的算术表达式文法跑一遍就收工。真正能暴露问题的输入有三类：带嵌套空产生式的文法（考验 FIRST/FOLLOW 的 ε 传播）、带公共前缀的文法（考验左公因子提取和 LL(1) 冲突判定）、带二义性运算符优先级的文法（考验 LR 冲突消解）。每一类都用同一份 Token 序列喂给两个分析器，如果两边都接受，再看生成的语法树结构是否一致——树形不一致往往意味着某个版本的归约/展开顺序有偏差，而这在只跑单版本的时候是完全看不出来的。

从那以后我每次写这类分析器，都会强制走一遍「先手算一个极小文法的 FIRST/FOLLOW 和项目集，再让程序输出同样的结果去对」这个流程，因为凡是跳过了手算这一步的，最后都要花几倍的时间在调试器里倒推自己算错了哪一步。希望帮到你。

本文还有配套的精品资源，点击获取