简介面向编译原理学习者和开发者这份资源聚焦 LR(0) 分析表的构建与运行机制。压缩包内含可执行的 C 源程序以及两个文本说明文件完整展示 LR(0) 分析表的生成思路涵盖初始状态构造、状态闭包计算、移进与归约动作生成等核心步骤。通过运行源码用户可以直观观察自底向上语法分析的整个过程理解在读取输入符号时解析器如何决定继续移进还是执行归约从而将教材中抽象的文法理论转化为具体工具演示。资源整体包体很小仅 5KB共 3 个文件便于下载与本地调试。目前已有 336 人浏览学习对于正在准备编译原理课程设计、复习语法分析章节或希望深入掌握 LR 分析方法的学生和开发者这份资料能够提供清晰的示例与对照帮助梳理 LR(0) 分析表的构造逻辑以及状态集与动作表之间的对应关系兼具学习参考和教学演示价值。1. LR(0).rar 里的 LR分析表编译器课设里最容易被冲突卡死的表打开 LR(0).rar 这个压缩包之前你得先想清楚一个问题LR分析表到底是什么。它不是一张随手填的二维表格而是自底向上语法分析器的核心产物——编译器拿到文法后第一步就是把它变成 LR 分析表之后每次移进、归约、接受都查这张表。常见做法是把这张表拆成 ACTION 表和 GOTO 表前者管终结符决定当前是移进还是归约后者管非终结符决定归约完之后跳回哪个状态。我第一次接触 LR(0) 时以为它是最简单的分析表结果发现它恰恰是最容易被冲突卡死的表——因为 LR(0) 完全不看下一个输入符号归约条件最粗糙能用它的文法很有限。下面就从 LR(0) 分析表怎么构造讲起把代码和踩坑都写清楚适合正在做编译原理课设、准备面试或者想自己写语法分析器的人。2. 先手工推开项目集规范族LR分析表的图纸是怎么立住的LR(0) 分析表的构造不依赖任何复杂的运行时信息它只做一件事把文法里所有可能的分析进度枚举出来再把这些进度按符号跳转关系连成一张状态图。这张状态图就是项目集规范族。分析表的每一行对应其中一个状态每一格的值来自状态之间的跳转。所以写一切代码之前先把项目集规范族的手工推导练熟后面填表就是体力活。2.1 为什么要先拓广文法让接受状态只有一个项目item是产生式右部加一个圆点比如E - E T变成E - E . T圆点左边表示已经读到的部分右边表示还期待的部分。一个项目集就是若干这样的项目聚在一起表示分析器当前处在同一条路径上的多个可能进度。这里有个前提原文法的开始符号可能出现在多个产生式右部直接构造项目集时没办法唯一定义分析完成了没所以要先拓广文法——加入新的开始符号 S 和产生式S - S。拓广产生式在整个编号表里固定是 0 号它唯一的归约项目[S - S .]就是接受项目。构造项目集规范族时初态从closure({[S - .S]})开始而不是从原开始符号的项目开始。这一步看起来只是加了一条产生式实际决定了后面 ACTION 表里acc动作只能出现在一个状态的一格上不至于出现两个状态都声称接受。2.2 闭包和 GO 函数项目集规范族的两个基本操作项目集规范族的构造依赖两个操作closure 闭包计算和 go 转移。闭包的含义是如果当前项目是[A - α . B β]圆点后面是非终结符 B说明分析器接下来可能从 B 推导任意产生式所以 B 的所有产生式左部的零进度项目[B - . γ]都要加进当前项目集。这个过程要重复到项目集不再膨胀为止。go 函数负责状态转移项目集 I 读入符号 x 之后把所有圆点后面正好是 x 的项目圆点右移一位再对结果做闭包得到下一个项目集。下面用 Python 写这两个函数文法用编号产生式列表表示项目用(产生式编号, 圆点位置)的二元组表示。# 产生式统一编号0 号固定是拓广产生式 S - S prods [ (S, E), # 0 (E, ET), # 1 (E, T), # 2 (T, T*F), # 3 (T, F), # 4 (F, (E)), # 5 (F, id), # 6 ] def closure(prods, items): 计算项目集的闭包。 prods: 编号后的产生式列表每个元素是 (左部, 右部字符串) items: 项目集合元素是 (产生式编号, 圆点位置) 返回闭包后的项目集合。 result set(items) changed True while changed: changed False for pid, pos in list(result): lhs, rhs prods[pid] if pos len(rhs): symbol rhs[pos] if symbol in nonterminals: # 圆点后是非终结符 for nxt_pid, (left, _) in enumerate(prods): if left symbol: item (nxt_pid, 0) if item not in result: result.add(item) changed True return result def go(prods, items, x): GO 函数项目集在符号 x 上的转移。 items: 当前项目集必须是闭包后的结果 x: 文法符号终结符或非终结符 返回下一个项目集的闭包。 moved set() for pid, pos in items: lhs, rhs prods[pid] if pos len(rhs) and rhs[pos] x: moved.add((pid, pos 1)) return closure(prods, moved)closure 里的while changed循环是关键不能只扫一遍。比如[E - . E T]引入了[E - . T]这个新项目圆点后面又是非终结符 T必须继续把 T 的产生式加进来。go 函数同样依赖 closure它没有直接调用闭包的话转移到下一个状态的项目集会残缺不全。这里的nonterminals是一个全局集合代码里在prods的左部集合里取即可不要用isupper()判断原因后面避坑章细说。2.3 把闭包和 GO 串起来生成完整状态图有了 closure 和 go项目集规范族就是一个从初态出发、对每个状态按所有文法符号求转移、反复扩张到没有新状态为止的过程。下面的build_states返回两个东西状态列表states和转移表transitions转移表用(状态编号, 符号)作为键目标是目标状态编号。def build_states(prods, nonterminals): 构造项目集规范族。 返回 (states, transitions)。 states: 列表每个元素是 frozenset 形式的项目集 transitions: dict键是 (状态编号, 符号)值是目标状态编号 start frozenset(closure(prods, {(0, 0)})) states [start] state_ids {start: 0} transitions {} pending [0] while pending: cur pending.pop() syms set() for pid, pos in states[cur]: lhs, rhs prods[pid] if pos len(rhs): syms.add(rhs[pos]) for x in sorted(syms): nxt frozenset(go(prods, states[cur], x)) if not nxt: continue if nxt not in state_ids: state_ids[nxt] len(states) states.append(nxt) pending.append(len(states) - 1) transitions[(cur, x)] state_ids[nxt] return states, transitions这里用frozenset做状态去重而不是直接拿 set 对象比较。项目集本身是集合两个集合内容相同就是同一个状态但直接states.index()每次线性扫描文法一大就慢得没法看而且 set 的顺序不稳定日志里对比状态时容易看走眼。用frozenset作为字典键既保证内容判断又拿到 O(1) 查找。后面填表时transitions里每一项都对应 ACTION 表的移进动作或 GOTO 表的跳转目标这条映射关系是整个构造算法的主线。提示手工推项目集时建议先在纸上把每个状态的项目写成[产生式编号, 圆点位置]再在旁边标注从哪个符号转移过来。做完一遍再对代码输出能很快发现是不是闭包漏了递归或者转移时圆点位置写错。3. 把项目集变成 LR分析表ACTION 和 GOTO 的填表规则与代码项目集规范族只是中间产物最终要落到 LR 分析表上。填表规则本身不难难在搞清楚哪些项目填哪一格、填什么动作。LR(0) 的归约动作有很强的个性只要某个状态里出现归约项目就在这一行的所有终结符列上填归约动作完全不管下一个输入是什么。这就是 LR(0) 和 SLR(1)、LR(1) 最本质的差别。3.1 三种项目决定三种动作移进、归约、接受每个项目按照圆点位置分三类圆点后面是终结符这是移进项目圆点已经在产生式右部末尾这是归约项目归约项目恰好是 0 号产生式S - S这是接受项目。分类直接决定 ACTION 表的填法用一个表就能说清。项目形态圆点含义ACTION 表动作[A - α . a β]a 是终结符期待输入串出现 aACTION[i, a] s jj 是 go(Ii, a) 的目标状态[A - α .]编号为 kα 已经归约完ACTION[i, 所有终结符和 $] r kLR(0) 不看下一个符号[S - S .]整个输入已经归约成 S只在$列填acc需要注意归约项目填全列并不是可以填而是必须填。LR(0) 的约定位是零个向前看符号所以它没有资格判断下一个输入是什么只能假设任何符号后面都可以归约。这也解释了为什么 LR(0) 描述能力弱文法稍微复杂一点移进项目和归约项目撞在同一个格子里冲突就产生了。3.2 一份能直接跑的填表代码检测冲突并生成二维数组填表代码要做的就是把 3.1 的规则翻译成循环。下面这份实现比教材伪代码多了两件事一是用set_cell统一处理格子被填过的情况二是把冲突收集起来返回供上层调用方直接看到文法是否满足 LR(0)。def set_cell(table, row, col, value, conflicts, i, sym): 填一格 ACTION 表如果已有其他动作则记录冲突。 table: ACTION 表二维列表 row/col: 行列下标 value: 要填的动作字符串如 s3、r2、acc conflicts: 冲突列表元素是 (状态编号, 符号, 旧动作, 新动作) if table[row][col] and table[row][col] ! value: conflicts.append((i, sym, table[row][col], value)) elif not table[row][col]: table[row][col] value def build_table(states, transitions, prods, terminals, nonterminals): 生成 LR(0) 分析表。 返回 (action, goto, conflicts)。 action: len(states) 行列依次是 terminals [$] goto: len(states) 行列依次是 nonterminals cols terminals [$] action [[] * len(cols) for _ in range(len(states))] goto [[-1] * len(nonterminals) for _ in range(len(states))] conflicts [] for i, items in enumerate(states): for pid, pos in items: lhs, rhs prods[pid] if pid 0 and pos len(rhs): set_cell(action, i, cols.index($), acc, conflicts, i, $) elif pos len(rhs) and rhs[pos] in terminals: j transitions.get((i, rhs[pos])) if j is not None: set_cell(action, i, cols.index(rhs[pos]), fs{j}, conflicts, i, rhs[pos]) elif pos len(rhs): for c in cols: set_cell(action, i, cols.index(c), fr{pid}, conflicts, i, c) for (i, x), j in transitions.items(): if x in nonterminals: goto[i][nonterminals.index(x)] j return action, goto, conflictsterminals列表里不要包含$$固定追加在 ACTION 列的最后这样cols.index($)可以直接定位最后一列。goto矩阵的列顺序和nonterminals列表一一对应非终结符的次序在前后端必须保持一致。set_cell把冲突记录下来而不是直接抛异常是方便一次性看清楚这个文法哪里有冲突如果只是做合法性判断conflicts非空就返回 False 也行。真正在工程里冲突列表要逐条人肉检查不能自动选一条吞掉。3.3 手工推一个例子用 5 个状态验证填表逻辑拿经典文法E - ET | T, T - id走一遍。拓广后产生式是0: S - E, 1: E - ET, 2: E - T, 3: T - id。初态 I0 做闭包后有三个项目[0, 0]、[1, 0]、[2, 0]、[3, 0]。按符号转移得到的状态和 ACTION 表如下。状态项目集要点id$ET0S-.E, E-.ET, E-.T, T-.ids3121S-E., E-E.Ts4acc2E-T.r2r2r23T-id.r3r3r34E-E.T, T-.ids355E-ET.r1r1r1状态 1 比较特殊包含S - E .和E - E . T前者在$列填acc后者在列填s4互不冲突所以这个文法能过 LR(0)。如果状态 1 里多一个归约项目比如T - id .那么列会同时被s4和r3争夺set_cell就会记一条冲突。手工推这个例子的意义在于你能直观看到 LR(0) 的归约填全列是什么效果也能理解为什么只要多一个归约项目就容易翻车。4. 分析表落到程序里二维矩阵、状态栈和驱动循环分析表构造出来之后语法分析器就是一个纯粹的查表循环。这个阶段最容易出的问题不是算法而是数据结构和边界条件表怎么存、错误格用什么值、归约时弹几个状态、$怎么参与查表。这些细节越早定清楚后面调试越省事。4.1 表的物理布局把 ACTION 和 GOTO 拼成一张大表很多教材把 ACTION 表和 GOTO 表分开画工程上我更推荐拼成一张宽表状态是行符号是列终结符列放 ACTION 动作非终结符列放 GOTO 目标状态。拼表的好处是索引逻辑统一查表时只需要一个二维数组和一套列名。列类型列名列表单元格内容空值含义ACTION 列所有终结符 $s状态号/r产生式号/acc空字符串表示 errorGOTO 列所有非终结符目标状态号非负整数-1表示 errorACTION 列和 GOTO 列的空值必须区分开不能在代码里都用同一个常量。ACTION 的空格用空字符串因为动作本身是字符串用判断干净利落GOTO 的空格用-1因为跳转目标是整数0是合法状态编号占用0会让错误跳转到状态 0排查时极难发现。这段用两个不同空值的处理属于典型的边界细节新手最容易在这上面踩坑。def init_table(states, terminals, nonterminals): 初始化一张合并的 LR 分析表。 返回 (table, cols)cols 是全部列名列表。 cols terminals [$] nonterminals table [] for _ in range(len(states)): row [] * len(terminals) # ACTION 部分 row.append() # $ 列 row [-1] * len(nonterminals) # GOTO 部分 table.append(row) return table, cols初始化之后把build_table的结果填进这张表ACTION 部分用兜底GOTO 部分填跳转号。合并表的列序必须固定建议把终结符、$、非终结符依次排列方便后面驱动循环用一套列名映射。terminals.index(符号)这种查询在循环里反复执行很慢可以预先建一个符号 - 列号的字典分析器跑长输入时能省下不少时间。4.2 驱动循环状态栈加输入串就够跑完语法检查LR 分析器的运行时结构是状态栈加输入串。严格来说还需要符号栈用来记住归约出来的非终结符但如果只做接受还是拒绝的判断状态栈加输入已经足够归约时从状态栈弹出与产生式右部等长的状态再查 GOTO 表压入新状态。符号栈只在携带语义值时才必须存在。def run_parser(tokens, prods, table, cols): 用合并分析表驱动 LR 语法分析。 tokens: 输入记号列表不含 $ 返回 True 表示接受False 表示拒绝。 col_index {sym: i for i, sym in enumerate(cols)} stack [0] tokens list(tokens) [$] pos 0 while True: state stack[-1] sym tokens[pos] col col_index[sym] cell table[state][col] if cell or cell -1: return False if cell acc: return True if isinstance(cell, str) and cell[0] s: stack.append(int(cell[1:])) pos 1 elif isinstance(cell, str) and cell[0] r: pid int(cell[1:]) _, rhs prods[pid] for _ in range(len(rhs)): stack.pop() goto_col col_index[prods[pid][0]] stack.append(table[stack[-1]][goto_col]) else: return Falsecell -1的判断不能省因为 GOTO 表的整数 0 是合法目标状态用if not cell会把状态 0 误判成 error。归约时弹出len(rhs)个状态这是由 LR 分析的性质保证的右部多长就对应栈里多少条已完成的转移记录。查 GOTO 表时用归约后的左部符号去定位列并且要在弹栈之后查因为 GOTO 的目标状态依赖栈顶的新状态。这段代码没有处理语义值如果后面要做表达式求值再维护一个与状态栈平行的符号栈就行。4.3 边界情况error 格的处理和 $ 的作用$ 不是一个普通终结符它在驱动循环里承担两个职责输入读完时的哨兵以及归约项目填全列时的最后一个列。cols列表里 $ 排在终结符之后、非终结符之前这个顺序保证了col_index[$]落在 ACTION 区域不会错进 GOTO 区域。输入串处理时把$追加到 tokens 末尾循环里遇到acc直接返回遇到非法格返回 False这就是整个错误处理策略。注意如果输入串里包含$作为普通终结符比如某些语言里真的存在$标识符那就要把输入结束符改名成#或EOF避免和符号表的列名撞在一起。这种改名要在构造分析表之前就统一不然后面查表全错位。5. LR(0)分析表避坑五个能把程序跑崩的边界细节LR(0) 分析表构造的代码量不大翻车往往不在算法本身而在文法表示、符号判断、去重方式这些边角料上。下面五条是我自己写课程设计和给同事 review 代码时反复遇到的坑按出现频率排个序。5.1 不拓广文法直接编号初态不唯一接受动作没法写现象ACTION 表里有多个状态在某个终终结符列填了类似接受的动作或者初态里同时出现好几个起点项目状态数比手推结果多。原因没加S - S拓广产生式项目集初态直接拿原开始符号的所有产生式做闭包。原开始符号可能出现在多条产生式左部导致多个归约项目都像归约到开始符号程序不知道该认哪个。解决编号表里固定把 0 号产生式留作拓广产生式闭包初态从{(0, 0)}开始。这行代码加在build_states之前任何文法的项目集规范族构造都必须先做这一步。5.2 闭包函数只扫一遍圆点后面是非终结符时要反复膨胀现象状态 0 的项目集少了好几条产生式比如[E - . T]加进去了但T - . F和 F - . (E) 却没有出现。原因闭包循环写成for item in sorted(initial_items)单遍扫描新加入的项目圆点后面如果还有非终结符没有继续处理。闭包的定义是传递闭包必须迭代到集合不再变化。解决用while changed循环每次从当前集合里取项目检查有新增就标记下次继续扫。把闭包的循环写熟这个坑就再也不会出现。可以加一个计数器限制最大迭代次数防御文法表示错误导致的死循环。5.3 随便定义一个非终结符集合符号分类不显式现象rhs[pos]是一个多字符记号比如id、num、while结果symbol in nonterminals永远为 False项目集规范族分裂成碎片。原因很多人写代码时用symbol.isupper()或者not symbol.islower()判断非终结符这只对单大写字母的文法示例成立。真实的词法记号往往是小写单词或者混合拼写字符级判断完全失效。解决在构造前显式收集nonterminals {left for left, _ in prods}终结符也显式定义成集合。所有符号分类都查这两个集合不要依赖字符大小写。这个决定要在 closure 函数第一版就定下来中途改容易漏掉 go 函数的判断。5.4 状态去重用列表比较慢且难排查现象文法状态一多build_states运行明显变慢或者项目集内容相同但状态编号对不上。原因用if nxt not in states加states.index(nxt)做去重每次都要对项目集做全量比较。set 内容相同就是相等这没问题问题是线性扫描 O(n) 开销项目集一多就卡。解决把每个项目集转成frozenset放进state_ids字典做键。先查字典不存在再加入。这样状态比较变成哈希比较速度提升明显。打印日志时用sorted(frozenset)保证项目顺序固定方便和手推结果对照。5.5 冲突检测漏掉 GOTO 表归约跳转写飞了现象输入串明明合法驱动循环在归约时table[stack[-1]][goto_col]取到-1直接返回 False但手推分析表这一步明明有跳转。原因build_table里只处理了 ACTION 表忘了把transitions里非终结符的转移填进 GOTO 矩阵。归约动作r2执行完查 GOTO 表发现格子是空的整个栈就废了。解决在填表函数最后加一段循环遍历transitions凡目标符号属于nonterminals的都写进 GOTO 矩阵对应格。同时给 GOTO 表初始化成-1而不是0不然漏填时跳转到状态 0驱动循环要跑很久才能发现异常误判成输入串被接受比直接报错更可怕。6. 从 LR(0) 到 SLR(1)用 FOLLOW 集反向自检你的分析表LR(0) 分析表最大的短板是归约动作不看输入符号导致大量移进-归约冲突。SLR(1) 的做法很简单归约项目不再填全列而是只填FOLLOW(左部)里的终结符列。这个改动只要在build_table的归约分支加一个集合判断就行其他代码全部复用。对每个非终结符算 FOLLOW 集时标准做法是先看所有产生式右部遇到B - ... A β就把 FIRST(β) 加入 FOLLOW(A)遇到B - ... A就把 FOLLOW(B) 加入 FOLLOW(A)循环到不动点。有了 FOLLOW 集把归约分支从for c in cols改成for c in follow[lhs]:空出来的格子让位给移进动作冲突数量会肉眼可见地下降。拿 3.3 的例子验证E - ET | T, T - id在 LR(0) 下本身无冲突不需要 SLR(1) 修正。但换一个文法比如S - L R | R, L - * R | id, R - LLR(0) 会在状态里同时出现L - . * R和R - . L这类移进-归约冲突SLR(1) 通过 FOLLOW 集把归约动作限制到特定列冲突可能就消掉了。我排错时会写一个对比脚本同一个文法分别跑 LR(0) 和 SLR(1)输出conflicts列表如果 SLR(1) 仍然有冲突说明文法不是 SLR(1) 文法该换 LALR(1) 或者 LR(1) 了。分析表构造完成之后再用几条已知的合法和非法输入串跑驱动循环核对接受/拒绝结果这个黑匣子才算真正打开。这个两条腿走路的习惯帮我少调了无数个深夜也把对分析表内部机制的判断从玄学变成了可复现的检查步骤希望帮到你。本文还有配套的精品资源点击获取