# 手把手教你用Python实现编译器前端：词法分析+语法分析+语义分析全流程 很多编程爱好者在学习编译原理时，常常会陷入一个困境：理论书籍读起来云里雾里，各种形式化定义和算法描述让人望而生畏，但内心深处又渴望亲手实现一个能真正“理解”代码的程序。这种感觉，就像站在一座宏伟的宫殿外，知道里面藏着精妙的机械，却找不到那扇可以亲手触摸齿轮的门。 实际上，构建一个编译器前端——也就是那个将源代码字符流转化为带有语义信息的中间表示的部分——并没有想象中那么遥不可及。它更像是一场精心设计的解谜游戏，你需要依次解决三个核心问题：如何把一连串字符切割成有意义的单词（词法分析），如何判断这些单词的排列是否符合语法规则（语法分析），以及如何为符合语法的结构赋予实际含义（语义分析）。今天，我们就抛开厚重的教科书，直接用Python作为我们的工具，从零开始，一步步搭建起这个系统的骨架。你会发现，那些看似抽象的概念，一旦用代码具象化，就会变得清晰而有趣。无论你是想为课程设计寻找灵感，还是单纯好奇日常使用的编程工具背后是如何工作的，这篇文章都将为你提供一条可操作、可验证的实践路径。 ## 1. 环境准备与项目蓝图 在开始敲代码之前，我们需要明确两件事：一是我们最终要做出一个什么东西，二是需要准备好哪些工具。我们的目标是实现一个简化版算术表达式计算器的“编译器前端”。它能够读取像 `"3 + 5 * (10 - 4)"` 这样的字符串，识别出数字、运算符和括号，验证其结构是否正确，并最终计算出结果（或生成对应的计算指令）。这个目标足够小，可以在一篇文章的篇幅内完成；又足够典型，涵盖了编译器前端的三大核心阶段。 首先，确保你的Python环境在3.6以上。我们不需要任何复杂的外部库，纯粹使用标准库来展示核心原理，这能让你更清晰地看到每个环节是如何运作的。创建一个新的项目目录，比如 `mini_compiler/`，并在其中初始化我们的主要模块。 ```bash mkdir mini_compiler cd mini_compiler touch lexer.py parser.py semantic.py main.py ``` 我们的项目结构将非常直观： - `lexer.py`: 负责词法分析，把字符串变成令牌（Token）序列。 - `parser.py`: 负责语法分析，根据文法规则将令牌序列组织成语法树。 - `semantic.py`: 负责语义分析，遍历语法树并进行求值或生成中间代码。 - `main.py`: 主程序，串联整个流程。 在开始每个模块的编码前，我们先定义好它们之间通信的“协议”，也就是**Token**的数据结构。一个Token至少需要包含类型（是数字还是加号）和具体的值。 ```python # 在 lexer.py 或一个单独的 tokens.py 中定义 from enum import Enum, auto class TokenType(Enum): INTEGER = auto() # 整数，如 123 PLUS = auto() # 加号 + MINUS = auto() # 减号 - MUL = auto() # 乘号 * DIV = auto() # 除号 / LPAREN = auto() # 左括号 ( RPAREN = auto() # 右括号 ) EOF = auto() # 文件结束标志 class Token: def __init__(self, type_: TokenType, value: str = None): self.type = type_ self.value = value # 对于整数，value存储字符串形式的数字，如"123" def __repr__(self): return f'Token({self.type}, {repr(self.value)})' ``` 有了这个基础框架，我们就可以分兵三路，逐个击破词法、语法和语义分析的堡垒了。 ## 2. 词法分析器：从字符流到令牌序列 词法分析器（Lexer）的工作，好比阅读时先把句子拆分成一个个单词。它的输入是源代码字符串，输出是我们刚才定义好的Token对象列表。核心任务是**识别词素**并为其分类。 我们支持的词素很简单：整数、四则运算符和括号。整数由连续的数字字符构成，运算符和括号是单个字符。此外，我们还需要处理空格，它们在大多数语言中只是分隔符，不产生任何Token。 下面是一个**手写**的、基于状态循环的简单词法分析器实现。与使用Lex等生成器工具不同，手写能让你更透彻地理解识别过程。 ```python # lexer.py from tokens import Token, TokenType class Lexer: def __init__(self, text: str): self.text = text # 输入的源代码字符串 self.pos = 0 # 当前字符的索引位置 self.current_char = self.text[self.pos] if self.text else None def error(self): raise Exception('Invalid character') def advance(self): """向前移动一个字符位置，并更新current_char。""" self.pos += 1 if self.pos >= len(self.text): self.current_char = None else: self.current_char = self.text[self.pos] def skip_whitespace(self): """跳过所有空白字符（空格、制表符等）。""" while self.current_char is not None and self.current_char.isspace(): self.advance() def integer(self): """读取一个多位整数，返回其字符串形式。""" result = '' while self.current_char is not None and self.current_char.isdigit(): result += self.current_char self.advance() return result def get_next_token(self): """词法分析器的核心方法：获取下一个Token。""" 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, '+') if self.current_char == '-': self.advance() return Token(TokenType.MINUS, '-') if self.current_char == '*': self.advance() return Token(TokenType.MUL, '*') if self.current_char == '/': self.advance() return Token(TokenType.DIV, '/') if self.current_char == '(': self.advance() return Token(TokenType.LPAREN, '(') if self.current_char == ')': self.advance() return Token(TokenType.RPAREN, ')') # 遇到无法识别的字符，报错 self.error() # 输入已耗尽，返回EOF令牌 return Token(TokenType.EOF) ``` > 注意：这个简单的词法分析器没有实现像 `==`、`>=` 这样的多字符运算符，也没有处理负数（`-5`中的负号会被识别为减法运算符）。在实际的编译器中，这些都需要更精细的状态机来处理。但作为入门，理解这个基础版本至关重要。 我们可以写个简单的测试来验证词法分析器是否工作正常： ```python # 在 main.py 中测试 from lexer import Lexer text = "12 + 34 * (56 - 78)" lexer = Lexer(text) tokens = [] while True: token = lexer.get_next_token() tokens.append(token) if token.type == TokenType.EOF: break print(tokens) # 预期输出类似: [Token(INTEGER, '12'), Token(PLUS, '+'), Token(INTEGER, '34'), ...] ``` 词法分析器就像编译器的“眼睛”，它完成了从原始字符到结构化数据的第一步转换。接下来，就需要“大脑”——语法分析器来理解这些Token之间的结构关系了。 ## 3. 语法分析器：构建抽象语法树 语法分析器（Parser）的任务是检查Token序列是否符合预定义的语法规则，并通常以**抽象语法树**的形式构建出程序的层次结构。我们采用**递归下降分析法**，这是一种直观且易于手写实现的自顶向下分析方法。 首先，我们需要为我们的算术表达式定义一个**上下文无关文法**。考虑运算符优先级（乘除高于加减）和结合性（左结合），以及括号的强制分组能力，一个经典的表达式文法如下（使用巴科斯范式表示）： ``` expr : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expr RPAREN ``` 这个文法的含义是： - 一个表达式（`expr`）由一个或多个项（`term`）通过加号或减号连接而成。 - 一个项（`term`）由一个或多个因子（`factor`）通过乘号或除号连接而成。 - 一个因子（`factor`）可以是一个整数，或者一个用括号括起来的完整表达式。 这种分层结构天然地定义了优先级：括号内的`expr`优先级最高，其次是`term`中的乘除，最后是`expr`中的加减。 递归下降分析器会为文法中的每个非终结符（`expr`, `term`, `factor`）编写一个对应的解析函数。这些函数会“消费”Token，并返回对应的语法树节点。我们首先定义AST节点的数据结构： ```python # 在 parser.py 或 ast.py 中定义 class ASTNode: pass class BinOp(ASTNode): """二元操作节点，如 3 + 4""" def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left = left self.op = op # 这是一个Token对象，如 Token(PLUS, '+') self.right = right def __repr__(self): return f'BinOp({self.left}, {self.op.type}, {self.right})' class Num(ASTNode): """数字叶子节点""" def __init__(self, token: Token): self.token = token self.value = int(token.value) # 将字符串转换为整数 def __repr__(self): return f'Num({self.value})' ``` 现在，基于之前的文法，我们可以实现递归下降语法分析器： ```python # parser.py from tokens import TokenType from ast import BinOp, Num class Parser: def __init__(self, lexer): self.lexer = lexer self.current_token = self.lexer.get_next_token() def error(self): raise Exception('Invalid syntax') def eat(self, token_type): """“消费”当前Token，如果类型匹配则获取下一个Token，否则报错。""" if self.current_token.type == token_type: self.current_token = self.lexer.get_next_token() else: self.error() def factor(self): """解析因子：整数或括号表达式。""" token = self.current_token if token.type == TokenType.INTEGER: self.eat(TokenType.INTEGER) return Num(token) elif token.type == TokenType.LPAREN: self.eat(TokenType.LPAREN) node = self.expr() # 递归解析括号内的表达式 self.eat(TokenType.RPAREN) return node else: self.error() def term(self): """解析项：因子之间的乘除运算。""" node = self.factor() while self.current_token.type in (TokenType.MUL, TokenType.DIV): token = self.current_token if token.type == TokenType.MUL: self.eat(TokenType.MUL) else: self.eat(TokenType.DIV) node = BinOp(left=node, op=token, right=self.factor()) return node def expr(self): """解析表达式：项之间的加减运算。""" node = self.term() while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): token = self.current_token if token.type == TokenType.PLUS: self.eat(TokenType.PLUS) else: self.eat(TokenType.MINUS) node = BinOp(left=node, op=token, right=self.term()) return node def parse(self): """解析的入口点，返回整个表达式的AST根节点。""" return self.expr() ``` 这个解析器的精妙之处在于其递归结构完美映射了文法。`expr` 和 `term` 函数中的 `while` 循环处理了 `*` 号（零次或多次）的情况，实现了左结合性。你可以看到，优先级是通过调用顺序实现的：`expr` 调用 `term`，`term` 调用 `factor`，所以 `factor` 最先被求值，优先级最高。 让我们测试一下语法分析器构建的AST： ```python from lexer import Lexer from parser import Parser text = "3 + 5 * 2" lexer = Lexer(text) parser = Parser(lexer) ast = parser.parse() print(ast) # 输出可能类似于: BinOp(Num(3), PLUS, BinOp(Num(5), MUL, Num(2))) # 这清晰地显示了乘法节点(5*2)是加法节点的右子节点，符合乘法的更高优先级。 ``` 生成的AST是一个树形结构，它是后续语义分析的完美输入。语法分析器确保了源代码在结构上是“正确”的，接下来，我们需要让这棵树“活”起来，赋予它计算或生成代码的能力。 ## 4. 语义分析与解释执行 语义分析是编译器前端最后，也是最体现“理解”的一步。它的任务是基于AST，进行上下文相关的检查（如类型检查、变量是否声明等）并生成最终结果（如计算结果、中间代码等）。在我们的算术表达式例子中，语义相对简单，主要是**求值**。我们将实现一个树遍历解释器，直接计算表达式的值。 我们将实现一个访问者模式（Visitor Pattern）来遍历AST。这种方式结构清晰，便于扩展，例如未来可以很容易地修改为生成三地址码而不是直接求值。 ```python # semantic.py 或 interpreter.py from ast import BinOp, Num class NodeVisitor: """访问者基类，为每种AST节点类型提供访问方法。""" def visit(self, node): method_name = 'visit_' + type(node).__name__ visitor = getattr(self, method_name, self.generic_visit) return visitor(node) def generic_visit(self, node): raise Exception(f'No visit_{type(node).__name__} method') class Interpreter(NodeVisitor): """语义分析器/解释器：遍历AST并求值。""" def __init__(self, parser): self.parser = parser def visit_BinOp(self, node): """访问二元操作节点，递归计算左右子树的值，然后执行运算。""" left_val = self.visit(node.left) right_val = self.visit(node.right) op_type = node.op.type if op_type == TokenType.PLUS: return left_val + right_val elif op_type == TokenType.MINUS: return left_val - right_val elif op_type == TokenType.MUL: return left_val * right_val elif op_type == TokenType.DIV: return left_val // right_val # 使用整数除法 else: raise Exception('Invalid operator') def visit_Num(self, node): """访问数字节点，直接返回值。""" return node.value def interpret(self): """解释执行的入口点。""" tree = self.parser.parse() return self.visit(tree) ``` 现在，让我们把词法分析、语法分析和语义分析串联起来，形成一个完整的流程： ```python # main.py import sys from lexer import Lexer from parser import Parser from interpreter import Interpreter def main(): print("Mini Expression Compiler (Type 'exit' to quit)") while True: try: text = input('calc> ') if text.strip().lower() == 'exit': break if not text: continue lexer = Lexer(text) parser = Parser(lexer) interpreter = Interpreter(parser) result = interpreter.interpret() print(result) except Exception as e: print(f"Error: {e}") if __name__ == '__main__': main() ``` 运行这个程序，你就得到了一个支持优先级和括号的命令行计算器！这虽然简单，但完整演绎了编译器前端的三部曲。 然而，直接求值只是语义分析的一种形式。在真正的编译器中，更常见的做法是生成一种介于源代码和目标代码之间的**中间表示**，例如**三地址码**。这种表示更接近机器指令，便于后续的优化和代码生成。作为拓展，我们可以修改访问者，让它不进行计算，而是生成一个三地址指令列表。 ```python # 三地址码生成器的简化示例 class TACGenerator(NodeVisitor): def __init__(self): self.temp_count = 0 # 临时变量计数器，如 t1, t2 self.code = [] # 存储三地址指令 def new_temp(self): self.temp_count += 1 return f't{self.temp_count}' def visit_BinOp(self, node): left_temp = self.visit(node.left) right_temp = self.visit(node.right) result_temp = self.new_temp() op_map = {TokenType.PLUS: '+', TokenType.MINUS: '-', TokenType.MUL: '*', TokenType.DIV: '/'} self.code.append(f'{result_temp} = {left_temp} {op_map[node.op.type]} {right_temp}') return result_temp def visit_Num(self, node): # 数字直接作为操作数 return str(node.value) def generate(self, tree): final_temp = self.visit(tree) self.code.append(f'result = {final_temp}') # 假设最终结果赋给result return self.code # 使用方式 lexer = Lexer("3 + 5 * 2") parser = Parser(lexer) ast = parser.parse() tac_gen = TACGenerator() tac_code = tac_gen.generate(ast) for instr in tac_code: print(instr) # 输出可能为: # t1 = 5 * 2 # t2 = 3 + t1 # result = t2 ``` 从直接求值到生成三地址码，这体现了语义分析的多样性。在实际项目中，你可能会根据需求选择不同的语义动作。我自己的第一个玩具编译器在实现时，就曾卡在如何正确传递属性值上，后来发现画出一棵具体的语法树，然后手动模拟访问者的遍历过程，是调试这类问题最有效的方法。