LR(0) 分析表构造实战：从文法到 DFA 的 5 步 Python 实现
LR(0) 分析表构造实战：从文法到 DFA 的 5 步 Python 实现
在编译原理领域，语法分析是编译器前端的关键环节。LR(0) 分析作为自底向上语法分析的基础方法，其核心在于构造能够指导分析过程的状态机和分析表。本文将带你用 Python 从零实现 LR(0) 分析表的完整构造流程，涵盖拓广文法、项目集闭包、GOTO 函数等核心概念，最终输出可用的 ACTION 和 GOTO 表。
1. 理解 LR(0) 分析基础
LR(0) 分析器的核心是一个有限状态自动机（DFA），它通过维护状态栈和符号栈来决定下一步动作。要构造这个自动机，我们需要以下关键组件：
- 项目（Item）：在产生式右部某位置加点的形式，如
A → α·β，表示已识别 α 并期待 β - 项目集闭包：包含核心项目及其通过非终结符推导出的所有项目
- GOTO 函数：定义从当前状态遇到符号 X 后转移到的下一个状态
class LR0Item: def __init__(self, prod, dot_pos=0): self.production = prod # 产生式对象 self.dot_pos = dot_pos # 点的位置(0到len(prod.rhs)) @property def next_symbol(self): """返回点后面的下一个符号""" if self.dot_pos < len(self.production.rhs): return self.production.rhs[self.dot_pos] return None def __eq__(self, other): return (self.production == other.production and self.dot_pos == other.dot_pos)2. 拓广文法与初始状态构建
LR(0) 分析需要从拓广文法开始，即在原始文法中添加新的开始符号 S' → S。这一步确保分析器有唯一的接受状态。
def augment_grammar(grammar): """拓广文法：添加 S' -> S 产生式""" new_start = grammar.start_symbol + "'" new_productions = [(new_start, [grammar.start_symbol])] new_productions.extend(grammar.productions) return Grammar(new_start, new_productions) def get_initial_state(aug_grammar): """构造初始状态 I0 = CLOSURE({[S' -> ·S]})""" start_prod = aug_grammar.productions[0] # S' -> S initial_item = LR0Item(start_prod, 0) return closure({initial_item}, aug_grammar)3. 计算项目集闭包
闭包操作是 LR(0) 分析的核心，它确保每个状态包含所有可能的项目。计算闭包需要不断添加通过非终结符推导出的新项目。
def closure(items, grammar): """计算项目集闭包""" closure_set = set(items) changed = True while changed: changed = False for item in list(closure_set): next_sym = item.next_symbol if next_sym and next_sym in grammar.nonterminals: # 添加所有以该非终结符为左部的产生式 for prod in grammar.productions_for(next_sym): new_item = LR0Item(prod, 0) if new_item not in closure_set: closure_set.add(new_item) changed = True return frozenset(closure_set)4. GOTO 函数与状态转移
GOTO 函数定义了状态之间的转移关系。对于给定状态和符号，计算转移后的新状态：
def goto(items, symbol, grammar): """计算 GOTO(I, X) = CLOSURE({[A→αX·β] | [A→α·Xβ] ∈ I})""" new_items = set() for item in items: if item.next_symbol == symbol: new_item = LR0Item(item.production, item.dot_pos + 1) new_items.add(new_item) return closure(new_items, grammar) if new_items else None5. 构造完整 DFA 和分析表
通过不断应用 GOTO 函数，我们可以构建完整的 LR(0) 自动机，并据此填充 ACTION 和 GOTO 表：
def build_lr0_automaton(grammar): """构造完整的 LR(0) 自动机""" aug_grammar = augment_grammar(grammar) C = [closure({LR0Item(aug_grammar.productions[0], 0)}, aug_grammar)] transitions = {} # (state_idx, symbol) -> target_state_idx changed = True while changed: changed = False for i, state in enumerate(C): for symbol in aug_grammar.symbols: new_state = goto(state, symbol, aug_grammar) if new_state and new_state not in C: C.append(new_state) changed = True if new_state: transitions[(i, symbol)] = C.index(new_state) return C, transitions def build_parsing_table(automaton, grammar): """根据自动机构造 LR(0) 分析表""" states, transitions = automaton action_table = {} goto_table = {} for (state_idx, symbol), target_idx in transitions.items(): if symbol in grammar.terminals: action_table[(state_idx, symbol)] = ('shift', target_idx) else: goto_table[(state_idx, symbol)] = target_idx for state_idx, state in enumerate(states): for item in state: if item.next_symbol is None: # 归约项目 if item.production.lhs == grammar.start_symbol + "'": action_table[(state_idx, '$')] = ('accept',) else: prod_idx = grammar.productions.index(item.production) for term in grammar.terminals + ['$']: action_table[(state_idx, term)] = ('reduce', prod_idx) return action_table, goto_table6. 实战案例：表达式文法分析
让我们用一个简单的表达式文法验证我们的实现：
# 定义简单表达式文法 expr_grammar = Grammar( start_symbol='E', productions=[ ('E', ['E', '+', 'T']), ('E', ['T']), ('T', ['T', '*', 'F']), ('T', ['F']), ('F', ['(', 'E', ')']), ('F', ['id']) ] ) # 构造分析表 automaton = build_lr0_automaton(expr_grammar) action_table, goto_table = build_parsing_table(automaton, expr_grammar) # 输出分析表（部分） print("ACTION 表片段:") for (state, term), action in list(action_table.items())[:5]: print(f"ACTION[{state}, {term}] = {action}") print("\nGOTO 表片段:") for (state, nt), target in list(goto_table.items())[:3]: print(f"GOTO[{state}, {nt}] = {target}")典型输出结果示例：
ACTION 表片段: ACTION[0, id] = ('shift', 5) ACTION[0, (] = ('shift', 4) ACTION[1, +] = ('shift', 6) ACTION[1, $] = ('accept',) ACTION[2, +] = ('reduce', 1) GOTO 表片段: GOTO[0, E] = 1 GOTO[0, T] = 2 GOTO[0, F] = 37. 处理冲突与优化
在实际应用中，LR(0) 分析可能会遇到移进-归约或归约-归约冲突。我们可以通过以下方式优化：
def resolve_conflicts(grammar): """冲突处理策略""" automaton = build_lr0_automaton(grammar) conflicts = detect_conflicts(automaton) if conflicts: print(f"检测到 {len(conflicts)} 处冲突") # 实现SLR(1)冲突解决策略 return build_slr_table(grammar) return build_parsing_table(automaton, grammar) def detect_conflicts(automaton): """检测状态中的冲突""" states, _ = automaton conflicts = [] for i, state in enumerate(states): reduce_items = [item for item in state if item.next_symbol is None] shift_items = [item for item in state if item.next_symbol in grammar.terminals] if len(reduce_items) > 1: conflicts.append((i, 'reduce-reduce', [item.production for item in reduce_items])) if reduce_items and shift_items: conflicts.append((i, 'shift-reduce', (shift_items[0].production, reduce_items[0].production))) return conflicts通过这五个关键步骤，我们实现了从文法定义到完整 LR(0) 分析表的 Python 构造过程。这个实现虽然简化，但涵盖了核心算法逻辑，可以作为更复杂分析器（如 SLR 或 LR(1)）的开发基础。