企业官网建设流程全解析

简介：编译原理中，LR(1)分析法是自底向上语法分析的重要代表，理解其分析表构造和驱动流程是掌握编译器设计的关键。这份实验报告以河南工业大学实验四为背景，围绕文法E→S、S→BB、B→aB、B→b，设计了一个可对以#结束的输入串（如abb#）进行判定的LR(1)分析程序，完整呈现了从ACTION/GOTO分析表定义、状态栈与符号栈变化，到移进、归约、接受、报错等核心处理过程的C语言实现。实验代码采用二维数组保存ACTION表和GOTO表，输入串扫描过程中逐步输出状态栈、符号栈与剩余输入，便于通过运行截屏直观理解每一步的归约或移进动作。内容还包含实验目的、要求、运行过程截屏以及实验心得，既适合计算机专业学生用于课程实验参考，也适合复习语法分析时对照理解。资源共有1个doc文档，压缩包大小34KB，便于直接下载阅读；目前已有3467人浏览学习，对需要完成编译原理实验、梳理LR(1)分析步骤或参考原始程序代码的读者具有较高参考价值。

1. LR(1)分析法实验：为什么这个实验让编译原理课最难拿分

在编译原理实验里，LR(1)分析法实验向来是分水岭：很多同学 LR(0) 和 SLR(1) 都能跑通，一到 LR(1) 就卡在项目集规范族的构造上。它解决的问题很明确——给定一个文法，如何自动生成一张无冲突的 LR 分析表，让移进-归约分析器高效识别该文法定义的语言。这个实验适合正在修编译原理课程、需要手工构造分析表或动手实现代码的学生，也适合想弄清 LALR 和 SLR 区别的从业者。它的“难”不在于算法本身，而在于向前看符号的传播很容易算错，一步错，后面整个状态机全错。

2. 从 LR(0) 到 LR(1)：项目集规范族与向前看符号

2.1 先补定义：LR(1) 项目、闭包和活前缀

LR(1) 项目的形式是 [A → α·β, a]，其中 A → αβ 是文法产生式，圆点表示当前分析位置，a 是一个终结符，叫作向前看符号。它的语义是：在分析过程中，我们期望先看到 α 对应的输入串，然后期待 β 展开，并且只有当下一个输入符号是 a 时，这个项目才能被用于归约。

为什么要加这个 a？LR(0) 项目没有向前看符号，归约条件过宽；SLR(1) 用 FOLLOW(A) 近似替代，精度仍然不够。LR(1) 把 a 精确到“在当前上下文中真正能跟在 A 后面的终结符”，这正是它比 SLR 强大、能识别更多文法的根本原因。

活前缀是指一个规范句型的前缀，它包含句柄但不越过句柄。项目集规范族里的每一个状态，本质上对应一组活前缀的等价类。构造 LR(1) 分析表的第一步，就是把所有这样的项目集算出来，这个过程叫项目集规范族构造。

2.2 闭包计算与向前看符号的传播机制

closure 的算法如下：对一个项目集 I，反复执行直到没有新项目加入——对 I 中的每个项目 [A → α·Bβ, a]，其中 B 是非终结符，对 B 的每个产生式 B → γ，以及每个 b ∈ FIRST(βa)，把 [B → ·γ, b] 加入 I。

这里最容易出错的就是 FIRST(βa)：先看点后面的符号串 β，如果 β 为空，FIRST(βa) 就是 {a}；如果 β 以终结符开头，FIRST(βa) 就是那个终结符；如果 β 以非终结符开头，要取该非终结符的 FIRST 集，并且如果它能推出空串，还要继续往后看，直到遇到终结符或回溯到 a 为止。

这个传播机制会形成一条链：从增广产生式 [S' → ·S, $] 开始，向前看符号 $ 会沿着产生式右部一级一级往下传，同时被 FIRST 集改写。手工构造时容易漏项，就是因为只算了直接生成的产生式，没有继续对新加入项目里的非终结符做闭包。

2.3 一个经典非 SLR 文法的状态演化

看这个教科书里常用的文法：

S → L = R | R L → * R | id R → L

它不是 SLR(1) 文法，但是 LR(1) 文法。先算初始项目集 I0 = closure({[S' → ·S, $]})。

第一步，[S' → ·S, $] 点后是 S，加入 S 的产生式，向前看符号取 FIRST($) = {$}，得到 [S → ·L=R, $] 和 [S → ·R, $]。

第二步，对 [S → ·L=R, $]，点后是 L，加入 L 的产生式，向前看符号取 FIRST(=R$) = {=}，得到 [L → ·*R, =] 和 [L → ·id, =]。

第三步，对 [S → ·R, $]，点后是 R，加入 R 的产生式，向前看符号取 FIRST($) = {$}，得到 [R → ·L, $]。

第四步，对 [R → ·L, $]，点后是 L，再次加入 L 的产生式，向前看符号取 FIRST($) = {$}，得到 [L → ·*R, $] 和 [L → ·id, $]。

最终 I0 里共有 9 个条目。注意 [L → ·*R, =] 和 [L → ·*R, $] 是两条不同项目，向前看符号分别是 = 和 $，不能合并。

接着算 goto(I0, L)：把点移过 L 的项目是 [S → L·=R, $] 和 [R → L·, $]，闭包不再增加新项目，得到 I2。关键看 I2：它同时包含一个移进项目 [S → L·=R, $] 和一个归约项目 [R → L·, $]。SLR 在这里会用 FOLLOW(R) = {=, $} 决定归约，遇到 = 也归约，和 shift 冲突；而 LR(1) 只在下一个符号是 $ 时归约，遇到 = 时移进，冲突消失。这就是 LR(1) 的精妙之处，也是它在实验报告里最值得写清楚的一页。

注意：手工构造规范族时，每算完一个状态的闭包就核对一遍项目数，对不上就一定在哪一步漏了 FIRST 传播，不要急着往下建表。

3. 从规范族到分析表：ACTION/GOTO 表的构造与冲突消解

3.1 四条填表规则与表结构

拿到项目集规范族 C 和状态转移集合 GOTO 之后，分析表分两部分。ACTION 表以状态编号为行、终结符为列，GOTO 表以状态编号为行、非终结符为列。

填 ACTION 表的规则有四条：

GOTO 表比较简单：对每个非终结符 A，如果 goto(Ii, A) 存在且 A 不是增广文法的开始符号，就填 GOTO[i, A] = goto(Ii, A)。注意增广文法引入的 S' 只用于初始项目集和接受判定，不参与 GOTO 表的填表。

3.2 冲突消解：LR(1) 比 SLR 强在哪

填表时如果某个格子被同时填了两种动作，就产生了冲突，分两类。移进-归约冲突是同一个格子里既是 shift 又是 reduce；归约-归约冲突是同一个格子里并入了两个不同的归约动作。

SLR 的冲突来源是用 FOLLOW 集代替真正的向前看集合，导致归约条件放宽。LR(1) 用精确向前看集合后，很多冲突自然消失。以第 2 章那个文法为例，状态 I2 中 [R → L·, $] 的归约符号只有 $，而 [S → L·=R, $] 要求输入 = 时移进，两者互不干扰。如果你在实验报告里对比 SLR 和 LR(1) 的 ACTION 表，这张表的差别就是全文最有说服力的部分。

填表时还容易漏掉一种情况：归约项目的向前看符号不是只有一个，比如项目 [A → α·, a/b] 其实是两条记录，分别写进 ACTION[i, a] 和 ACTION[i, b]。手工填写时要逐条展开。

3.3 文法边界：LR(1) 不是万能的

LR(1) 能处理所有确定型上下文无关语言，但不代表所有文法都能转为 LR(1)。二义性文法一定存在冲突，比如表达式文法如果不改写优先级，LR(1) 也无能为力。常见的做法是改写文法消除二义性，或者让分析器引入优先级和结合性去消解移进-归约冲突。

另外，LR(1) 分析表的状态数可能非常大。同样的文法，SLR 可能几十个状态，LR(1) 可能上百个。实验报告里如果要手工填表，建议选一个规模在 10 到 15 个产生式以内的小文法，否则项目集会膨胀到自己都看不下去。LALR(1) 通过合并同心项目集来缩小状态数，是实际编译器里的折中方案，我在第 6 章会演示怎么合并。

注意：填 ACTION 表时，如果出现冲突，先回查项目集闭包算对没有，再查向前看符号集合。大部分“假冲突”都是闭包漏项，不是文法真的二义。

4. 用 Python 实现 LR(1) 分析器：可复现的最小实现

4.1 数据结构与文法输入

我用 Python 写一个最小实现，配实验足够用。文法用列表存储，每一项是 (左部, 右部元组)，编号从 0 开始，编号 0 固定为增广产生式。项目用三元组 (产生式编号, 点位置, 向前看符号) 表示，项目集用 frozenset 方便去重和做字典键。

# 两两一组：产生式编号、左部、右部 grammar = [ ("S'", ("S",)), ("S", ("L", "=", "R")), ("S", ("R",)), ("L", ("*", "R")), ("L", ("id",)), ("R", ("L",)), ] terminals = {"=", "*", "id", "$"} nonterminals = {"S'", "S", "L", "R"} start_symbol = "S'"

这里用第 2 章的非 SLR 文法，方便验证程序的表确实比其他方法少冲突。如果你手上实验要求的文法不同，直接改 grammar 列表和两个符号集合即可。实际实验里我见过很多同学把终结符和非终结符写错，导致 FIRST 集的集合运算全部白算。

4.2 FIRST 集与 closure / goto 函数

FIRST 集是一切的基础。下面的实现假设文法没有空产生式，这样代码简洁很多；有 ε 产生式的文法需要额外处理，但实验课大多用不到。

def compute_first(grammar, nonterminals): first = {nt: set() for nt in nonterminals} changed = True while changed: changed = False for left, right in grammar: before = set(first[left]) if not right: first[left].add("ε") else: all_nullable = True for sym in right: if sym in nonterminals: first[left] |= first[sym] - {"ε"} if "ε" not in first[sym]: all_nullable = False break else: # 终结符 first[left].add(sym) all_nullable = False break if all_nullable: first[left].add("ε") if first[left] != before: changed = True return first

逻辑说明：循环不断扫描产生式，直到所有 FIRST 集不再变化。右部为空时直接加 ε；右部由多个符号组成时，逐个看符号，非终结符就并入它的 FIRST 集并去掉 ε，遇到终结符就加入并停止；整个右部都能推出空时，最后给左部加 ε。如果你把这段换成 Java 或 C++，思路完全一样，就是把集合操作拆成循环和数组。

closure 函数是手工构造的机械化版本：

def closure(itemset, grammar, first, nonterminals): itemset = set(itemset) stack = list(itemset) while stack: prod_id, dot, lookahead = stack.pop() left, right = grammar[prod_id] if dot < len(right) and right[dot] in nonterminals: target = right[dot] beta = right[dot + 1:] suffix = beta + (lookahead,) # 把 beta 和 a 拼起来算 FIRST for b in first_of_sequence(suffix, first, terminals): for pid, (l, r) in enumerate(grammar): if l == target: item = (pid, 0, b) if item not in itemset: itemset.add(item) stack.append(item) return frozenset(itemset)

这里默认生成顺序是“把所有产生式扫一遍”，不保证产生式编号顺序，但对结果无影响。FIRST(βa) 的计算用一个辅助函数以避免重复逻辑。

def first_of_sequence(syms, first, terminals): result = set() for s in syms: if s in terminals: result.add(s) return result result |= first[s] - {"ε"} if "ε" not in first[s]: return result result.add("ε") return result

参数说明：syms 是元组，first 是字典，terminals 是集合。函数逐个符号取 FIRST，遇到终结符或不可为空的非终结符就停下；全空时最后补 ε。注意这里把 lookahead 先转成元组再拼接，避免字符串和元组类型混用报错。

goto 函数本身很简单，关键是先筛项目再闭包：

def goto(itemset, symbol, grammar, first, nonterminals): moved = set() for prod_id, dot, lookahead in itemset: left, right = grammar[prod_id] if dot < len(right) and right[dot] == symbol: moved.add((prod_id, dot + 1, lookahead)) if not moved: return None return closure(moved, grammar, first, nonterminals)

4.3 项目集规范族与分析表生成

建状态机的过程类似图搜索：I0 作为初始状态压栈，每从栈里弹出一个状态，枚举它能识别的所有符号，计算 goto，如果得到一个新的项目集就分配新编号并记录转移边。

def build_states(grammar, first, nonterminals): init = frozenset([(0, 0, "$")]) init = closure(init, grammar, first, nonterminals) states = [init] trans = {} seen = {init: 0} stack = [0] while stack: idx = stack.pop() itemset = states[idx] symbols = set() for prod_id, dot, lookahead in itemset: left, right = grammar[prod_id] if dot < len(right): symbols.add(right[dot]) for sym in symbols: nxt = goto(itemset, sym, grammar, first, nonterminals) if nxt is None: continue if nxt not in seen: seen[nxt] = len(states) states.append(nxt) stack.append(len(states) - 1) trans[(idx, sym)] = seen[nxt] return states, trans

这段代码里，symbols 是当前状态点后所有符号的集合，不区分终结符和非终结符；goto 时非终结符走闭包，终结符也能闭包但闭包不会新增项目，结果等价于 LR(0) 的 shift。用 seen 字典以项目集本身做键，这样同构状态天然去重。

建表函数最需要注意冲突检测：

def build_table(grammar, states, trans, terminals, nonterminals): action = {} goto_table = {} for i, itemset in enumerate(states): for prod_id, dot, lookahead in itemset: left, right = grammar[prod_id] if dot < len(right): sym = right[dot] if sym in terminals and (i, sym) in trans: action[(i, sym)] = ("s", trans[(i, sym)]) elif prod_id == 0: if lookahead == "$": if (i, "$") in action: raise Exception(f"冲突：状态{i} 的 $ 已有动作") action[(i, "$")] = ("acc",) else: key = (i, lookahead) if key in action: raise Exception(f"冲突：状态{i} 的 {lookahead} 已有动作 {action[key]}") action[key] = ("r", prod_id) for A in nonterminals: if A != "S'" and (i, A) in trans: goto_table[(i, A)] = trans[(i, A)] return action, goto_table

归约项目的填表顺序在 reduce 分支里，和移进的判断天然分开，所以遇到同一个格子已有动作时必然是真冲突，直接抛异常即可。GOTO 表最后填，用 (状态, 非终结符) 做键。

4.4 驱动：移进-归约模拟器

分析表建好后，驱动函数只有三十行。状态栈和符号栈一定是同步压入、同步弹出的，这是新手最容易写错的地方。

def parse(tokens, grammar, action, goto_table): state_stack = [0] sym_stack = ["$"] tokens = list(tokens) + ["$"] idx = 0 while True: state = state_stack[-1] a = tokens[idx] act = action.get((state, a)) if act is None: print(f"错误：状态 {state} 遇到 {a}，无动作") return False if act[0] == "s": state_stack.append(act[1]) sym_stack.append(a) idx += 1 elif act[0] == "r": prod_id = act[1] left, right = grammar[prod_id] if len(right) > 0: state_stack = state_stack[:-len(right)] sym_stack = sym_stack[:-len(right)] gs = goto_table[(state_stack[-1], left)] state_stack.append(gs) sym_stack.append(left) elif act[0] == "acc": return True

逻辑说明：shift 时读入一个终结符压符号栈，归约时按右部长度弹出同样数量的状态和符号，再按左部查 GOTO 转移压入。acc 直接返回 True。这里的 tokens 是终结符序列，比如 ["id", "=", "id"]。跑这个文法时，输入 id=id 能接受，输入 id= 会在第二个输入处报错。

提示：如果你想验证第 2 章手工算的状态数，加一行 print(len(states))，对比自己画的规范族，状态数和转移边能完全对上就意味着手工计算没有漏项。

5. 避坑记录：LR(1) 实验的 5 个典型翻车现场

5.1 FIRST(βa) 把 β 和 a 分开算了，结果多出莫名其妙的项目

现象：closure 得到的项目集里出现明显不该有的向前看符号，比如 [L → ·*R, =] 和 [L → ·*R, $] 这种，本来应该有，但多出 [L → ·*R, id] 这种。

原因：计算 FIRST(βa) 时，只求了 β 的 FIRST 集，忽略了后面跟着的 lookahead a。β 为空时就没有正确处理，直接把 a 丢了，或者把 β 的 FIRST 集和 a 直接做并集而不是顺序拼接。

解决：把 β 和 a 拼成一个元组整体交给 first_of_sequence 函数，保证顺序语义。只要这样算，向前看符号就绝不会多。

5.2 状态编号对不上，手工表和程序表差一个转移

现象：手工构造的项目集规范族状态数比程序跑出来的少，或者多一个状态，GOTO 边对不上。

原因：程序对同构状态按项目集去重，而你手工画图时，两个项目集内容一样但因为生成顺序不同给了不同编号，最后忘记合并。

解决：每生成一个新状态，先和已有状态逐项比较，完全一致就复用编号。程序里用 frozenset 做字典键，天然解决这个问题；手工就老老实实把每个状态的项目全列出来再比较。

5.3 归约时符号栈和状态栈不一致，导致 GOTO 查错

现象：分析一个明显合法的句子，比如 id=id，跑到中间报 KeyError，查 goto_table 发现没有 (某个状态, 左部) 这个键。

原因：归约时状态栈弹出了 len(right) 项，但符号栈没有同步弹出，或者只弹了一半。goto 查的是“弹出右部后栈顶状态”，栈顶状态错了，跳转自然错。

解决：牢记归约的原子操作是状态栈和符号栈同时弹。建议在驱动函数里加断言 len(state_stack) == len(sym_stack)，跑一遍所有用例，保证栈同步。

5.4 CC 增广文法的接受项在非 $ 符号上

现象：程序能正确归约到 S' → S，但跑到最后不进入 acc，反而报无动作。

原因：写增广产生式时，如果项目 [S' → S·, $] 里的向前看符号不是 $，接受条件就不会触发；或者你在闭包初始化时写的是 other，而不是 $。

解决：初始化项目集永远从 (0, 0, "$") 开始。检查代码里有没有把 acc 条件写成 prod_id == 0 且 lookahead == "$"，两者缺一不可。

5.5 把符号表混进 LR(1) 分析器

现象：分析器带了一堆符号表管理代码，输入 id 时要查表、填类型，报错信息经常和 LR 分析的错误混在一起。

原因：这个实验的边界被自己加宽了。LR(1) 分析只负责语法识别，符号表是语义分析阶段的内容，两者混在一起，移进时既要做词法检查又要做语义检查，冲突排查难度翻倍。

解决：实验报告里明确写清边界：词法分析输出 token 流，LR(1) 分析器只吃 token 流。符号表相关的内容可以在报告“后续工作”里提一句，说清楚它属于语义分析阶段即可，不用硬塞进核心实现。

6. 用 LALR(1) 合并缩小分析表：一个验证与进阶技巧

判断你的 LR(1) 实现是否正确，有一个很实用的验证套路：找几个该文法能识别的句子逐个跑通，再找必须被拒绝的句子确认报错，然后把分析表的冲突检测打开跑一遍，确认没有抛异常。这三步过了，说明程序侧实现基本没问题，剩下的就是和手工推导的规范族对比状态数。

真正想进阶，推荐试一下 LALR(1)：把 LR(1) 项目集中具有相同核心的项目合并，核心就是去掉向前看符号后的项目集合。合并后状态数大幅减少，分析表也会小很多。实现起来不过十几行：

def merge_lalr(states): core_map = {} for idx, itemset in enumerate(states): core = frozenset((p, d) for p, d, _ in itemset) core_map.setdefault(core, []).append(idx) merged = [] mapping = {} for core, idxs in core_map.items(): mset = set() for i in idxs: mset |= states[i] mapping[tuple(sorted(idxs))] = len(merged) merged.append(frozenset(mset)) return merged

合并后的项目集是原始多个项目集的并集，向前看符号变多。这里有个经典结论：LALR 合并不会产生新的移进-归约冲突，但可能产生归约-归约冲突。如果合并后报冲突，说明原 LR(1) 表能区分，而 LALR 不能——这也反向验证了 LR(1) 表的精度。

我一般做完 LR(1) 实验后，会顺手把合并逻辑跑一遍，记录原始状态数和合并后状态数，写进报告的“进一步讨论”里。这个数据很能体现对原理的理解，比大段文字描述 LALR 是什么更有说服力。我第一次做这个实验时，就是因为懒，直接用 SLR 表交差，结果老师一问“这个归约为什么合法”就卡住了，后来老老实实手推了一遍项目集才真正弄懂向前看符号的传播。希望帮到你。

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