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_, valueNone): self.type type_ self.value value # 对于整数value存储具体的数值 def __repr__(self): return fToken({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(leftnode, optoken, rightself.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(leftnode, optoken, rightself.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, operandNone): 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或PLYPython Lex-Yacc这样的编译器生成工具。你只需要定义词法规则和语法规则它们会自动生成分析器代码。这能让你更专注于语言设计和语义分析。避坑指南不要过早优化先从最简单、最直接的实现开始确保逻辑正确。比如先让只有加减乘除和括号的编译器稳定运行再考虑加变量。测试驱动为每个阶段Lexer, Parser, CodeGen编写单元测试。输入一个字符串断言输出的Token列表、AST结构或指令序列是否符合预期。这能极大提升开发效率和代码质量。可视化调试在开发Parser时将生成的AST打印出来可以写一个递归打印树结构的函数。肉眼观察AST的形状是否正确是调试语法规则最有效的方法之一。理解“递归下降”的局限性我们的递归下降解析器只能处理LL(1)文法。对于一些复杂的语法结构如某些左递归文法需要先对文法进行改写。如果遇到解析困难可能是文法设计的问题需要复习一下形式语言的相关知识。构建这个简单的编译器就像在显微镜下观察编程语言的运行机制。每一个阶段都对应着计算机科学中一个经典的理论模型词法分析对应有限自动机语法分析对应下推自动机和上下文无关文法代码生成则涉及中间表示和代码优化。当你亲手走完这一遍流程再去看gcc -S输出的汇编代码或者Python的dis模块反编译的字节码那种“原来如此”的通透感是任何书本理论都无法替代的。这个项目最大的价值不在于结果而在于过程中对程序本质的层层剥离和审视。
从零构建编译器：词法分析、语法分析与代码生成实战
发布时间：2026/6/18 10:35:37
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_, valueNone): self.type type_ self.value value # 对于整数value存储具体的数值 def __repr__(self): return fToken({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(leftnode, optoken, rightself.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(leftnode, optoken, rightself.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, operandNone): 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或PLYPython Lex-Yacc这样的编译器生成工具。你只需要定义词法规则和语法规则它们会自动生成分析器代码。这能让你更专注于语言设计和语义分析。避坑指南不要过早优化先从最简单、最直接的实现开始确保逻辑正确。比如先让只有加减乘除和括号的编译器稳定运行再考虑加变量。测试驱动为每个阶段Lexer, Parser, CodeGen编写单元测试。输入一个字符串断言输出的Token列表、AST结构或指令序列是否符合预期。这能极大提升开发效率和代码质量。可视化调试在开发Parser时将生成的AST打印出来可以写一个递归打印树结构的函数。肉眼观察AST的形状是否正确是调试语法规则最有效的方法之一。理解“递归下降”的局限性我们的递归下降解析器只能处理LL(1)文法。对于一些复杂的语法结构如某些左递归文法需要先对文法进行改写。如果遇到解析困难可能是文法设计的问题需要复习一下形式语言的相关知识。构建这个简单的编译器就像在显微镜下观察编程语言的运行机制。每一个阶段都对应着计算机科学中一个经典的理论模型词法分析对应有限自动机语法分析对应下推自动机和上下文无关文法代码生成则涉及中间表示和代码优化。当你亲手走完这一遍流程再去看gcc -S输出的汇编代码或者Python的dis模块反编译的字节码那种“原来如此”的通透感是任何书本理论都无法替代的。这个项目最大的价值不在于结果而在于过程中对程序本质的层层剥离和审视。
