1. 项目缘起为什么我们要“手搓”一个编译器最近在技术社区里看到不少朋友在讨论“手搓编译器”这个话题。有人觉得这是屠龙之技离日常开发太远也有人跃跃欲试但被“编译原理”这座大山吓退。作为一个写过几个玩具编译器也深度使用过各种工业级编译器GCC、Clang、MSVC的老码农我想说自己动手从零构建一个简单的编译器可能是理解计算机如何“理解”你写的代码最直接、也最深刻的方式。这绝不是为了造轮子。当你为一个嵌入式平台比如你提到的51单片机找不到合适的编译器而发愁时当你使用MATLAB/Simulink的代码生成功能Stateflow、Embedded Coder却对生成的代码效率不满意想介入优化时当你好奇AI代码生成工具如Codex底层是不是某种“编译器”时甚至当你只是单纯想搞懂为什么Python解释器执行print(“hello”)而C语言需要先gcc -o hello hello.c时——编译技术的身影无处不在。它连接了高级的人类思维编程语言和冰冷的机器指令是这个数字世界的基石翻译官。所以这篇长文我想带你抛开那些厚重的教科书用一个下午的时间真正“手搓”出一个能工作的简单编译器。我们将实现一个超级精简的语言就称它为TinyLang吧它只支持整数加减乘除、变量赋值和打印。但麻雀虽小五脏俱全词法分析、语法分析、代码生成这三个核心阶段一个不少。最终我们的编译器将能把TinyLang代码翻译成类似汇编的中间指令甚至可以直接运行。你会看到编译器不是魔法而是一系列精巧字符串处理和树形结构转换的工程组合。2. 编译器全景图三个阶段与我们的TinyLang设计在动手写代码之前我们必须像建筑师看蓝图一样看清编译器的全貌。一个典型的编译过程就像一条精密的流水线词法分析Lexical Analysis把源代码字符串拆分成一个个有意义的“单词”称为“词法单元”或“Token”。比如面对a 10 b * 2;这串字符词法分析器会识别出a标识符、赋值运算符、10整数常量、加法运算符、b标识符、*乘法运算符、2整数常量、;分号。它不关心语法对不对只负责“认字”。语法分析Syntax Analysis把一维的Token序列根据预定义的语法规则组装成一棵多维的“语法树”AST。这棵树体现了代码的层次结构。例如它会知道*的优先级比高所以b * 2会先结合成一个子树然后再与10相加。这一步会检查语法是否正确比如括号是否匹配、语句结构是否合规。代码生成Code Generation遍历语法树为每个语法结构生成等价的目标代码可以是汇编、字节码甚至是另一种高级语言。这是从“理解”到“产出”的关键一步。我们的TinyLang语言就围绕这三个阶段来设计。为了极致简化我们约定数据类型只有整数int。语句只有赋值语句如x 10 5;和打印语句如print x;。表达式支持加减乘除,-,*,/和整数常量、变量标识符。程序结构一个程序就是一系列语句顺序执行。一个TinyLang的示例程序如下a 5; b 10; c a b * 2; print c;我们的编译器目标是将它转化为可以顺序执行的一系列低级指令。为了最直观地展示我们生成一种非常简单的“栈式虚拟机指令”它易于理解和实现PUSH将一个整数常量压入栈。LOAD将某个变量的值压入栈。STORE将栈顶的值弹出存入某个变量。ADD,SUB,MUL,DIV弹出栈顶两个元素进行运算将结果压回栈顶。PRINT弹出栈顶元素并打印。那么上面示例程序的目标代码可能就是PUSH 5 STORE a PUSH 10 STORE b LOAD a PUSH 2 LOAD b MUL ADD STORE c LOAD c PRINT有了这个全景图和目标我们就可以分步拆解了。3. 第一阶段词法分析器——让机器“认字”词法分析器也叫扫描器Scanner它的核心工作就是“切词”。我们不需要一次性写出复杂的正则表达式引擎对于TinyLang我们可以逐个字符扫描根据当前字符的特征来决定如何切分。3.1 Token的定义首先我们要定义TinyLang中有哪些类型的“单词”。我们用Python的枚举类来清晰定义from enum import Enum class TokenType(Enum): # 关键字 PRINT PRINT # 标识符 (变量名) IDENTIFIER IDENTIFIER # 字面量 INTEGER INTEGER # 运算符 ASSIGN # 赋值 PLUS MINUS - MUL * DIV / # 分隔符 SEMICOLON ; # 文件结束 EOF EOF同时我们需要一个Token类来记录每个“单词”的具体信息它的类型TokenType和它的字面值lexeme对于整数常量就是具体的数字字符串对于标识符就是变量名字符串。class Token: def __init__(self, type_: TokenType, lexeme: str): self.type type_ self.lexeme lexeme def __repr__(self): return fToken({self.type}, {repr(self.lexeme)})3.2 扫描器的实现逻辑接下来是实现扫描器Lexer类。它的核心是一个pos指针指向源代码字符串的当前位置以及一个next_token()方法每次调用就返回下一个Token。注意在实现中跳过空白字符空格、换行、制表符是第一步也是最容易忘记的一步。很多初学者写的词法分析器第一个Bug就是无法处理空格。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 _advance(self): 移动pos指针更新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 int(result) def _identifier(self): 读取一个完整的标识符变量名或关键字 result while self.current_char is not None and (self.current_char.isalnum() or self.current_char _): result self.current_char self._advance() # 检查是否是关键字 if result print: return Token(TokenType.PRINT, result) return Token(TokenType.IDENTIFIER, result) def 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(): num self._integer() return Token(TokenType.INTEGER, str(num)) if self.current_char.isalpha() or self.current_char _: return self._identifier() # 处理单字符运算符和分隔符 single_char_tokens { : TokenType.ASSIGN, : TokenType.PLUS, -: TokenType.MINUS, *: TokenType.MUL, /: TokenType.DIV, ;: TokenType.SEMICOLON, } if self.current_char in single_char_tokens: char self.current_char self._advance() return Token(single_char_tokens[char], char) # 如果遇到无法识别的字符抛出错误 raise Exception(fLexer error: invalid character {self.current_char}) # 源代码已读完返回EOF return Token(TokenType.EOF, )3.3 测试与踩坑点写完后立刻用一个小程序测试一下code a 5 3; print result; lexer Lexer(code) tokens [] while True: token lexer.next_token() tokens.append(token) if token.type TokenType.EOF: break print(tokens)输出应该类似于[Token(TokenType.IDENTIFIER, a), Token(TokenType.ASSIGN, ), Token(TokenType.INTEGER, 5), Token(TokenType.PLUS, ), Token(TokenType.INTEGER, 3), Token(TokenType.SEMICOLON, ;), Token(TokenType.PRINT, print), Token(TokenType.IDENTIFIER, result), Token(TokenType.SEMICOLON, ;), Token(TokenType.EOF, )]实操心得词法分析器看似简单但边界条件很多。一个常见的坑是多字符运算符如,。我们的TinyLang没有设计这些但如果要支持在next_token中看到第一个字符是时需要再peek预看下一个字符是不是然后再决定生成ASSIGN还是EQ等于Token。这就是为什么很多工业级词法分析器如GCC、Clang的lexer部分代码非常复杂的原因——它们要处理各种语言特性、宏、注释、跨行字符串等。4. 第二阶段语法分析器——构建理解的“树”词法分析器给了我们一堆单词现在需要按照“语法”把这堆单词组成有意义的句子。语法分析器Parser就是干这个的。我们采用“递归下降”的方法这是一种直观的、手写Parser的常用方法它的核心思想是为每一种语法结构如语句、表达式编写一个解析函数这些函数可能会递归地调用彼此。4.1 定义抽象语法树AST节点在解析之前要先定义好AST节点的数据结构。AST是编译器内部表示程序结构的核心数据结构。class ASTNode: pass # 表达式基类 class Expr(ASTNode): pass class Integer(Expr): 整数常量如 5 def __init__(self, value: int): self.value value class Identifier(Expr): 变量标识符如 a def __init__(self, name: str): self.name name class BinOp(Expr): 二元运算如 a b def __init__(self, left: Expr, op: TokenType, right: Expr): self.left left self.op op # 会是 PLUS, MINUS, MUL, DIV 之一 self.right right # 语句基类 class Stmt(ASTNode): pass class AssignStmt(Stmt): 赋值语句如 a 10; def __init__(self, identifier: Identifier, expr: Expr): self.identifier identifier self.expr expr class PrintStmt(Stmt): 打印语句如 print a; def __init__(self, expr: Expr): self.expr expr # 程序根节点一系列语句 class Program(ASTNode): def __init__(self, statements: list[Stmt]): self.statements statements4.2 递归下降解析器的实现我们的Parser将消费Lexer产生的Token流。关键点在于处理运算符优先级。对于表达式a b * c我们需要让*比更早结合即优先级更高。常用的方法是定义多层解析函数parse_expression(): 解析赋值表达式我们这里没有直接到下一层。parse_additive(): 处理和-。parse_multiplicative(): 处理*和/。parse_primary(): 处理最基本的元素整数、标识符、括号表达式。parse_multiplicative会先调用parse_primary获取左边的操作数然后看后面是不是*或/如果是就继续获取右边的操作数构建BinOp节点。parse_additive同理但它会调用parse_multiplicative作为它的左边操作数这样自然就实现了*//的优先级高于/-。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.next_token() def _eat(self, token_type: TokenType): 消费当前Token并获取下一个Token。如果类型不匹配则报错。 if self.current_token.type token_type: self.current_token self.lexer.next_token() else: raise Exception(fSyntax error: expected {token_type}, got {self.current_token}) def parse_primary(self) - Expr: 解析基本表达式整数或标识符 token self.current_token if token.type TokenType.INTEGER: self._eat(TokenType.INTEGER) return Integer(int(token.lexeme)) elif token.type TokenType.IDENTIFIER: self._eat(TokenType.IDENTIFIER) return Identifier(token.lexeme) else: raise Exception(fSyntax error in primary expression: {token}) def parse_multiplicative(self) - Expr: 解析乘除法表达式 node self.parse_primary() while self.current_token.type in (TokenType.MUL, TokenType.DIV): op self.current_token.type self._eat(op) right self.parse_primary() # 注意这里简化了实际应该继续调用parse_primary node BinOp(leftnode, opop, rightright) return node def parse_additive(self) - Expr: 解析加减法表达式 node self.parse_multiplicative() # 乘除法优先级更高 while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): op self.current_token.type self._eat(op) right self.parse_multiplicative() node BinOp(leftnode, opop, rightright) return node def parse_expression(self) - Expr: 解析表达式目前就是加减乘除表达式 return self.parse_additive() def parse_statement(self) - Stmt: 解析单条语句赋值或打印 token self.current_token if token.type TokenType.PRINT: self._eat(TokenType.PRINT) expr self.parse_expression() stmt PrintStmt(expr) elif token.type TokenType.IDENTIFIER: ident Identifier(token.lexeme) self._eat(TokenType.IDENTIFIER) self._eat(TokenType.ASSIGN) expr self.parse_expression() stmt AssignStmt(ident, expr) else: raise Exception(fSyntax error: unexpected token {token} at start of statement) # 语句以分号结尾 self._eat(TokenType.SEMICOLON) return stmt def parse_program(self) - Program: 解析整个程序多条语句直到文件结束 statements [] while self.current_token.type ! TokenType.EOF: stmt self.parse_statement() statements.append(stmt) return Program(statements)4.3 验证AST的构建让我们用之前的示例代码来测试Parsercode a 5; b 10; c a b * 2; print c; lexer Lexer(code) parser Parser(lexer) ast parser.parse_program() # 简单打印一下AST结构 def print_ast(node, indent0): prefix * indent if isinstance(node, Program): print(f{prefix}Program:) for stmt in node.statements: print_ast(stmt, indent1) elif isinstance(node, AssignStmt): print(f{prefix}AssignStmt:) print_ast(node.identifier, indent1) print(f{prefix} to:) print_ast(node.expr, indent2) elif isinstance(node, PrintStmt): print(f{prefix}PrintStmt:) print_ast(node.expr, indent1) elif isinstance(node, BinOp): print(f{prefix}BinOp({node.op.value}):) print_ast(node.left, indent1) print_ast(node.right, indent1) elif isinstance(node, Integer): print(f{prefix}Integer({node.value})) elif isinstance(node, Identifier): print(f{prefix}Identifier({node.name})) else: print(f{prefix}{node}) print_ast(ast)输出应该能清晰地展示出树形结构特别是b * 2这个子树会作为的右孩子正确反映了运算优先级。踩坑实录递归下降解析器最怕左递归文法。例如如果我们把加法规则写成expr expr term那么在parse_expression函数里它一上来就会无休止地调用自己导致栈溢出。所以我们必须通过改写文法变成expr term ( term)*来消除左递归这正是我们parse_additive函数里用while循环来实现的模式。这是手写Parser时必须掌握的一个关键技巧。5. 第三阶段代码生成器——从树到指令现在我们有了结构清晰的AST最后一步就是遍历这棵树为每个节点生成相应的目标代码。我们将生成之前设计的那种简单的栈式指令。5.1 指令集与代码生成器设计我们定义一个简单的指令列表作为输出。代码生成器CodeGen本质上是一个AST的访问者Visitor它根据节点类型执行不同的动作。class Instruction: def __init__(self, opcode: str, operandNone): self.opcode opcode self.operand operand # 可能是整数或字符串变量名 def __repr__(self): if self.operand is not None: return f{self.opcode} {self.operand} else: return self.opcode class CodeGenerator: def __init__(self): self.instructions [] # 符号表记录变量名和它在“内存”中的位置这里简化用变量名直接作为引用 # 更复杂的实现会分配内存地址或寄存器编号。 self.symbol_table set() def emit(self, opcode: str, operandNone): 生成一条指令 self.instructions.append(Instruction(opcode, operand)) def visit(self, node: ASTNode): 分发访问方法 method_name visit_ node.__class__.__name__ visitor getattr(self, method_name, self.generic_visit) return visitor(node) def generic_visit(self, node): raise Exception(fNo visit method for {node.__class__.__name__}) def visit_Program(self, node: Program): for stmt in node.statements: self.visit(stmt) def visit_AssignStmt(self, node: AssignStmt): # 1. 生成计算表达式值的指令 self.visit(node.expr) # 2. 生成存储指令将栈顶值存入变量 var_name node.identifier.name self.emit(STORE, var_name) self.symbol_table.add(var_name) # 记录变量已定义 def visit_PrintStmt(self, node: PrintStmt): # 1. 生成计算表达式值的指令 self.visit(node.expr) # 2. 生成打印指令 self.emit(PRINT) def visit_BinOp(self, node: BinOp): # 后序遍历先左子树再右子树最后操作符 self.visit(node.left) self.visit(node.right) # 根据操作符生成对应的运算指令 op_map { TokenType.PLUS: ADD, TokenType.MINUS: SUB, TokenType.MUL: MUL, TokenType.DIV: DIV, } self.emit(op_map[node.op]) def visit_Integer(self, node: Integer): # 生成加载常量指令 self.emit(PUSH, node.value) def visit_Identifier(self, node: Identifier): # 生成加载变量指令 if node.name not in self.symbol_table: # 这里简化处理实际编译器前端应做“使用前定义”检查 pass self.emit(LOAD, node.name) def generate(self, ast: Program) - list[Instruction]: self.visit(ast) return self.instructions5.2 生成指令并模拟执行让我们把前几个阶段的成果串联起来并写一个简单的虚拟机来执行生成的指令验证结果。# 1. 源代码 source_code a 5; b 10; c a b * 2; print c; # 2. 词法分析 lexer Lexer(source_code) # 3. 语法分析 parser Parser(lexer) ast parser.parse_program() # 4. 代码生成 codegen CodeGenerator() instructions codegen.generate(ast) print(Generated Instructions:) for instr in instructions: print(instr) # 5. 一个极简的栈式虚拟机来执行这些指令 print(\n--- Execution Output ---) stack [] variables {} # 模拟内存 for instr in instructions: if instr.opcode PUSH: stack.append(instr.operand) elif instr.opcode LOAD: if instr.operand in variables: stack.append(variables[instr.operand]) else: raise Exception(fUndefined variable: {instr.operand}) elif instr.opcode STORE: value stack.pop() variables[instr.operand] value elif instr.opcode ADD: b stack.pop() a stack.pop() stack.append(a b) elif instr.opcode SUB: b stack.pop() a stack.pop() stack.append(a - b) elif instr.opcode MUL: b stack.pop() a stack.pop() stack.append(a * b) elif instr.opcode DIV: b stack.pop() a stack.pop() stack.append(a // b) # 整数除法 elif instr.opcode PRINT: value stack.pop() print(value) else: raise Exception(fUnknown instruction: {instr.opcode}) print(fFinal variables: {variables})运行这段代码你会在控制台看到生成的指令序列以及最终的打印输出25因为5 10 * 2 25。恭喜你一个真正能工作的微型编译器诞生了核心原理与扩展思考我们生成的是一种基于栈的中间表示IR。现代编译器如Java的JVM、.NET的CLR都使用栈式或寄存器式虚拟机作为中间层。它的好处是与具体机器架构无关便于优化和移植。如果你想挑战更接近真实机器的代码可以尝试生成x86或ARM的汇编片段那需要了解调用约定、寄存器分配等更复杂的概念这就是GCC、LLVM等编译器后端Backend的核心工作。6. 从玩具到工具编译器工程的深化路径我们成功“手搓”了一个编译器核心流程但它离实用还有光年之遥。下面是一些关键的深化方向每一个都对应着编译原理中的一个重要模块1. 增强前端能力类型系统为TinyLang加入浮点数、布尔值、字符串类型。这需要在词法分析时区分不同字面量在语法分析树中记录类型信息并在代码生成时选择不同的指令如FADD用于浮点加。控制流实现if-else条件判断和while循环。这会让AST变得复杂需要IfStmt,WhileStmt节点代码生成则涉及“跳转”指令JMP,JZ跳转到指定指令地址和标签Label的管理。函数定义与调用这是质的飞跃。需要引入作用域管理、栈帧概念、参数传递、返回值处理。你会深刻理解“调用栈”是怎么回事。2. 引入语义分析Semantic Analysis这是介于语法分析和代码生成之间往往被初学者忽略但至关重要的阶段。它检查语法正确但无意义的代码。类型检查int a “hello”;语法可能没问题如果语法支持字符串但语义错误。符号表管理更完善地记录每个标识符的类型、作用域。检查变量是否重复定义、是否在使用前已声明或定义。静态检查比如break语句是否在循环内函数返回值类型是否匹配等。3. 优化中间表示直接在AST上做优化比较困难。通常编译器会先将AST转换为一种更利于优化的中间表示IR比如三地址码、静态单赋值形式SSA。在我们的栈式指令上就可以做简单的优化常量折叠在编译时直接计算a 5 3 * 2生成PUSH 11而不是PUSH 5; PUSH 3; PUSH 2; MUL; ADD。窥孔优化匹配短小的、低效的指令序列替换为更高效的序列。4. 面向真实机器的代码生成要生成x86/ARM汇编你需要指令选择将IR操作映射到目标机器指令。比如我们的ADDIR在x86上可能是add eax, ebx。寄存器分配这是后端最复杂的问题之一。机器寄存器有限需要智能地把大量的虚拟变量分配到有限的物理寄存器上放不下的就“溢出”到内存。涉及图着色等算法。指令调度重排指令顺序以充分利用CPU的流水线避免数据依赖带来的停顿。5. 使用编译器构造工具工业编译器很少完全手写词法语法分析。Lex/Flex Yacc/Bison经典的词法/语法分析器生成器。你写规则正则表达式和上下文无关文法它们帮你生成C代码。很多老牌编译器如GCC早期版本用它。ANTLR更现代、强大的解析器生成器支持多种目标语言Java, Python, C等适合构建复杂的领域特定语言DSL。LLVM这不是一个工具而是一个编译器基础设施。你可以用任何语言写编译器前端生成LLVM IR然后LLVM负责所有后端优化和代码生成支持多种CPU和GPU。这是目前最主流的学术和工业选择。回过头看我们“手搓”的过程正是理解这些庞大工具和框架内在逻辑的最佳途径。当你再使用GCC的-O2优化选项或在MATLAB里点击“生成代码”按钮或在网上搜索“MSVC编译器离线安装包”时你看到的将不再是一个黑盒而是一个由词法分析、语法分析、语义分析、优化、代码生成等精密模块协同工作的复杂系统。这份理解是通往更高级的软件系统设计、性能优化和语言工程领域的宝贵门票。
从零手搓编译器：词法分析、语法分析与代码生成实战
1. 项目缘起为什么我们要“手搓”一个编译器最近在技术社区里看到不少朋友在讨论“手搓编译器”这个话题。有人觉得这是屠龙之技离日常开发太远也有人跃跃欲试但被“编译原理”这座大山吓退。作为一个写过几个玩具编译器也深度使用过各种工业级编译器GCC、Clang、MSVC的老码农我想说自己动手从零构建一个简单的编译器可能是理解计算机如何“理解”你写的代码最直接、也最深刻的方式。这绝不是为了造轮子。当你为一个嵌入式平台比如你提到的51单片机找不到合适的编译器而发愁时当你使用MATLAB/Simulink的代码生成功能Stateflow、Embedded Coder却对生成的代码效率不满意想介入优化时当你好奇AI代码生成工具如Codex底层是不是某种“编译器”时甚至当你只是单纯想搞懂为什么Python解释器执行print(“hello”)而C语言需要先gcc -o hello hello.c时——编译技术的身影无处不在。它连接了高级的人类思维编程语言和冰冷的机器指令是这个数字世界的基石翻译官。所以这篇长文我想带你抛开那些厚重的教科书用一个下午的时间真正“手搓”出一个能工作的简单编译器。我们将实现一个超级精简的语言就称它为TinyLang吧它只支持整数加减乘除、变量赋值和打印。但麻雀虽小五脏俱全词法分析、语法分析、代码生成这三个核心阶段一个不少。最终我们的编译器将能把TinyLang代码翻译成类似汇编的中间指令甚至可以直接运行。你会看到编译器不是魔法而是一系列精巧字符串处理和树形结构转换的工程组合。2. 编译器全景图三个阶段与我们的TinyLang设计在动手写代码之前我们必须像建筑师看蓝图一样看清编译器的全貌。一个典型的编译过程就像一条精密的流水线词法分析Lexical Analysis把源代码字符串拆分成一个个有意义的“单词”称为“词法单元”或“Token”。比如面对a 10 b * 2;这串字符词法分析器会识别出a标识符、赋值运算符、10整数常量、加法运算符、b标识符、*乘法运算符、2整数常量、;分号。它不关心语法对不对只负责“认字”。语法分析Syntax Analysis把一维的Token序列根据预定义的语法规则组装成一棵多维的“语法树”AST。这棵树体现了代码的层次结构。例如它会知道*的优先级比高所以b * 2会先结合成一个子树然后再与10相加。这一步会检查语法是否正确比如括号是否匹配、语句结构是否合规。代码生成Code Generation遍历语法树为每个语法结构生成等价的目标代码可以是汇编、字节码甚至是另一种高级语言。这是从“理解”到“产出”的关键一步。我们的TinyLang语言就围绕这三个阶段来设计。为了极致简化我们约定数据类型只有整数int。语句只有赋值语句如x 10 5;和打印语句如print x;。表达式支持加减乘除,-,*,/和整数常量、变量标识符。程序结构一个程序就是一系列语句顺序执行。一个TinyLang的示例程序如下a 5; b 10; c a b * 2; print c;我们的编译器目标是将它转化为可以顺序执行的一系列低级指令。为了最直观地展示我们生成一种非常简单的“栈式虚拟机指令”它易于理解和实现PUSH将一个整数常量压入栈。LOAD将某个变量的值压入栈。STORE将栈顶的值弹出存入某个变量。ADD,SUB,MUL,DIV弹出栈顶两个元素进行运算将结果压回栈顶。PRINT弹出栈顶元素并打印。那么上面示例程序的目标代码可能就是PUSH 5 STORE a PUSH 10 STORE b LOAD a PUSH 2 LOAD b MUL ADD STORE c LOAD c PRINT有了这个全景图和目标我们就可以分步拆解了。3. 第一阶段词法分析器——让机器“认字”词法分析器也叫扫描器Scanner它的核心工作就是“切词”。我们不需要一次性写出复杂的正则表达式引擎对于TinyLang我们可以逐个字符扫描根据当前字符的特征来决定如何切分。3.1 Token的定义首先我们要定义TinyLang中有哪些类型的“单词”。我们用Python的枚举类来清晰定义from enum import Enum class TokenType(Enum): # 关键字 PRINT PRINT # 标识符 (变量名) IDENTIFIER IDENTIFIER # 字面量 INTEGER INTEGER # 运算符 ASSIGN # 赋值 PLUS MINUS - MUL * DIV / # 分隔符 SEMICOLON ; # 文件结束 EOF EOF同时我们需要一个Token类来记录每个“单词”的具体信息它的类型TokenType和它的字面值lexeme对于整数常量就是具体的数字字符串对于标识符就是变量名字符串。class Token: def __init__(self, type_: TokenType, lexeme: str): self.type type_ self.lexeme lexeme def __repr__(self): return fToken({self.type}, {repr(self.lexeme)})3.2 扫描器的实现逻辑接下来是实现扫描器Lexer类。它的核心是一个pos指针指向源代码字符串的当前位置以及一个next_token()方法每次调用就返回下一个Token。注意在实现中跳过空白字符空格、换行、制表符是第一步也是最容易忘记的一步。很多初学者写的词法分析器第一个Bug就是无法处理空格。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 _advance(self): 移动pos指针更新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 int(result) def _identifier(self): 读取一个完整的标识符变量名或关键字 result while self.current_char is not None and (self.current_char.isalnum() or self.current_char _): result self.current_char self._advance() # 检查是否是关键字 if result print: return Token(TokenType.PRINT, result) return Token(TokenType.IDENTIFIER, result) def 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(): num self._integer() return Token(TokenType.INTEGER, str(num)) if self.current_char.isalpha() or self.current_char _: return self._identifier() # 处理单字符运算符和分隔符 single_char_tokens { : TokenType.ASSIGN, : TokenType.PLUS, -: TokenType.MINUS, *: TokenType.MUL, /: TokenType.DIV, ;: TokenType.SEMICOLON, } if self.current_char in single_char_tokens: char self.current_char self._advance() return Token(single_char_tokens[char], char) # 如果遇到无法识别的字符抛出错误 raise Exception(fLexer error: invalid character {self.current_char}) # 源代码已读完返回EOF return Token(TokenType.EOF, )3.3 测试与踩坑点写完后立刻用一个小程序测试一下code a 5 3; print result; lexer Lexer(code) tokens [] while True: token lexer.next_token() tokens.append(token) if token.type TokenType.EOF: break print(tokens)输出应该类似于[Token(TokenType.IDENTIFIER, a), Token(TokenType.ASSIGN, ), Token(TokenType.INTEGER, 5), Token(TokenType.PLUS, ), Token(TokenType.INTEGER, 3), Token(TokenType.SEMICOLON, ;), Token(TokenType.PRINT, print), Token(TokenType.IDENTIFIER, result), Token(TokenType.SEMICOLON, ;), Token(TokenType.EOF, )]实操心得词法分析器看似简单但边界条件很多。一个常见的坑是多字符运算符如,。我们的TinyLang没有设计这些但如果要支持在next_token中看到第一个字符是时需要再peek预看下一个字符是不是然后再决定生成ASSIGN还是EQ等于Token。这就是为什么很多工业级词法分析器如GCC、Clang的lexer部分代码非常复杂的原因——它们要处理各种语言特性、宏、注释、跨行字符串等。4. 第二阶段语法分析器——构建理解的“树”词法分析器给了我们一堆单词现在需要按照“语法”把这堆单词组成有意义的句子。语法分析器Parser就是干这个的。我们采用“递归下降”的方法这是一种直观的、手写Parser的常用方法它的核心思想是为每一种语法结构如语句、表达式编写一个解析函数这些函数可能会递归地调用彼此。4.1 定义抽象语法树AST节点在解析之前要先定义好AST节点的数据结构。AST是编译器内部表示程序结构的核心数据结构。class ASTNode: pass # 表达式基类 class Expr(ASTNode): pass class Integer(Expr): 整数常量如 5 def __init__(self, value: int): self.value value class Identifier(Expr): 变量标识符如 a def __init__(self, name: str): self.name name class BinOp(Expr): 二元运算如 a b def __init__(self, left: Expr, op: TokenType, right: Expr): self.left left self.op op # 会是 PLUS, MINUS, MUL, DIV 之一 self.right right # 语句基类 class Stmt(ASTNode): pass class AssignStmt(Stmt): 赋值语句如 a 10; def __init__(self, identifier: Identifier, expr: Expr): self.identifier identifier self.expr expr class PrintStmt(Stmt): 打印语句如 print a; def __init__(self, expr: Expr): self.expr expr # 程序根节点一系列语句 class Program(ASTNode): def __init__(self, statements: list[Stmt]): self.statements statements4.2 递归下降解析器的实现我们的Parser将消费Lexer产生的Token流。关键点在于处理运算符优先级。对于表达式a b * c我们需要让*比更早结合即优先级更高。常用的方法是定义多层解析函数parse_expression(): 解析赋值表达式我们这里没有直接到下一层。parse_additive(): 处理和-。parse_multiplicative(): 处理*和/。parse_primary(): 处理最基本的元素整数、标识符、括号表达式。parse_multiplicative会先调用parse_primary获取左边的操作数然后看后面是不是*或/如果是就继续获取右边的操作数构建BinOp节点。parse_additive同理但它会调用parse_multiplicative作为它的左边操作数这样自然就实现了*//的优先级高于/-。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.next_token() def _eat(self, token_type: TokenType): 消费当前Token并获取下一个Token。如果类型不匹配则报错。 if self.current_token.type token_type: self.current_token self.lexer.next_token() else: raise Exception(fSyntax error: expected {token_type}, got {self.current_token}) def parse_primary(self) - Expr: 解析基本表达式整数或标识符 token self.current_token if token.type TokenType.INTEGER: self._eat(TokenType.INTEGER) return Integer(int(token.lexeme)) elif token.type TokenType.IDENTIFIER: self._eat(TokenType.IDENTIFIER) return Identifier(token.lexeme) else: raise Exception(fSyntax error in primary expression: {token}) def parse_multiplicative(self) - Expr: 解析乘除法表达式 node self.parse_primary() while self.current_token.type in (TokenType.MUL, TokenType.DIV): op self.current_token.type self._eat(op) right self.parse_primary() # 注意这里简化了实际应该继续调用parse_primary node BinOp(leftnode, opop, rightright) return node def parse_additive(self) - Expr: 解析加减法表达式 node self.parse_multiplicative() # 乘除法优先级更高 while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): op self.current_token.type self._eat(op) right self.parse_multiplicative() node BinOp(leftnode, opop, rightright) return node def parse_expression(self) - Expr: 解析表达式目前就是加减乘除表达式 return self.parse_additive() def parse_statement(self) - Stmt: 解析单条语句赋值或打印 token self.current_token if token.type TokenType.PRINT: self._eat(TokenType.PRINT) expr self.parse_expression() stmt PrintStmt(expr) elif token.type TokenType.IDENTIFIER: ident Identifier(token.lexeme) self._eat(TokenType.IDENTIFIER) self._eat(TokenType.ASSIGN) expr self.parse_expression() stmt AssignStmt(ident, expr) else: raise Exception(fSyntax error: unexpected token {token} at start of statement) # 语句以分号结尾 self._eat(TokenType.SEMICOLON) return stmt def parse_program(self) - Program: 解析整个程序多条语句直到文件结束 statements [] while self.current_token.type ! TokenType.EOF: stmt self.parse_statement() statements.append(stmt) return Program(statements)4.3 验证AST的构建让我们用之前的示例代码来测试Parsercode a 5; b 10; c a b * 2; print c; lexer Lexer(code) parser Parser(lexer) ast parser.parse_program() # 简单打印一下AST结构 def print_ast(node, indent0): prefix * indent if isinstance(node, Program): print(f{prefix}Program:) for stmt in node.statements: print_ast(stmt, indent1) elif isinstance(node, AssignStmt): print(f{prefix}AssignStmt:) print_ast(node.identifier, indent1) print(f{prefix} to:) print_ast(node.expr, indent2) elif isinstance(node, PrintStmt): print(f{prefix}PrintStmt:) print_ast(node.expr, indent1) elif isinstance(node, BinOp): print(f{prefix}BinOp({node.op.value}):) print_ast(node.left, indent1) print_ast(node.right, indent1) elif isinstance(node, Integer): print(f{prefix}Integer({node.value})) elif isinstance(node, Identifier): print(f{prefix}Identifier({node.name})) else: print(f{prefix}{node}) print_ast(ast)输出应该能清晰地展示出树形结构特别是b * 2这个子树会作为的右孩子正确反映了运算优先级。踩坑实录递归下降解析器最怕左递归文法。例如如果我们把加法规则写成expr expr term那么在parse_expression函数里它一上来就会无休止地调用自己导致栈溢出。所以我们必须通过改写文法变成expr term ( term)*来消除左递归这正是我们parse_additive函数里用while循环来实现的模式。这是手写Parser时必须掌握的一个关键技巧。5. 第三阶段代码生成器——从树到指令现在我们有了结构清晰的AST最后一步就是遍历这棵树为每个节点生成相应的目标代码。我们将生成之前设计的那种简单的栈式指令。5.1 指令集与代码生成器设计我们定义一个简单的指令列表作为输出。代码生成器CodeGen本质上是一个AST的访问者Visitor它根据节点类型执行不同的动作。class Instruction: def __init__(self, opcode: str, operandNone): self.opcode opcode self.operand operand # 可能是整数或字符串变量名 def __repr__(self): if self.operand is not None: return f{self.opcode} {self.operand} else: return self.opcode class CodeGenerator: def __init__(self): self.instructions [] # 符号表记录变量名和它在“内存”中的位置这里简化用变量名直接作为引用 # 更复杂的实现会分配内存地址或寄存器编号。 self.symbol_table set() def emit(self, opcode: str, operandNone): 生成一条指令 self.instructions.append(Instruction(opcode, operand)) def visit(self, node: ASTNode): 分发访问方法 method_name visit_ node.__class__.__name__ visitor getattr(self, method_name, self.generic_visit) return visitor(node) def generic_visit(self, node): raise Exception(fNo visit method for {node.__class__.__name__}) def visit_Program(self, node: Program): for stmt in node.statements: self.visit(stmt) def visit_AssignStmt(self, node: AssignStmt): # 1. 生成计算表达式值的指令 self.visit(node.expr) # 2. 生成存储指令将栈顶值存入变量 var_name node.identifier.name self.emit(STORE, var_name) self.symbol_table.add(var_name) # 记录变量已定义 def visit_PrintStmt(self, node: PrintStmt): # 1. 生成计算表达式值的指令 self.visit(node.expr) # 2. 生成打印指令 self.emit(PRINT) def visit_BinOp(self, node: BinOp): # 后序遍历先左子树再右子树最后操作符 self.visit(node.left) self.visit(node.right) # 根据操作符生成对应的运算指令 op_map { TokenType.PLUS: ADD, TokenType.MINUS: SUB, TokenType.MUL: MUL, TokenType.DIV: DIV, } self.emit(op_map[node.op]) def visit_Integer(self, node: Integer): # 生成加载常量指令 self.emit(PUSH, node.value) def visit_Identifier(self, node: Identifier): # 生成加载变量指令 if node.name not in self.symbol_table: # 这里简化处理实际编译器前端应做“使用前定义”检查 pass self.emit(LOAD, node.name) def generate(self, ast: Program) - list[Instruction]: self.visit(ast) return self.instructions5.2 生成指令并模拟执行让我们把前几个阶段的成果串联起来并写一个简单的虚拟机来执行生成的指令验证结果。# 1. 源代码 source_code a 5; b 10; c a b * 2; print c; # 2. 词法分析 lexer Lexer(source_code) # 3. 语法分析 parser Parser(lexer) ast parser.parse_program() # 4. 代码生成 codegen CodeGenerator() instructions codegen.generate(ast) print(Generated Instructions:) for instr in instructions: print(instr) # 5. 一个极简的栈式虚拟机来执行这些指令 print(\n--- Execution Output ---) stack [] variables {} # 模拟内存 for instr in instructions: if instr.opcode PUSH: stack.append(instr.operand) elif instr.opcode LOAD: if instr.operand in variables: stack.append(variables[instr.operand]) else: raise Exception(fUndefined variable: {instr.operand}) elif instr.opcode STORE: value stack.pop() variables[instr.operand] value elif instr.opcode ADD: b stack.pop() a stack.pop() stack.append(a b) elif instr.opcode SUB: b stack.pop() a stack.pop() stack.append(a - b) elif instr.opcode MUL: b stack.pop() a stack.pop() stack.append(a * b) elif instr.opcode DIV: b stack.pop() a stack.pop() stack.append(a // b) # 整数除法 elif instr.opcode PRINT: value stack.pop() print(value) else: raise Exception(fUnknown instruction: {instr.opcode}) print(fFinal variables: {variables})运行这段代码你会在控制台看到生成的指令序列以及最终的打印输出25因为5 10 * 2 25。恭喜你一个真正能工作的微型编译器诞生了核心原理与扩展思考我们生成的是一种基于栈的中间表示IR。现代编译器如Java的JVM、.NET的CLR都使用栈式或寄存器式虚拟机作为中间层。它的好处是与具体机器架构无关便于优化和移植。如果你想挑战更接近真实机器的代码可以尝试生成x86或ARM的汇编片段那需要了解调用约定、寄存器分配等更复杂的概念这就是GCC、LLVM等编译器后端Backend的核心工作。6. 从玩具到工具编译器工程的深化路径我们成功“手搓”了一个编译器核心流程但它离实用还有光年之遥。下面是一些关键的深化方向每一个都对应着编译原理中的一个重要模块1. 增强前端能力类型系统为TinyLang加入浮点数、布尔值、字符串类型。这需要在词法分析时区分不同字面量在语法分析树中记录类型信息并在代码生成时选择不同的指令如FADD用于浮点加。控制流实现if-else条件判断和while循环。这会让AST变得复杂需要IfStmt,WhileStmt节点代码生成则涉及“跳转”指令JMP,JZ跳转到指定指令地址和标签Label的管理。函数定义与调用这是质的飞跃。需要引入作用域管理、栈帧概念、参数传递、返回值处理。你会深刻理解“调用栈”是怎么回事。2. 引入语义分析Semantic Analysis这是介于语法分析和代码生成之间往往被初学者忽略但至关重要的阶段。它检查语法正确但无意义的代码。类型检查int a “hello”;语法可能没问题如果语法支持字符串但语义错误。符号表管理更完善地记录每个标识符的类型、作用域。检查变量是否重复定义、是否在使用前已声明或定义。静态检查比如break语句是否在循环内函数返回值类型是否匹配等。3. 优化中间表示直接在AST上做优化比较困难。通常编译器会先将AST转换为一种更利于优化的中间表示IR比如三地址码、静态单赋值形式SSA。在我们的栈式指令上就可以做简单的优化常量折叠在编译时直接计算a 5 3 * 2生成PUSH 11而不是PUSH 5; PUSH 3; PUSH 2; MUL; ADD。窥孔优化匹配短小的、低效的指令序列替换为更高效的序列。4. 面向真实机器的代码生成要生成x86/ARM汇编你需要指令选择将IR操作映射到目标机器指令。比如我们的ADDIR在x86上可能是add eax, ebx。寄存器分配这是后端最复杂的问题之一。机器寄存器有限需要智能地把大量的虚拟变量分配到有限的物理寄存器上放不下的就“溢出”到内存。涉及图着色等算法。指令调度重排指令顺序以充分利用CPU的流水线避免数据依赖带来的停顿。5. 使用编译器构造工具工业编译器很少完全手写词法语法分析。Lex/Flex Yacc/Bison经典的词法/语法分析器生成器。你写规则正则表达式和上下文无关文法它们帮你生成C代码。很多老牌编译器如GCC早期版本用它。ANTLR更现代、强大的解析器生成器支持多种目标语言Java, Python, C等适合构建复杂的领域特定语言DSL。LLVM这不是一个工具而是一个编译器基础设施。你可以用任何语言写编译器前端生成LLVM IR然后LLVM负责所有后端优化和代码生成支持多种CPU和GPU。这是目前最主流的学术和工业选择。回过头看我们“手搓”的过程正是理解这些庞大工具和框架内在逻辑的最佳途径。当你再使用GCC的-O2优化选项或在MATLAB里点击“生成代码”按钮或在网上搜索“MSVC编译器离线安装包”时你看到的将不再是一个黑盒而是一个由词法分析、语法分析、语义分析、优化、代码生成等精密模块协同工作的复杂系统。这份理解是通往更高级的软件系统设计、性能优化和语言工程领域的宝贵门票。
