LL(1) 文法实战：从文法定义到预测分析表生成的 4 步 Python 实现

LL(1) 文法实战从文法定义到预测分析表生成的 4 步 Python 实现在编译原理的学习中语法分析是连接词法分析和语义分析的关键环节。而 LL(1) 文法作为一类重要的上下文无关文法因其简单高效的特性成为许多编程语言语法设计的基础。本文将带你用 Python 实现从文法定义到预测分析表生成的全过程通过代码揭示算法背后的计算逻辑。1. 理解 LL(1) 文法的核心概念LL(1) 文法得名于它的解析方式从左(L)向右扫描输入构建最左(L)推导并且只需向前查看 1(1) 个符号。要判断一个文法是否是 LL(1) 文法需要满足三个条件无左递归文法中不能存在形如 A → Aα 的产生式首符集不相交对于每个非终结符 A它的各个产生式的候选首符集两两不相交ε 产生式的特殊处理若某个非终结符 A 的某个候选首符集包含 ε则 FIRST(A) ∩ FOLLOW(A) ∅这些抽象的定义在实际应用中往往让人困惑。下面我们通过具体的 Python 实现将这些条件转化为可计算的逻辑。2. 构建文法数据结构首先我们需要设计合适的数据结构来表示文法。在 Python 中可以用字典来存储产生式用集合来保存终结符和非终结符class Grammar: def __init__(self): self.productions {} # 产生式字典键为非终结符值为产生式右部列表 self.terminals set() # 终结符集合 self.non_terminals set() # 非终结符集合 self.start_symbol None # 开始符号 def add_production(self, left, right): if left not in self.productions: self.productions[left] [] self.productions[left].append(right) self.non_terminals.add(left) for symbol in right: if symbol.islower() and symbol ! ε: self.terminals.add(symbol) def set_start(self, symbol): self.start_symbol symbol使用示例grammar Grammar() grammar.add_production(E, [T, E]) grammar.add_production(E, [, T, E]) grammar.add_production(E, [ε]) grammar.add_production(T, [F, T]) grammar.add_production(T, [*, F, T]) grammar.add_production(T, [ε]) grammar.add_production(F, [(, E, )]) grammar.add_production(F, [id]) grammar.set_start(E)3. 计算 FIRST 集和 FOLLOW 集3.1 FIRST 集的计算FIRST(α) 是可以从 α 推导出的所有串的首符号的集合。计算规则如下若 X 是终结符则 FIRST(X) {X}若 X 是非终结符且有产生式 X → ε则 ε ∈ FIRST(X)对于产生式 X → Y₁Y₂...Yₙ将 FIRST(Y₁) 中非 ε 的元素加入 FIRST(X)若 ε ∈ FIRST(Y₁)则继续加入 FIRST(Y₂) 中非 ε 的元素以此类推若所有 Yᵢ 都包含 ε则将 ε 加入 FIRST(X)Python 实现def compute_first_sets(grammar): first {nt: set() for nt in grammar.non_terminals} changed True while changed: changed False for nt in grammar.non_terminals: for production in grammar.productions[nt]: # 处理产生式右部的每个符号 all_epsilon True for symbol in production: if symbol in grammar.terminals: if symbol not in first[nt]: first[nt].add(symbol) changed True all_epsilon False break else: # 加入非ε元素 before_len len(first[nt]) first[nt].update(first[symbol] - {ε}) if len(first[nt]) ! before_len: changed True if ε not in first[symbol]: all_epsilon False break if all_epsilon and ε not in first[nt]: first[nt].add(ε) changed True return first3.2 FOLLOW 集的计算FOLLOW(A) 是所有句型中紧跟在 A 后面的终结符的集合。计算规则对于开始符号 S将 $ 加入 FOLLOW(S)对于产生式 A → αBβ将 FIRST(β) 中非 ε 的元素加入 FOLLOW(B)若 β 可推导出 ε 或 β ε则将 FOLLOW(A) 加入 FOLLOW(B)对于产生式 A → αB将 FOLLOW(A) 加入 FOLLOW(B)Python 实现def compute_follow_sets(grammar, first_sets): follow {nt: set() for nt in grammar.non_terminals} follow[grammar.start_symbol].add($) changed True while changed: changed False for nt in grammar.non_terminals: for production in grammar.productions[nt]: trailer follow[nt] # 从右向左处理产生式 for symbol in reversed(production): if symbol in grammar.non_terminals: before_len len(follow[symbol]) follow[symbol].update(trailer) if len(follow[symbol]) ! before_len: changed True if ε in first_sets.get(symbol, set()): trailer trailer.union(first_sets[symbol] - {ε}) else: trailer first_sets.get(symbol, set()) elif symbol in grammar.terminals and symbol ! ε: trailer {symbol} return follow4. 构建预测分析表有了 FIRST 和 FOLLOW 集我们就可以构建预测分析表 M。对于每个产生式 A → α对于 FIRST(α) 中的每个终结符 a将 A → α 加入 M[A, a]如果 ε ∈ FIRST(α)则对于 FOLLOW(A) 中的每个终结符 b包括 $将 A → α 加入 M[A, b]Python 实现def build_predictive_table(grammar, first_sets, follow_sets): table {} # 初始化表 for nt in grammar.non_terminals: for t in grammar.terminals.union({$}): table[(nt, t)] None for nt in grammar.non_terminals: for production in grammar.productions[nt]: first_alpha compute_first_of_string(production, first_sets) for terminal in first_alpha - {ε}: if table[(nt, terminal)] is not None: raise ValueError(fConflict in predictive table at [{nt}, {terminal}]) table[(nt, terminal)] production if ε in first_alpha: for terminal in follow_sets[nt]: if table[(nt, terminal)] is not None: raise ValueError(fConflict in predictive table at [{nt}, {terminal}]) table[(nt, terminal)] production return table def compute_first_of_string(symbols, first_sets): first set() for symbol in symbols: if symbol in first_sets: # 非终结符 first.update(first_sets[symbol] - {ε}) if ε not in first_sets[symbol]: return first else: # 终结符 first.add(symbol) return first first.add(ε) # 所有符号都能推导出ε return first5. 验证 LL(1) 文法条件在构建预测分析表的过程中我们实际上已经隐式验证了 LL(1) 文法的条件。如果在填表时发现冲突同一个表项有多个产生式则说明文法不是 LL(1) 的。我们可以添加一个显式的验证函数def is_ll1(grammar): try: first compute_first_sets(grammar) follow compute_follow_sets(grammar, first) build_predictive_table(grammar, first, follow) return True except ValueError: return False6. 可视化输出结果为了让计算结果更直观我们可以添加可视化输出的功能def print_first_follow_sets(grammar, first, follow): print(FIRST sets:) for nt in sorted(grammar.non_terminals): print(fFIRST({nt}) {sorted(first[nt])}) print(\nFOLLOW sets:) for nt in sorted(grammar.non_terminals): print(fFOLLOW({nt}) {sorted(follow[nt])}) def print_predictive_table(grammar, table): terminals sorted(grammar.terminals.union({$})) print(\nPredictive Analysis Table:) print(NT\t \t.join(terminals)) for nt in sorted(grammar.non_terminals): row [nt] for t in terminals: production table.get((nt, t), None) if production: row.append(f{nt}→{.join(production)}) else: row.append() print(\t.join(row))7. 完整示例运行让我们用一个完整的例子来测试我们的实现# 创建文法 g Grammar() g.add_production(E, [T, E]) g.add_production(E, [, T, E]) g.add_production(E, [ε]) g.add_production(T, [F, T]) g.add_production(T, [*, F, T]) g.add_production(T, [ε]) g.add_production(F, [(, E, )]) g.add_production(F, [id]) g.set_start(E) # 计算集合 first compute_first_sets(g) follow compute_follow_sets(g, first) # 构建分析表 table build_predictive_table(g, first, follow) # 输出结果 print_first_follow_sets(g, first, follow) print_predictive_table(g, table) print(f\nIs this grammar LL(1)? {is_ll1(g)})运行结果将显示每个非终结符的 FIRST 集和 FOLLOW 集预测分析表文法是否为 LL(1) 的判断8. 实际应用中的注意事项在实际实现编译器时还需要考虑以下问题错误恢复当预测分析表项为空时如何优雅地报告错误并恢复文法扩展支持更多的语法结构如选择语句、循环语句等性能优化对于大型文法可能需要优化集合计算算法符号处理如何处理用户定义的标识符和字面量通过这个实现我们不仅理解了 LL(1) 文法的理论条件还掌握了如何用代码将这些抽象概念具体化。这种从理论到实践的转化能力正是编译原理学习的核心价值所在。