从零构建编译器：词法分析、语法分析与代码生成实战
1. 项目概述：为什么我们要“手搓”一个编译器？
“手搓编译器”这个词最近在开发者社区里挺火的，听起来像是个深不可测的“屠龙之术”。很多朋友一听到“编译器”就觉得头大，联想到那些庞大复杂的工业级项目，比如GCC、LLVM，觉得那是只有顶尖大牛才能碰的领域。但事实并非如此。编译器，本质上就是一个将一种语言（源代码）翻译成另一种语言（目标代码）的程序。我们日常写的“Hello World”程序能被计算机执行，背后就是编译器的功劳。自己动手从零构建一个简单的编译器，是理解计算机如何“理解”我们代码的最直接、最深刻的方式。
这个过程能帮你打通任督二脉。你会彻底明白，你写下的if、while、int a = 10;这些语句，在计算机眼里究竟是一串怎样的字符流，又是如何被一步步拆解、分析，最终变成可以运行的机器指令或中间代码的。这不仅仅是编译原理课程的知识，它直接提升了你的debug能力（你能从编译器的视角看错误）、设计能力（如何设计一门DSL领域特定语言）以及对编程语言本质的理解。本次我们要构建的，是一个针对简化版算术表达式（比如3 + 5 * (10 - 4)）的编译器，最终将其翻译成一种类似汇编的简单指令序列。麻雀虽小，五脏俱全，词法分析、语法分析、代码生成这三个核心阶段一个不少。
2. 编译器核心三阶段的设计思路拆解
一个典型的编译过程就像一条流水线，源代码从一端进入，经过多个车间的加工，最终从另一端产出目标代码。我们这个小项目主要聚焦三个核心车间。
2.1 词法分析：从字符流到单词序列
想象一下你在读一段英文句子。你不是一个字母一个字母地去理解，而是本能地将字符流分割成一个个有意义的单词（token），比如“apple”、“eat”、“the”。词法分析器（Lexer）干的就是这个活儿。它负责读取源代码的原始字符流（一个个字符），忽略掉空格、换行、制表符这些“空白字符”，然后根据预定义的规则，将字符组合成具有独立意义的最小单元，也就是“词法单元”（Token）。
对于我们的算术表达式编译器，需要识别的Token类型很简单：
- 数字：像
123,45.67这样的整数或浮点数。词法分析器需要把连续的数字字符识别出来，并转换成程序内部可用的数值（整数或浮点数）。 - 运算符：加（
+）、减（-）、乘（*）、除（/）、括号（(,)）。 - 标识符（为后续扩展准备）：比如变量名
x,count。虽然我们第一个版本可能只支持常数运算，但预留识别标识符的能力能让编译器更容易扩展。 - 结束符：一个特殊的Token，用来表示源代码的结束。
词法分析器的输出就是一个Token列表。例如，对于表达式“3 + 5”，词法分析器会产出：[Token(类型: 数字, 值: 3), Token(类型: 加号), Token(类型: 数字, 值: 5), Token(类型: 结束符)]。这个过程消除了无关的空白格式，为下一阶段提供了结构化的输入。
注意：在实现词法分析器时，一个常见的“坑”是向前看（Lookahead）字符的处理。比如遇到字符
>，它可能只是一个大于号，也可能是>=（大于等于）的一部分。我们的算术表达式简单，不需要处理这个。但如果你未来要支持比较运算符，词法分析器就需要在遇到>时，再偷偷看一眼下一个字符是不是=，然后再决定生成一个还是两个Token。这被称为“有限自动机”的思想，是词法分析的理论基础。
2.2 语法分析：构建抽象语法树
拿到单词序列后，下一步是理解句子的结构。光有单词“I”、“eat”、“apple”还不够，我们需要知道是“I eat apple”还是“Apple eat I”（后者显然不合语法）。语法分析器（Parser）的任务就是根据预定义的语法规则（Grammar），检查Token序列的结构是否合法，并构建出一棵“抽象语法树”（Abstract Syntax Tree, AST）。
AST是源代码抽象语法结构的树状表示。树上的每个节点都代表源代码中的一种结构。对于表达式3 + 5 * 2，正确的AST应该反映出乘法的优先级高于加法，而不是从左到右顺序计算。它的AST看起来应该是这样：
(+) / \ 3 (*) / \ 5 2（根节点是加法，左孩子是数字3，右孩子是一个乘法节点，乘法节点的左右孩子分别是数字5和2）。
我们通常使用“递归下降分析法”来实现一个简单的Parser。这种方法非常直观，为语法规则中的每个非终结符（如“表达式”、“项”、“因子”）编写一个对应的解析函数。这些函数会递归地调用彼此，同时“消费”掉对应的Token，最终构建出AST。
语法规则可以用巴科斯范式（BNF）或其扩展EBNF来定义。对于我们这个算术表达式，一个经典的优先级文法可以这样定义：
表达式 -> 项 ( (‘+’ | ‘-’) 项 )* 项 -> 因子 ( (‘*’ | ‘/’) 因子 )* 因子 -> 数字 | ‘(’ 表达式 ‘)’这条规则清晰地定义了优先级：括号()内的表达式优先级最高，其次是乘除法（*,/），最后是加减法（+,-）。Parser会按照这个规则去“匹配”Token流。
2.3 代码生成：从AST到可执行指令
AST建好了，它完美地表达了运算的优先级和结合性。现在我们需要把这棵树“翻译”成目标机器能执行的东西。这就是代码生成器（Code Generator）的工作。目标代码可以是真实的机器码（如x86汇编）、虚拟机字节码（如JVM字节码、Python字节码），或者是一种更简单的中间表示（IR）。
为了让项目足够简单且具有可观测性，我们选择生成一种“堆栈机指令”。这是一种非常经典且易于理解的模型。堆栈机有一个操作数栈，所有运算都围绕这个栈进行。
- PUSH n：将数值 n 压入栈顶。
- ADD：弹出栈顶的两个元素，相加，将结果压回栈顶。
- SUB, MUL, DIV：类似ADD，执行相应的减、乘、除运算。
代码生成的过程通常通过对AST进行后序遍历来实现。后序遍历的顺序是：左子树 -> 右子树 -> 根节点。对于上面的AST例子3 + 5 * 2，后序遍历生成的指令序列会是：
PUSH 3 PUSH 5 PUSH 2 MUL // 执行 5 * 2，结果10入栈 ADD // 执行 3 + 10，结果13入栈指令执行完毕后，栈顶存放的就是整个表达式的计算结果。这种“逆波兰表示法”（后缀表达式）天然适合堆栈机执行，也完美对应了AST的后序遍历。
3. 实战：用Python实现一个表达式编译器
我们选择Python来实现，因为它语法简洁，能让我们更专注于编译逻辑本身。项目将分为三个核心模块：lexer.py,parser.py,codegen.py。
3.1 词法分析器实现详解
首先，我们定义Token类型。用一个枚举类（Enum）或简单的类来定义。
# lexer.py class TokenType: INTEGER = 'INTEGER' PLUS = 'PLUS' MINUS = 'MINUS' MUL = 'MUL' DIV = 'DIV' LPAREN = 'LPAREN' RPAREN = 'RPAREN' EOF = 'EOF' # 表示输入结束 class Token: def __init__(self, type_, value=None): self.type = type_ self.value = value # 对于整数，value存储具体的数值 def __repr__(self): return f'Token({self.type}, {repr(self.value)})'接下来是词法分析器Lexer类。它的核心是一个指针pos，指向当前处理的字符在文本中的位置，以及一个current_char变量保存当前字符。
# lexer.py class Lexer: def __init__(self, text): 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): """移动指针，获取下一个字符""" self.pos += 1 if self.pos > len(self.text) - 1: 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 int(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() return Token(TokenType.EOF)实操心得：在
integer()方法中，我们通过循环累积数字字符，最后一次性转换成整数。这里有个细节：如果我们要支持浮点数，逻辑会复杂一些，需要处理小数点.，并且要区分像3.14和3.（这可能是个错误）这样的情况。初期建议先做好整数，这是最稳定的基石。
3.2 语法分析器与AST构建
AST节点的设计。我们至少需要两种节点：二元运算符节点（如加减乘除）和数字节点。
# ast.py class AST: pass class BinOp(AST): """二元操作符节点，如 3 + 4""" def __init__(self, left, op, right): self.left = left # 左子树节点 self.op = op # 操作符Token (PLUS, MINUS, etc.) self.right = right # 右子树节点 class Num(AST): """数字节点""" def __init__(self, token): self.token = token self.value = token.value递归下降语法分析器。我们会为之前BNF文法中的每个规则（表达式、项、因子）创建一个方法。
# parser.py from lexer import Lexer, 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): """因子 : INTEGER | LPAREN 表达式 RPAREN""" 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): """项 : 因子 ((MUL | DIV) 因子)*""" 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) elif token.type == TokenType.DIV: self.eat(TokenType.DIV) node = BinOp(left=node, op=token, right=self.factor()) return node def expr(self): """表达式 : 项 ((PLUS | MINUS) 项)*""" 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) elif token.type == TokenType.MINUS: self.eat(TokenType.MINUS) node = BinOp(left=node, op=token, right=self.term()) return node def parse(self): """解析入口，返回AST的根节点""" return self.expr()这个Parser的工作流程非常清晰：parse()方法调用expr()，expr()先调用term()获取一个项，然后循环查看后面是不是加减号，如果是，就继续构建更高级的BinOp节点。term()和factor()同理，层层递归，最终正确地处理了运算符优先级和括号。
3.3 代码生成器与解释执行
现在我们有了AST，可以遍历它来生成堆栈机指令。我们定义一个简单的指令集和代码生成器。
# codegen.py class Instruction: def __init__(self, opcode, operand=None): self.opcode = opcode # 'PUSH', 'ADD', 'SUB', 'MUL', 'DIV' self.operand = operand # 对于PUSH指令，operand是数值 def __repr__(self): if self.operand is not None: return f'{self.opcode} {self.operand}' return f'{self.opcode}' class CodeGenerator: def __init__(self): self.instructions = [] def generate(self, node): """根据AST节点生成指令，后序遍历""" if isinstance(node, Num): self.instructions.append(Instruction('PUSH', node.value)) elif isinstance(node, BinOp): # 后序遍历：左 -> 右 -> 根 self.generate(node.left) self.generate(node.right) if node.op.type == TokenType.PLUS: self.instructions.append(Instruction('ADD')) elif node.op.type == TokenType.MINUS: self.instructions.append(Instruction('SUB')) elif node.op.type == TokenType.MUL: self.instructions.append(Instruction('MUL')) elif node.op.type == TokenType.DIV: self.instructions.append(Instruction('DIV')) return self.instructions最后，我们需要一个堆栈机解释器来执行这些指令。
# interpreter.py class StackMachine: def __init__(self, instructions): self.instructions = instructions self.stack = [] def run(self): for instr in self.instructions: if instr.opcode == 'PUSH': self.stack.append(instr.operand) elif instr.opcode in ('ADD', 'SUB', 'MUL', 'DIV'): b = self.stack.pop() a = self.stack.pop() if instr.opcode == 'ADD': self.stack.append(a + b) elif instr.opcode == 'SUB': self.stack.append(a - b) elif instr.opcode == 'MUL': self.stack.append(a * b) elif instr.opcode == 'DIV': self.stack.append(a / b) # 注意除零错误 if self.stack: return self.stack[-1] return None现在，我们可以将整个流程串联起来：
# main.py from lexer import Lexer from parser import Parser from codegen import CodeGenerator from interpreter import StackMachine def compile_and_run(source_code): # 1. 词法分析 lexer = Lexer(source_code) # 2. 语法分析 & 构建AST parser = Parser(lexer) ast = parser.parse() # 3. 代码生成 generator = CodeGenerator() instructions = generator.generate(ast) print("生成的指令:", instructions) # 4. 解释执行 machine = StackMachine(instructions) result = machine.run() return result if __name__ == '__main__': code = "3 + 5 * (10 - 4)" result = compile_and_run(code) print(f"表达式 '{code}' 的计算结果是: {result}")运行这段代码，你会看到输出类似：
生成的指令: [PUSH 3, PUSH 5, PUSH 10, PUSH 4, SUB, MUL, ADD] 表达式 '3 + 5 * (10 - 4)' 的计算结果是: 33这正是我们期望的结果：5 * (10 - 4) = 30，然后3 + 30 = 33。指令序列完美地反映了运算的优先级和顺序。
4. 常见问题、扩展方向与避坑指南
第一个能跑通的编译器虽然令人兴奋，但它非常脆弱。下面是一些你马上就会遇到的问题和进阶思考。
4.1 错误处理：让编译器更健壮
我们之前的代码在遇到错误时（如非法字符、括号不匹配）只是简单地抛出异常。一个友好的编译器应该能给出更有用的错误信息，包括出错位置和原因。
改进思路：
- 在Lexer和Parser中记录行号、列号：在
Lexer初始化时，增加line和column计数器。每次advance()时更新列号，遇到换行符时重置列号并增加行号。当错误发生时，可以报告“第X行第Y列：非法字符‘@’”。 - 定义明确的错误类型：创建
LexerError、ParserError、RuntimeError等自定义异常类，而不是通用的Exception。 - 在Parser中实现错误恢复（中级话题）：当语法分析出错时，不是立即停止，而是尝试跳过一些Token，同步到下一个安全点（如分号、右大括号）继续分析，以便在一次编译中报告多个错误。
4.2 支持更多特性
我们的微型编译器可以按以下路径逐步扩展，每个阶段都是对编译原理不同知识的实践：
- 变量赋值与读取：增加
=运算符和标识符Token。AST需要新增Assign（赋值）和Var（变量）节点。代码生成需要维护一个“符号表”来存储变量名和其值（或内存地址）的映射。执行PUSH时，如果操作数是变量名，就需要去符号表查找值。 - 控制流语句：实现
if-else和while循环。这需要引入布尔表达式、比较运算符（>, <, ==, !=）和标签跳转指令（JUMP_IF_FALSE,JUMP）。AST会新增If和While节点。代码生成会变得复杂，需要处理指令地址的回填（forward referencing）。 - 函数定义与调用：这是质的飞跃。需要处理作用域、参数传递、返回地址和栈帧。你会接触到“调用栈”的概念。代码生成需要生成
CALL、RETURN指令，并在运行时管理活动记录。 - 类型系统：引入不同的数据类型，如整数、浮点数、字符串、布尔值。需要在词法分析、语法分析、语义分析（新增阶段）和代码生成中处处考虑类型信息，并处理类型转换。
4.3 性能优化与进阶思考
当功能完善后，可以考虑优化：
- AST优化：在生成代码前，对AST进行优化。例如，常量折叠（Constant Folding）：将
3 + 5这样的子树直接计算成8，用一个Num(8)节点替换整个BinOp子树。 - 生成真实目标代码：不满足于堆栈机解释执行，可以尝试将AST翻译成LLVM IR，然后利用LLVM工具链生成本地机器码。这是通往工业级编译器的关键一步。
- 使用工具：对于更复杂的语言，手工编写词法分析器和语法分析器会很繁琐。可以学习使用
Lex/Yacc、ANTLR或PLY（Python Lex-Yacc）这样的编译器生成工具。你只需要定义词法规则和语法规则，它们会自动生成分析器代码。这能让你更专注于语言设计和语义分析。
避坑指南：
- 不要过早优化：先从最简单、最直接的实现开始，确保逻辑正确。比如，先让只有加减乘除和括号的编译器稳定运行，再考虑加变量。
- 测试驱动：为每个阶段（Lexer, Parser, CodeGen）编写单元测试。输入一个字符串，断言输出的Token列表、AST结构或指令序列是否符合预期。这能极大提升开发效率和代码质量。
- 可视化调试：在开发Parser时，将生成的AST打印出来（可以写一个递归打印树结构的函数）。肉眼观察AST的形状是否正确，是调试语法规则最有效的方法之一。
- 理解“递归下降”的局限性：我们的递归下降解析器只能处理LL(1)文法。对于一些复杂的语法结构（如某些左递归文法），需要先对文法进行改写。如果遇到解析困难，可能是文法设计的问题，需要复习一下形式语言的相关知识。
构建这个简单的编译器，就像在显微镜下观察编程语言的运行机制。每一个阶段都对应着计算机科学中一个经典的理论模型：词法分析对应有限自动机，语法分析对应下推自动机和上下文无关文法，代码生成则涉及中间表示和代码优化。当你亲手走完这一遍流程，再去看gcc -S输出的汇编代码，或者Python的dis模块反编译的字节码，那种“原来如此”的通透感，是任何书本理论都无法替代的。这个项目最大的价值不在于结果，而在于过程中对程序本质的层层剥离和审视。