保姆级教程：用Python实现一个简易编译器（从词法分析到语法树）

从零构建Python编译器手把手实现词法分析与语法树周末想挑战一个硬核编程项目不如用Python实现一个迷你编译器本文将带你从零开始用不到200行代码完成一个能处理算术表达式的编译器前端。无需编译原理基础我们会通过具体代码将抽象概念可视化——当你看到(35)*2变成一棵语法树时那些教科书上的FIRST集、递归下降等术语会突然变得清晰起来。1. 编译器前端架构设计现代编译器就像一条流水线我们今天要打造的是前端部分——负责把源代码转化为结构化表示的翻译官。这个迷你编译器将包含三个关键组件class MiniCompiler: def __init__(self): self.lexer Lexer() # 词法分析器 self.parser Parser() # 语法分析器 self.symbol_table {} # 符号表关键设计决策采用递归下降分析法Recursive Descent Parsing这是最符合人类直觉的语法分析方法语法规则使用LL(1)文法确保每个步骤只需向前看一个token输出结果为抽象语法树AST这是后续代码生成的基础提示虽然真实编译器会更复杂但这个简化版已经包含了所有核心概念。完成这个项目后你会对Clang、GCC等工业级编译器有全新的认识。2. 词法分析器实现词法分析器就像编译器的眼睛负责将字符流转化为有意义的单词token。我们先定义需要识别的token类型from enum import Enum class TokenType(Enum): INTEGER INTEGER PLUS PLUS MINUS MINUS MUL MUL DIV DIV LPAREN LPAREN RPAREN RPAREN EOF EOF # 输入结束标记实现词法分析器的核心是一个有限状态自动机DFA。以下代码展示了如何识别整数和运算符def get_next_token(self): while self.current_char is not None: if self.current_char.isspace(): self.skip_whitespace() continue if self.current_char.isdigit(): return Token(TokenType.INTEGER, self.integer()) if self.current_char : self.advance() return Token(TokenType.PLUS, ) # 类似地处理其他运算符...常见问题排查遇到123abc这样的输入时应该报错而不是识别为123需要正确处理负数如-5的情况换行符和制表符等空白字符应该被忽略3. 递归下降语法分析语法分析器是编译器的大脑我们采用递归下降分析法来实现。首先需要定义算术表达式的文法规则expression : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expression RPAREN对应的Python实现展示了如何将文法规则转化为代码def expression(self): node self.term() while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): token self.current_token self.eat(token.type) node BinOp(leftnode, optoken, rightself.term()) return node关键点解析expression()对应文法中的expression规则term()和factor()同理实现文法中的对应部分每个方法返回AST节点最终构建出完整的语法树eat()方法用于消费验证并跳过当前token4. 构建抽象语法树ASTAST是源代码的树形表示我们定义以下节点类型class ASTNode: pass class BinOp(ASTNode): def __init__(self, left, op, right): self.left left self.op op self.right right class Num(ASTNode): def __init__(self, token): self.token token self.value token.value当解析(35)*2时生成的AST结构如下* / \ 2 / \ 3 5可以用以下函数可视化ASTdef print_ast(node, level0): indent * level if isinstance(node, Num): print(f{indent}Num({node.value})) else: print(f{indent}BinOp({node.op.value})) print_ast(node.left, level1) print_ast(node.right, level1)5. 错误处理与扩展建议一个健壮的编译器需要友好的错误提示。我们在关键位置添加错误检测def eat(self, token_type): if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: raise Exception( f语法错误期望 {token_type}, 实际得到 {self.current_token.type} f 在位置 {self.lexer.pos} )项目扩展方向添加变量支持如x53实现简单的类型检查增加代码生成器将AST转化为栈式机代码支持更复杂的数据类型如字符串、数组添加函数调用语法这个周末项目最让我惊喜的是当第一次看到12*3被正确解析为预期AST时那些编译原理课本上的抽象概念突然变得具体可感。如果你卡在某个环节试着用更简单的表达式如单个数字开始调试逐步增加复杂度。