简介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)为例分析过程是这样的输入第一个符号(移进栈变成(输入a移进栈变成( a栈顶的a匹配S - a归约栈变成( S栈顶的( S )匹配S - ( S )归约栈变成S归约到开始符号接受。每一步到底选择移进还是归约由 LR 分析表决定。这张表之所以能跑起来是因为它把“当前栈里已经形成什么结构”压缩成了一个状态编号。只要状态编号一致栈里的详细符号串就不影响后续决策这就省去了每次遍历栈的代价。LR(0) 分析表的构造过程本质上是从文法生成一个确定有限自动机DFA。这个 DFA 的节点就是项目集边就是文法符号。后面填表、驱动全是围绕这个 DFA 展开的。2.2 项目与项目集把文法转成 DFA 的原子单元“项目”item是在产生式右部插了一个圆点得到的结构。圆点左边是“已经看到的符号”右边是“期望继续看到的符号”。例如S - ( S )可以写成三种不同的项目S - . ( S )还没看到右部的任何符号S - ( . S )已经看到左括号正等一个SS - ( 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 与状态去重生成整个 DFAgoto 函数回答的问题是从当前状态读入一个文法符号后应该跳到哪个状态。实现方法是扫描状态里所有项目把圆点后面正好等于该符号的项目圆点后移一位再做一次闭包。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 非终结符”定位状态。动作类型只有四种动作含义触发条件shift把输入符号压栈进入新状态项目圆点后面是终结符reduce按某条产生式归约项目圆点已在右部末尾acc接受增广产生式的圆点到了末尾error表项为空报语法错误ACTION 表查不到对应项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_pos0 的误解现象文法里有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读入agoto 得到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)。你现在能分辨这个区别以后看别人的报告就不会被带偏了。希望帮到你。本文还有配套的精品资源点击获取