企业官网建设流程全解析

简介：LR(0).rar_LR分析表是一份面向编译原理学习者与编译器开发者的LR分析表学习工具包，围绕自底向上语法分析中的LR(0)解析器展开，帮助用户理解状态闭包、移进-归约动作与分析表构建流程。压缩包共3个文件，包含1个C++源程序与2个文本说明文件，整体仅5KB，轻量易用；源代码展示分析表构建主逻辑，包括状态集、闭包计算与动作表的生成与输出，文本文件则记录测试文法及对应解析结果，两者配合可直观演示分析表生成过程。已有336人学习下载，适合正在复习编译原理、调试文法或准备相关课程实验的学生参考，对于完成编译原理课程设计也有直接帮助。借助这份材料，读者既能查看LR(0)分析表的具体实现思路，又能结合文本示例对照运行结果，快速掌握编译器中语法分析模块的核心机制，为后续学习SLR(1)、LALR(1)等更复杂的分析表奠定基础。

1. 一个压缩包背后的 LR(0) 分析表：从文法到状态机的最小闭环

你从课程设计包或师兄师姐那里拿到的LR(0).rar，打开后往往只有一份报告、一个文本文法和一张手画的 LR 分析表。真正动手复现时你会发现，报告里“构造了 LR(0) 分析表”这句话被一笔带过，而自己却要卡在 closure、goto、状态编号、冲突处理之间来回绕。LR(0) 分析表是自底向上语法分析的核心产物：它把文法编译成一张“状态 + 动作”的表，再用一个驱动器在栈上反复移进和归约，最终判断 token 流是否属于该文法。这篇笔记用最小文法把这条链路完整走通，适合正在写编译器前端、或者对着分析表发呆的从业者。

2. 为什么要从“项目”造状态：LR(0) 分析表的状态驱动原理

2.1 自底向上分析的任务：移进与归约

语法分析有两条路线。LL 家族自上而下做推导，LR 家族自底向上做归约。LR(0) 属于后者。自底向上的核心动作只有两个：把输入符号压进栈里叫“移进”；当栈顶符号串匹配到某条产生式的右部时，用左部替换掉这段符号串叫“归约”。

以文法S -> ( S ) | a和句子(a)为例，分析过程是这样的：

1. 输入第一个符号(，移进，栈变成(；
2. 输入a，移进，栈变成( a；
3. 栈顶的a匹配S -> a，归约，栈变成( S；
4. 栈顶的( S )匹配S -> ( S )，归约，栈变成S；
5. 归约到开始符号，接受。

每一步到底选择移进还是归约，由 LR 分析表决定。这张表之所以能跑起来，是因为它把“当前栈里已经形成什么结构”压缩成了一个状态编号。只要状态编号一致，栈里的详细符号串就不影响后续决策，这就省去了每次遍历栈的代价。

LR(0) 分析表的构造过程，本质上是从文法生成一个确定有限自动机（DFA）。这个 DFA 的节点就是项目集，边就是文法符号。后面填表、驱动，全是围绕这个 DFA 展开的。

2.2 项目与项目集：把文法转成 DFA 的原子单元

“项目”（item）是在产生式右部插了一个圆点得到的结构。圆点左边是“已经看到的符号”，右边是“期望继续看到的符号”。例如S -> ( S )可以写成三种不同的项目：

• S -> . ( S )：还没看到右部的任何符号；
• S -> ( . S )：已经看到左括号，正等一个S；
• S -> ( S . )：已经看到左括号和S，正等右括号；
• S -> ( S ) .：整个右部都已看到，可以归约。

项目集就是若干项目的集合。为什么不能只保留一个项目？因为在分析的某个瞬间，分析器面对的选择往往不止一个。比如初始状态下，它知道目标是从S开始，但还没决定用哪条产生式去展开S，于是S' -> . S、S -> . ( S )、S -> . a这三个项目必须同时存在。一个项目集对应 DFA 的一个状态，记录的是“在当前栈顶状态下，所有仍然可能成立的分析路径”。

构造项目集时，“闭包”是一个关键操作：如果当前项目里圆点后面是一个非终结符，那么所有以这个非终结符为左部的产生式，也都要以“圆点在最前”的形式加入当前项目集。反复执行这个过程直到项目集不再增长，就得到这个状态的完整闭包。

2.3 为什么 LR(0) 不看输入符号也能填表

LR(0) 名字里的“0”指的是向前看符号数量为 0。也就是说，一个项目只要圆点已经到右部末尾，就直接做归约，完全不看下一个输入符号是什么。这是它和 SLR(1)、LR(1) 最本质的区别。在表的结构上，这种“不看输入”体现在：归约动作要填满当前状态的所有终结符列，而不是只填部分终结符列。

这个特性让 LR(0) 表实现很简单，但也带来了严格限制。考虑经典算术文法E -> E + T | T、T -> T * F | F、F -> ( E ) | id，在一个状态里可能同时存在E -> T .（归约项）和T -> . * F（移进项）。这时同一个符号*既可能触发归约又可能触发移进，LR(0) 无法裁决，这就是移进-归约冲突。所以大多数真实编程语言的文法都不是 LR(0) 文法，课设里常见的做法是选一个足够简单、无冲突的文法来演示。下面代码用的S -> ( S ) | a就是一个严格 LR(0) 文法，状态少、冲突少，适合完整跑通流程。

3. 用 Python 实现 closure 与 goto：项目集规范族的造表代码

3.1 文法的表示：产生式、终结符与非终结符

先把文法的数据结构定下来。产生式用元组表示，左部是字符串，右部是符号元组。不要用可变 list 存右部，因为后面要拿项目做集合去重和哈希，元组才能保证可哈希。

grammar = [ ("S'", ("S",)), # 增广产生式，接受状态靠它识别 ("S", ("(", "S", ")")), ("S", ("a",)), ] nonterms = {lhs for lhs, _ in grammar} all_syms = {sym for _, rhs in grammar for sym in rhs} terms = all_syms - nonterms terms.add("$") # 结束符，必须手工加进终结符集合

这里S'是增广开始符号，它的作用是让“归约到开始符号”和“接受”这两个事件解耦。如果不加增广产生式，最后一步归约到S时无法区分“还能继续归约”和“已经接受”，表就没法填了。terms集合从所有产生式右部推导出来，再补一个$，这样后面填表时终结符列是完整的。

3.2 closure 闭包：把点后面的非终结符展开

closure 函数的输入是一个项目集合，输出是它的闭包。规则只有一条：如果某个项目的圆点后面是非终结符，就把该非终结符的所有产生式以圆点在最前的形式加入集合，直到集合稳定。

def closure(items): items = set(items) while True: added = False for lhs, rhs, dot in list(items): if dot >= len(rhs): continue # 圆点在末尾，不需要展开 sym = rhs[dot] if sym in nonterms: # 点后是非终结符 for n_lhs, n_rhs in grammar: if n_lhs == sym: cand = (n_lhs, n_rhs, 0) if cand not in items: items.add(cand) added = True if not added: return frozenset(items)

这段代码的要点是：dot >= len(rhs)把归约项排除；sym in nonterms判断是否需要展开；cand = (n_lhs, n_rhs, 0)展开时圆点永远放在最前面。闭包的结果返回frozenset，因为 frozenset 可哈希，后面要作为字典的键做状态去重。如果返回 set，会直接报unhashable type。

3.3 goto 与状态去重：生成整个 DFA

goto 函数回答的问题是：从当前状态读入一个文法符号后，应该跳到哪个状态。实现方法是扫描状态里所有项目，把圆点后面正好等于该符号的项目圆点后移一位，再做一次闭包。

def goto(items, symbol): moved = set() for lhs, rhs, dot in items: if dot < len(rhs) and rhs[dot] == symbol: moved.add((lhs, rhs, dot + 1)) return closure(moved)

有了 goto，就可以从初始项目集出发，不断对每个状态、每个文法符号求 goto，把新状态加入列表，直到没有新状态出现。这个循环就是 DFA 构造的“工作列表算法”。

start_set = closure({("S'", ("S",), 0)}) state_to_id = {start_set: 0} state_list = [start_set] i = 0 while i < len(state_list): for sym in sorted(terms | nonterms): nxt = goto(state_list[i], sym) if nxt and nxt not in state_to_id: state_to_id[nxt] = len(state_list) state_list.append(nxt) i += 1

遍历符号时加sorted不是功能需要，而是为了让状态编号顺序稳定可复现。如果少了排序，每次运行状态编号可能不同，对课设里“手工核表”很不友好。if nxt判断跳过空结果；nxt not in state_to_id做去重。这个循环跑完，state_list就是项目集规范族。

4. 填出 ACTION/GOTO 表并跑通 LR 驱动器：从 DFA 到可执行解析器

4.1 动作表的三种基本动作与 GOTO 跳转

LR 分析表分两部分：ACTION 表按“状态 x 终结符”定位动作；GOTO 表按“状态 x 非终结符”定位状态。动作类型只有四种：

reduce 动作要记录产生式编号，shift 要记录目标状态，acc 只在增广开始符号的完成项目上出现。GOTO 表只在归约时用到，归约弹出右部符号后，根据栈顶状态和左部查 GOTO。

4.2 从 DFA 到表：shift/reduce/accept 的判定规则

填表逻辑就是遍历每个状态里的每个项目，按项目形态分发动作。

ACTION = {} GOTO = {} for sid, items in enumerate(state_list): ACTION[sid] = {} GOTO[sid] = {} for lhs, rhs, dot in items: if lhs == "S'" and dot == len(rhs): ACTION[sid]["$"] = ("acc",) # 接受状态 elif dot == len(rhs): rid = grammar.index((lhs, rhs)) # 归约项：取产生式编号 for t in sorted(terms): if t in ACTION[sid]: print("冲突: 状态", sid, "符号", t, ACTION[sid][t], ("reduce", rid)) else: ACTION[sid][t] = ("reduce", rid) else: sym = rhs[dot] nxt = state_to_id[goto(items, sym)] if sym in terms: # 移进项 if sym in ACTION[sid]: print("冲突: 状态", sid, "符号", sym, ACTION[sid][sym], ("shift", nxt)) else: ACTION[sid][sym] = ("shift", nxt) else: # 非终结符 GOTO[sid][sym] = nxt

这里最容易忽略的是grammar.index((lhs, rhs))。因为之前约定产生式的右部用元组保存，index 才能直接命中；如果右部是 list，这一步会匹配失败。另外我特意把冲突检测写成了“发现冲突就打印”，而不是直接覆盖。很多实现图省事直接覆盖，结果动作表被 reduce 填满，shift 动作静默丢失，调试时根本看不出问题。打印冲突可以在状态构造阶段就暴露文法缺陷。

再写个打印函数，把表输出成文本，方便和手工推导的表格对账：

def print_table(): header = ["状态"] + sorted(terms) + sorted(nonterms) print("\t".join(header)) for sid in range(len(state_list)): row = [] for sym in sorted(terms): row.append(str(ACTION[sid].get(sym, ""))) for sym in sorted(nonterms): row.append(str(GOTO[sid].get(sym, ""))) print(str(sid) + "\t" + "\t".join(row)) print_table()

sorted(nonterms)会把S和S'都排进去，虽然S'不会出现在 GOTO 列，但表打印出来能看到 GOTO[S] 的跳转，方便核验。

4.3 驱动器：用状态栈识别句子

LR 驱动器的思路很直接：状态栈和符号栈交替压入，初始状态 0 入栈。查 ACTION 表决定动作。

def parse(tokens): tokens = list(tokens) + ["$"] stack = [0] # 状态栈，栈中状态与符号交替出现 pos = 0 while True: state = stack[-1] sym = tokens[pos] entry = ACTION[state].get(sym) if entry is None: raise SyntaxError(f"状态 {state} 遇到符号 {sym!r}: 表项为空") kind = entry[0] if kind == "shift": _, target = entry stack.append(sym) # 先压符号 stack.append(target) # 再压状态 pos += 1 elif kind == "reduce": _, rid = entry lhs, rhs = grammar[rid] stack = stack[:-2 * len(rhs)] # 弹出右部对应的符号和状态 top = stack[-1] stack.append(lhs) stack.append(GOTO[top][lhs]) else: return True

注意stack[:-2 * len(rhs)]：栈里符号和状态是交替存放的，比如0 ( 3 a 5，归约S -> a时右部长度是 1，要弹掉a和5两层，所以乘 2。空产生式长度是 0，切片不会弹任何东西，top就是当前栈顶状态，逻辑仍然成立。真正工程化的驱动器还会在这里校验弹出的符号是否和右部匹配，我这里省略是为了让核心逻辑更直观。

把话说得再直白一点：驱动器能不能跑，完全取决于表和栈的“坐标系”是否对齐。表里 shift 填的是终结符，GOTO 填的是非终结符，驱动器压栈、弹栈必须和这个数据类型一一对应。很多跑不通的实现，问题都出在“表填对了，驱动器把符号拆错”。

5. LR(0) 的五个典型坑与排查：冲突、空产生式和终结符表示

5.1 漏掉增广产生式：最后一个状态拿不到 acc

现象：整个分析过程到最后一步，状态机报告“表项为空”，根本没有接受动作。

原因：直接用S作为开始符号，没有加S' -> S。这样当S被归约到栈顶时，没有任何项目能表达“整个句子已经推导完成”，自然也没有 acc 动作。

解决：在文法列表第一项加增广产生式，且只有增广左部的完成项目才填 acc；普通产生式的完成项目只填 reduce。这个规则要在填表代码里写死，否则普通归约项也会被误判成接受。

5.2 reduce 把整行都填满：表上看不出冲突位置

现象：打印出来的 ACTION 表每一行都塞满 reduce，某个符号明明同时需要 shift 和 reduce，表里却只有一个动作，程序跑起来也不报错，但分析结果明显不对。

原因：LR(0) 的归约动作本来就要填满所有终结符列，这是它的标准填法。问题往往出在实现时直接用赋值覆盖已有表项，后填的 reduce 把先填的 shift 覆盖了，冲突被静默吞掉。

解决：填表时遇到已有表项就打印冲突，不要覆盖。我在 4.2 的代码里已经内置了这个检查。如果你想升级成 SLR(1)，可以在这里加一个 FOLLOW 集合判断，只把 reduce 填进 FOLLOW 里出现过的终结符列，很多冲突会自然消失。

5.3 空产生式 dot_pos=0 的误解

现象：文法里有A -> ε，状态构造和填表阶段都没报错，但驱动器在归约A -> ε时栈不弹、状态不跳，最后死循环或者栈越界。

原因：空产生式的项目只有一个，就是(A, (), 0)。这个“0”常被误解为“圆点在最前”，但右部长度是 0，圆点其实已经在末尾。有些实现会额外区分“起始项目”和“完成项目”，空产生式只有完成项目，没有起始项目。

解决：统一用dot >= len(rhs)判断归约项，空产生式自然满足条件。closure 里dot >= len(rhs)的检查会让它跳过展开逻辑，不需要特殊处理。驱动器里2 * len(rhs)弹栈时长度为 0，切片不弹，逻辑也是自洽的。

5.4 多字符终结符被拆开：表对上了，栈对不上

现象：文法里有一个终结符id，表里 shift 项也填了id，但驱动器运行时把id当成i和d两个字符压栈，归约永远匹配不上。

原因：LR 分析表里的终结符是“符号类型”，不是“字符”。课设里常见的 token 名如ID、NUM是多字符字符串，如果把 token 流按字符拆分，和表里的键就对不上了。

解决：驱动器的输入必须是词法分析器输出的 token 序列，token 的字符串就是表的键。我在前文用list(s)传入只是为了演示单字符终结符(、)、a；换成多字符终结符时，一定要保证 token 流和表键一致。

5.5 二义性文法引发冲突，误判为代码 bug

现象：用E -> E + T | T这类算术文法跑状态构造，控制台刷出一堆冲突，反复检查 closure 和 goto 都找不到逻辑错误。

原因：这不是实现 bug，而是文法本身不是 LR(0) 文法。算术表达式文法在E -> T .和T -> . * F并存时会产生移进-归约冲突，LR(0) 没有向前看符号，裁决不了。

解决：先用S -> ( S ) | a这类严格 LR(0) 文法跑通流程，确认实现无误后，再考虑把它升级成 SLR(1) 或 LALR(1)。LR(0) 适合教学演示和简单配置文法，面对真实编程语言文法时，直接上 SLR(1) 更务实。

6. 验证你的 LR 分析表：手工推导、边界测试与 SLR 平滑升级

6.1 手工算前两个状态，和程序输出对账

代码跑完以后，先别急着塞句子。手工推一遍初始状态和它的一条出边，再和程序输出对比，能快速定位状态编号或闭包逻辑的问题。

初始项目集I0 = closure({("S'", ("S",), 0)})，圆点后是S，展开它的两条产生式，得到I0 = { S' -> . S, S -> . ( S ), S -> . a }。从I0读入a，goto 得到I_a = { S -> a . }，这是一个纯归约状态。程序打印的表里，I_a应该对所有终结符列填reduce(S -> a)。如果程序输出的状态数和这张手工推导对不上，优先检查状态编号的生成顺序。

6.2 让分析器吃边界句子：非法符号、空串、超长嵌套

验证一个 LR 分析器，不能只跑合法句子。我一般会同时测四类输入：合法短句、合法长句、非法符号、空串。对应这个文法，可以这样跑：

tests = ["a", "(a)", "((a))", "()", "a)", ")("] for s in tests: try: print(s, parse(list(s))) except SyntaxError as e: print(s, "False ->", e)

parse(list(s))只适用于单字符终结符，这里恰好能拆成(、)、a。结果应该是a、(a)、((a))通过，()、a)、)(全部报错。注意()不能通过，因为文法要求括号里必须有一个S，空串不满足。边界测试的要点是：报错必须在 ACTION 表项为空时精准发生，而不是在弹栈或归约阶段越界崩溃。如果你发现非法输入能把驱动器跑出IndexError，多半是弹栈逻辑里没有对“归约后找 GOTO 失败”做兜底。

6.3 从 LR(0) 平滑升级到 SLR(1)

把 LR(0) 升级成 SLR(1) 的改动很小，一句话概括：reduce 不再填满所有终结符列，只填左部lhs的 FOLLOW 集合中的终结符。这也是我个人的习惯——即使最终目标是 LR(0)，我也会先把 FOLLOW 集合算出来放在旁边，因为它能快速判断冲突到底能不能靠向前看一个符号来解决。

关键代码只改填表那一处：

# 假设 follow 是已经算好的 FOLLOW 集合字典 for t in sorted(terms): if t in follow[lhs]: if t in ACTION[sid]: print("冲突: 状态", sid, "符号", t) else: ACTION[sid][t] = ("reduce", rid)

驱动器完全不用改。很多在 LR(0) 下冲突的文法，到 SLR(1) 就能无冲突填表。这也解释了为什么课设报告里经常写着“用 LR(0) 分析”却又拿算术文法举例——他们实际的表多半是 SLR(1) 的表，只是名字还叫 LR(0)。你现在能分辨这个区别，以后看别人的报告就不会被带偏了。希望帮到你。

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