分析器C++实现核心算法与调试指南)
最近在帮几个学弟学妹调编译原理的实验代码，发现绝大多数人卡在同一个地方：LR(0)文法分析器。说难吧，它比递归下降和LL(1)都更“机械”，说白了就是查表；说容易吧，那张表怎么来、分析栈怎么配合，课本上写得又密又抽象，真到自己写C++代码时直接懵掉。这篇文章就把我实际写过、调试过的一整套LR(0)分析器实现思路完整拆开来讲，从文法存储、项目集构造、状态机构建，到ACTION/GOTO表生成、分析主循环，最后附上我自己踩过的坑和一个可以手工核对的小例子。适合正在做编译原理实验的本科生，以及想快速理解LR族语法分析原理的开发者。
先说结论：LR(0)这个名字看起来很唬人，但它的核心逻辑可以用一句话概括——根据当前的“状态”，查一张预先算好的表，决定下一步是“移进”还是“归约”。整个过程不依赖任何“向前看”符号，所以它约定俗成地用“0”来表示向前看符号的个数。这篇文章里的所有代码我都用现代C++编写，只用STL，不依赖第三方库，你只要能编译C++11以上标准就能跑。
1. 为什么我推荐用C++实现LR(0)分析器
1.1 LR(0)在编译器里到底扮演什么角色
语法分析在编译器里的位置，是夹在词法分析和中间代码生成之间的那一层。词法分析把源代码切成token流，语法分析就要判断这串token能不能由文法推导出来。编译原理教材里通常讲两大类方法：自顶向下和自底向上。LL(1)是自顶向下的代表，顺着开始符号往下推导；LR族是自底向上的代表，从输入串逐步“归约”回开始符号。
LR(0)是LR家族里最基础的一种，也是课程实验里最常见的一种。它之所以叫LR(0)，是因为它在每一步决策时都不看当前输入符号，只根据分析栈顶部的状态来决定动作。这种“盲人摸象”式的决策方式注定了它的分析能力有限，但也是因为足够简单，才适合拿来做实验、理解整个LR分析框架。
实际工程里几乎没有编译器直接采用纯LR(0)，但几乎所有自底向上的分析器——包括YACC的LALR、Bison的LALR(1)、GCC里的GLR——都是在LR(0)状态机基础上扩展出来的。把LR(0)吃透，后面理解SLR(1)、LR(1)、LALR(1)就是一层窗户纸的事。
1.2 实验题的常见要求与这份代码的定位
大部分高校的编译原理实验，对LR(0)的要求是长这样的：输入一个上下文无关文法，程序自动构造出它的LR(0)项目集族，生成LR(0)分析表，然后给定一个输入串（token序列），模拟分析过程，输出每一步的栈内容、剩余输入和所作动作。有些要求更高一点的题目还会要求你检测文法是不是LR(0)文法，遇到冲突要报错。
这份代码的定位就很明确了：一个能完整跑通“读入文法 → 构造项目集 → 生成分析表 → 分析输入串”的LR(0)分析器。我选择C++来做这个实验，原因有三个：一是STL里的set、map、vector、queue能极方便地表达项目集、状态转移和栈；二是C++的运行效率足够高，构造状态机时哪怕有几百个状态也不会有任何压力；三是语法分析器的数据结构天然就跟“状态”和“栈”这两个概念深度绑定，C++写起来思路最直白。
2. 动手前的设计：文法表示、符号表与状态机结构
2.1 用一套“产生式编号”结构把文法存起来
写LR(0)之前，第一件事是定义文法怎么存。我的做法非常简单：给每条产生式一个全局唯一的编号，然后用一个结构体记录左部和右部。右部是一个符号数组，符号统一用string表示，不用char，因为终结符有可能是id、num这种多字符的token。
struct Production { std::string left; // 产生式左部非终结符 std::vector<std::string> right; // 产生式右部符号序列 Production(const std::string& l, const std::vector<std::string>& r) : left(l), right(r) {} };所有的产生式放在一个vector里，下标就是产生式编号。这里有一个非常重要的约定：编号0永远留给增广文法的产生式。比如原文法有S -> E，增广后就必须变成：
// 0号产生式：S' -> S // 1号产生式：S -> E // ...为什么一定要增广？因为LR(0)分析需要一个“唯一”的接受状态。没有增广产生式，你没法判断“什么时候算分析成功”。增广后，当分析到S' -> S · 这个项目时，就能确定性地执行接受动作。这个习惯建议从一开始就建立，后面很多逻辑都会依赖它。
符号的归类我用了一个简单粗暴的规则：首字母是大写字母的就是非终结符，否则是终结符。作业级的文法这么处理完全够用。当然你也可以做得更严谨，让用户显式声明终结符集合，但会增加输入复杂度，实验没必要。
输入格式上，我最常用的是每行一条产生式，左部和右部用 -> 分隔，右部符号之间用空格分隔。比如：
E -> E + T E -> T T -> id2.2 项目集、闭包集合与DFA状态怎么表示
理解LR(0)的关键是理解“项目”。所谓项目，就是一条产生式右部的某个位置放了一个圆点。比如产生式 E -> E + T 可以产生四个项目：
E -> . E + T E -> E . + T E -> E + . T E -> E + T .圆点的含义是“已经分析了圆点左边的部分，准备分析圆点右边的部分”。如果圆点在最右边，说明这个产生式的右部已经完整识别，可以准备归约了。项目在C++里用两个数字就能表示：产生式编号和圆点位置。
struct Item { int prodIdx; int dotPos; bool operator<(const Item& other) const { if (prodIdx != other.prodIdx) return prodIdx < other.prodIdx; return dotPos < other.dotPos; } bool operator==(const Item& other) const { return prodIdx == other.prodIdx && dotPos == other.dotPos; } };这里重载operator<非常重要，因为我会用std::set 来表示一个项目集，set需要排序规则才能去重和比较。整个DFA的每个状态，本质上就是一个set 。
DFA状态机和状态转移表，我用两个全局变量来存：
std::vector<std::set<Item>> states; // 所有LR(0)状态 std::map<std::pair<int, std::string>, int> transitions; // (状态编号, 转移符号) -> 目标状态编号关于状态查找，我还需要一个辅助操作：给定一个项目集，在states里查找是否已经存在完全相同的状态。如果存在就直接复用编号，否则创建一个新状态。这个“查重”逻辑是构造DFA时最容易被忽略、也是最容易写出bug的地方，后面我会专门讲。
3. 核心算法：从项目集族到LR(0)分析表的完整实现
3.1 项目集闭包CLOSURE的计算
闭包是整个LR(0)算法的发动机。它的作用是从一个“种子”项目集合出发，把所有能推导出来的项目全部加进来。规则很简单：如果项目里圆点后面是一个非终结符B，那么所有以B为左部的产生式，都要以圆点在开头的形式加入当前集合。
用C++实现时，我推荐用队列做工作列表，一边往里加项目一边消费，直到队列空。这里有个细节：如果B产生式里又出现其他非终结符，闭包会继续递归扩展，所以必须用循环而不是一次遍历。
std::set<Item> closure(const std::set<Item>& I) { std::set<Item> J = I; std::queue<Item> worklist; for (const auto& item : I) worklist.push(item); while (!worklist.empty()) { Item cur = worklist.front(); worklist.pop(); // 圆点已经在最右边，没有后续符号 if (cur.dotPos == productions[cur.prodIdx].right.size()) continue; const std::string& X = productions[cur.prodIdx].right[cur.dotPos]; if (!isNonTerminal(X)) continue; for (int i = 0; i < productions.size(); ++i) { if (productions[i].left == X) { Item newItem{i, 0}; if (J.insert(newItem).second) { worklist.push(newItem); } } } } return J; }我一开始写这个函数时没加队列，只做了一次遍历就以为闭包算完了。结果在稍微复杂一点的文法上，状态总是少几个项目，分析表也缺行。后来才反应过来：闭包是传递闭包，必须反复处理新增项目带来的新非终结符。用队列处理是标准做法，建议直接照搬。
3.2 GOTO函数与整个DFA的构建
GOTO(I, X)的含义是：在项目集I里，把所有圆点后面正好是X的项目，把圆点往后移一位，得到一批新项目，再对这些新项目做闭包，就得到转移后的目标状态。
构建完整DFA的过程，本质上就是一个BFS。第一步是计算初始状态，也就是对增广产生式S' -> . S做闭包。然后从初始状态出发，穷举所有可能的转移符号，生成新状态，再去重、入队，直到没有新状态为止。
void buildDFA() { states.push_back(closure({{0, 0}})); // 初始状态 I0 std::queue<int> q; q.push(0); while (!q.empty()) { int s = q.front(); q.pop(); // 按照圆点后的符号分组 std::map<std::string, std::set<Item>> groups; for (const Item& item : states[s]) { if (item.dotPos == productions[item.prodIdx].right.size()) continue; const std::string& X = productions[item.prodIdx].right[item.dotPos]; groups[X].insert({item.prodIdx, item.dotPos + 1}); } for (const auto& [X, core] : groups) { std::set<Item> target = closure(core); // 查重 int id = -1; for (int i = 0; i < states.size(); ++i) { if (states[i] == target) { id = i; break; } } if (id == -1) { id = states.size(); states.push_back(target); q.push(id); } transitions[{s, X}] = id; } } }这段代码有两个细节值得说。第一，groups里存的是“圆点已经移动过的核心项目”，target再对core做closure。不要直接对整组项目做闭包，否则会出现“项目还没实际移动圆点，就被闭包加了进来”这种错误。第二，查重时用std::set的比较来对比两个状态是否相等，set自动排序，逐个状态比较就行，几百个状态的文法实测下来也就是毫秒级。
3.3 ACTION/GOTO表的填写规则与冲突判定
DFA构建完成，项目集族就出来了，接下来是填LR(0)分析表。分析表分两部分：ACTION表以终结符为列，GOTO表以非终结符为列。行都是DFA状态编号。
填表规则总结起来是三条：
- 移进项目A -> α . a β，其中a是终结符，那么在ACTION[当前状态][a]填SHIFT，值是转移目标状态编号。
- 归约项目A -> α .，那么对所有终结符（包括#）在ACTION[当前状态][终结符]填REDUCE，值是产生式编号。
- 接受项目S' -> S .，那么在ACTION[当前状态][#]填ACC。
GOTO表就比较简单了：对项目 A -> α . B β，其中B是非终结符，在GOTO[当前状态][B]填转移目标状态编号。
这里有一个LR(0)与其他LR变体最大的区别，也是几乎所有初学者的困惑点：归约项目为什么对“所有”终结符都填归约？因为LR(0)不看下一个输入符号，它只知道“当前句柄已经形成，该归约了”。这种一刀切的做法会产生大量冲突。如果同一个表格位置既要填SHIFT又要填REDUCE，或者要填两个不同的REDUCE，就说明文法不是LR(0)文法，分析表构造失败。
enum ActionType { ERROR, SHIFT, REDUCE, ACC }; struct Action { ActionType type; int value; }; std::vector<std::vector<Action>> actionTable; std::vector<std::vector<int>> gotoTable; bool buildTables() { bool ok = true; actionTable.assign(states.size(), std::vector<Action>(terminals.size(), {ERROR, -1})); gotoTable.assign(states.size(), std::vector<int>(nonTerminals.size(), -1)); for (int s = 0; s < states.size(); ++s) { for (const Item& item : states[s]) { if (item.dotPos < productions[item.prodIdx].right.size()) { const std::string& X = productions[item.prodIdx].right[item.dotPos]; if (isTerminal(X)) { fillAction(s, terminalIndex[X], {SHIFT, transitions[{s, X}]}); } else { gotoTable[s][nonTerminalIndex[X]] = transitions[{s, X}]; } } else { if (productions[item.prodIdx].left == startSymbol) { fillAction(s, terminalIndex["#"], {ACC, -1}); } else { for (int t = 0; t < terminals.size(); ++t) { fillAction(s, t, {REDUCE, item.prodIdx}); } } } } } return ok; }fillAction是我用来检测冲突的封装：如果目标格子原本是ERROR，直接写入；如果已经有内容但跟现在想写的内容不一致，就标记冲突，输出错误信息。
4. 分析器主循环：移进、归约、接受、报错怎么跑通
4.1 双栈结构与主循环流程
分析表有了，分析器本身反而最简单。LR分析器的运行模型是“状态栈 + 符号栈”双栈并行。状态栈从0开始，符号栈初始为空，输入串末端追加一个#。
主循环的每一轮只做四件事：看状态栈顶查到对应行的ACTION表；根据动作类型执行操作；然后循环。整个过程用伪代码描述：
while (true) { 查 ACTION[状态栈顶][当前输入符号]; if (SHIFT 状态s) { 状态栈push(s); 符号栈push(当前输入); 输入指针后移; } else if (REDUCE 产生式编号p) { 弹出右部长度个状态和符号; 查GOTO表; 压入新状态; 符号栈push(左部); } else if (ACC) { 接受; break; } else { 报错; break; } }这个循环是所有LR家族分析器共同的“骨架”，不管是LR(0)、SLR(1)还是LALR(1)，甚至LR(1)，驱动部分都长这样。区别只在于ACTION表是怎么填出来的。所以在实现时，我建议把主循环跟建表逻辑分开封装，后面扩展实验时会非常舒服。
4.2 归约时的出栈入栈细节和空产生式
归约动作是新手最容易写错的地方。归约 A -> β 时，要做的事情是：从两个栈里各弹掉 |β| 个元素，然后把A作为符号压回符号栈，再根据当前状态栈顶，查GOTO表得到新状态，压入状态栈。
这里我要强调一个很多人第一遍写都会犯的错：状态栈和符号栈必须同时、同步地弹出|β|个元素。符号栈弹出|β|个符号，状态栈也要弹出|β|个状态。如果弹出数量不对，状态栈顶就落在错误的位置，下一步查表必然错乱。
空产生式（ε产生式）是一个特殊的边缘情况。如果 A -> ε 这种产生式存在，它的right是空的，那么归约时要弹出的数量是0。也就是说，状态栈和符号栈都不弹任何东西，直接查当前状态栈顶的GOTO表，压入新状态。这个逻辑代码上天然支持，只要弹出的循环次数等于right.size()，空产生式自动就是0次。我第一次实现时没想过这个问题，后来跑一个带空产生式的文法才发现这么处理正好是对的。
分析过程要打印出来给实验报告用。我每次循环迭代都会输出状态栈内容、符号栈内容、剩余输入串、以及本次动作，格式类似：
状态栈: 0 5 3 符号栈: # id * 输入串: id $ # 动作: 归约 T -> T * F这个输出格式从最初调试一直用到现在，直观程度比任何调试器都高。
5. 实测踩坑记录与调试技巧（附一个完整例子）
5.1 五个高频运行错误的排查速查表
我把这几次调试LR(0)分析器时遇到的所有问题汇总成一张速查表，每一行都是真实踩过的。
| 现象 | 根本原因 | 解决办法 |
|---|---|---|
| 程序启动后状态只有一两个，明显少于预期 | CLOSURE只做了一次遍历，没有传递闭包 | 改用队列做工作列表，参照3.1节 |
| 分析id+id时到第N步开始乱归约 | 归约时状态栈弹出个数和右部长度不一致 | 检查归约代码，状态栈和符号栈同步弹 |
| 某个状态在表中找不到对应行 | 状态编号查重失误，生成了重复状态 | 确认set 的operator<是否正确定义 |
| 报一堆斜杠冲突，但文法明明应该没问题 | 多个归约项目同时存在，归约填了全部终结符 | 确认是否真为LR(0)，若是则改用SLR(1) |
| 输入串用std::string存储，多字符token被拆开 | 没有做词法切分，直接把string当字符数组 | 先对输入串按空格切分得到token数组 |
这里面最坑的是第一个和第二个。闭包没算全的bug特别隐蔽，因为错误不在闭包函数本身报出来，而是后续分析表处处对不上。我的排查经验是：写一个dumpState()函数，把每个项目集的所有项目全部打印出来，再和课本例题人工核对。如果状态数量和项目内容完全一致，闭包就是对的，再往下查表。
第二个问题出现的原因是归约函数里的循环我一开始写的是for (int i = 0; i < alpha.size(); ++i) { stateStack.pop_back(); symbolStack.pop_back(); }，看似没问题，但alpha我取的是产生式右部的长度，某个产生式的右部长度是2，写代码时却误用了产生式编号，弹了2个状态却弹了3个符号栈。这类问题用打印输出加断言（assert(stateStack.size() == symbolStack.size())）可以很早发现。
5.2 一个可手工核对的小例子
拿一个经典小文法来完整走一遍：
0) S' -> E 1) E -> E + T 2) E -> T 3) T -> id终结符是 +、id、#，非终结符是 S'、E、T。构造出的LR(0)状态机如下：
I0 = { S' -> . E, E -> . E + T, E -> . T, T -> . id } I1 = { S' -> E ., E -> E . + T } // 从I0经E I2 = { E -> T . } // 从I0经T I3 = { T -> id . } // 从I0经id I4 = { E -> E + . T, T -> . id } // 从I1经+ I5 = { E -> E + T . } // 从I4经TACTION表和GOTO表整理出来应该是这样：
| 状态 | id | + | # | E | T |
|---|---|---|---|---|---|
| 0 | S3 | 1 | 2 | ||
| 1 | S4 | ACC | |||
| 2 | R2 | R2 | |||
| 3 | R3 | R3 | |||
| 4 | S3 | 5 | |||
| 5 | R1 | R1 |
用输入串“id + id #”手工跑一遍：
初始: 状态栈[0] 符号栈[#] 输入[id + id #] 查ACTION[0][id]=S3，移进 → 状态栈[0,3] 符号栈[#,id] 查ACTION[3][+]=R3，按T->id归约，弹出1个 → 状态栈[0] 符号栈[#] 查GOTO[0][T]=2，压入 → 状态栈[0,2] 符号栈[#,T] 查ACTION[2][+]=R2，按E->T归约，弹出1个 → 状态栈[0] 符号栈[#] 查GOTO[0][E]=1，压入 → 状态栈[0,1] 符号栈[#,E] 查ACTION[1][+]=S4，移进 → 状态栈[0,1,4] 符号栈[#,E,+] ... 最后查ACTION[1][#]=ACC，分析成功这段手工推导非常值钱。我调试时经常拿这种小例子，人工算一遍流程，再跟程序输出比对，很快就能定位到出错环节。
6. 从LR(0)走向SLR(1)：下一步还能做什么
6.1 LR(0)的冲突本质
LR(0)最大的限制，就是归约动作“不看任何向前看符号”。一个状态下只要同时存在一个可归约项目和另一个可移进项目，而且它们的动作都落在同一个终结符上，就产生移进-归约冲突。两个归约项目同时存在就叫归约-归约冲突。经典例子是这个文法：
S -> L = R | R L -> * R | id R -> L它在某些状态里同时含有可以继续移进=的项目和已经可以归约R->L的项目。遇到=时到底移进还是归约？LR(0)无法决策。不过这类文法实际意义很大（赋值语句和右值表达式的归并），所以必须引入向前看信息来消除冲突。
6.2 SLR(1)到底改了什么
SLR(1)的改进只有一句话：归约项目A -> α . 不再对“所有”终结符填归约，而是只对FOLLOW(A)里的终结符填归约。这样很多在LR(0)下冲突的格子就被区分开了。实现上只需要在建表前多算一步FIRST和FOLLOW集合，然后归约时遍历FOLLOW(A)而不是遍历所有终结符。
我建议实验做完LR(0)之后，顺手把SLR(1)也实现了。改动量非常小，算FOLLOW集合是200行以内的事，但你对LR族分析器的理解会立刻上一个台阶。毕竟课程考核里最常问“为什么这个文法不是LR(0)而是SLR(1)”这类问题，亲手改一遍比背十遍定义都管用。
6.3 如果实验还想加码还能做什么
如果时间和精力允许，后面还有几条扩展路线值得做：一是给分析器加上语义动作，在归约时执行代码，能直接算出一个算术表达式的值，实验的观赏性立刻翻倍；二是输出分析树，归约时记录树的父子关系，就能让分析过程“看得见”；三是做错误恢复，加入几条常用的panic模式，处理不合法的输入串时不至于一报错就崩溃。
我个人在实际操作中的体会是：LR(0)分析器是编译原理实验里最值得手写一遍的项目之一。它不像词法分析那样只要会写循环就行，也不像LL(1)那样预测分析表的构造过程比较直觉。LR(0)逼迫你把“文法 → 项目 → 状态 → 表 → 栈”这条完整链路串起来理解。第一次看到自己构造的状态机和写死的课本例子完全吻合，第一次看到程序对输入串准确做出一连串移进和归约，那种成就感还是挺真实的。最后再分享一个小技巧：所有LR族分析器的调试，第一优先级永远是打印状态机和分析表，对着打印结果手工跑一个小例子，哪一步对不上，bug就在哪一步前面。
