简介：面向编译原理课程的LR(1)分析法实验报告，适合计算机专业本科生、考研复习者及需要完成语法分析实验的开发者。报告以文法E→S、S→BB、B→aB、B→b为例，系统讲解LR(1)分析法的基本原理、ACTION表与GOTO表构造、驱动程序工作流程，并附完整C语言实现代码和运行截屏；可处理abb#等以#结束的符号串，动态输出状态栈、符号栈、输入串及ACTION/GOTO转移过程，展示移进、归约、接受和错误处理细节。资源包共1个doc文档，压缩包仅34KB，轻量易读，目前已吸引3467人学习。整体结构完整，可作为实验报告撰写模板或提纲参考，快速完成课程作业。

1. LR(1) 分析法实验报告：从手推项目集到一份能跑的语法分析器

LR(1) 分析法在编译原理实验里出现频率极高，但很多人交上去的是用 yacc 生成的 LALR 表冒充 LR(1)，老师一追问项目集就露馅。LR(1) 的全称是“从左到右扫描、最右推导、向前看一个符号”，核心做法是把前瞻符号写进每个项目，让移进和归约的判定从“大概能用”变成“精确到输入符号”。这份实验报告要做的核心事有三件：手工构造出 LR(1) 项目集族，按规则填入 ACTION/GOTO 分析表，再写一个表驱动分析器验证句子是否被接受。适合正在赶编译原理实验、准备面试手写分析器，或者不想把语法分析器当黑匣子用的人。跟着本文把文法和代码都跑通一遍，报告里的原理、表格、验证步骤自然就齐了。

2. LR(1) 项目与 CLOSURE 闭包：一个前瞻符号如何消掉 SLR 的冲突

2.1 让 SLR 翻车的经典文法

编译原理教材讲 LR(1) 几乎必提下面这个文法：

S' → S S → L = R S → R L → * R L → id R → L

SLR 在构造某个状态时，归约 R → L 的条件是“下一个输入符号属于 FOLLOW(R)”。FOLLOW(R) 里有 = 也有 $，而这个状态里同时存在项目 [S → L·=R]，表示“看到 = 就该移进”。于是 = 既触发移进又触发归约，SLR 当场翻车。

LR(1) 的差别在于，它把每个归约项目的前瞻符号限定成了某个特定上下文里真正可能出现的符号。同样的位置，LR(1) 写成 [R → L·, $]，归约 R → L 只在下个符号是 $ 时执行；输入符号是 = 时，表里只有移进动作，冲突被消化掉了。这个例子几乎每个学校都会拿来做实验报告的原理分析，值得亲手推一遍。

2.2 LR(1) 项目的数学形式与闭包规则

一个 LR(1) 项目是带前瞻符号的产生式：A → α·β, a。点号左边是已经看到的符号，右边是接下来期望看到的符号，a 是这个项目的向前看符号。含义是：当前状态下已经读到 α，期望后面出现 β，并且只有当输入符号是 a 时，才允许考虑执行这条产生式的归约。

CLOSURE(I) 的扩展规则只有一条。如果 I 里有项目 [A → α·Bβ, a]，B 是非终结符，那么对 B 的每一条产生式 B → γ，都要加入项目 [B → ·γ, b]，其中 b 属于 FIRST(βa)。

注意这里一定是 FIRST(βa)，不是 FIRST(β) 再加 a。β 为空时，FIRST(βa) 就是 {a}；β 如果可空，a 照样出现在 FIRST(βa) 里。闭包要反复执行到项目集合不再变化为止，它本质是一个不动点计算。

2.3 从初始项目手推 I0

初始项目是 [S' → ·S, $]，对它做一次完整闭包。先看 S 的产生式，加入 [S → ·L=R, $] 和 [S → ·R, $]。

扩展 [S → ·L=R, $] 时，B 是 L，β 是 =R，所以 L 产生式的前瞻符号来自 FIRST(=R$)，计算结果就是 =。于是加入 [L → ·*R, =] 和 [L → ·id, =]。

扩展 [S → ·R, $] 时，B 是 R，β 空，R → L 的前瞻就是 $，得到 [R → ·L, $]。再扩展这个项目里的 L，前瞻来自 FIRST($)，仍然是 $，于是又加入 [L → ·*R, $] 和 [L → ·id, $]。

I0 的最终内容如下：

[S' → ·S, $] [S → ·L = R, $] [S → ·R, $] [L → ·* R, =] [L → ·id, =] [R → ·L, $] [L → ·* R, $] [L → ·id, $]

注意 [L → ·*R, =] 和 [L → ·*R, $] 是两个不同的项目，不能合并。同一产生式带了不同前瞻就算不同项，这正是 LR(1) 项目集数量比 LALR 多的原因。很多新手在这里手一抖就合并了，后面表就对不上。

2.4 LR(1) 与 SLR 的关键对照

实验报告里如果只写“LR(1) 比 SLR 更强大”一句空话，老师的批注通常不会好看。把上面这张表画出来，再配经典文法的冲突位置说明，原理部分就立住了。

提示：LR(1) 并不是“完全没有冲突”的魔法，而是把决策信息前置到项目里；该有冲突的文法照样有冲突，只是位置比 LALR 更早、更好定位。

3. 构造 LR(1) 项目集族：GO 函数与分析表三条生成规则的落地

3.1 GO 函数与整体构造流程

GOTO(I, X) 的定义是：CLOSURE({[A → αX·β, a] | [A → α·Xβ, a] ∈ I})。直观理解，当前状态已经看完符号 X，点号右移一位之后再做一次闭包，得到的就是“看过 X 之后该进入的状态”。

项目集族的构造流程分五步。第一步，加增广产生式 S' → S；第二步，求所有非终结符的 FIRST 集；第三步，令 I0 = CLOSURE({[S' → ·S, $]})；第四步，对每个已生成状态 I 和每个文法符号 X，计算 J = GOTO(I, X)，如果 J 非空且从未出现过，加入状态集；第五步，重复第四步直到没有新状态。

状态去重的条件是“项目集合完全相同”，不能只看产生式和点号就把不同前瞻合并。后者是 LALR 的做法，实验要求写 LR(1) 时不要做这个优化，否则你交上去的是 LALR 分析表。

3.2 手工走一遍 I0 的 GOTO

回到上一章的 I0。GOTO(I0, L) 只有 [S → L·=R, $] 和 [R → L·, $]，闭包不新增项目。GOTO(I0, R) 只有 [S → R·, $]。GOTO(I0, *) 从 [L → ·*R, =] 和 [L → ·*R, $] 分别移动点，得到 [L → *·R, =] 和 [L → *·R, $]，再对 R 做闭包，加入 [R → ·L, =] 与 [R → ·L, $]，继续扩展 L 时还带这两个前瞻，最后共 6 个项目。GOTO(I0, id) 得到 [L → id·, =] 与 [L → id·, $]。

这个手工步骤在实验报告里最常被跳过，但它是老师判断你是否真懂的关键。建议报告里用表格列状态编号、项目集内容、由哪个 GOTO 生成三列，把 I0 到 I4 的推导过程写出来。

3.3 从项目集到 ACTION/GOTO 表的三条主规则

填表规则可以压缩成三条。第一条是移进：项目 [A → α·aβ, b] 中 a 是终结符，ACTION[I, a] = s(目标状态号)。第二条是归约：项目 [A → α·, a] 且 A 不是增广开始符号，ACTION[I, a] = r(产生式编号)。第三条是接受：项目 [S' → S·, $]，ACTION[I, $] = acc。

GOTO 表则把所有项目中非终结符 B 对应的 GOTO(I, B) 填进相应列。如果某个格子同时出现 s 和 r，是移进-归约冲突；同时出现两个不同的 r，是归约-归约冲突。LR(1) 分析表理论上是无冲突的，真出现冲突就从 CLOSURE 的前瞻计算和 FIRST 集合查起。

3.4 分析表的必填项检查单

实验报告里的分析表不需要把几十个状态全画出来，但表格结构要完整。

很多实验报告只贴一张程序跑出来的大表，没有手推过程。至少要保证 I0 到 I2 是手推的，后续状态可以引用程序输出。

4. 从手推走向程序：CLOSURE、GOTO 与分析表生成的最小 Python 实现

如果你实验选型是 Java，核心逻辑等价，只是把项目封装成类，重写 equals 和 hashCode。我这里用 Python 写，因为它表达集合和产生式最直接，代码量最小，方便对照实验报告。

4.1 文法表示与 FIRST 集

先定义一个小而全的表达式文法，后面所有手推和程序验证都用它：

terminals = {'int', '+', '(', ')', '$'} nonterminals = {'S', 'E', 'T'} grammar = { 'S': [('E',)], 'E': [('E', '+', 'T'), ('T',)], 'T': [('(', 'E', ')'), ('int',)], } # nullable：非终结符能否推出空串 nullable = {nt: False for nt in nonterminals} changed = True while changed: changed = False for lhs, rules in grammar.items(): for right in rules: # 产生式右部所有符号都可空，左部就可空 if all(not (sym in nonterminals) or nullable[sym] for sym in right): if not nullable[lhs]: nullable[lhs] = True changed = True # FIRST 集：终结符的 FIRST 是自己，非终结符迭代计算 first = {sym: {sym} for sym in terminals} first.update({nt: set() for nt in nonterminals}) changed = True while changed: changed = False for lhs, rules in grammar.items(): for right in rules: before = set(first[lhs]) for sym in right: first[lhs] |= (first[sym] - {'ε'}) if not nullable.get(sym, False): break else: # 右部所有符号都可空，左部 FIRST 加入 ε first[lhs].add('ε') if first[lhs] != before: changed = True

这段代码有两个关键参数。nullable记录非终结符能否推导出空串，它影响 FIRST 计算里要不要继续向后扫描；first是符号到集合的映射，终结符的 FIRST 集合就是自身。迭代终止条件是集合不再变化，和闭包思路一致，都是不动点算法。

4.2 CLOSURE 与 GOTO 两个核心函数

项目用四元组表示：左部、右部、点号位置、前瞻符号。写成元组自然就可以放进集合去重。

def first_of_seq(seq): """计算一个符号串的 FIRST 集，序列尾部通常是前瞻符号""" res = set() for sym in seq: res |= first[sym] - {'ε'} if not nullable.get(sym, False): break else: res.add('ε') return res def closure(base_items): """闭包：反复加入 B 的产生式，直到项目集合不变""" items = set(base_items) changed = True while changed: changed = False additions = set() for lhs, right, dot, lookahead in items: if dot < len(right) and right[dot] in nonterminals: B = right[dot] beta = right[dot + 1:] # 关键：前瞻来自 FIRST(beta + lookahead) for b in first_of_seq(beta + (lookahead,)): if b == 'ε': continue for prod in grammar[B]: new_item = (B, prod, 0, b) if new_item not in items: additions.add(new_item) if additions: items |= additions changed = True return frozenset(items) def go_to(items, symbol): """GOTO：点号右移一位后做闭包""" moved = set() for lhs, right, dot, lookahead in items: if dot < len(right) and right[dot] == symbol: moved.add((lhs, right, dot + 1, lookahead)) return closure(moved) if moved else None

first_of_seq里的nullable.get(sym, False)是安全写法，终结符不在 nullable 字典里，直接按不可空处理，遇到终结符就停止扫描。closure里过滤掉 ε 作为前瞻，因为 LR(1) 分析表的列里不会出现 ε，它只参与 FIRST 计算。go_to为空时返回 None，调用方用它判断“这个符号在当前状态不可见”。

4.3 主循环生成状态族与分析表

all_symbols = sorted(terminals) + sorted(nonterminals) rule_ids = { ('E', ('E', '+', 'T')): 1, ('E', ('T',)): 2, ('T', ('(', 'E', ')')): 3, ('T', ('int',)): 4, } states = [] state_no = {} def add_state(items): if items not in state_no: state_no[items] = len(states) states.append(items) # 增广产生式 S' -> S add_state(closure({('S_start', ('S',), 0, '$')})) transitions = {} worklist = list(states) while worklist: I = worklist.pop() for sym in all_symbols: J = go_to(I, sym) if not J: continue old_len = len(states) add_state(J) if len(states) > old_len: worklist.append(J) transitions[(state_no[I], sym)] = state_no[J] # 初始化 ACTION 和 GOTO 表 term_index = {sym: i for i, sym in enumerate(sorted(terminals))} nt_index = {sym: i for i, sym in enumerate(sorted(nonterminals))} action = [[None] * len(terminals) for _ in states] go_to_table = [[None] * len(nonterminals) for _ in states] for idx, items in enumerate(states): for lhs, right, dot, lookahead in items: if dot < len(right) and right[dot] in terminals: a = right[dot] target = transitions.get((idx, a)) if target is not None: # 写入前检查冲突 if action[idx][term_index[a]] is not None: print(f"冲突: 状态{idx} 符号{a}") action[idx][term_index[a]] = ('s', target) elif dot == len(right): if lhs == 'S_start' and lookahead == '$': action[idx][term_index['$']] = ('acc',) else: rule_no = rule_ids.get((lhs, right)) key = term_index[lookahead] if action[idx][key] is not None: print(f"冲突: 状态{idx} 归约{ruled_on} lookahead={lookahead}") if rule_no is not None: action[idx][key] = ('r', rule_no) for (state, sym), target in transitions.items(): if sym in nonterminals: go_to_table[state][nt_index[sym]] = target

主循环里有一个细节值得单独说明：worklist.pop()弹栈顺序影响状态编号，但不会影响表的结构。为了让实验报告和程序编号一致，all_symbols用sorted固定顺序，这样每次运行生成的编号都一样。冲突检查必须在写入前做，发现 None 被覆盖就把状态和符号打出来，比跑完输入再报错直观得多。

注意：rule_ids 只收录了非增广的产生式。增广产生式 S' → S 不参与归约动作，它只在接受条件里出现。如果给增广产生式也编了号，ACTION 表会多出无意义的 r 项。

5. LR(1) 项目集构造常见问题排查：状态爆炸、空串与接受状态

5.1 程序无限循环：CLOSURE 没判断“集合是否不再变化”

现象：程序运行很久不结束，或者状态数一路涨到几千甚至上万。

原因：CLOSURE 循环体里每次扩展都基于同一个 items，但扩展出来的新项目没有触发下一轮迭代。更常见的写法错误是在 for 循环里直接修改正在遍历的集合，导致项目反复被加入。

解决：用 additions 暂存新项目，循环结束后统一合并；每次合并后把 changed 置为 True，直到某轮 additions 为空再退出。可以加一个调试计数器，超过预期状态数就打印当前闭包大小，立刻能看出是否在空转。

5.2 手推状态与程序编号对不上：遍历顺序不固定

现象：报告里手推的状态 3 是 GOTO(I0, id)，程序输出里状态 3 却是 GOTO(I0, *)，两张表对不上。

原因：字典和集合的迭代顺序取决于哈希，不同运行可能给出不同编号。如果在报告里引用程序输出的编号，必须保证程序每次跑出来一样。

解决：把所有符号列表排序，状态队列用先进先出或先进后出但固定顺序。文中代码用 sorted(terminals) + sorted(nonterminals) 保证 all_symbols 顺序固定，worklist 的弹出顺序也随之固定。报告里状态编号直接引用程序输出，并在表注里写“编号由生成程序决定”。

5.3 接受判断总失败：输入串末尾没补结束符

现象：明明正确的句子，程序跑到最后报“语法错误”。

原因：分析表里 acc 只在 [S' → S·, $] 且输入为 $ 时出现。如果输入串没有在末尾追加 $，驱动循环永远不会触发接受，最后访问到未定义的动作格，报错退出。

解决：驱动分析器之前把输入 token 列表复制一份，末尾强制加 '$'。状态栈初始化 [0]，符号栈初始化 ['$']，这两个初始化动作也经常被漏掉，漏掉后第一步移进就会访问空栈。

5.4 空产生式让前瞻集合缺项：FIRST 漏处理可空符号

现象：文法里存在 nullable 非终结符时，分析表某些格子该有归约动作却没有，输入在正确位置报错。

原因：CLOSURE 计算前瞻用了 FIRST(β) 而不是 FIRST(βa)。β 可空时，正确结果要把 a 并进去；只算 FIRST(β) 就丢掉了 a，对应格的归约动作缺失。

解决：统一走first_of_seq(beta + (lookahead,))这个函数，先算 nullable 再算 FIRST，不要把前瞻符号单独拼接。检查方法是在 CLOSURE 里故意把 beta 换成空元组跑一遍，确认 acc 状态的前瞻确实是 $。

5.5 冲突排查困难：没有在构造期留下状态快照

现象：分析表生成后，某个输入失灵，查了半天不知道哪个状态先出的问题。

原因：冲突检查只在写入时打印一行文字，没有把冲突所在状态的项目集内容打出来。状态号不是人脑能直接读的，你看到的只是“状态7冲突”五个字。

解决：冲突发生时，把该状态的全部项目按行打印，并标注冲突的项目来自哪个 GOTO。这个习惯帮我解决过至少三次 CLOSURE 实现错误，比对着表格反复看效率高得多。

6. 给分析器加一个带打印的跟踪循环，把句子跑给大家看

实验报告最后一个环节一般是“验证输入串能被接受”。与其只贴一句“运行成功”，不如把每一步移进归约过程打出来。下面这个跟踪循环是我常用的版本，文字和表格都靠它生成：

def parse_trace(tokens, action, go_to_table, term_index, nt_index, rule_map): state_stack = [0] symbol_stack = ['$'] pos = 0 source = list(tokens) + ['$'] while True: state = state_stack[-1] a = source[pos] cell = action[state][term_index[a]] print(f"state={state_stack} symbol={symbol_stack} " f"input={source[pos:]} action={cell}") if cell is None: return False kind = cell[0] if kind == 's': state_stack.append(cell[1]) symbol_stack.append(a) pos += 1 elif kind == 'r': left, right = rule_map[cell[1]] for _ in right: state_stack.pop() symbol_stack.pop() next_state = go_to_table[state_stack[-1]][nt_index[left]] state_stack.append(next_state) symbol_stack.append(left) elif kind == 'acc': return True

这个循环的价值在于：每执行一步，你都能看到状态栈、符号栈、剩余输入和动作四个量。把输出粘进实验报告，再对每一步做两三句注释，验证部分就比单纯贴“True”有说服力。

我自己做语法分析器留下的习惯是：任何表格生成后，先挑一个只有归约没有移进的输入跑跟踪，再挑一个带嵌套括号的输入跑。前者验证归约链，后者验证移进和 GOTO 是否正确。有一次我在 CLOSURE 里漏处理了可空非终结符，正是靠跟踪循环看到某个状态缺少归约动作，才定位到 FIRST(βa) 的实现问题，前前后后查了三小时。希望这篇笔记能帮你把这三个小时省下来。

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