LR(0) 分析表构造实战：Python 实现 5 步自动生成算法（附完整代码）
LR(0)分析表构造实战：Python实现5步自动生成算法（附完整代码）
1. 理解LR(0)分析的核心概念
在编译原理中，语法分析是编译器前端的关键环节。LR(0)分析法作为一种自底向上的分析方法，因其强大的分析能力和相对简单的构造逻辑，成为许多编译器实现的首选方案。
LR(0)名称的由来：
- L：从左到右扫描输入串（Left-to-right）
- R：构造最右推导的逆过程（Rightmost derivation）
- 0：分析时不需向前查看任何符号（零个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 = [f"S' → {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_pos+1].isupper(): non_terminal = item[dot_pos+1] 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_pos+1] == symbol: moved_item = item[:dot_pos] + symbol + '·' + item[dot_pos+2:] 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两个子表。
| 状态 | ACTION | GOTO |
|---|---|---|
| a | b | |
| 0 | s1 | s2 |
| 1 | ||
| ... | ... | ... |
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)] = f's{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)] = f'r{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 [f"S' → {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_pos+1].isupper(): non_terminal = item[dot_pos+1] 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_pos+1] == symbol: moved_item = item[:dot_pos] + symbol + '·' + item[dot_pos+2:] 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)] = f's{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)] = f'r{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(f"Syntax 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 = f"I{i}\n" + "\n".join(items) dot.node(str(i), label=label) for src, symbol, dest in transitions: dot.edge(str(src), str(dest), label=symbol) dot.render('lr0_dfa', view=True)测试验证：
# 测试用例 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(f"Test passed: '{test_input}'") except (SyntaxError, AssertionError): print(f"Test failed: '{test_input}'")通过以上实现，我们完成了一个完整的LR(0)分析表生成器。这个实现不仅能够自动构造分析表，还能验证输入串是否符合文法规则，为后续的编译器开发奠定了坚实基础。