简介：编译原理课程语法分析实验的C++实现资料，面向正在完成递归子程序法分析、词法结果衔接与自动评测提交的高校学生参考。压缩包共2个文件，含1份doc实验问题说明和1份cpp源码，大小约17KB，结构精简，便于对照文法规则梳理程序组织与调试路径。内容围绕统一读取testfile.txt、将词法分析识别结果写入output.txt、按单词顺序逐行输出信息，并在指定语法成分分析结束前另起一行输出“<常量说明>”等名称的要求展开；未要求输出的语法成分同样需要完成分析。实现上采用递归下降方式覆盖文法中定义的各类语法成分，同时兼顾预读场景下不重复输出单词的细节。代码已在CG实验平台满分通过，已有6110人学习，可作为文法覆盖、预读处理与输出格式校验的对照样例，帮助读者快速定位分析流程和评测细节中的易错点。

1. 语法分析：为什么「能跑通」和「写对了」之间差着一张表

写编译原理实验的人大多有过这样的体验：递归下降版本两百行就跑通了课件上那个算术表达式文法，换成带左递归、带 ε 产生式的那套，程序立刻栈溢出或者死循环。语法分析表面上在做「匹配 Token」，真正决定一个实现能不能通用的，是它有没有把文法机械地翻译成一张可查的表。C++ 版语法分析实验里那些看起来最枯燥的部分——FIRST/FOLLOW 集合、项目集规范族、ACTION 表——恰恰是整个机制的地基。搞懂文法怎么变成表、表又怎么驱动一个状态栈，比背下 SLR 和 LR(1) 的区别有用得多，也能让人在以后看到任何分析器生成器的输出时心里有底。

2. 文法预处理：FIRST/FOLLOW 为什么必须迭代到不动点

把文法读进内存之后，几乎所有的表构造算法都建立在两个集合之上：FIRST 和 FOLLOW。这两个集合的定义是递归的——FIRST(A) 依赖 FIRST(B)，FOLLOW(A) 又依赖 FOLLOW(B)，而 B 可能反过来依赖 A。递归定义的结果是：任何一趟单向扫描都只能把依赖传播一层，必须反复扫到「这一轮没有任何集合发生变化」为止，得到的东西才叫最小不动点，否则后面算出来的项目集和表全是错的。

2.1 产生式落进 C++：符号表、ε 与增广文法

第一步是把文本文法转成结构体。最常见的写法是给每个符号分配一个整数 id，终结符和非终结符共用同一个 id 空间，另开一个布尔数组标记谁是终结符。这样做的直接好处是后面所有集合都能退化成std::set<int>甚至bitset，比较和合并都快得多。

// 右部用空 vector 表示 ε，比塞一个特殊符号干净： // 好处是归约长度天然等于 rhs.size()，不需要到处特判 EPS struct Production { int lhs; // 左部非终结符 id std::vector<int> rhs; // 右部符号 id 序列；空表示 A -> ε }; std::map<std::string, int> symId; // 符号名 -> id std::vector<bool> isTerminal; // 按 id 索引 std::vector<Production> prods; std::vector<std::vector<int>> prodsOf; // prodsOf[B] = 左部为 B 的产生式编号

非终结符的判定不需要额外标注：所有出现在lhs位置上的符号自动是非终结符，剩下的一律按终结符处理。这个约定省掉了一堆手工分类的麻烦，也顺手把「某个符号既当终结符又当非终结符」这种低级错误暴露出来。

接下来必须做一件事：增广文法。新增一个不出现在原文法任何右部的非终结符S'，并加入唯一的产生式S' -> S。

// 增广：让「接受」只对应一个项目 [S' -> S·, $] // 不增广的话，S 在右部出现时，[S -> α·] 和「整个输入读完」的项目会混在一起 int S_aug = newNonTerminal("S'"); prods.push_back({S_aug, {startSymbol}});

这一步经常被当成形式主义跳过，后果会在表构造阶段显现：如果直接把起始符号 S 当成分析目标，那么当 S 也在某条产生式右部出现时（递归文法里非常常见），圆点走完 S 的那些项目到底该归约还是该接受，就没有唯一依据了。增广之后，[S' -> S·, $]是整个项目集里唯一一个「左部是 S'」的项目，ACCEPT 动作有了干净的判据。

2.2 FIRST 集：空串会顺着产生式「传染」

FIRST 的定义里有两条容易写错的传播路径。第一条是明显的：A -> X1 X2 ... Xn里，FIRST(X1) 的每个元素都进 FIRST(A)。第二条是隐蔽的：如果 X1 能推出 ε，那么 FIRST(X2) 也得进 FIRST(A)；如果 X2 也能推空，就继续往后看，直到遇到第一个不能推空的符号为止。这就是所谓的空串传染，一个 nullable 的非终结符会让后面所有符号的 FIRST 集往后「漏」一层。

所以实现上要拆成两步。先单独把 nullable 算干净：

// 第一步：nullable 的不动点 // 只要某条产生式右部所有符号都可空（含右部为空的情况），左部就可空 bool changed = true; while (changed) { changed = false; for (const Production& p : prods) { bool allNullable = true; for (int X : p.rhs) if (!nullable[X]) { allNullable = false; break; } if (allNullable && !nullable[p.lhs]) { nullable[p.lhs] = true; changed = true; } } }

右部为空的产生式天生满足allNullable == true，不需要特殊分支，这是用空 vector 表示 ε 换来的便利。

然后算 FIRST，注意集合里不放 ε，可空性由 nullable 单独承载：

// 第二步：FIRST 的不动点。EPS 不进集合，靠 nullable 单独表示 changed = true; while (changed) { changed = false; for (const Production& p : prods) { for (int X : p.rhs) { if (isTerminal[X]) { // 终结符：并入后立即停止 changed |= first[p.lhs].insert(X).second; break; } for (int t : first[X]) // 非终结符：并入 FIRST(X) changed |= first[p.lhs].insert(t).second; if (!nullable[X]) break; // X 不能推空，后面的符号够不着 } } }

insert().second是判断「这一轮有没有变化」最省事的手段，它只在新元素真正插入时返回 true。为什么非循环不可：A -> B、B -> C、C -> x这种链，正向扫描一趟只能把 x 传播到 C，反向扫描一趟只能传播到 B，只有反复扫才能到 A。收敛轮数的上界是非终结符个数，实际几轮就稳定了。

提示：如果文法规模到了几百个符号，std::set<int>的插入会成为瓶颈，换成bitset<256>之后合并就是一次按位或，判断变化就是一次比较，速度差一个数量级。实验里符号数通常只有几十个，set 完全够用。

2.3 FOLLOW 集：$ 的注入与「谁依赖谁」

FOLLOW 回答的是另一个问题：在某个句型里，非终结符 A 后面「可能」紧跟哪些终结符。起点符号先无条件拿到输入结束符$，然后按两条规则传播。

// FOLLOW：起点符号拿到输入结束符 $ follow[startSymbol].insert(END); bool changed = true; while (changed) { changed = false; for (const Production& p : prods) { // A -> X1 X2 ... Xn for (size_t i = 0; i < p.rhs.size(); ++i) { int B = p.rhs[i]; if (isTerminal[B]) continue; // 规则一：FIRST(β) \ {ε} ⊆ FOLLOW(B)，β 是 B 右边那一段 bool betaNullable = true; for (size_t j = i + 1; j < p.rhs.size(); ++j) { int X = p.rhs[j]; if (isTerminal[X]) { changed |= follow[B].insert(X).second; betaNullable = false; break; } for (int t : first[X]) changed |= follow[B].insert(t).second; if (!nullable[X]) { betaNullable = false; break; } } // 规则二：β ⇒* ε 时 FOLLOW(A) ⊆ FOLLOW(B) if (betaNullable) for (int t : follow[p.lhs]) changed |= follow[B].insert(t).second; } } }

规则二的直觉是：既然 B 后面那一串能全部推空，那 B 后面能跟什么，就等价于 A 后面能跟什么。这条规则是 FOLLOW 依赖关系里唯一会产生「环」的地方，也是必须迭代到底的原因。

理解了 FOLLOW 是怎么算出来的，就能看清它的局限：它是按整个文法统计出来的全局近似，不区分 A 究竟出现在哪个上下文里。同一个非终结符在十个地方出现，FOLLOW 只会把它们后面可能跟的终结符求个并集。这个粗粒度在下一章会直接变成假冲突——SLR 分析表里那些莫名其妙的移进/归约冲突，根源几乎都在这里。

3. 项目集规范族：closure 和 goto 到底在「展开」什么

文法是一组规则，分析器要的却是一台自动机。中间那层转换就是项目集规范族。一个项目（Item）就是「某条产生式 + 一个圆点 + 一个展望符」，圆点左边是已经读进来的部分，右边是还期待的部分。整个状态机干的事情，就是把「我可能读到哪了」这个问题的所有答案枚举出来，并且为每个答案记下「下一个符号该往哪走」。

3.1 项目的数据结构与「点」的三种命运

struct Item { int prod; // 产生式编号 int dot; // 圆点位置，取值 0..rhs.size() int la; // 展望符（终结符 id）；构造 LR(0) 项目集时统一填 -1 bool operator<(const Item& o) const { // 供 set / map 排序去重 if (prod != o.prod) return prod < o.prod; if (dot != o.dot ) return dot < o.dot; return la < o.la; } bool operator==(const Item& o) const { return prod == o.prod && dot == o.dot && la == o.la; } };

la这个字段是整套代码能不能「一份实现跑三种模式」的关键。SLR 和 LR(0) 用不上它，但保留之后，闭包函数和表构造函数只需要改一行取值逻辑，就能在 LR(0)/SLR/LR(1) 之间切换，实验里对比三种算法的冲突数量会非常方便。

圆点的位置决定了项目接下来的三种命运。点在末尾（dot == rhs.size()）意味着右部已经全部读完，这是个可归约项目；点后面是终结符意味着需要移进；点后面是非终结符意味着要展开它所有的产生式，也就是闭包运算。

3.2 CLOSURE：递归定义与 worklist 实现

闭包的定义是递归的：若[A -> α·Bβ, a]在集合里，那么对每条B -> γ和每个b ∈ FIRST(βa)，[B -> ·γ, b]也要在集合里。

std::set<Item> closure(std::set<Item> I) { std::vector<Item> work(I.begin(), I.end()); // 待处理队列 while (!work.empty()) { Item it = work.back(); work.pop_back(); const Production& p = prods[it.prod]; if (it.dot >= (int)p.rhs.size()) continue; // 点在末尾，无可展开 int B = p.rhs[it.dot]; if (isTerminal[B]) continue; // 点后是终结符，等移进 // 先算 FIRST(β a)：β 是 rhs[dot+1..]，a 是外层展望符 std::set<int> lookahead = firstOfSuffix(p.rhs, it.dot + 1, it.la); for (int pi : prodsOf[B]) { // 所有左部为 B 的产生式 for (int a : lookahead) { Item ni{pi, 0, a}; // 圆点置于右部最左端 if (I.insert(ni).second) work.push_back(ni); } } } return I; }

firstOfSuffix是这段代码的核心：它算的是 FIRST(βa)，即右部剩余部分加上外层展望符。当 β 能推出 ε 时，外层的 a 要「穿透」进来成为新项目的展望符——这正是 LR(1) 比 LR(0) 精确的全部来源。LR(0) 相当于把 la 恒定当成「任意终结符」，于是闭包里每个 B 的产生式都被无差别展开，展望信息全部丢失；SLR 事后用 FOLLOW(B) 来补，粒度又太粗。只有 LR(1) 是在闭包阶段就把上下文精确携带下去。

用 worklist 而不是递归，主要不是怕栈深。真正的理由是同一个项目可能被多条路径重复推导出来，递归写法会把同一批展开做好几遍，规模一大就明显变慢。insert().second在去重的同时顺手完成了「只在真正新增时才入队」，天然避免重复处理。

3.3 GOTO 与状态编号：去重靠什么比较

GOTO 的语义很简单：把集合里所有「点后正好是 X」的项目，圆点往右挪一格，然后对新得到的核心集合求闭包。

std::set<Item> goTo(const std::set<Item>& I, int X) { std::set<Item> kernel; for (const Item& it : I) { const Production& p = prods[it.prod]; if (it.dot < (int)p.rhs.size() && p.rhs[it.dot] == X) kernel.insert(Item{it.prod, it.dot + 1, it.la}); // 圆点右移一格 } return kernel.empty() ? kernel : closure(kernel); // 空集不建状态 }

这里有个容易忽略的细节：GOTO 结果的空判断必须放在闭包之前。如果先闭包再判空，一个空的核心集合经过闭包仍然是空（因为 worklist 初始为空），结果一样，但语义上不清晰，而且多算一次。

主循环用一张map<set<Item>, int>完成状态去重和编号：

std::vector<std::set<Item>> states; std::map<std::set<Item>, int> stateId; std::queue<int> work; auto addState = [&](const std::set<Item>& I) -> int { auto r = stateId.emplace(I, (int)states.size()); if (r.second) { states.push_back(I); work.push(r.first->second); } return r.first->second; }; addState(closure({Item{prodOfAugStart, 0, END}})); // 初始状态：[S' -> ·S, $]

初始状态必须带着$做闭包，这是 LR(1) 的种子；SLR 模式下虽然 la 不参与，但保留这个写法能让三种模式共用同一段构造代码。

去重的代价需要心里有数：每个状态都要做一次集合的字典序比较，复杂度是 O(|I| log|I|)，状态数上百时完全无感，上千之后就开始肉疼。常见的优化是只比较核心项目（kernel，即圆点不在最左端的那些），因为闭包由核心唯一决定。这个观察不只是性能技巧，它还是 LALR(1) 状态合并的理论依据——两个 LR(1) 状态如果核心相同，它们的区别只在展望符上，合并它们得到的就是 LALR(1)。

4. 分析表：ACTION 和 GOTO 里每个格子的值是怎么算出来的

项目集规范族建好之后，剩下的活是把「状态 + 符号」翻译成「动作」。ACTION 表管终结符，GOTO 表管非终结符，两边的填写规则只有三条，但它们之间的差别正好覆盖了三种分析算法的全部分歧。

4.1 三条填写规则与它们的直观含义

for (int i = 0; i < (int)states.size(); ++i) { for (const Item& it : states[i]) { const Production& p = prods[it.prod]; if (it.dot < (int)p.rhs.size()) { int X = p.rhs[it.dot]; int j = trans[i][X]; // goto(Ii, X) 的目标状态 if (isTerminal[X]) setAction(i, X, SHIFT, j); // 规则一：移进 else setGoto(i, X, j); // 规则三：GOTO } else if (p.lhs == S_aug) { setAction(i, END, ACCEPT, 0); // [S' -> S·, $] } else { // 规则二：归约。LR(1) 用项目自带展望符；SLR 退化成 FOLLOW(lhs) const std::set<int>& labels = (mode == SLR) ? follow[p.lhs] : std::set<int>{it.la}; for (int a : labels) setAction(i, a, REDUCE, it.prod); } } }

三条规则的直观含义值得掰开说。规则一（移进）处理的是「圆点后面蹲着一个终结符」，说明分析器打算把这个符号吃进来，于是把目标状态压栈。规则三（GOTO）处理的是「圆点后面蹲着一个非终结符」，这不是当前符号能决定的，要等归约之后把左部符号压栈时才会查这张表。规则二（归约）是唯一可能产生冲突的地方：同一个格子上如果已经被写过 SHIFT，再写 REDUCE 就是移进/归约冲突；如果被写过另一个 REDUCE，就是归约/归约冲突。

setAction里的冲突检测强烈建议保留，并且把冲突打成可读的信息：

void setAction(int state, int terminal, int type, int arg) { auto& cell = action[state]; // map<int, Action> auto it = cell.find(terminal); if (it == cell.end()) { cell[terminal] = {type, arg}; return; } if (it->second.type != type || it->second.arg != arg) conflicts.push_back({state, terminal, it->second, {type, arg}}); }

冲突信息是整个实验里信息量最大的调试输出。移进/归约冲突意味着分析器不知道该继续读还是该收手；归约/归约冲突意味着两条规则都能收，通常指向文法本身有二义性，或者用错了算法档位。

4.2 SLR、LR(1)、LALR(1)：三档精度与状态数

用悬垂 else 这个经典文法就能把 SLR 和 LR(1) 的差距看得很清楚：

stmt -> if E then stmt | if E then stmt else stmt | id

在读完if E then stmt之后，分析器面对一个可归约项目stmt -> if E then stmt ·。SLR 查的是 FOLLOW(stmt)，而else确实可能出现在 stmt 后面（来自第二条产生式），于是else这一格既要移进又要归约，冲突就这么凭空冒出来了——注意这不是文法有二义性，是 SLR 的精度不够。LR(1) 里这个项目的展望符取决于它是在哪个上下文里被推出来的，在「外层没有 else 可配」的那个上下文里，展望符集合压根不包含else，冲突自然消失。

LALR(1) 的代价在另一个方向。合并同核心状态时，两个状态原本各有各的展望符，合并之后展望符取并集，本来分别在两个状态里互不干扰的归约动作，可能被塞进同一个格子里，凭空造出归约/归约冲突。存在一类文法，它是 LR(1) 的但不是 LALR(1) 的，经典例子是S -> aAd | bBd | aBe | bAe、A -> c、B -> c，读入a c和b c之后的两条路径核心相同、展望符不同，合并就炸。

4.3 表的存储与驱动循环：状态栈才是真正的「记忆」

文法不大时，用稀疏表比二维数组更省内存，调试时也更好打印：

struct Action { int type; int arg; }; // SHIFT: arg=目标状态; REDUCE: arg=产生式号; ACCEPT std::vector<std::map<int, Action>> action; // action[state][terminal] std::vector<std::map<int, int>> goTab; // goTab[state][nonTerminal] bool parse(const std::vector<int>& tokens) { std::vector<int> states{0}; // 状态栈，栈顶是当前状态 std::vector<int> syms; // 符号栈，主要给建树和报错用 std::vector<Node*> nodes; // 与 syms 平行，归约时挂子树 size_t pos = 0; while (true) { int s = states.back(); int a = (pos < tokens.size()) ? tokens[pos] : END; auto it = action[s].find(a); if (it == action[s].end()) return reportError(states, a); // 空格子 = 语法错误 const Action& act = it->second; if (act.type == SHIFT) { states.push_back(act.arg); syms.push_back(a); nodes.push_back(new Leaf(a)); ++pos; } else if (act.type == REDUCE) { const Production& p = prods[act.arg]; int k = (int)p.rhs.size(); int s2 = states[states.size() - 1 - k]; // 弹出 k 个状态后露出的栈顶 Node* n = new Node(p.lhs); for (int i = 0; i < k; ++i) { n->children.push_back(nodes.back()); nodes.pop_back(); states.pop_back(); syms.pop_back(); } std::reverse(n->children.begin(), n->children.end()); syms.push_back(p.lhs); nodes.push_back(n); states.push_back(goTab[s2][p.lhs]); // GOTO 压入 } else { root = nodes.back(); return true; // ACCEPT } } }

这段代码里有一个永远成立的不变式：states.size() == syms.size() + 1。原因很直白，初始状态单独占一格，之后每次移进或归约都同时改两个栈，且改动量一致。归约时先算出s2再弹栈，顺序不能反，弹出 k 个状态后剩下的栈顶就是 GOTO 表的行号——这个下标计算是全场最容易写错的地方，写成states[size - k]会查到被弹掉的那个状态上去。

k == 0（归约 ε 产生式）时循环体一次都不执行，s2就等于当前栈顶，行为天然正确，这是用空 vector 表示 ε 换来的第二个便利。

5. 避坑与排查：语法分析实验里最容易翻车的五处

5.1 文法与集合层面

现象：输入稍微长一点的表达式就栈溢出，短输入完全正常。原因多半是直接左递归，E -> E + T | T这种写法在 LR 里毫无问题，但如果同时写了一份递归下降做对照实验，那它必然会无限递归。解决方向有两个：要么明确分工，LR 版本保留左递归不动（LR 天生擅长处理左递归，消除它反而让文法变丑），递归下降版本改写成右递归E -> T E'、E' -> + T E' | ε；要么干脆用 SLR 版本做主力，递归下降只留作教学演示。

现象：FIRST 集合里出现了 ε，导致分析表的列里冒出一个不该存在的终结符。根源是把 ε 当成了普通终结符塞进集合。正确的做法是让 ε 完全不进 FIRST，可空性用 nullable 布尔单独承载，代码里所有「并入 FIRST」的地方都跳过 ε。这样 FOLLOW 的规则二只需要判断betaNullable，不需要在集合里做差集。

5.2 表构造层面

现象：整张表跑完，ACCEPT 就是不肯触发，输入读到底也只报错。十有八九是漏了增广文法。直接用起始符号 S 建初始项目[S -> ·α]，当 S 在右部出现时，[S -> α·]既可能是「归约到 S」，也可能是「整个输入读完了」，判据不唯一。加上S' -> S，初始项目变成[S' -> ·S, $]，接受条件就是「存在项目[S' -> S·, $]且当前符号是$」，一句话判完。

现象：用 SLR 跑出来一堆移进/归约冲突，但理论课上明确说这个文法是 LR(1) 的。这不是 bug，是算法精度问题。先打印冲突涉及的那两个项目，看看归约项目的左部符号的 FOLLOW 集里是不是混进了不该有的终结符。如果确实是 FOLLOW 太粗，切到 LR(1) 模式重跑一遍，冲突应该消失；如果切了还有，那才是文法真有问题。

5.3 运行时层面

现象：归约之后 goto 查表拿到 0、越界或者直接崩溃，而且只在特定输入上出现。大概率是s2的下标算错了，或者归约长度k取的不是rhs.size()。最有效的排查手段是在parse循环里加断言assert(states.size() == syms.size() + 1)，一旦这个不变式被破坏，问题一定出在上一次弹栈/压栈的配对操作上。再往下查，就把每一步的state、pos、动作类型打出来对着表看，通常三步之内就能定位。

注意：报错位置差一个 Token 是另一个高频问题。错误处理里打印的应该是「当前状态期待的终结符集合」加上「实际读到的那个」，后者是tokens[pos]而不是tokens[pos-1]。期待的终结符集合直接从action[state]的所有 key 里取，不需要另外维护一份，这样报错信息和表永远同步。

6. 设计取舍：为什么「一份代码三种模式」比三个独立程序更值得写

把 SLR、LR(1)、LALR(1) 写成三个独立程序，短期看最省事，长期看会丢掉这个实验最有价值的部分：对比。当Item.la字段保留、表构造里归约展望信息只差一行取值逻辑时，切换算法档位就是一个枚举值的事，代价是运行时多几个分支判断，收益是能在同一份文法上直接看到冲突数量从 SLR 的七八个降到 LR(1) 的零，然后再看 LALR 合并状态之后会不会冒出新冲突。

验证这套实现对不对，不需要等到跑通真实语言。构造三个「陷阱文法」逐个过一遍就够：悬垂 else 用来区分 SLR 与 LR(1)，S -> aAd | bBd | aBe | bAe用来区分 LR(1) 与 LALR(1)，一个故意写成二义的表达式文法用来看冲突报告是否如预期。三个都符合理论预测，说明闭包、GOTO、表填写这三段逻辑基本可信。

缺陷也很清楚：状态合并之后无法回溯，一旦 LALR 引入了归约/归约冲突，只能回到 LR(1) 硬扛状态爆炸；稀疏表在超大文法上查询是map的 log 复杂度，换成一维数组加偏移索引会更快但可读性下降。这些取舍没有标准答案，取决于目的是「跑通实验」还是「做一个小型分析器生成器」。

我自己的习惯是：每加一个新文法，先只打印 FIRST/FOLLOW 和冲突列表，确认这两样对了再去看分析结果。有一年赶实验报告，跳过这步直接跑，结果在一个 ε 产生式上耗了整整一晚上，最后发现是 nullable 没算到不动点。从那以后我每次动表构造的代码，都强制先把这三个陷阱文法跑一遍。希望帮到你。

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