LR(0) 分析表构造实战：Python 实现 5 步自动生成算法（附完整代码）

LR(0)分析表构造实战Python实现5步自动生成算法附完整代码1. 理解LR(0)分析的核心概念在编译原理中语法分析是编译器前端的关键环节。LR(0)分析法作为一种自底向上的分析方法因其强大的分析能力和相对简单的构造逻辑成为许多编译器实现的首选方案。LR(0)名称的由来L从左到右扫描输入串Left-to-rightR构造最右推导的逆过程Rightmost derivation0分析时不需向前查看任何符号零个lookahead符号项目集与活前缀是理解LR(0)分析的两个核心概念# 示例项目表示例 production E → E T items [ E → · E T, # 初始状态 E → E · T, # 部分匹配 E → E · T, # 继续匹配 E → E T · # 完全匹配 ]活前缀是指规范句型的一个前缀它不包含句柄之后的任何符号。在分析过程中栈中的符号串始终构成活前缀这是LR分析正确性的重要保证。2. 构建LR(0)分析器的5个关键步骤2.1 拓广文法拓广文法是为了给分析过程定义一个明确的起点和终点。通过在原始文法中添加一个新的开始符号和产生式我们可以确保分析器有唯一的接受状态。def augment_grammar(grammar): 拓广文法示例 start_symbol grammar[0][0] new_grammar [fS → {start_symbol}] grammar return new_grammar # 原始文法示例 original_grammar [ E → E T, E → T, T → T * F, T → F, F → ( E ), F → id ] augmented_grammar augment_grammar(original_grammar)2.2 构造项目集闭包项目集闭包是LR(0)分析的基础数据结构它表示分析器在某一时刻可能处于的所有状态。闭包运算规则将初始项目加入闭包对于闭包中形如A→α·Bβ的项目将所有B→·γ的项目加入闭包重复步骤2直到闭包不再扩大def closure(items, grammar): 计算项目集闭包 closure_set set(items) changed True while changed: changed False for item in list(closure_set): dot_pos item.index(·) if dot_pos 1 len(item) and item[dot_pos1].isupper(): non_terminal item[dot_pos1] for prod in grammar: if prod.startswith(non_terminal →): new_item f{non_terminal} → ·{prod.split(→)[1].strip()} if new_item not in closure_set: closure_set.add(new_item) changed True return sorted(list(closure_set))2.3 计算GOTO函数GOTO函数定义了从一个项目集通过某个文法符号能够到达的新项目集。def goto(items, symbol, grammar): 计算GOTO函数 new_items [] for item in items: dot_pos item.index(·) if dot_pos 1 len(item) and item[dot_pos1] symbol: moved_item item[:dot_pos] symbol · item[dot_pos2:] new_items.append(moved_item) return closure(new_items, grammar) if new_items else []2.4 构造项目集规范族通过系统地应用闭包和GOTO函数我们可以构建出完整的项目集规范族即DFA的所有状态。def build_canonical_collection(grammar): 构造项目集规范族 start_item closure([f{grammar[0].split(→)[0].strip()} → ·{grammar[0].split(→)[1].strip()}], grammar) C [start_item] transitions [] changed True while changed: changed False for i, items in enumerate(C): symbols {item[item.index(·)1] for item in items if item.index(·)1 len(item)} for symbol in symbols: new_items goto(items, symbol, grammar) if new_items and new_items not in C: C.append(new_items) changed True if new_items: transitions.append((i, symbol, C.index(new_items) if new_items in C else -1)) return C, transitions2.5 构造LR(0)分析表基于项目集规范族我们可以构建LR(0)分析表包括ACTION和GOTO两个子表。状态ACTIONGOTOab0s1s21.........def build_lr0_table(C, transitions, grammar): 构造LR(0)分析表 action_table {} goto_table {} terminals set() non_terminals set() for prod in grammar: lhs, rhs prod.split(→) non_terminals.add(lhs.strip()) terminals.update([c for c in rhs.strip() if c.islower() or not c.isalpha()]) terminals.discard(·) terminals.add(#) # 结束符号 for state, items in enumerate(C): # 处理移进和GOTO for src, symbol, dest in transitions: if src state: if symbol in terminals: action_table[(state, symbol)] fs{dest} else: goto_table[(state, symbol)] dest # 处理归约 for item in items: if item.endswith(·): prod_num grammar.index(item.replace(·, ).strip()) for term in terminals: if (state, term) not in action_table: action_table[(state, term)] fr{prod_num} # 处理接受状态 if f{grammar[0].split(→)[0].strip()} → {grammar[0].split(→)[1].strip()}· in items: action_table[(state, #)] acc return action_table, goto_table, terminals, non_terminals3. Python实现完整代码以下是完整的LR(0)分析表生成器实现包含所有辅助函数和主流程class LR0ParserGenerator: def __init__(self, grammar): self.grammar self.augment_grammar(grammar) self.C, self.transitions self.build_canonical_collection() self.action_table, self.goto_table, self.terminals, self.non_terminals self.build_lr0_table() def augment_grammar(self, grammar): start_symbol grammar[0].split(→)[0].strip() return [fS → {start_symbol}] grammar def closure(self, items): closure_set set(items) changed True while changed: changed False for item in list(closure_set): dot_pos item.index(·) if dot_pos 1 len(item) and item[dot_pos1].isupper(): non_terminal item[dot_pos1] for prod in self.grammar: if prod.startswith(non_terminal →): new_item f{non_terminal} → ·{prod.split(→)[1].strip()} if new_item not in closure_set: closure_set.add(new_item) changed True return sorted(list(closure_set)) def goto(self, items, symbol): new_items [] for item in items: dot_pos item.index(·) if dot_pos 1 len(item) and item[dot_pos1] symbol: moved_item item[:dot_pos] symbol · item[dot_pos2:] new_items.append(moved_item) return self.closure(new_items) if new_items else [] def build_canonical_collection(self): start_item self.closure([ f{self.grammar[0].split(→)[0].strip()} → ·{self.grammar[0].split(→)[1].strip()} ]) C [start_item] transitions [] changed True while changed: changed False for i, items in enumerate(C): symbols {item[item.index(·)1] for item in items if item.index(·)1 len(item)} for symbol in symbols: new_items self.goto(items, symbol) if new_items and new_items not in C: C.append(new_items) changed True if new_items: transitions.append((i, symbol, C.index(new_items) if new_items in C else -1)) return C, transitions def build_lr0_table(self): action_table {} goto_table {} terminals set() non_terminals set() for prod in self.grammar: lhs, rhs prod.split(→) non_terminals.add(lhs.strip()) terminals.update([c for c in rhs.strip() if c.islower() or not c.isalpha()]) terminals.discard(·) terminals.add(#) for state, items in enumerate(self.C): # 处理移进和GOTO for src, symbol, dest in self.transitions: if src state: if symbol in terminals: action_table[(state, symbol)] fs{dest} else: goto_table[(state, symbol)] dest # 处理归约 for item in items: if item.endswith(·): prod_num self.grammar.index(item.replace(·, ).strip()) for term in terminals: if (state, term) not in action_table: action_table[(state, term)] fr{prod_num} # 处理接受状态 if f{self.grammar[0].split(→)[0].strip()} → {self.grammar[0].split(→)[1].strip()}· in items: action_table[(state, #)] acc return action_table, goto_table, terminals, non_terminals def print_tables(self): print(ACTION Table:) sorted_terms sorted(self.terminals) print(State\t \t.join(sorted_terms)) for state in range(len(self.C)): row [str(state)] for term in sorted_terms: row.append(self.action_table.get((state, term), )) print(\t.join(row)) print(\nGOTO Table:) sorted_non_terms sorted(self.non_terminals - {S}) print(State\t \t.join(sorted_non_terms)) for state in range(len(self.C)): row [str(state)] for nt in sorted_non_terms: row.append(str(self.goto_table.get((state, nt), ))) print(\t.join(row)) # 使用示例 if __name__ __main__: grammar [ E → E T, E → T, T → T * F, T → F, F → ( E ), F → id ] parser_gen LR0ParserGenerator(grammar) parser_gen.print_tables()4. 实战案例分析让我们以一个简单的算术表达式文法为例演示完整的LR(0)分析表构造过程示例文法E → E T | T T → T * F | F F → ( E ) | id步骤1拓广文法0: S → E 1: E → E T 2: E → T 3: T → T * F 4: T → F 5: F → ( E ) 6: F → id步骤2构造初始项目集闭包I0: S → ·E E → ·E T E → ·T T → ·T * F T → ·F F → ·( E ) F → ·id步骤3计算GOTO函数GOTO(I0, E) I1: S → E· E → E· T GOTO(I0, T) I2: E → T· T → T· * F GOTO(I0, F) I3: T → F· GOTO(I0, () I4: F → (· E ) E → ·E T E → ·T T → ·T * F T → ·F F → ·( E ) F → ·id GOTO(I0, id) I5: F → id·步骤4继续扩展所有项目集重复上述过程直到不再产生新的项目集。最终我们会得到12个项目集I0-I11。步骤5构造LR(0)分析表根据项目集规范族和GOTO函数我们可以填充ACTION和GOTO表ACTION Table: State id * ( ) # 0 s5 s4 1 s6 acc 2 r2 s7 r2 r2 r2 3 r4 r4 r4 r4 r4 4 s5 s4 5 r6 r6 r6 r6 r6 6 s5 s4 7 s5 s4 8 s6 s9 9 r5 r5 r5 r5 r5 10 r3 r3 r3 r3 r3 11 r1 r1 r1 r1 r1 GOTO Table: State E T F 0 1 2 3 1 2 3 4 8 2 3 5 6 10 3 7 11 8 9 10 115. 算法优化与工程实践在实际工程实现中我们还需要考虑以下优化点性能优化使用更高效的数据结构如字典存储项目集对项目集进行哈希处理加快查找速度并行计算闭包和GOTO函数错误处理def parse(input_string, action_table, goto_table, grammar): stack [0] # 初始状态 input_string input_string.split() [#] pointer 0 while True: state stack[-1] current_symbol input_string[pointer] action action_table.get((state, current_symbol), ) if not action: raise SyntaxError(fSyntax error at position {pointer}, unexpected symbol {current_symbol}) if action.startswith(s): # 移进 new_state int(action[1:]) stack.append(current_symbol) stack.append(new_state) pointer 1 elif action.startswith(r): # 归约 prod_num int(action[1:]) lhs, rhs grammar[prod_num].split(→) lhs lhs.strip() rhs rhs.strip() pop_len 2 * len(rhs.split()) stack stack[:-pop_len] state stack[-1] stack.append(lhs) stack.append(goto_table[(state, lhs)]) elif action acc: # 接受 return True else: raise SyntaxError(Invalid action during parsing)可视化输出def visualize_dfa(C, transitions): 使用Graphviz可视化DFA from graphviz import Digraph dot Digraph() for i, items in enumerate(C): label fI{i}\n \n.join(items) dot.node(str(i), labellabel) for src, symbol, dest in transitions: dot.edge(str(src), str(dest), labelsymbol) dot.render(lr0_dfa, viewTrue)测试验证# 测试用例 test_cases [ (id id * id, True), (( id id ) * id, True), (id * id, False), (id id, False) ] for test_input, expected in test_cases: try: result parse(test_input, action_table, goto_table, grammar) assert result expected print(fTest passed: {test_input}) except (SyntaxError, AssertionError): print(fTest failed: {test_input})通过以上实现我们完成了一个完整的LR(0)分析表生成器。这个实现不仅能够自动构造分析表还能验证输入串是否符合文法规则为后续的编译器开发奠定了坚实基础。