别再死记硬背了！用Python一步步带你生成LR(1)分析表（附完整代码）-平芜编程栈

用Python实战解析LR(1)分析表生成：从理论到代码的完整指南

编译原理中的LR(1)分析算法常被视为"龙书"中最具挑战性的内容之一。许多计算机专业学生在学习时，往往陷入抽象概念的泥沼而难以自拔。本文将通过Python代码实现，带您一步步构建LR(1)分析表，让这些抽象概念变得触手可及。

1. 理解LR(1)分析的核心概念

LR(1)分析是自底向上语法分析中最强大的方法之一，它能够处理绝大多数上下文无关文法。与SLR(1)相比，LR(1)通过引入向前搜索符(lahead)显著提高了分析的精确度。

关键术语解析：

项目(Item): 形如A→α·β, a的表达式，其中·表示当前分析位置，a是向前搜索符
闭包(Closure): 对项目集进行扩展的操作
GOTO函数: 状态转移函数，决定在遇到特定符号时转移到哪个状态

注意：LR(1)分析表由ACTION和GOTO两部分组成，前者处理终结符动作，后者处理非终结符转移

2. 准备工作：文法表示与数据结构设计

在开始编码前，我们需要设计合适的数据结构来表示文法和分析过程中的各种元素。

from collections import defaultdict class Grammar: def __init__(self): self.productions = defaultdict(list) # 产生式存储 self.non_terminals = set() # 非终结符集合 self.terminals = set() # 终结符集合 self.start_symbol = None # 开始符号 def add_production(self, head, body): """添加产生式""" self.productions[head].append(body) self.non_terminals.add(head) for symbol in body: if not symbol.isupper() and symbol != 'ε': self.terminals.add(symbol)

文法示例（我们将使用这个简单但足够展示特性的文法贯穿全文）：

E → E + T | T T → T * F | F F → ( E ) | id

3. 构建LR(1)项目集规范族

项目集规范族的构造是LR(1)分析表生成的核心步骤，它包括闭包计算和状态转移两个主要操作。

3.1 拓广文法

首先需要对原文法进行拓广，添加一个新的开始符号S'和产生式S'→S。

def augment_grammar(grammar): """拓广文法""" augmented = Grammar() augmented.start_symbol = grammar.start_symbol + "'" augmented.add_production(augmented.start_symbol, [grammar.start_symbol]) for head in grammar.productions: for body in grammar.productions[head]: augmented.add_production(head, body) return augmented

3.2 计算闭包

闭包操作是LR(1)分析中最关键也最容易出错的环节。以下代码展示了如何正确计算带向前搜索符的项目集闭包。

def closure(items, grammar): """计算LR(1)项目集的闭包""" closure_set = set(items) changed = True while changed: changed = False temp_set = set(closure_set) for item in temp_set: head, body, pos, lookahead = item if pos < len(body) and body[pos] in grammar.non_terminals: B = body[pos] beta = body[pos+1:] if pos+1 < len(body) else [] first_beta = first_of_sequence(beta + [lookahead], grammar) for production in grammar.productions[B]: for b in first_beta: new_item = (B, production, 0, b) if new_item not in closure_set: closure_set.add(new_item) changed = True return frozenset(closure_set)

4. 生成LR(1)分析表

有了项目集规范族后，我们就可以构建分析表了。分析表包括ACTION和GOTO两部分。

4.1 构建ACTION表

ACTION表处理移进和规约操作：

def build_action_table(canonical_collection, grammar): """构建ACTION表""" action_table = defaultdict(dict) for i, state in enumerate(canonical_collection): for item in state: head, body, pos, lookahead = item # 移进项目 if pos < len(body) and body[pos] in grammar.terminals: symbol = body[pos] next_state = goto(state, symbol, grammar) if next_state in canonical_collection: j = canonical_collection.index(next_state) action_table[i][symbol] = ('shift', j) # 规约项目 elif pos == len(body): if head != grammar.start_symbol + "'": for a in [lookahead]: action_table[i][a] = ('reduce', (head, body)) else: action_table[i]['$'] = ('accept',) return action_table

4.2 构建GOTO表

GOTO表处理非终结符的转移：

def build_goto_table(canonical_collection, grammar): """构建GOTO表""" goto_table = defaultdict(dict) for i, state in enumerate(canonical_collection): for A in grammar.non_terminals: next_state = goto(state, A, grammar) if next_state in canonical_collection: j = canonical_collection.index(next_state) goto_table[i][A] = j return goto_table

5. 完整代码实现与测试

现在我们将所有部分组合起来，形成一个完整的LR(1)分析表生成器。

def generate_lr1_table(grammar): """生成完整的LR(1)分析表""" augmented = augment_grammar(grammar) start_item = (augmented.start_symbol, [grammar.start_symbol], 0, '$') canonical_collection = [closure({start_item}, augmented)] changed = True while changed: changed = False temp_collection = list(canonical_collection) for state in temp_collection: for symbol in augmented.terminals | augmented.non_terminals: next_state = goto(state, symbol, augmented) if next_state and next_state not in canonical_collection: canonical_collection.append(next_state) changed = True action_table = build_action_table(canonical_collection, augmented) goto_table = build_goto_table(canonical_collection, augmented) return action_table, goto_table

测试示例：

# 定义示例文法 g = Grammar() g.start_symbol = 'E' g.add_production('E', ['E', '+', 'T']) g.add_production('E', ['T']) g.add_production('T', ['T', '*', 'F']) g.add_production('T', ['F']) g.add_production('F', ['(', 'E', ')']) g.add_production('F', ['id']) # 生成分析表 action, goto = generate_lr1_table(g) # 打印ACTION表 print("ACTION表:") for state in action: for symbol in action[state]: print(f"action[{state}][{symbol}] = {action[state][symbol]}")