企业官网建设流程全解析

简介：LR(0)分析表是编译原理中自底向上语法分析的核心工具。该压缩包提供了一套轻量级演示程序，面向学习编译原理、调试文法规则的学生与开发者，帮助直观理解LR(0)分析表从闭包构造到移进-归约动作的完整流程。包内共3个文件，包含1个cpp源码和2个txt说明文档，整体大小仅5KB，麻雀虽小却覆盖了分析表构建的关键步骤，适合快速阅读与二次修改。目前已有336人学习浏览，足以说明其作为教学辅助的实用价值。通过运行这套代码，读者可以清晰观察状态转换、闭包计算以及归约决策的具体实现；配套的txt文本则提供算法说明与示例数据，便于逐步跟踪分析过程，加深对句柄识别、状态转移等难点的理解，为学习更复杂的SLR、LALR分析表打下坚实基础，也可直接用于编译原理课程实验或自学入门。

1. LR(0)分析表为什么劝退：这份资源能让你少熬三个通宵

编译原理课里最劝退的一页PPT，大概率就是LR(0)分析表。原理听懂了，但让你手算项集族、闭包、ACTION表和GOTO表的时候，三张草稿纸都不够用，一不留神状态就从14跳没了。LR(0)分析表是自底向上语法分析的基础设施，编译器拿它决定遇到当前状态和输入符号时，该移进还是该归约。这份资源里带一个能跑的C++程序，输入产生式就能自动生成LR(0)项目集族和分析表，压缩包里还有两个样例文本文件。适合正在学编译原理、要交课程设计的学生，也适合想快速验证一个文法是不是LR(0)、调试冲突的在职开发。这篇文章直接把拆包、运行、读表、避坑和表驱动验证一次讲完。

2. LR(0)分析表是怎么来的：闭包、GOTO与移进-归约

在动手跑程序之前，最好先把LR(0)分析表的生成流程过一次。工具只是把流程自动化了，你看不懂输出，冲突发生也找不到原因。下面这段原理对应的是程序里最核心的几段逻辑，后文所有的输出解读都依赖这几个概念。

2.1 LR(0)里的“0”到底是什么意思

LR的完整含义是Left-to-right scanning加上Rightmost derivation，也就是从左到右扫描输入，按最右推导的逆序做归约。所谓自底向上分析，本质上就是反复执行“找句柄→归约”的过程，直到把输入串归约成文法的开始符号。举个最朴素的例子，文法只有三条产生式：

S->E E->E+T E->T T->n

输入串是n+n。分析时你实际做的事情是：先把最右边的n归约成E，再归约成T？不对，顺序是从左往右读，先看到n，把它归约成T，再归约成E，读到+之后继续读n，最后把E+T归约成E，再由E归约到S。这一串动作的逆序恰好就是最右推导。

LR(0)里的0表示构造分析表时不看任何前瞻符号。当前状态下的动作完全由项集内部决定，不管下一个输入符号是什么，归约项都会触发归约。这个“不看”是LR(0)简单的原因，也是冲突容易爆发的根源。后面的章节你会反复看到，LR(0)的ACTION表里归约动作经常“整行填满”，这不是程序bug，而是LR(0)的天然行为。

2.2 项、闭包、GOTO函数：构造项集族的三件套

LR(0)的状态机里，每个状态都是一个项集。项就是“产生式右部某个位置带一个圆点”的式子，例如E->E·+T表示已经看到E，下一个期望的符号是+。圆点在右部最左端表示还没有匹配任何符号，圆点在右部最末尾表示这个产生式已经完整匹配，可以归约。

闭包操作负责把一个状态补全。给定一个初始项集，闭包反复执行这样一个规则：如果项A->α·Bβ存在，且B是非终结符，就把所有B->·γ形式的项加入当前项集，直到不再有新项加入。用上面的文法做演示，增广文法加一条S'->S，初始项S'->·S的闭包结果如下：

S'->·S S->·E E->·E+T E->·T T->·n

这个过程是自顶向下展开的：圆点后面跟着S，就把S的所有产生式加进来；圆点后面跟着E，就把E的产生式加进来；圆点后面跟着T，就把T的产生式加进来。最后T->·n圆点后是终结符n，闭包结束。

GOTO函数则负责状态之间的跳转。GOTO(I, X)的意思是，从状态I出发，读入符号X之后到达的新状态。计算方式也很直接：先找出项集中所有圆点后面正好是X的项，把圆点向右移动一位，再对新项集做闭包。例如从I0读入E，得到的状态就是{S->E·, E->E·+T}。注意S->E·的圆点已经在末尾，所以这个状态里天然存在一个归约项。

2.3 从项集族到ACTION/GOTO表：五步走

拿到完整项集族之后，填表就是机械动作。完整的构建流程分五步：

1. 给原文法加增广产生式S'->S，保证接受状态唯一。
2. 从closure({S'->·S})出发，反复对每个状态、每个文法符号计算GOTO，直到所有状态都展开。
3. 标记每个状态里的移进项、归约项和接受项。
4. 根据项的形式填ACTION表。
5. 根据非终结符上的GOTO填GOTO表。

ACTION表的填法遵循三条规则，整理成表格就是下面这样：

GOTO表则是把每个状态遇到非终结符时的跳转目标填进去。这套规则实现起来非常固定，几乎没有可以自由发挥的地方，所以程序输出的分析表长什么样，你照着规则就能手工核对。

2.4 LR(0)的边界：跟SLR(1)、LR(1)差在哪

理解LR(0)的局限，才能知道什么时候该用它，什么时候该往上走。四类分析器的差异说白了就是“归约的时候看不看下一个输入符号，以及看到什么程度”。我用一张表把这层关系摆清楚：

LR(0)之所以容易冲突，是因为归约动作不看输入。假设某个状态的项集里同时存在E->T·和E->E·+T，那么遇到+时，到底应该移进+继续拼E+T，还是应该先归约成T，LR(0)完全没法判断，这就是移进-归约冲突。SLR(1)的做法是在归约前查一下当前输入是否在E的FOLLOW集合里，在才归约，能消掉一部分冲突。LR(1)则每个项都带自己的展望符，信息更精确，但状态数量会暴涨。理解了这层边界，你拿到工具输出的时候，才不会一看到冲突就怀疑程序写错了。

3. 把 LR(0).rar 跑起来：编译、输入格式与核心代码

原理部分过完，接下来是落地环节。压缩包解压之后，先别急着双击，搞清楚里面几个文件的分工，能省掉后面一多半的排错时间。

3.1 压缩包里的三样东西分别干什么

压缩包里最核心的是LR(0).cpp，这是程序的全部源码，包含文法的读取、闭包计算、GOTO表生成和分析表输出。整个工程是单文件结构，没有额外的头文件和依赖库，编译需要什么环境后面说。另外两个文本文件a.txt和b.txt按课程作业最常见的约定，一个放文法产生式，一个放待分析的输入串。具体哪个放文法，打开看一眼就知道：里面是E->E+T这种格式的就是文法文件，里面是表达式串的就是输入文件。

程序里读文件用的多半是相对路径。也就是说，程序运行时会直接在当前工作目录下找这两个txt。不要把txt放在其他路径，然后编译出的程序放在桌面运行，这样程序大概率报文件找不到。确定a.txt和b.txt哪个对应文法后，后面的操作都以你自己确认过的为准。

3.2 第一次编译运行

LR(0).cpp这个文件名里带了括号，在Linux和macOS的bash里直接敲命令会被当成特殊字符处理，编译时需要把文件名用引号包起来。命令如下：

g++ "LR(0).cpp" -o lr0 ./lr0

-o lr0指定输出可执行文件名，避免每次都生成一个叫a.out的文件。文件名里的括号在shell里本来有组合命令的含义，加引号就是告诉shell把整个LR(0).cpp当成一个普通字符串。Windows的cmd对括号没那么敏感，直接执行g++ LR(0).cpp -o lr0.exe通常也能过，但如果你用的终端比较特殊，最省事的办法就是把源文件重命名成lr0.cpp再编译。

运行之后，程序可能有两种交互方式：一种是从控制台逐个读取文法产生式和输入串，另一种是固定读取a.txt和b.txt。如果是前者，启动后会有提示要求输入产生式数量，按提示一步步填；如果是后者，启动后直接输出项集族和分析表。判断标准很简单：启动后如果看到中文或英文提示，就是控制台交互；如果屏幕上直接开始刷状态，就是文件驱动。

提示：如果程序提示无法打开文件，先确认是否始终在LR(0).cpp所在目录运行。这个坑在第五章会专门展开。

3.3 输入格式约定：把文法写成程序能认的样子

LR(0)工具的输入格式通常比正规的编译器前端敏感得多。它不会像bison那样宽容地处理各种空白字符和符号别名，所以必须按约定提供文法。我建议所有输入统一遵守下面这套格式，兼容大多数同类程序：

标准的输入模板长这样：

S->E E->E+T E->T T->n # n+n#

模板里前四行是产生式，单独一行#表示文法部分结束，最后的n+n#是待分析的输入串。如果程序是按固定文件读取的，就把这些内容写进对应的txt文件。注意E->E+T不要写成E=E+T，也不要写全角箭头→，程序切分字符串时只认->这两个字符。

3.4 核心代码逻辑解读：闭包计算

闭包函数是整个程序最核心的部分，也是最容易写错的部分。拿到源码后建议第一时间找到这个函数，对照下面的简化版逻辑理解程序的流程。代码里的Item结构体保存两个字段：产生式编号和圆点位置，nextSymbol返回圆点后面的符号，返回0表示圆点已在末尾。

void closure(vector<Item>& items, const vector<Production>& prods) { queue<int> q; for (int i = 0; i < (int)items.size(); i++) q.push(i); while (!q.empty()) { Item cur = items[q.front()]; q.pop(); char next = cur.nextSymbol(prods); // 圆点后面的符号 if (next == 0 || !isupper(next)) continue; // 不是非终结符就跳过 for (int i = 0; i < (int)prods.size(); i++) { if (prods[i].lhs != next) continue; Item it(i, 0); // 新项圆点在最左端 if (!contains(items, it)) { items.push_back(it); q.push((int)items.size() - 1); } } } }

逻辑上这是一个典型的BFS扩展：队列里的每个项都要检查圆点后是不是非终结符，如果是，就把该非终结符的所有产生式作为新项加入。新加入的项也要进队列继续扩展，因为它的圆点后面可能又跟着一个非终结符。contains函数负责查重，一般直接遍历现有items做逐字段比较就行，文法规模不大时O(n²)的查重完全能接受。

代码里isupper做了硬编码，意思是只有大写字母会被当成非终结符。如果你的文法里非终结符用了多个字母或者小写字母，程序要么报错要么输出全乱，这是这类教学工具最常见的局限。看懂这段闭包逻辑，后面分析程序输出和排查死循环，就有一个明确的方向。

4. 拿它验证自己的文法：输出表怎么读、冲突怎么定位

工具运行起来只是第一步，真正有价值的动作是解读分析表，并根据输出判断自己的文法到底是不是LR(0)。这一章用一个完整例子串一遍读表流程，再讲冲突的定位方法。

4.1 一个完整例子：E->E+T|T、T->n

用最典型的表达式文法做演示：

S->E E->E+T E->T T->n

程序跑完会输出项集族和ACTION/GOTO表。项集族一共6个状态，状态0到状态5，其中状态0就是前面闭包演示里的初始项集。GOTO(0,E)得到状态1，GOTO(0,T)得到状态2，GOTO(0,n)得到状态3，GOTO(1,+)得到状态4，GOTO(4,n)回到状态3，GOTO(4,T)得到状态5。核心的ACTION表简化后如下：

表格里s3表示移进并跳转到状态3，r3表示按编号为3的产生式归约，acc表示接受，空白表示报错。产生式编号从0开始，这里r1对应E->E+T，r2对应E->T，r3对应T->n。注意状态2、3、5的归约动作占满了+、n、#三列，这就是LR(0)不看前瞻的直接表现，对照2.4节的说明就能理解。

4.2 从输出里定位冲突

判断文法是不是LR(0)，核心原则只有一条：能不能在ACTION表里找到同一个状态的同一列同时出现两个不同动作。如果找到，就是冲突；找不到，文法就是LR(0)的。

冲突分两种。第一种是移进-归约冲突，同一格子里既有s又有r。第二种是归约-归约冲突，同一格子里有两个不同的r，比如状态里同时存在A->x·和B->x·，两个归约项都对终结符a触发归约，程序不知道该按哪个产生式归约。

程序输出的通常不是规整的二维表，而是逐项列出每个状态包含的项。找一个典型输出片段，状态2的内容长这样：

状态2的项: S->iS· S->iS·eS

第一个项圆点在末尾，是归约项；第二个项圆点后跟着终结符e，是移进项。当状态2遇到输入e时，移进和归约同时成立，这就是移进-归约冲突。输出里如果出现冲突: shift/reduce conflict at state 2 on symbol e之类的提示，直接定位到对应状态看项即可。

4.3 翻车案例：悬空else当场暴露

经典的“悬空else”文法非常适合拿来验证冲突检测：

S->iS S->iSeS S->o

这个文法把if、else、other分别简写成i、e、o。程序运行后，项集族的构建过程本身不会报错，但填ACTION表时，在某个状态会遇到前面描述的情况：S->iS·要求归约，S->iS·eS要求继续移进e。于是e列同时出现s和r，二义性当场暴露。

注意一个反直觉的点：并不是所有二义文法都会在LR(0)里表现出冲突。比如E->E+E|n这种简单二义文法，它的LR(0)分析表可能是能构造出来的，因为归约项所在的状态里没有对应的移进项。所以遇到“程序说你文法有冲突”的结论，就老老实实按冲突改文法；遇到“程序没报冲突”，也只能说明这个文法存在一个确定的LR(0)分析表，并不能说明文法是二义的。工具能帮你排除问题，但不能替你证明一切。

4.4 文法的三个调整手段

如果验证结果确实有冲突，常用的调整手段有三个。第一个是优先级分层，把E->E+E|E*E|(E)|n这种平铺的写法拆成多层：

E->E+T E->T T->T*F T->F F->(E) F->n

第二个是提取左因子，处理S->iS和S->iSeS这种前缀相同的产生式：

S->iS S' S->o S'->eS S'->@

第三个是谨慎处理空产生式。空串会让闭包计算多出大量非终结符，项集族规模明显膨胀，如果程序不支持空串符号，宁可用@占位再人工核对归约逻辑。

5. 避坑：LR(0)工具常见的五个翻车现场

这类教学工具代码量不大，但坑不少。下面五条是我实际用下来最常碰到的问题，每一条都按现象、原因、解决的顺序写。你在跑这个程序时如果遇到奇怪行为，先来这里对号入座。

5.1 文件读不进去，程序一启动就报错退出

现象：运行程序后提示file not found，或者没有任何输出就直接退出。有的情况下程序虽然跑了，但分析表是空的，看起来像什么都没做。

原因：第一，程序用相对路径找a.txt和b.txt，而你在别的目录下执行程序，文件自然找不到。第二，Windows记事本默认把文件存成UTF-8带BOM，fscanf读第一行时会先读到一个不可见字符，导致第一条产生式解析失败。第三，文件在保存时被Windows的隐藏扩展名机制改成了a.txt.txt，程序查找a.txt找不到。

解决：确保txt文件和编译出的可执行文件在同一个目录里；在资源管理器里打开“显示文件扩展名”，确认文件名没有变成a.txt.txt；用记事本打开txt文件后另存为，编码选择ANSI。程序稳定跑通之后，再考虑改成UTF-8。

5.2 产生式写成了E=E+T或者用了全角符号

现象：程序输出的项集里全是些莫名其妙的符号，或者闭包结果只有一个初始项，文法规则完全没进去。

原因：程序切分产生式的逻辑基本是找->子串，左边的字符作为非终结符，右边作为右部。写成E=E+T切不开，写成全角箭头→也切不开。有些输入法还会自动把-和>换成全角字符，肉眼根本看不出来。

解决：统一用ASCII的->，写完文件后用十六进制查看确认一下，或者直接在程序源码里搜分隔符定义。输入文本里如果发现全角空格，一并替换掉，否则程序会把空格当成终结符。

5.3 文法里有空串，闭包闭出几百个状态

现象：文法里含空产生式的时候，项集族数量暴涨，输出刷屏，分析表大得没法看。更隐蔽的情况是空串符号@被当成普通终结符处理，结果状态里出现A->@·这种奇怪的项。

原因：程序对空串符号的约定和你写进去的不一致。有的程序约定@，有的约定epsilon，有的干脆要求右边什么都不写。你没按约定写，程序就把空串符号当成一个普通字符参与闭包和GOTO计算。

解决：翻开源码找一下对epsilon的判断条件，按它约定的符号修改文法输入。如果程序不支持空串，就用@占位，然后自己手动核对归约逻辑。空产生式在LR(0)里本来就是个容易引起状态爆炸的地方，建议先去掉空串验证程序能跑通，再加回来逐步排查。

5.4 闭包函数死循环，程序直接卡死

现象：运行后程序没有任何输出，CPU直接拉满，等几分钟也不见反应。任务管理器里能看到进程占满一个核心。

原因：闭包函数的查重逻辑失效是最常见的元凶。contains函数如果没正确比较产生式编号和圆点位置，同一个项会被反复加入，队列永远清不空。另外，文法里如果存在A->B、B->A这种循环，闭包也会无限扩展。教学工具的源码多半没做状态数上限保护，所以一死循环就是整个程序卡住。

解决：先检查文法里有没有循环依赖。然后给程序临时加一个计数器，每加入一个新项就累加，当状态数超过100时强制退出并打印当前项集大小，看数值是不是还在涨。如果一直涨，问题就在查重函数；如果停在某个数值不动，问题在循环遍历逻辑。

5.5 输出乱码，表格错位

现象：中文提示变成????或者一片乱码，分析表里中文注释的宽度把列对齐全打乱了。

原因：Windows控制台默认代码页是GBK，程序源码和输出如果按UTF-8编码，直接在cmd里跑就会乱码。反过来，源码是GBK而终端设成了UTF-8，也会乱。

解决：在程序的main函数开头加一行setlocale(LC_ALL, "")，让程序跟随系统区域设置输出中文。如果不想改源码，运行程序前先执行chcp 65001把控制台切到UTF-8。最省事的方案是把程序里的中文提示全部改成英文输出，因为这个工具的分析表本身就是符号，换成英文完全不损失信息。

6. 进阶：把分析表接到表驱动分析器上做验证

分析表生成之后，最有价值的验证方式不是盯着表格看，而是写一个几十行的表驱动分析器，拿真实句子把表走一遍。这一步能把理论上的“这个表没有冲突”真正落实成“这条输入串能被正确接受”。

6.1 一个紧凑的LR表驱动器

驱动器的逻辑就是查表执行移进、归约、接受三个动作。核心循环如下：

while (true) { char sym = input[pos]; int state = stk.top(); Action act = actionTable[state][sym]; if (act.type == SHIFT) { stk.push(act.target); // 移进: 压入目标状态 symStack.push(sym); // 输入字符进符号栈 pos++; } else if (act.type == REDUCE) { Production& p = prod[act.prodIndex]; for (int i = 0; i < (int)p.rhs.size(); i++) { symStack.pop(); // 弹出句柄 stk.pop(); // 每个符号对应一个状态 } symStack.push(p.lhs); stk.push(gotoTable[stk.top()][p.lhs]); } else if (act.type == ACCEPT) break; else { error("非法输入"); break; } }

归约时弹出状态的数量必须等于产生式右部符号数量，少弹一个或多弹一个，整个状态栈就错位了。移进时符号栈和状态栈一起压，归约时一起弹，两个栈的栈顶始终是“当前符号对应的状态”这个关系。表驱动分析器的参数就三个：actionTable管移进和归约，gotoTable只管归约后的跳转，prod保存产生式右部的长度供弹出操作使用。

6.2 用句子n+n完整走一遍

拿4.1节的表和输入n+n#过一遍，每一步动作如下：

注意第6步，状态栈从0 1 4 3归约T->n后变成0 1 4 5，这个5来自GOTO(4,T)而不是GOTO(0,T)。很多人第一次手推时容易把这一步算错，归约后GOTO的起点是弹出句柄后的栈顶状态。这行对上之后，整条链路的验证就算通过了。

6.3 从LR(0)到SLR(1)的最小改造

如果你已经验证表能驱动，还想进一步消掉几种冲突，SLR(1)是成本最低的改造。做法只有一步：归约动作从“填满整列”改成“只填FOLLOW集合内出现的终结符”。换句话说，状态3原本对所有输入都执行r3，加上FOLLOW过滤后，只有当前输入属于FOLLOW(T)时才执行r3。FOLLOW集合可以在读取文法后顺便算出来，不需要重写闭包和GOTO逻辑。

说实话，我当年第一次跑这个程序的时候，闭包函数里的查重写漏了一个字段，状态数一路涨到两百多，Ctrl+C都按麻了。后来加了个计数器才算抓到元凶。从那以后，我每次构造完LR(0)分析表，都会拿三四个最短的合法句子走一遍表驱动分析器，确认每一步移进归约都能落到表上，再下结论说这个文法是LR(0)。这套验证习惯帮我省了不知多少无用功，希望帮到你。

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