简介面向编译原理课程的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 → LSLR 在构造某个状态时归约 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 → ·LR, $] 和 [S → ·R, $]。扩展 [S → ·LR, $] 时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 的关键对照对比维度SLRLR(1)归约判定依据FOLLOW(产生式左部)项目里记录的前瞻符号每个非终结符全局共享一个 FOLLOW 集每条产生式在不同上下文有不同前瞻典型冲突移进-归约冲突靠人工处理冲突在构造表时就精确暴露项目形态LR(0) 项目无第二分量A → α·β, a实验报告里如果只写“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 分析表的必填项检查单实验报告里的分析表不需要把几十个状态全画出来但表格结构要完整。检查项要求ACTION 表行数等于状态数ACTION 表列每个终结符加 $GOTO 表列每个非终结符接受项全表只能有一个 acc且只在 [S → S·, $] 所在状态冲突项每个格子最多一个动作冲突要在备注里解释原因表头状态号 文法符号很多实验报告只贴一张程序跑出来的大表没有手推过程。至少要保证 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 Nonefirst_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(fstate{state_stack} symbol{symbol_stack} finput{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) 的实现问题前前后后查了三小时。希望这篇笔记能帮你把这三个小时省下来。本文还有配套的精品资源点击获取