1. 项目概述为什么我们要亲手“造轮子”如果你已经写过不少代码可能偶尔会好奇我写的print(Hello, World)电脑的CPU到底是怎么看懂并执行的呢中间到底发生了什么编译器就是这个问题的答案。它就像一个精通多国语言的同声传译把我们用高级语言比如Python、Java写的“人类友好”指令精准地翻译成CPU能直接执行的“机器友好”指令。很多人觉得编译器是操作系统、编程语言开发者才需要关心的“黑魔法”离日常开发很远。其实不然。理解编译器原理哪怕只是最基础的部分也能带来实实在在的好处当你的代码性能出现瓶颈时你能更精准地定位到是算法问题还是语言运行时或编译器优化策略的问题当你需要设计一个配置文件解析器、一个模板引擎甚至是一个领域特定语言DSL时编译器前端的知识词法、语法分析就是你的工具箱它能从根本上提升你阅读和理解复杂代码、框架源码的能力。今天我们就抛开那些厚重的编译原理教材用一个下午的时间动手构建一个能计算(1 2) * 3这类算术表达式的“微型编译器”。我们的目标不是造一个GCC或Clang而是亲手走一遍“源代码 - Token - 抽象语法树 - 目标代码”的核心链路把抽象的理论变成可运行的代码。你会看到这个过程充满了工程化的乐趣和“啊哈”时刻。2. 核心思路与整体设计在开始写代码之前我们必须先想清楚整个流程。一个完整的编译器流水线非常复杂包含前端处理源代码、中端优化、后端生成目标代码。为了让第一个项目可控我们做以下精简和设计2.1 明确范围一个算术表达式编译器我们只处理简单的整数算术表达式支持的操作符包括加()、减(-)、乘(*)、除(/)和括号()。例如1 2 * (3 - 4)就是一个合法的输入。我们的编译器最终会输出计算这个表达式的结果。这本质上是一个“解释器”但我们会模仿编译器的步骤先产生一个中间结构抽象语法树再“执行”它这包含了编译的核心思想。2.2 核心流程三步走我们的微型编译器将分为三个清晰的阶段这也是所有编译器的核心前端流程词法分析将源代码字符串拆分成一个个有意义的“单词”称为Token。例如将“123”拆分成[Token(类型: 整数, 值: 1), Token(类型: 加号), Token(类型: 整数, 值: 23)]。这一步会忽略空格、制表符等无关字符。语法分析根据预定义的语法规则将Token序列组织成一棵结构化的树即抽象语法树。这棵树体现了运算的优先级和结合性。例如对于1 2 * 3AST会确保乘法节点(*)是加法节点()的右子节点表示乘法优先计算。代码生成与执行遍历AST以某种方式计算出最终结果。我们可以直接解释执行遍历树并求值也可以生成一种简单的“中间指令”再执行。这里我们采用前者因为它最直观。2.3 技术选型为什么用Python选择Python来实现主要基于以下几点考量快速原型Python语法简洁能让我们专注于算法逻辑本身而不是内存管理、复杂类型系统等细节非常适合教学和原型验证。强大的内置数据结构列表、字典、枚举类Enum能优雅地表示Token流、AST节点。清晰的表达力递归下降分析法在Python中可以用非常清晰的递归函数来实现代码几乎就是语法规则的直译。 虽然生产级编译器多用C、Rust等但用Python打通核心原理是完全可行且高效的。3. 阶段一词法分析器的构建词法分析器也叫扫描器它的任务就像读文章时先划分出一个个词语。我们首先需要定义什么是“词语”。3.1 定义Token类型我们用枚举类来定义所有可能的Token类型。对于我们的算术表达式需要以下几种from enum import Enum, auto class TokenType(Enum): INTEGER auto() # 整数如 1, 42 PLUS auto() # 加号 MINUS auto() # 减号 - MUL auto() # 乘号 * DIV auto() # 除号 / LPAREN auto() # 左括号 ( RPAREN auto() # 右括号 ) EOF auto() # 文件结束符表示输入已处理完3.2 实现Lexer类Lexer类接收源代码字符串并提供一个get_next_token()方法每次调用都返回下一个Token。class Token: def __init__(self, type_: TokenType, value: str None): self.type type_ self.value value # 对于INTEGERvalue存储整数值字符串对于操作符value可以是符号本身或None def __repr__(self): return fToken({self.type}, value{self.value}) 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): 移动pos指针获取下一个字符。 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)3.3 词法分析器的工作原理与避坑指南逐字符扫描advance()方法是引擎它驱动指针向前移动。skip_whitespace()确保我们的语法分析器不会受到空格干扰。数字识别integer()方法展示了如何识别多位整数。它持续读取数字字符直到遇到非数字字符为止然后将字符串转换为整数。这是词法分析中“贪心算法”的一个简单例子——尽可能多地匹配。错误处理简单的error()方法在遇到无法识别的字符时抛出异常。在实际编译器中这里会收集错误信息如行号、列号并可能尝试恢复。实操心得边界条件与状态管理编写词法分析器时最容易出错的地方是边界条件。比如在advance()方法中必须检查self.pos是否已超过字符串长度否则会引发索引错误。另外skip_whitespace()中的循环条件self.current_char is not None至关重要它防止在跳过文件末尾的空格后继续访问字符。一个健壮的词法分析器是语法分析器稳定运行的基础。你可以这样测试你的词法分析器def test_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(MUL), Token(LPAREN), ...]4. 阶段二语法分析与抽象语法树构建拿到Token流后我们需要理解它的结构。语法分析器根据一组称为“文法”的规则检查Token序列是否符合语法并构建出AST。4.1 定义我们的文法我们使用一种称为“上下文无关文法”的形式来描述表达式语法。以下是一种经典的表达式文法使用巴科斯-诺尔范式变体expr : term ( (PLUS | MINUS) term )* term : factor ( (MUL | DIV) factor )* factor : INTEGER | LPAREN expr RPARENexpr表达式由term项组成后面可以跟零个或多个(加/减 term)。term项由factor因子组成后面可以跟零个或多个(乘/除 factor)。factor因子可以是一个整数或者一个用括号括起来的expr。 这种分层结构隐式地定义了优先级括号()最高其次是*和/最后是和-。*和/是左结合的。4.2 定义AST节点AST的节点需要能表示各种语法结构。我们定义几种节点类型class ASTNode: pass class BinOp(ASTNode): 二元操作节点如 左操作数 右操作数 def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left left self.op op # 这是一个Token其type是PLUS, MINUS等 self.right right class Num(ASTNode): 数字叶子节点 def __init__(self, token: Token): self.token token self.value token.value class UnaryOp(ASTNode): 一元操作节点可选扩展如 -5 def __init__(self, op: Token, expr: ASTNode): self.op op self.expr expr目前我们主要使用BinOp和Num。4.3 实现递归下降语法分析器递归下降分析法非常直观为文法中的每个非终结符expr,term,factor编写一个函数这个函数负责从Token流中识别并构建对应的AST子树。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化当前Token def error(self): raise Exception(Invalid syntax) def eat(self, token_type: TokenType): “消耗”当前Token。如果类型匹配则获取下一个Token否则报错。 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: self.error() def factor(self): factor : INTEGER | LPAREN expr 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): term : factor ((MUL | DIV) factor)* 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): expr : term ((PLUS | MINUS) term)* 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()4.4 语法分析的关键递归与优先级处理递归注意factor()函数中当遇到左括号时它调用了self.expr()。这就是递归它优雅地处理了任意深度的嵌套括号。优先级优先级是通过函数调用顺序实现的。expr()先调用term()term()先调用factor()。这意味着在构建AST时factor()括号和数字最先被组合然后是term()处理乘除最后是expr()处理加减。这保证了乘除节点在树中处于更低层更早被计算。结合性while循环中我们将当前结果节点作为新BinOp的左子节点。对于左结合的操作符如1 - 2 - 3应理解为(1-2)-3这种构造方式天然就是正确的。注意事项错误恢复与Token前瞻我们这个简单的分析器在遇到错误时会直接抛出异常。真正的编译器需要错误恢复机制比如跳过一些Token直到遇到一个同步点如分号然后继续分析以便报告多个错误。此外我们的分析器只“前瞻”一个Tokenself.current_token。对于更复杂的语法可能需要前瞻多个TokenLL(k)分析。构建AST后我们可以用一个简单的函数来可视化它以缩进形式def print_ast(node: ASTNode, indent0): indent_str * indent if isinstance(node, Num): print(f{indent_str}Num({node.value})) elif isinstance(node, BinOp): print(f{indent_str}BinOp({node.op.type.name})) print_ast(node.left, indent 1) print_ast(node.right, indent 1)5. 阶段三解释执行与代码生成思想有了AST我们就有了对源代码的完整理解。现在有两种方式得到结果1) 解释执行直接遍历AST计算2) 代码生成将AST转换为另一种表示如字节码、汇编再执行。我们先实现第一种因为它更简单再探讨第二种思想。5.1 实现AST解释器解释器就是一个深度优先遍历AST的递归函数class Interpreter: def __init__(self, parser: Parser): self.parser parser def visit(self, node: ASTNode): 访问者模式的简化实现根据节点类型调用不同方法。 method_name visit_ type(node).__name__ visitor getattr(self, method_name, self.generic_visit) return visitor(node) def generic_visit(self, node): raise Exception(fNo visit_{type(node).__name__} method) def visit_Num(self, node: Num): return node.value def visit_BinOp(self, node: BinOp): left_val self.visit(node.left) right_val self.visit(node.right) if node.op.type TokenType.PLUS: return left_val right_val elif node.op.type TokenType.MINUS: return left_val - right_val elif node.op.type TokenType.MUL: return left_val * right_val elif node.op.type TokenType.DIV: return left_val // right_val # 整数除法 else: raise Exception(Invalid operator) def interpret(self): tree self.parser.parse() return self.visit(tree)现在将三个阶段串联起来def main(): while True: try: text input(calc ) except EOFError: break if not text: continue lexer Lexer(text) parser Parser(lexer) interpreter Interpreter(parser) result interpreter.interpret() print(result) if __name__ __main__: main()运行它输入(1 2) * 3你应该得到输出9。5.2 迈向代码生成一种简单的中间表示直接解释执行简单但缺乏优化空间也不便于移植。编译器的核心思想是生成代码。我们可以定义一种非常简单的“栈式中间指令”class OpCode(Enum): PUSH auto() # 将整数压入栈 ADD auto() # 弹出栈顶两个数相加后结果压栈 SUB auto() MUL auto() DIV auto() class Instruction: def __init__(self, opcode: OpCode, operandNone): self.opcode opcode self.operand operand # 对于PUSH指令operand是整数值然后我们可以写一个CodeGenerator类来遍历AST生成指令序列class CodeGenerator: def __init__(self): self.instructions [] def visit_Num(self, node: Num): self.instructions.append(Instruction(OpCode.PUSH, node.value)) def visit_BinOp(self, node: BinOp): self.visit(node.left) self.visit(node.right) if node.op.type TokenType.PLUS: self.instructions.append(Instruction(OpCode.ADD)) elif node.op.type TokenType.MINUS: self.instructions.append(Instruction(OpCode.SUB)) # ... 类似处理 MUL, DIV def generate(self, tree: ASTNode): self.visit(tree) return self.instructions最后实现一个栈式虚拟机来执行这些指令class StackVM: def __init__(self): self.stack [] def run(self, instructions): for instr in instructions: if instr.opcode OpCode.PUSH: self.stack.append(instr.operand) elif instr.opcode OpCode.ADD: b self.stack.pop() a self.stack.pop() self.stack.append(a b) # ... 实现其他操作 return self.stack.pop() if self.stack else None现在流程变成了源代码 - Lexer - Parser (AST) - CodeGenerator (指令序列) - StackVM (执行)。这已经是一个微型编译器的完整雏形了你可以看到代码生成器将AST这种与具体机器无关的表示转换成了另一种更接近执行过程的线性表示。6. 常见问题、扩展方向与实战技巧6.1 常见问题排查输入2 3 *导致程序崩溃或输出错误这是语法错误。我们的语法分析器在term()中调用self.factor()后如果当前Token是EOF或RPAREN等while循环不会进入直接返回节点。但如果当前Token是PLUSexpr()的while循环会尝试获取下一个term而term()又会尝试获取factor此时遇到EOF就会在factor()中触发error()。解决方法是在语法分析器中加入更完善的错误检测和恢复或者至少给出更友好的错误信息如“在位置X期待一个因子”。除零错误我们的解释器在visit_BinOp中做除法时没有检查除数是否为零。在生产环境中必须添加检查并给出明确的运行时错误信息。处理负数一元运算符当前的文法不支持-5这样的表达式。要支持它需要扩展factor规则factor : (PLUS | MINUS) factor | INTEGER | LPAREN expr RPAREN并在factor()函数中处理一元操作符创建UnaryOp节点。6.2 如何扩展这个微型编译器增加更多数据类型支持浮点数。需要在词法分析器中修改integer()方法来识别小数点并定义新的FLOATToken类型和AST节点。增加变量赋值与读取例如x 1 2。这需要引入符号表一个字典来存储变量名和值的映射。词法分析器需要增加IDToken类型来识别变量名。语法需要增加赋值语句规则解释器或代码生成器需要能处理变量的存储和加载。增加控制流如if语句和while循环。这需要引入新的AST节点If,While并可能扩展中间指令集增加跳转指令JMP,JZ等。生成真正的汇编代码不满足于栈式虚拟机可以尝试将AST或中间指令生成x86或ARM的汇编代码哪怕是极简子集。这需要你了解目标平台的基本指令、寄存器和调用约定。这是一个巨大的飞跃但会让人对“机器如何执行代码”有刻骨铭心的理解。6.3 实战心得与资源推荐从简到繁千万不要一开始就想实现一个C语言的子集。从算术表达式开始然后加入变量再加入函数一步一步来。每完成一个特性都能获得巨大的成就感。测试驱动为你的词法分析器、语法分析器、解释器编写单元测试。输入各种合法和非法的字符串确保行为符合预期。编译器的调试可能很棘手好的测试能节省大量时间。利用现成工具进阶工业级编译器很少手写词法/语法分析器。它们使用如Lex/Flex词法分析器生成器、Yacc/Bison语法分析器生成器或ANTLR等工具。这些工具根据你提供的文法规则自动生成分析器代码。在你亲手实现一遍之后再去学习这些工具你会更理解它们的工作原理和优势。经典资源《编译原理》龙书经典教材理论扎实。《编程语言实现模式》更偏实践提供了大量可复用的模式。Let’s Build a Compiler (Jack Crenshaw)一个非常著名的系列教程用Pascal实现但思想通用循序渐进。Crafting Interpreters (Robert Nystrom)一本绝对精彩的免费在线书手把手教你用Java和C实现两门完整的脚本语言解释器文笔幽默实践性强。亲手实现一个编译器哪怕是微型的是一次深刻的旅程。它剥开了编程语言神秘的外衣让你看到其下严谨的数学逻辑和精巧的工程设计。当你第一次看到自己写的程序将自己定义的几行代码转换成可执行指令并输出正确结果时那种感觉无与伦比。这不仅是一项技能更是一种理解计算机科学核心的思维方式。希望这个简单的表达式计算器能成为你探索广阔编译世界的第一块基石。
从零构建算术表达式编译器：Python实现词法分析、语法树与解释器
发布时间：2026/6/8 13:20:49
1. 项目概述为什么我们要亲手“造轮子”如果你已经写过不少代码可能偶尔会好奇我写的print(Hello, World)电脑的CPU到底是怎么看懂并执行的呢中间到底发生了什么编译器就是这个问题的答案。它就像一个精通多国语言的同声传译把我们用高级语言比如Python、Java写的“人类友好”指令精准地翻译成CPU能直接执行的“机器友好”指令。很多人觉得编译器是操作系统、编程语言开发者才需要关心的“黑魔法”离日常开发很远。其实不然。理解编译器原理哪怕只是最基础的部分也能带来实实在在的好处当你的代码性能出现瓶颈时你能更精准地定位到是算法问题还是语言运行时或编译器优化策略的问题当你需要设计一个配置文件解析器、一个模板引擎甚至是一个领域特定语言DSL时编译器前端的知识词法、语法分析就是你的工具箱它能从根本上提升你阅读和理解复杂代码、框架源码的能力。今天我们就抛开那些厚重的编译原理教材用一个下午的时间动手构建一个能计算(1 2) * 3这类算术表达式的“微型编译器”。我们的目标不是造一个GCC或Clang而是亲手走一遍“源代码 - Token - 抽象语法树 - 目标代码”的核心链路把抽象的理论变成可运行的代码。你会看到这个过程充满了工程化的乐趣和“啊哈”时刻。2. 核心思路与整体设计在开始写代码之前我们必须先想清楚整个流程。一个完整的编译器流水线非常复杂包含前端处理源代码、中端优化、后端生成目标代码。为了让第一个项目可控我们做以下精简和设计2.1 明确范围一个算术表达式编译器我们只处理简单的整数算术表达式支持的操作符包括加()、减(-)、乘(*)、除(/)和括号()。例如1 2 * (3 - 4)就是一个合法的输入。我们的编译器最终会输出计算这个表达式的结果。这本质上是一个“解释器”但我们会模仿编译器的步骤先产生一个中间结构抽象语法树再“执行”它这包含了编译的核心思想。2.2 核心流程三步走我们的微型编译器将分为三个清晰的阶段这也是所有编译器的核心前端流程词法分析将源代码字符串拆分成一个个有意义的“单词”称为Token。例如将“123”拆分成[Token(类型: 整数, 值: 1), Token(类型: 加号), Token(类型: 整数, 值: 23)]。这一步会忽略空格、制表符等无关字符。语法分析根据预定义的语法规则将Token序列组织成一棵结构化的树即抽象语法树。这棵树体现了运算的优先级和结合性。例如对于1 2 * 3AST会确保乘法节点(*)是加法节点()的右子节点表示乘法优先计算。代码生成与执行遍历AST以某种方式计算出最终结果。我们可以直接解释执行遍历树并求值也可以生成一种简单的“中间指令”再执行。这里我们采用前者因为它最直观。2.3 技术选型为什么用Python选择Python来实现主要基于以下几点考量快速原型Python语法简洁能让我们专注于算法逻辑本身而不是内存管理、复杂类型系统等细节非常适合教学和原型验证。强大的内置数据结构列表、字典、枚举类Enum能优雅地表示Token流、AST节点。清晰的表达力递归下降分析法在Python中可以用非常清晰的递归函数来实现代码几乎就是语法规则的直译。 虽然生产级编译器多用C、Rust等但用Python打通核心原理是完全可行且高效的。3. 阶段一词法分析器的构建词法分析器也叫扫描器它的任务就像读文章时先划分出一个个词语。我们首先需要定义什么是“词语”。3.1 定义Token类型我们用枚举类来定义所有可能的Token类型。对于我们的算术表达式需要以下几种from enum import Enum, auto class TokenType(Enum): INTEGER auto() # 整数如 1, 42 PLUS auto() # 加号 MINUS auto() # 减号 - MUL auto() # 乘号 * DIV auto() # 除号 / LPAREN auto() # 左括号 ( RPAREN auto() # 右括号 ) EOF auto() # 文件结束符表示输入已处理完3.2 实现Lexer类Lexer类接收源代码字符串并提供一个get_next_token()方法每次调用都返回下一个Token。class Token: def __init__(self, type_: TokenType, value: str None): self.type type_ self.value value # 对于INTEGERvalue存储整数值字符串对于操作符value可以是符号本身或None def __repr__(self): return fToken({self.type}, value{self.value}) 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): 移动pos指针获取下一个字符。 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)3.3 词法分析器的工作原理与避坑指南逐字符扫描advance()方法是引擎它驱动指针向前移动。skip_whitespace()确保我们的语法分析器不会受到空格干扰。数字识别integer()方法展示了如何识别多位整数。它持续读取数字字符直到遇到非数字字符为止然后将字符串转换为整数。这是词法分析中“贪心算法”的一个简单例子——尽可能多地匹配。错误处理简单的error()方法在遇到无法识别的字符时抛出异常。在实际编译器中这里会收集错误信息如行号、列号并可能尝试恢复。实操心得边界条件与状态管理编写词法分析器时最容易出错的地方是边界条件。比如在advance()方法中必须检查self.pos是否已超过字符串长度否则会引发索引错误。另外skip_whitespace()中的循环条件self.current_char is not None至关重要它防止在跳过文件末尾的空格后继续访问字符。一个健壮的词法分析器是语法分析器稳定运行的基础。你可以这样测试你的词法分析器def test_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(MUL), Token(LPAREN), ...]4. 阶段二语法分析与抽象语法树构建拿到Token流后我们需要理解它的结构。语法分析器根据一组称为“文法”的规则检查Token序列是否符合语法并构建出AST。4.1 定义我们的文法我们使用一种称为“上下文无关文法”的形式来描述表达式语法。以下是一种经典的表达式文法使用巴科斯-诺尔范式变体expr : term ( (PLUS | MINUS) term )* term : factor ( (MUL | DIV) factor )* factor : INTEGER | LPAREN expr RPARENexpr表达式由term项组成后面可以跟零个或多个(加/减 term)。term项由factor因子组成后面可以跟零个或多个(乘/除 factor)。factor因子可以是一个整数或者一个用括号括起来的expr。 这种分层结构隐式地定义了优先级括号()最高其次是*和/最后是和-。*和/是左结合的。4.2 定义AST节点AST的节点需要能表示各种语法结构。我们定义几种节点类型class ASTNode: pass class BinOp(ASTNode): 二元操作节点如 左操作数 右操作数 def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left left self.op op # 这是一个Token其type是PLUS, MINUS等 self.right right class Num(ASTNode): 数字叶子节点 def __init__(self, token: Token): self.token token self.value token.value class UnaryOp(ASTNode): 一元操作节点可选扩展如 -5 def __init__(self, op: Token, expr: ASTNode): self.op op self.expr expr目前我们主要使用BinOp和Num。4.3 实现递归下降语法分析器递归下降分析法非常直观为文法中的每个非终结符expr,term,factor编写一个函数这个函数负责从Token流中识别并构建对应的AST子树。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化当前Token def error(self): raise Exception(Invalid syntax) def eat(self, token_type: TokenType): “消耗”当前Token。如果类型匹配则获取下一个Token否则报错。 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: self.error() def factor(self): factor : INTEGER | LPAREN expr 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): term : factor ((MUL | DIV) factor)* 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): expr : term ((PLUS | MINUS) term)* 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()4.4 语法分析的关键递归与优先级处理递归注意factor()函数中当遇到左括号时它调用了self.expr()。这就是递归它优雅地处理了任意深度的嵌套括号。优先级优先级是通过函数调用顺序实现的。expr()先调用term()term()先调用factor()。这意味着在构建AST时factor()括号和数字最先被组合然后是term()处理乘除最后是expr()处理加减。这保证了乘除节点在树中处于更低层更早被计算。结合性while循环中我们将当前结果节点作为新BinOp的左子节点。对于左结合的操作符如1 - 2 - 3应理解为(1-2)-3这种构造方式天然就是正确的。注意事项错误恢复与Token前瞻我们这个简单的分析器在遇到错误时会直接抛出异常。真正的编译器需要错误恢复机制比如跳过一些Token直到遇到一个同步点如分号然后继续分析以便报告多个错误。此外我们的分析器只“前瞻”一个Tokenself.current_token。对于更复杂的语法可能需要前瞻多个TokenLL(k)分析。构建AST后我们可以用一个简单的函数来可视化它以缩进形式def print_ast(node: ASTNode, indent0): indent_str * indent if isinstance(node, Num): print(f{indent_str}Num({node.value})) elif isinstance(node, BinOp): print(f{indent_str}BinOp({node.op.type.name})) print_ast(node.left, indent 1) print_ast(node.right, indent 1)5. 阶段三解释执行与代码生成思想有了AST我们就有了对源代码的完整理解。现在有两种方式得到结果1) 解释执行直接遍历AST计算2) 代码生成将AST转换为另一种表示如字节码、汇编再执行。我们先实现第一种因为它更简单再探讨第二种思想。5.1 实现AST解释器解释器就是一个深度优先遍历AST的递归函数class Interpreter: def __init__(self, parser: Parser): self.parser parser def visit(self, node: ASTNode): 访问者模式的简化实现根据节点类型调用不同方法。 method_name visit_ type(node).__name__ visitor getattr(self, method_name, self.generic_visit) return visitor(node) def generic_visit(self, node): raise Exception(fNo visit_{type(node).__name__} method) def visit_Num(self, node: Num): return node.value def visit_BinOp(self, node: BinOp): left_val self.visit(node.left) right_val self.visit(node.right) if node.op.type TokenType.PLUS: return left_val right_val elif node.op.type TokenType.MINUS: return left_val - right_val elif node.op.type TokenType.MUL: return left_val * right_val elif node.op.type TokenType.DIV: return left_val // right_val # 整数除法 else: raise Exception(Invalid operator) def interpret(self): tree self.parser.parse() return self.visit(tree)现在将三个阶段串联起来def main(): while True: try: text input(calc ) except EOFError: break if not text: continue lexer Lexer(text) parser Parser(lexer) interpreter Interpreter(parser) result interpreter.interpret() print(result) if __name__ __main__: main()运行它输入(1 2) * 3你应该得到输出9。5.2 迈向代码生成一种简单的中间表示直接解释执行简单但缺乏优化空间也不便于移植。编译器的核心思想是生成代码。我们可以定义一种非常简单的“栈式中间指令”class OpCode(Enum): PUSH auto() # 将整数压入栈 ADD auto() # 弹出栈顶两个数相加后结果压栈 SUB auto() MUL auto() DIV auto() class Instruction: def __init__(self, opcode: OpCode, operandNone): self.opcode opcode self.operand operand # 对于PUSH指令operand是整数值然后我们可以写一个CodeGenerator类来遍历AST生成指令序列class CodeGenerator: def __init__(self): self.instructions [] def visit_Num(self, node: Num): self.instructions.append(Instruction(OpCode.PUSH, node.value)) def visit_BinOp(self, node: BinOp): self.visit(node.left) self.visit(node.right) if node.op.type TokenType.PLUS: self.instructions.append(Instruction(OpCode.ADD)) elif node.op.type TokenType.MINUS: self.instructions.append(Instruction(OpCode.SUB)) # ... 类似处理 MUL, DIV def generate(self, tree: ASTNode): self.visit(tree) return self.instructions最后实现一个栈式虚拟机来执行这些指令class StackVM: def __init__(self): self.stack [] def run(self, instructions): for instr in instructions: if instr.opcode OpCode.PUSH: self.stack.append(instr.operand) elif instr.opcode OpCode.ADD: b self.stack.pop() a self.stack.pop() self.stack.append(a b) # ... 实现其他操作 return self.stack.pop() if self.stack else None现在流程变成了源代码 - Lexer - Parser (AST) - CodeGenerator (指令序列) - StackVM (执行)。这已经是一个微型编译器的完整雏形了你可以看到代码生成器将AST这种与具体机器无关的表示转换成了另一种更接近执行过程的线性表示。6. 常见问题、扩展方向与实战技巧6.1 常见问题排查输入2 3 *导致程序崩溃或输出错误这是语法错误。我们的语法分析器在term()中调用self.factor()后如果当前Token是EOF或RPAREN等while循环不会进入直接返回节点。但如果当前Token是PLUSexpr()的while循环会尝试获取下一个term而term()又会尝试获取factor此时遇到EOF就会在factor()中触发error()。解决方法是在语法分析器中加入更完善的错误检测和恢复或者至少给出更友好的错误信息如“在位置X期待一个因子”。除零错误我们的解释器在visit_BinOp中做除法时没有检查除数是否为零。在生产环境中必须添加检查并给出明确的运行时错误信息。处理负数一元运算符当前的文法不支持-5这样的表达式。要支持它需要扩展factor规则factor : (PLUS | MINUS) factor | INTEGER | LPAREN expr RPAREN并在factor()函数中处理一元操作符创建UnaryOp节点。6.2 如何扩展这个微型编译器增加更多数据类型支持浮点数。需要在词法分析器中修改integer()方法来识别小数点并定义新的FLOATToken类型和AST节点。增加变量赋值与读取例如x 1 2。这需要引入符号表一个字典来存储变量名和值的映射。词法分析器需要增加IDToken类型来识别变量名。语法需要增加赋值语句规则解释器或代码生成器需要能处理变量的存储和加载。增加控制流如if语句和while循环。这需要引入新的AST节点If,While并可能扩展中间指令集增加跳转指令JMP,JZ等。生成真正的汇编代码不满足于栈式虚拟机可以尝试将AST或中间指令生成x86或ARM的汇编代码哪怕是极简子集。这需要你了解目标平台的基本指令、寄存器和调用约定。这是一个巨大的飞跃但会让人对“机器如何执行代码”有刻骨铭心的理解。6.3 实战心得与资源推荐从简到繁千万不要一开始就想实现一个C语言的子集。从算术表达式开始然后加入变量再加入函数一步一步来。每完成一个特性都能获得巨大的成就感。测试驱动为你的词法分析器、语法分析器、解释器编写单元测试。输入各种合法和非法的字符串确保行为符合预期。编译器的调试可能很棘手好的测试能节省大量时间。利用现成工具进阶工业级编译器很少手写词法/语法分析器。它们使用如Lex/Flex词法分析器生成器、Yacc/Bison语法分析器生成器或ANTLR等工具。这些工具根据你提供的文法规则自动生成分析器代码。在你亲手实现一遍之后再去学习这些工具你会更理解它们的工作原理和优势。经典资源《编译原理》龙书经典教材理论扎实。《编程语言实现模式》更偏实践提供了大量可复用的模式。Let’s Build a Compiler (Jack Crenshaw)一个非常著名的系列教程用Pascal实现但思想通用循序渐进。Crafting Interpreters (Robert Nystrom)一本绝对精彩的免费在线书手把手教你用Java和C实现两门完整的脚本语言解释器文笔幽默实践性强。亲手实现一个编译器哪怕是微型的是一次深刻的旅程。它剥开了编程语言神秘的外衣让你看到其下严谨的数学逻辑和精巧的工程设计。当你第一次看到自己写的程序将自己定义的几行代码转换成可执行指令并输出正确结果时那种感觉无与伦比。这不仅是一项技能更是一种理解计算机科学核心的思维方式。希望这个简单的表达式计算器能成为你探索广阔编译世界的第一块基石。
相关文章
Web Components主题热切换方案揭秘
发散创新：用 adoptedStyleSheets Constructable Stylesheets 实现 Web Components 的主题热切换系统 在现代 Web Components 开发中，样式隔离与主题动态切换长期存在矛盾：Shadow DOM 天然阻断全局样式穿透，但传统 <link rel&…
MIFARE Ultralight AES安全芯片：低成本应用的AES-128与CMAC实战指南
1. 项目概述与核心价值如果你正在设计一个基于NFC的票务、门禁或者物流追踪系统，并且对成本敏感，但又不能完全牺牲安全性，那么MIFARE Ultralight AES这颗芯片很可能已经进入了你的备选清单。它不像它的“大哥”MIFARE DESFire那样拥有复杂的文…
Audacity音频编辑完全指南：从零基础到专业实战
Audacity音频编辑完全指南：从零基础到专业实战 【免费下载链接】audacity Audio Editor 项目地址: https://gitcode.com/GitHub_Trending/au/audacity 想要轻松处理音频却不知从何入手？Audacity作为业界知名的开源音频编辑神器，为您提…
终极指南：让Apple触控板在Windows上实现原生级精准操作
终极指南：让Apple触控板在Windows上实现原生级精准操作 【免费下载链接】mac-precision-touchpad Windows Precision Touchpad Driver Implementation for Apple MacBook / Magic Trackpad 项目地址: https://gitcode.com/gh_mirrors/ma/mac-precision-touchpad …
【QtPDF.pri直接导入项目使用
QtPDF 基于 Qt 框架的 PDF 生成库，提供简单易用的 API 用于生成 PDF 文档，支持文本、图片和表格输出。 分享文件：QtPDF 链接：https://pan.xunlei.com/s/VOuVlf6YM2oGZm_1F80_qisJA1?pwd=asj4# 复制这段内容后打开迅雷，查看更方便 通过网盘分享的文件：QtPDF 链接: ht…
2026主流AI模型实测横向对比：国产模型落地优势与企业选型指南
2026年AI大模型技术迭代速度持续加快，海外闭源模型不断升级，国产通用大模型、开源轻量化模型多点突破，各类模型性能、适配场景、部署成本差异极大。对于开发者、企业技术团队而言，如何根据业务场景挑选适配的AI模型，降…
Cursor AI × FPGA verilog开发效率革命
第一章：为什么 FPGA 开发者必须掌握 Cursor1.1 人员流动与技术壁垒：AI不再是"加分项"，而是"生存项"一家 FPGA 团队的健康度，往往靠顶尖那两三个人撑着。而顶尖的人，最容易走——能力强、市场报价高…
05 JAVA面向对象
✨博客主页： https://blog.csdn.net/m0_63815035?typeblog 💗《博客内容》：大数据、AI开发、Java、测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 📢博客专栏： https://blog.csdn.net/m0_6…
HC908EY16 LIN监控节点开发：从协议栈配置到硬件调试全解析
1. 项目概述与LIN总线基础在汽车电子开发领域，LIN总线是一个绕不开的经典技术。它不像CAN总线那样追求高性能和高可靠性，而是专注于为那些对成本敏感、对实时性要求不那么苛刻的车身控制单元提供一种“够用就好”的通信方案。想象一下车窗升降、后视镜调…
解决老旧机顶盒资源化难题：Amlogic S9xxx Armbian项目在TY1608设备上的系统适配实现
解决老旧机顶盒资源化难题：Amlogic S9xxx Armbian项目在TY1608设备上的系统适配实现 【免费下载链接】amlogic-s9xxx-armbian Supports running Armbian on Amlogic, Allwinner, and Rockchip devices. Support a311d, s922x, s905x3, s905x2, s912, s905d, s905x, …
Python Scrapy 爬虫实战进阶系列（一）：轻量化数据存储 - 数据精准写入 SQLite 数据库
前言 在 Python 爬虫开发领域中，Scrapy 作为高性能、高可扩展性的异步爬虫框架，是行业内采集结构化数据的首选工具。在中小型爬虫项目、本地数据采集、轻量化数据存储场景中，SQLite 无需独立服务、单文件存储、原生兼容 Python 的特性&#…
3步实现Windows直读Btrfs分区：跨平台文件系统互通终极方案
3步实现Windows直读Btrfs分区：跨平台文件系统互通终极方案 【免费下载链接】btrfs WinBtrfs - an open-source btrfs driver for Windows 项目地址: https://gitcode.com/gh_mirrors/bt/btrfs 还在为Windows无法访问Linux Btrfs分区而烦恼吗？你是…
LED驱动技术全解析：从核心架构到实战选型与避坑指南
1. 从一颗灯珠到千亿市场：LED驱动的技术演进与商业逻辑十几年前，当我第一次从料盘上拿起一颗0603封装的白色LED时，它微弱的光晕和高达几块钱的单颗成本，让我很难想象今天它几乎照亮了我们生活的每一个角落。从手机屏幕的一抹背光&…
索引堆及其优化
索引堆及其优化 引言 索引堆是一种数据结构，广泛应用于计算机科学和软件工程领域。它主要用于解决优先队列问题，如最小堆和最大堆。本文将详细介绍索引堆的概念、实现方法以及优化策略。 索引堆的定义 索引堆是一种基于堆数据结构的索引机制。它通过维护一个堆来存储数据…
从零到日增237精准粉丝，我靠CSDN这张AI卡片爆了！手把手复刻全流程，含配置避坑清单
更多请点击： https://intelliparadigm.com 第一章：CSDN AI 数字营销的官方引流卡片是什么功能？ CSDN AI 数字营销平台推出的「官方引流卡片」，是一种面向技术创作者的轻量级、可嵌入式内容分发组件，专为提升博文、教程…
Zotero Duplicates Merger：5步彻底清理文献库重复条目
Zotero Duplicates Merger：5步彻底清理文献库重复条目 【免费下载链接】ZoteroDuplicatesMerger A zotero plugin to automatically merge duplicate items 项目地址: https://gitcode.com/gh_mirrors/zo/ZoteroDuplicatesMerger 还在为文献库中堆积如山的重…
利用随机有限集理论对蜂群的ILQR和MPC控制研究附Matlab代码
✅作者简介：热爱科研的Matlab仿真开发者，擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。🍎 往期回顾关注个人主页：Matlab科研工作室🍊个人信条：格物致知,完整Matlab代码及仿真咨询…
为什么你的Gemini邮件CTE低于行业均值2.8倍？：从Prompt架构到发送时序的深度归因
更多请点击： https://intelliparadigm.com 第一章：为什么你的Gemini邮件CTE低于行业均值2.8倍？：从Prompt架构到发送时序的深度归因 Gemini邮件的客户转化效率（CTE）显著偏低，根本原因常被误判为…