企业官网建设流程全解析

简介：面向编译原理学习者和开发者，这份资源聚焦 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", "E+T"), # 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 表的填法，用一个表就能说清。

需要注意，归约项目填全列并不是"可以填"而是"必须填"。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]), f's{j}', conflicts, i, rhs[pos]) elif pos == len(rhs): for c in cols: set_cell(action, i, cols.index(c), f'r{pid}', conflicts, i, c) for (i, x), j in transitions.items(): if x in nonterminals: goto[i][nonterminals.index(x)] = j return action, goto, conflicts

terminals列表里不要包含$，$固定追加在 ACTION 列的最后，这样cols.index('$')可以直接定位最后一列。goto矩阵的列顺序和nonterminals列表一一对应，非终结符的次序在前后端必须保持一致。set_cell把冲突记录下来而不是直接抛异常，是方便一次性看清楚这个文法哪里有冲突；如果只是做合法性判断，conflicts非空就返回 False 也行。真正在工程里，冲突列表要逐条人肉检查，不能自动选一条吞掉。

3.3 手工推一个例子：用 5 个状态验证填表逻辑

拿经典文法E -> E+T | T, T -> id走一遍。拓广后产生式是0: S' -> E, 1: E -> E+T, 2: E -> T, 3: T -> id。初态 I0 做闭包后有三个项目：[0, 0]、[1, 0]、[2, 0]、[3, 0]。按符号转移，得到的状态和 ACTION 表如下。

状态 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 列和 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 False

cell == -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 -> E+T | T, T -> id在 LR(0) 下本身无冲突，不需要 SLR(1) 修正。但换一个文法，比如S -> L = R | R, L -> * R | id, R -> L，LR(0) 会在状态里同时出现L -> . * R和R -> . L这类移进-归约冲突，SLR(1) 通过 FOLLOW 集把归约动作限制到特定列，冲突可能就消掉了。我排错时会写一个对比脚本：同一个文法分别跑 LR(0) 和 SLR(1)，输出conflicts列表，如果 SLR(1) 仍然有冲突，说明文法不是 SLR(1) 文法，该换 LALR(1) 或者 LR(1) 了。分析表构造完成之后，再用几条已知的合法和非法输入串跑驱动循环，核对接受/拒绝结果，这个黑匣子才算真正打开。这个两条腿走路的习惯帮我少调了无数个深夜，也把对分析表内部机制的判断从"玄学"变成了可复现的检查步骤，希望帮到你。

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