语法分析器帮你彻底搞懂)
用Python实战LL(1)语法分析器：从FIRST集到预测分析表的全流程解密
当你第一次翻开编译原理教材，看到那些密密麻麻的FIRST集、FOLLOW集公式时，是否感到一阵眩晕？别担心，你不是一个人。大多数人在学习语法分析时都会陷入"理解公式→死记硬背→考试遗忘"的怪圈。今天，我们将用Python构建一个真实的LL(1)语法分析器，让这些抽象概念在你眼前活起来。
1. 环境准备与文法定义
在开始编码前，我们需要明确几个核心概念。LL(1)分析器之所以能高效工作，关键在于它能通过一个符号的前瞻（那个"1"的含义）确定使用哪条产生式。要实现这一点，我们需要三类关键数据：FIRST集（一个符号能推导出的首终结符）、FOLLOW集（一个非终结符后可能出现的符号）以及由此计算出的SELECT集。
让我们从一个简单的四则运算文法开始，这是理解LL(1)分析的绝佳示例：
grammar = { 'E': [['T', "E'"]], "E'": [['+', 'T', "E'"], ['ε']], 'T': [['F', "T'"]], "T'": [['*', 'F', "T'"], ['ε']], 'F': [['(', 'E', ')'], ['id']] }这个文法已经过消除左递归处理——这是LL(1)分析的前提条件。注意我们使用了'符号表示派生非终结符（如E'），这是编译原理中的常见约定。
提示：ε代表空串，在Python中我们可以用None或空列表表示，但为了清晰起见，这里保留ε符号。
2. 计算FIRST集的Python实现
FIRST集的计算看似简单，实则暗藏玄机。其核心规则是：如果一个符号能推导出空串，那么我们需要继续查看后续符号。以下是递归实现的Python代码：
def compute_first(grammar): first = {key: set() for key in grammar} changed = True while changed: changed = False for non_term in grammar: for production in grammar[non_term]: for symbol in production: if symbol in grammar: # 非终结符 before = len(first[non_term]) first[non_term].update(first[symbol] - {'ε'}) if 'ε' not in first[symbol]: break after = len(first[non_term]) if after > before: changed = True else: # 终结符 before = len(first[non_term]) first[non_term].add(symbol) after = len(first[non_term]) if after > before: changed = True break else: # 所有符号都能推导出ε first[non_term].add('ε') return first这个实现有几个关键点：
- 使用集合运算来避免重复元素
- 通过
changed标志检测是否需要进行下一轮迭代 - 处理ε产生式时的特殊逻辑
运行这个函数，你会得到类似这样的输出：
{ 'E': {'(', 'id'}, "E'": {'+', 'ε'}, 'T': {'(', 'id'}, "T'": {'*', 'ε'}, 'F': {'(', 'id'} }3. FOLLOW集计算的工程化实现
FOLLOW集的计算更加复杂，因为它需要考虑文法中符号的上下文关系。以下是分步实现的Python代码：
def compute_follow(grammar, first, start_symbol='E'): follow = {key: set() for key in grammar} follow[start_symbol].add('$') # 结束符号 changed = True while changed: changed = False for non_term in grammar: for production in grammar[non_term]: trail = follow[non_term] for symbol in reversed(production): if symbol in grammar: before = len(follow[symbol]) follow[symbol].update(trail) if 'ε' in first[symbol]: trail.update(first[symbol] - {'ε'}) else: trail = first[symbol] if before != len(follow[symbol]): changed = True else: trail = {symbol} return follow这个算法的精妙之处在于：
- 从右向左遍历产生式，逐步构建FOLLOW关系
- 处理ε产生式时的特殊逻辑
- 迭代直到没有新的元素加入任何FOLLOW集
对于我们的四则运算文法，输出结果应该是：
{ 'E': {')', '$'}, "E'": {')', '$'}, 'T': {'+', ')', '$'}, "T'": {'+', ')', '$'}, 'F': {'*', '+', ')', '$'} }4. 构建预测分析表的关键步骤
有了FIRST和FOLLOW集，我们就可以构建LL(1)分析的核心——预测分析表。这个表告诉我们在任何给定的非终结符和输入符号组合下，应该选择哪条产生式。
def build_parsing_table(grammar, first, follow): table = {} for non_term in grammar: table[non_term] = {} for production in grammar[non_term]: first_of_prod = set() for symbol in production: if symbol in grammar: first_of_prod.update(first[symbol] - {'ε'}) if 'ε' not in first[symbol]: break else: first_of_prod.add(symbol) break else: first_of_prod.add('ε') for term in first_of_prod - {'ε'}: table[non_term][term] = production if 'ε' in first_of_prod: for term in follow[non_term]: table[non_term][term] = production return table生成的预测分析表可以用以下结构表示：
| 非终结符 | id | + | * | ( | ) | $ |
|---|---|---|---|---|---|---|
| E | T E' | T E' | ||||
| E' | + T E' | ε | ε | |||
| T | F T' | F T' | ||||
| T' | ε | * F T' | ε | ε | ||
| F | id | ( E ) |
5. 实现表驱动分析器
现在，我们终于可以编写LL(1)分析器的主体部分了。这个分析器将使用我们构建的预测分析表来处理输入字符串。
def ll1_parse(input_string, grammar, parsing_table, start_symbol='E'): stack = ['$', start_symbol] input_string = input_string + '$' pointer = 0 while stack: top = stack[-1] current_input = input_string[pointer] if top == current_input == '$': print("Accept!") return True elif top == current_input: stack.pop() pointer += 1 elif top in grammar: if current_input in parsing_table[top]: production = parsing_table[top][current_input] stack.pop() if production != ['ε']: stack.extend(reversed(production)) else: print(f"Error: no production for {top} on {current_input}") return False else: print(f"Error: unexpected symbol {current_input}") return False return False让我们测试一下这个分析器：
# 测试用例 test_cases = [ "id+id*id", # 有效 "(id+id)*id", # 有效 "id+*id", # 无效 "id++id", # 无效 ] for test in test_cases: print(f"\nParsing: {test}") ll1_parse(test.replace(' ', ''), grammar, parsing_table)你会看到分析器能正确识别合法表达式并拒绝非法输入。更重要的是，通过单步调试，你可以直观地看到分析栈和输入流的变化，这正是理解LL(1)分析工作原理的最佳方式。
