LR(0) 是编译原理里自底向上语法分析的地基但很多人在课程里把它当成一个过渡概念匆匆翻过——知道有个圆点符号知道要构造项目集规范族然后就直接跳到 SLR 和 LALR 去了。我当初也是这么干的直到自己真的要用 C 从零实现一个语法分析器才发现 LR(0) 的 DFA、闭包、GOTO 这些概念一旦没有被亲手写成代码后面所有所谓的高级分析算法都是飘的。这篇文章我用 C 把整个 LR(0) 分析器完整实现一遍从数据结构、闭包与 GOTO 运算到规范族构建、ACTION/GOTO 表生成再到最终的表驱动分析循环每一步都给代码、讲原理、说坑点。适合正在学编译原理、要做课程设计或者想补强底层原理的同学照着敲一遍LR 分析这条线基本就通了。1. 从递归下降到LR(0)为什么自顶向下那套在这里不够用1.1 自顶向下与自底向上的本质差异语法分析有两套完全相反的策略。自顶向下分析比如递归下降是从开始符号出发不断用产生式右部替换非终结符试图推导出和输入串完全一致的一棵语法树。它的优点是实现直接、错误定位友好缺点也很明显左递归文法必须先消除、回溯会带来指数级开销、选择产生式在很大程度上靠人肉消除公共左因子。自底向上的思路刚好反过来。它从输入串的第一个符号开始不断把已经读入的符号串中能归约的部分替换成产生式的左部最终的目标是把整个输入串归约成开始符号。这个过程有一个非常重要的性质它不需要向前看一串符号来做选择而是完全由栈里的历史信息和下一个输入符号决定下一步动作。这就是 LR 分析家族的原理基础。很多初学者会把 LR 和黄家驹的歌曲混在一起念叨LR 就是 Left to Right 扫描这没错但它真正的全称是 Left-to-right scanning with Rightmost derivation in reverse也就是从左到右扫描输入 逆序执行最右推导。逆序的最右推导翻译成人话就是每一步栈顶都应该恰好是一个句柄我们反复把句柄归约掉。理解这一点后面所有运算就都有了锚点。1.2 LR分析器的整体形状DFA加一个栈一个 LR 分析器的机械结构其实非常朴素一条输入带、一个分析栈、一张由 DFA 状态转移演化出来的分析表。我们并不直接在程序里维护一棵语法树而是维护两个栈——状态栈和符号栈。状态栈记录的是当前我在自动机的哪个状态符号栈记录的是我已经读入并归约出了哪些文法符号。每次循环做三件事情读入下一个输入符号lookahead查看分析表 ACTION[状态栈顶][输入符号]然后执行移进shift、归约reduce或者接受accept中的一种动作。移进就是把输入符号压入符号栈把 DFA 的下一个状态压入状态栈归约则是弹出与产生式右部长度相同的符号和状态再根据 GOTO[状态栈顶][产生式左部] 压入新的状态。这就暴露了 LR 分析和递归下降最关键的区别递归下降把选择哪条产生式分散在代码的 if/else 和函数调用里而 LR 分析把所有选择集中成了一张表执行器是统一的。我最初觉得这种查表执行很蠢后来才意识到查表执行恰恰是它的优点文法变了表变了驱动循环一行都不用改。这也是为什么工业级的语法分析器生成器能够存在。1.3 活前缀与句柄LR(0)的项目直觉在进入代码之前还有两个概念必须花点力气讲清楚因为它们决定了你后面看闭包运算时能不能一眼看穿。第一个是句柄。在一个最右推导中每一步被替换掉的那个子串也就是产生式右部就是句柄。自底向上分析的核心流程可以简化成找到句柄、把句柄归约掉、重复直到只剩开始符号。第二个是活前缀。它更微妙一点活前缀是输入串某个前缀这个前缀后面还可以继续扩展成句柄的前缀换句话说它不会越过句柄的右端。为什么自底向上分析关注这个东西因为只要栈中的文法符号串是一个活前缀就说明当前分析还没有出错还有可能通过归约形成完整的句柄。LR(0) 的整个构造过程本质上就是为了构建一个能识别所有活前缀的 DFA。后面我们要写的所有代码——项目、闭包、GOTO、规范族、ACTION/GOTO 表——都是在为这个 DFA 服务。理解到这一层你就不会被为什么要增广文法为什么要造这么多状态之类的问题卡住不增广DFA 就没有唯一的接受状态不构造足够多的状态就无法区分下一步该移进还是归约。2. 项目与两个核心运算闭包和GOTO到底在算什么2.1 项目就是带圆点的产生式LR(0) 分析表是由一个叫LR(0) 项目集规范族的东西生成的。项目item这个概念极其重要但我见很多人学了一个学期还在问这个圆点到底放在哪个位置。其实圆点的作用就是标记分析进度。一个产生式A - αβ把圆点放在右部的任意位置就得到一个项目。圆点左边的部分表示我已经识别/归约出来的部分圆点右边的部分表示我接下来期待看到的部分。例如项目A - α·β表示我期待看到一个可以被归约成A αβ的句子目前已经确认了α接下来要处理β。按照圆点位置不同项目分几类。圆点在右部最左端比如A - ·β表示还没开始识别这个产生式的右部圆点后面是终结符比如A - α·aβ这种叫移进项目因为下一步的动作大概率是读入终结符a圆点在右部末尾比如A - α·这种叫归约项目表示我们已经收集齐了整个右部可以把α归约成A。如果右部恰好是空串 ε那么项目A - ·同时是开始项目和归约项目后面处理 ε 产生式时要特别注意。初学者容易犯的一个错误是认为项目就是产生式。不对一个产生式右部有几个符号就能产生几个项目加上圆点在末尾的是右部长度1个。这个区别在用代码表示的时候非常关键我们稍后在数据结构里会看到。2.2 closure运算为什么遇到非终结符要展开闭包运算closure是把一个项目集合扩大成自洽集合的操作。具体规则对于一个项目集合I不断执行以下操作直到集合不再变化如果集合中某个项目形如A - α·Bβ也就是圆点后面是一个非终结符B那么对于B的每一条产生式B - γ把项目B - ·γ加入集合。这条规则看起来只是机械地照做但它背后的直觉非常重要。当分析器期待识别一个非终结符B的时候它必须同时准备好B的所有开局方式。这就像你在一个岔路口准备走到目的地B你必须把所有通往B的路都放进视野里因为现在还不知道会走哪条。把B - ·γ全部加入集合就是把这些路都登记在案。换个角度理解状态里如果出现了A - α·Bβ说明自动机已经确认了α接下来是一个B。但B本身是一个非终结符它会被某条产生式展开所以在当前状态里B - ·γ这些未来的可能路径也必须存在。闭包做的正是这件事让项目集在遇到非终结符必须展开这个规则下封闭。实际写代码的时候closure 的对象是一个项目集合而且闭包结果中不允许有重复项目所以实现时用std::setItem最省心配合一个队列做迭代。std::setItem closure(const std::setItem I) { std::setItem J I; std::queueItem work; for (const auto item : J) work.push(item); while (!work.empty()) { Item cur work.front(); work.pop(); const Production p productions[cur.prod_id]; if (cur.dot_pos p.rhs.size()) { const std::string symbol p.rhs[cur.dot_pos]; if (is_nonterminal(symbol)) { for (const auto prod : prods_by_lhs[symbol]) { Item next_item{prod.id, 0}; if (J.insert(next_item).second) { work.push(next_item); } } } } } return J; }这里prod.id是产生式的全局编号dot_pos是圆点位置。用set插入返回值判断true/false可以顺便去重避免同一个项目被反复加入队列。我一开始实现的时候漏了加入后必须入队这一步导致闭包只扩了一轮就停了状态数少了一半后面排查了很久。2.3 goto运算把圆点往前推一格GOTO 运算是闭包的搭档。它的作用是在一个项目集I中读入一个文法符号X之后下一个状态的项目集合是什么。规则只有两条找出所有圆点后面正好是X的项目也就是形如A - α·Xβ把圆点移到X的右侧变成A - αX·β对得到的新项目集合再做一次闭包。用代码说就是先收集再整体右移圆点最后闭包std::setItem goto_set(const std::setItem I, const std::string X) { std::setItem J; for (const Item item : I) { const Production p productions[item.prod_id]; if (item.dot_pos p.rhs.size() p.rhs[item.dot_pos] X) { J.insert({item.prod_id, item.dot_pos 1}); } } return closure(J); }闭包和 GOTO 是 LR 自动机构造的两个核心引擎。一个管横向展开一个管纵向推进。我见过的很多人对这两个运算死记硬背但只要你抓住圆点移动到符号之后这个动作GOTO 就永远不会错只要抓住遇到非终结符必须展开其所有产生式这个动机闭包也永远不会忘。2.4 C端的数据结构选型在写算法之前先把 C 数据结构定下来。我建议做如下设计// 文法符号统一用字符串表示终结符、非终结符靠集合区分 enum SymbolKind { TERMINAL, NON_TERMINAL }; struct SymbolInfo { SymbolKind kind; }; struct Production { int id; std::string lhs; std::vectorstd::string rhs; }; // LR(0) 项目产生式编号 圆点位置 struct Item { int prod_id; int dot_pos; bool operator(const Item o) const { if (prod_id ! o.prod_id) return prod_id o.prod_id; return dot_pos o.dot_pos; } }; // 一个 DFA 状态 struct State { int id; std::setItem items; std::unordered_mapstd::string, int transitions; };这里有一个对新手来说很隐蔽的坑Item放进std::set必须定义严格弱序也就是operator。如果你忘了定义编译直接报错如果你定义的方式不稳定比如只比较dot_pos不比较prod_id那么两个不同但看起来排序一样的项目会被当成同一个状态和表就全错了。我的习惯是永远用两个字段做字典序比较简单可靠。符号识别方面我维护了两个unordered_setstd::string一个存终结符、一个存非终结符is_terminal和is_nonterminal就是查这两个集合。这样代码写起来最直观代价是查找时按字符串哈希走对课程设计规模的数据完全没有性能压力。如果要追求性能可以把符号字符串统一映射成整数 id后面所有比较都走整数但我建议先跑通再优化别一上来就把问题复杂化。3. 规范族构建从增广文法到识别活前缀的DFA3.1 增广文法给DFA一个唯一的起点构造 LR 自动机之前必须先给文法做一次增广。所谓增广就是添加一个新的开始符号S和一条产生式S - S其中S是原来的开始符号。为什么要多此一举因为原来的开始符号可能出现在某个产生式的右部直接拿它当起点DFA 无法区分这是开始状态和我刚好归约到了一个S。增广之后S永远不会出现在任何产生式的右部于是分析器看到项目S - S·时可以百分之百确定整个输入串已经成功归约成开始符号了这个项目就是唯一的接受项目。在实际的 C 实现里增广操作就是往产生式列表头部插入一个新产生式并把它设置为起始产生式。cpp // 假设原开始符号是 start_symbol std::string augmented_start S; productions.insert(productions.begin(), {0, augmented_start, {start_symbol}});### 3.2 BFS构建状态机与状态去重 有了闭包和 GOTO 两个函数构造规范族也叫 LR(0) 项集族就是一个标准的 BFS 1. 初始状态 I0 closure({S - ·S}) 2. 对当前状态的每个项目找出圆点后面的符号终结符或非终结符都算 3. 对这些符号分别求 GOTO 4. 如果 GOTO 得到的项目集是一个没见过的新集合就创建一个新状态并记录转移边 5. 重复直到没有新状态产生。 这里最关键的工程问题是状态去重。两个项目集可能是同一个状态但它们的 std::setItem 内容完全一样。怎么快速判断一个集合是否已经见过我的做法是对项目集生成一个唯一的字符串 key把所有项目按 prod_id 和 dot_pos 排序后序列化再用 unordered_mapstring, int 存放 key 到状态编号的映射。 cpp std::string state_key(const std::setItem items) { std::string key; for (const Item it : items) { key std::to_string(it.prod_id) : std::to_string(it.dot_pos) ;; } return key; }因为std::setItem本身有序直接遍历得到的就是稳定顺序生成的 key 完全确定不会因为迭代顺序不同而变化。这一步做对了整个状态机才是确定性的如果你用vector存项目又不排序同一个状态可能被创建两次DFA 就变成了一坨错误的状态乱麻。BFS 完整代码示意std::vectorState states; std::unordered_mapstd::string, int seen; void build_dfa() { Item init_item{0, 0}; // S - ·S std::setItem init_items closure({init_item}); states.push_back({0, init_items, {}}); seen[state_key(init_items)] 0; for (int i 0; i (int)states.size(); i) { std::setstd::string symbols; for (const Item it : states[i].items) { const Production p productions[it.prod_id]; if (it.dot_pos p.rhs.size()) { symbols.insert(p.rhs[it.dot_pos]); } } for (const std::string sym : symbols) { std::setItem g goto_set(states[i].items, sym); if (g.empty()) continue; std::string key state_key(g); int to; if (seen.count(key)) { to seen[key]; } else { to (int)states.size(); states.push_back({to, g, {}}); seen[key] to; } states[i].transitions[sym] to; } } }注意循环变量i states.size()因为循环体内部会往states里 push 新状态所以用这种动态增长的写法条件判断每次都会重算size()天然就实现了 BFS 的直到没有新状态。3.3 冲突检测LR(0)是不是够格的判断点规范族构造完之后最重要的一件事是检查每个状态内部是否存在分析冲突。冲突只有两类移进-归约冲突同一个状态里既存在移进项目A - α·aβ肯定是终结符a又存在归约项目B - γ·。归约-归约冲突同一个状态里存在两个不同的归约项目比如A - α·和B - β·。在代码层面遍历每个状态的所有项目统计是否同时出现移进项目和归约项目即可for (const State st : states) { bool has_reduce false; bool has_shift false; for (const Item it : st.items) { const Production p productions[it.prod_id]; if (it.dot_pos p.rhs.size()) { has_reduce true; } else if (is_terminal(p.rhs[it.dot_pos])) { has_shift true; } } if (has_reduce has_shift) { std::cout shift-reduce conflict in state st.id \n; } if (has_reduce /* 两个及以上不同的归约项目 */) { std::cout reduce-reduce conflict in state st.id \n; } }如果一个 LR(0) 文法的规范族里没有任何冲突那么它就是一个 LR(0) 文法可以直接构造无冲突的分析表。不过说实话真正能被 LR(0) 干净处理的文法很少后面我会详细说这个问题。4. ACTION与GOTO表把DFA翻译成一张可以查的表4.1 填表规则shift、reduce、accept各就各位DFA 构造完接下来把它翻译成驱动分析器用的两张表ACTION 表和 GOTO 表。ACTION 表的行是状态列是终结符表项是动作GOTO 表的行是状态列是非终结符表项是目标状态编号。对每个状态i遍历它的项目集合按下面的规则填表如果项目是A - α·aβ其中a是终结符且GOTO(i, a) j那么ACTION[i][a] shift(j)。如果项目是A - α·圆点在末尾且A不是增广开始符号S那么对于所有终结符列都填reduce(A - α)。注意这里没有向前看符号这就是LR(0)名字里那个0的含义。如果项目是S - S·那么ACTION[i][$] accept。对所有非终结符AGOTO[i][A] GOTO(i, A)。填表过程中如果某个位置已经填过动作再要填另一个动作就说明有冲突这个文法不是 LR(0) 文法。我把动作表实现成std::vectorstd::vectorAction每个 Action 存一个类型和一个整数参数enum class ActionType { ERROR, SHIFT, REDUCE, ACCEPT }; struct Action { ActionType type; int target; // SHIFT: 目标状态号; REDUCE: 产生式编号; 其余为 0 }; std::vectorstd::vectorAction action_table; std::vectorstd::unordered_mapstd::string, int goto_table;ERROR表项初始为全空填表时如果发现原来不是ERROR而是别的动作立刻报告冲突。这样冲突检测就不用单独做一遍了填表过程本身就是最终的验证。4.2 表驱动主循环状态栈和符号栈的配合表生成完毕剩下的分析主循环很简短。初始时状态栈只有一个状态 0符号栈底放一个特殊的$输入串末尾也放一个$。接下来循环执行void parse(const std::vectorstd::string tokens) { std::vectorint state_stack {0}; std::vectorstd::string symbol_stack {$}; int pos 0; while (true) { int state state_stack.back(); std::string lookahead (pos tokens.size() ? tokens[pos] : $); const Action act action_table[state][lookahead]; switch (act.type) { case ActionType::SHIFT: state_stack.push_back(act.target); symbol_stack.push_back(lookahead); pos; break; case ActionType::REDUCE: { const Production p productions[act.target]; for (size_t k 0; k p.rhs.size(); k) { state_stack.pop_back(); symbol_stack.pop_back(); } symbol_stack.push_back(p.lhs); int next_state goto_table[state_stack.back()][p.lhs]; state_stack.push_back(next_state); std::cout reduce: p.lhs - ; for (const auto s : p.rhs) std::cout s ; std::cout \n; break; } case ActionType::ACCEPT: std::cout accept!\n; return; case ActionType::ERROR: std::cout syntax error at position pos \n; return; } } }这个主循环里最容易出错的地方是REDUCE动作弹出状态栈和符号栈时数量必须等于右部符号个数但符号栈弹出的最后一个符号应该恰好是右部最右边的符号。如果你在归约前不小心先 push 了什么栈就错位了。另一个细节是归约后查 GOTO 表用的是新的栈顶状态不是归约之前的状态很多跑出来的乱码归约就是错在这一步。4.3 LR(0)表中整行归约背后的含义回到填表规则第二条一旦状态里存在归约项目A - α·就对所有终结符填 reduce。这正是 LR(0) 最耿直的地方——它完全不看圆点右边的输入符号是什么只管归约。换句话说LR(0) 假设当前状态一旦归约条件成立任何输入下都应该归约。这种不做选择的归约在文法简单时没问题但稍微复杂一点的文法就会炸因为一个状态里很容易同时出现移进和归约两种项目。比如当圆点后面是终结符的项目和圆点在末尾的归约项目同时存在于一个状态时LR(0) 会给所有终结符填归约包括而移进项目希望能对执行 shift冲突就爆发了。这个具体的例子我放在下一节详细拆。很多人到这里会有一个疑问既然 LR(0) 这么弱为什么还要学它我的回答是LR(1)、SLR(1)、LALR(1) 的底层 DFA 构造和表驱动循环和 LR(0) 几乎完全一样差别只在归约动作的判定逻辑上。搞懂了 LR(0)后面这些不过是在归约前多查一个集合的微小改动。5. LR(0)的软肋一个真实冲突与SLR(1)的修补5.1 一个看似简单却让LR(0)卡住的文法看一个非常简短的文法S - S S - id E | E E - id它描述的语言是一个标识符或者一个标识符赋值给一个表达式这里表达式简化成一个标识符。这个文法没有左递归、没有二义性、也没有 ε 产生式看起来人畜无害。但我们在构造 LR(0) 自动机时很快会遇到一个状态。初始状态I0做闭包后包含这些项目S - ·S S - ·id E S - ·E E - ·id读入id之后得到状态I1S - id· E E - id·问题出现了。E - id·是归约项目而S - id· E的圆点后面是终结符意味着这个状态期待下一步读入并移进。可是 LR(0) 的规则是有归约项目就把它填到所有终结符列上。于是在ACTION[I1][]这一格归约和移进同时发生冲突诞生。5.2 冲突的根源没有向前看符号仔细想想这个冲突的本质。读入id之后分析器面对两种可能输入可能是id $那么这里应该把id归约成E再归约成S结束输入可能是id E $那么这里应该继续移进。这两种可能性由什么区分由下一个输入符号是什么来区分。下一个是$就归约下一个是就移进。LR(0) 分析表里归约动作不看下一个符号于是它把这两种情况混为一谈——这就是没有向前看的代价。其实你不需要向前看一串符号只需要看一个就足够区分这两种情况了。这个思路直接引出了 SLR(1)Simple LR简单 LR归约A - α的时候不再对任意终结符都归约而是只对FOLLOW(A)中的终结符归约。如果下一个输入符号不属于FOLLOW(A)就坚决不归约。5.3 FIRST与FOLLOW集的计算要使用 SLR(1)就得先算出每个非终结符的FOLLOW集合。FOLLOW(A)的含义是在所有合法的句型中可能紧跟在A之后出现的终结符集合。规约成A之后下一个合法的输入终结符一定是FOLLOW(A)里的内容。FOLLOW的计算依赖两个前置知识FIRST集合和能否推出空串的判断。FIRST(X)表示从X出发能推导出的第一个终结符集合。计算FIRST时要用不动点迭代不断把产生式右部开头的符号的FIRST并入左部的FIRST直到所有集合不再变化。FOLLOW的计算规则如下$加入开始符号这里是S的FOLLOW。对于产生式A - αBβ把FIRST(β)中除了ε之外的所有终结符都加入FOLLOW(B)。如果β可以推导出ε包括β为空的情况把FOLLOW(A)的所有符号也加入FOLLOW(B)。重复直到所有FOLLOW集合稳定。对于上面那个文法简单推一下。产生式只有S - id E、S - E、E - id。初始FOLLOW(S) {$}。由S - EE在右部末尾所以FOLLOW(E)并入FOLLOW(S)得到FOLLOW(E) {$}。由S - id EE也在末尾还是并入FOLLOW(S)并没有给E加入因为在E的左边而不是右边。因此最终FOLLOW(E) {$}。注意FOLLOW(E)不含这正是解决方案的关键。5.4 SLR(1)只多一步查询就解决冲突SLR(1) 的填表规则和 LR(0) 唯一的区别在归约项目那一项LR(0)对所有终结符填reduce(A - α)。SLR(1)只对FOLLOW(A)中的终结符填reduce(A - α)。回到我们的冲突状态I1 {S - id· E, E - id·}。E的 FOLLOW 是{$}于是在ACTION[I1][]这一格只保留移进不填归约在ACTION[I1][$]这一格填归约E - id。冲突不就消失了吗当输入是id $时在I1看到$归约E - id。当输入是id id $时在I1看到移进。两条路各行其道分析表无冲突。这个例子非常有代表性。它让我意识到SLR(1) 相比 LR(0) 的改进从原理上讲只多了一个查一次 FOLLOW 集合的动作但能力上却能覆盖一大批实用文法。我那会儿第一次跑通 SLR(1) 的时候感慨最大的不是算法多精巧而是0 到 1 的跃迁确实往往是查表逻辑里一个小小的分支。5.5 LR分析家族的能力对比如果你把 LR(0)、SLR(1)、LR(1)、LALR(1) 放在一起比较能力是递增的但构造复杂度和表规模也递增方法归约时机向前看能力表规模LR(0)任意终结符都归约0 个符号最弱最小SLR(1)仅在FOLLOW(A)中的终结符归约1 个符号基于 FOLLOW中等较小LR(1)基于状态的向前看集合lookahead 精化1 个符号精确强可能很大LALR(1)LR(1) 合并同心状态1 个符号近似精确接近 LR(1)和 SLR(1) 差不多很多成熟的 LR 分析器生成器用的是 LALR(1)它的核心思想是把 LR(1) 自动机中项目相同但向前看集合不同的诸多状态合并到一起。而合并状态的前提仍然是先把 LR(0) 那套规范族构建出来。所以你看绕来绕去LR(0) 永远是那个地基。6. 完整跑通一个小语言构建、验证与排错记录6.1 选一个真正LR(0)的测试文法因为 LR(0) 很弱测试文法不能随便选。我用来做完整验证的文法是S - S S - A A - a A | b这个文法描述的语言是a*b也就是若干个a后面必须跟一个b。它虽然简单但足够展示 LR(0) 的完整工作流而且我能用手工推演和程序输出做对照。构造规范族I0 {S - ·S, S - ·A, A - ·aA, A - ·b}GOTO(I0, S) I1 {S - S·}接受状态GOTO(I0, A) I2 {S - A·}GOTO(I0, a) I3 {A - a·A, A - ·aA, A - ·b}GOTO(I0, b) I4 {A - b·}GOTO(I3, A) I5 {A - aA·}GOTO(I3, a) I3自己环回GOTO(I3, b) I4所有状态都没有同时出现移进项目和归约项目所以这是一个真正的 LR(0) 文法。看到这里你应该明白为什么这个语言这么乖——每个状态里要么只管归约要么只管移进互不干扰。6.2 自动机构建与表输出我用前面写的代码跑一遍把状态和转移边输出成文本State 0: S - .S S - .A A - .aA A - .b on S - 1 on A - 2 on a - 3 on b - 4 State 3: A - a.A A - .aA A - .b on A - 5 on a - 3 on b - 4这张输出的价值在于它和教材上手工画的 LR(0) 自动机完全吻合。如果你的程序输出和手工推导对不上绝大多数情况下是closure里少展开了一轮或者goto_set里筛错符号。我强烈建议先把自动机输出打印出来再做任何分析表的调试肉眼核对状态转移比对着错乱的归约动作猜原因快十倍。生成的 ACTION 表关键部分状态ab$0shift 3shift 4error3shift 3shift 4error4reduce A-breduce A-breduce A-b那是 LR(0)reduce 行全部填满。状态 4 只有归约项目A - b·因此无论下一个符号是什么哪怕是a这种当前状态下不可能合法出现的符号它都会归约。虽然在这里看不出大问题但这种不管三七二十一就归约的行为遇到更大的文法就会直接产生冲突。6.3 输入串分析过程跟踪用输入串a a b $走一遍步骤状态栈符号栈剩余输入动作10$aab$shift 320 3$ aab$shift 330 3 3$ a ab$shift 440 3 3 4$ a a b$reduce A-b50 3 3 5$ a a A$reduce A-aA60 3 5$ a A$reduce A-aA70 2$ A$reduce S-A80 1$ S$accept这个 trace 清晰地展示了移进直到句柄出现归约直到回到开始符号的整个过程。我在实现里加了一个打印步骤信息的开关每次 shift/reduce 都把栈打印出来调试效果非常好。6.4 常见排错经验与调试技巧最后记录几个我在写这个项目时踩过、也看身边同学踩过的坑。第一个坑是闭包迭代不完整。closure里新加入的项目必须进入待处理队列否则它会漏掉第二层展开。症状是 DFA 状态个数偏少且某些转移找不到目标状态。解决办法用set.insert的返回值判断是否新加入加入就入队。第二个坑是Item的排序定义不完整。前面提过operator必须同时比较prod_id和dot_pos只比较一个字段会让两个不同项目被set判定为等值直接导致状态内容错误。这个 bug 很阴险因为它不会编译报错只会在运行结果里悄悄出现。第三个坑是 ε 产生式。如果文法里有A - ε那么项目A - ·的dot_pos 0但同时rhs.size() 0所以它既是一个开始项目也是一个归约项目。在闭包里遇到A - ·时不要继续尝试把圆点后的符号展开因为右部为空代码要正确判断dot_pos p.rhs.size()。很多实现写死圆点位置从 0 开始判断就没考虑右部长度也是 0 的情况。第四个坑是状态去重的 key 不一致。如果两个项目集合内容一样但生成 key 时采用的序列化顺序不稳定比如用了vector而没排序同一个状态会被创建两次分析表里会出现一些幽灵状态。用std::setItem天然有序再按序遍历生成 key这个问题就避免了。调试技巧方面我最推荐的是打印状态图。把每个状态的编号、项目列表和所有转移边输出成文本然后拿它和教材上手工构造的自动机对照。一旦状态图正确分析表通常就是对的如果状态图有问题后面所有排查都是浪费。对状态比较多的文法我还会把输出整理成带缩进的树状结构一眼就能看出循环和分支的位置。另外一个实用的小技巧是在parse循环里设置最大步数上限比如 10000 步防止因为表填错而陷入死循环这在排查 shift/reduce 逻辑时能救你命。把 LR(0) 从理论走到 C 代码实际上是把一整条文法 - 项目集 - DFA - 分析表 - 驱动器的链路完整打通的过程。我个人的体会是这远比直接抄一份 LALR 生成器的代码更有价值因为当你亲手构造出第一个接受状态看到程序对aab输出 accept 的那一刻之前所有抽象的概念——活前缀、闭包、句柄——才真正在脑子里有了落点。后续如果还想继续做我建议在这个基础上把 FOLLOW 集合算出来扩展成 SLR(1)那个改动真的很小但对文法的覆盖能力提升是跨越式的。