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_pos0): 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_symbolE, 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(fACTION[{state}, {term}] {action}) print(\nGOTO 表片段:) for (state, nt), target in list(goto_table.items())[:3]: print(fGOTO[{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)的开发基础。