这类主题最值得先看的不是理论概念而是能不能用最少的代码把从源代码到抽象语法树AST的完整流程跑通。很多人一上来就陷进编译原理的术语里结果连一个能处理1 2 * 3的简单解释器都写不出来。这篇文章适合两类人一是想亲手实现一个玩具语言来理解编译器/解释器内部工作的开发者二是遇到需要解析自定义配置、DSL或表达式求值任务不知道从何下手的工程师。我会用一个极简但完整的例子带你走完词法分析Lexer- 语法分析Parser- 生成抽象语法树AST这三步并重点解释每个环节最容易卡住的地方在哪里。1. 先别管理论从“输入字符串”到“计算树”到底要几步在动手写代码之前我们需要把目标拆解成可执行的步骤。假设我们要实现一个能计算1 2 * 3这样表达式的语言最终目标是得到一棵能正确体现运算优先级先乘除后加减的树。整个过程可以分解为三个核心环节词法分析Lexer把源代码字符串切成一个个有意义的“单词”称为Token词法单元。比如1 2 * 3会被切成[数字(1), 加号, 数字(2), 乘号, 数字(3)]。这一步不关心语法结构只负责识别。语法分析Parser按照预定义的语法规则将 Token 序列组合成有结构的树状表示。它负责检查语法是否正确并建立运算之间的优先级和结合性关系。1 2 * 3在这里会被理解为1 (2 * 3)而不是(1 2) * 3。抽象语法树AST这是 Parser 的输出结果一棵树形数据结构。树上的每个节点都代表一个语法结构如表达式、运算符、字面量它剥离了源代码中的空格、括号在体现优先级后等无关细节只保留最核心的语法骨架。这棵树就是后续进行求值、优化或编译成其他代码的基础。很多人觉得难是因为试图一次性理解所有概念。我的建议是先让流程跑通再回头思考理论。下面我们就用 Python 来实现因为它语法简洁能让我们更专注于流程本身。你需要准备一个 Python 3.6 的环境不需要任何第三方库。2. 第一步写 Lexer核心是状态管理和正则匹配Lexer 的任务是“切词”。我们首先定义我们的语言里有哪些 Token。2.1 定义 Token 类型我们实现一个支持整数、加减乘除和括号的简单计算器语言。先为每种 Token 定义一个类型。# token.py from enum import Enum class TokenType(Enum): # 字面量 INTEGER INTEGER # 整数如 1, 42 # 运算符 PLUS PLUS # MINUS MINUS # - MUL MUL # * DIV DIV # / # 括号 LPAREN LPAREN # ( RPAREN RPAREN # ) # 特殊 EOF EOF # 文件结束表示输入已处理完 class Token: def __init__(self, type_: TokenType, value: str): self.type type_ self.value value # 原始字符串比如整数“123” def __repr__(self): return fToken({self.type.value}, {repr(self.value)})这里用枚举定义类型清晰且不易出错。Token类将类型和原始值如123绑定在一起。2.2 实现 Lexer逐个字符扫描Lexer 的核心是一个指针在输入字符串上移动识别出一个个 Token。# lexer.py from token 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): 移动指针到下一个字符 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 get_next_token(self): 获取下一个 Token这是 Lexer 的主方法 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, str(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, None)关键点与避坑提示状态管理current_char永远指向当前待处理的字符。advance()是移动指针的唯一方法这能避免索引混乱。空白处理必须在主循环里持续跳过空白否则一个空格就会导致error。整数识别integer()方法会连续读取数字字符直到遇到非数字然后一次性转换成整数。这比逐个字符处理更清晰。错误处理最简单的error()就是抛出异常。在实际语言中这里需要收集错误位置和上下文信息。测试 Lexer# test_lexer.py from lexer import Lexer def test_lexer(): text 1 2 * (3 - 4) lexer Lexer(text) tokens [] while True: token lexer.get_next_token() tokens.append(token) if token.type TokenType.EOF: break print(tokens) # 期望输出类似 # [Token(INTEGER, 1), Token(PLUS, ), Token(INTEGER, 2), # Token(MUL, *), Token(LPAREN, (), Token(INTEGER, 3), # Token(MINUS, -), Token(INTEGER, 4), Token(RPAREN, )), # Token(EOF, None)] if __name__ __main__: test_lexer()如果这一步能正确输出 Token 列表说明你的 Lexer 已经能正确“切词”了。这是所有后续工作的基础。3. 第二步写 Parser理解递归下降和语法优先级Parser 是核心难点。我们将实现一种称为递归下降解析Recursive Descent Parsing的方法并为我们的表达式语法手动处理运算符优先级。这是理解编译器如何“理解”代码的关键。3.1 定义语法规则文法首先我们需要用形式化的方式描述我们语言的语法。这里使用上下文无关文法CFG的一种简化写法expr : term ( (PLUS | MINUS) term )* term : factor ( (MUL | DIV) factor )* factor : INTEGER | LPAREN expr RPAREN解释expr表达式是起点。term项是比表达式优先级更高的单位由factor通过乘除连接构成。factor因子是最基本的单元要么是一个整数要么是一个括号包裹的表达式(expr)。*表示前面的部分可以出现零次或多次。(PLUS | MINUS)表示加号或减号。这个文法的精妙之处在于它隐式地定义了优先级乘除term层级比加减expr层级绑定得更紧。括号则通过factor - LPAREN expr RPAREN这条规则强制提升内部expr的优先级。3.2 实现 Parser 和 AST 节点在解析之前我们先定义 AST 的节点类型。AST 节点是我们要构建的树上的“果实”。# ast.py class ASTNode: 所有 AST 节点的基类 pass class BinOp(ASTNode): 二元运算符节点如 1 2, 3 * 4 def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left left self.op op # 存储操作符 Token包含类型和值 self.right right def __repr__(self): return fBinOp({self.left}, {self.op.type.value}, {self.right}) class Num(ASTNode): 数字字面量节点 def __init__(self, token: Token): self.token token self.value token.value def __repr__(self): return fNum({self.value})现在实现 Parser。Parser 会消费 Lexer 产生的 Token 流并调用对应文法规则的函数。# parser.py from token import Token, TokenType from ast import BinOp, Num class Parser: def __init__(self, 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): 解析因子: 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): 解析项: factor ( (MUL | DIV) factor )* node self.factor() # 第一个因子 # 处理连续的乘除 while self.current_token.type in (TokenType.MUL, TokenType.DIV): op_token self.current_token if op_token.type TokenType.MUL: self.eat(TokenType.MUL) elif op_token.type TokenType.DIV: self.eat(TokenType.DIV) right_node self.factor() # 获取右边的因子 node BinOp(leftnode, opop_token, rightright_node) # 构建新节点 return node def expr(self): 解析表达式: term ( (PLUS | MINUS) term )* node self.term() # 第一个项 # 处理连续的加减 while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): op_token self.current_token if op_token.type TokenType.PLUS: self.eat(TokenType.PLUS) elif op_token.type TokenType.MINUS: self.eat(TokenType.MINUS) right_node self.term() # 获取右边的项 node BinOp(leftnode, opop_token, rightright_node) # 构建新节点 return node def parse(self): 解析入口返回整个表达式的 AST 根节点 return self.expr()递归下降的精髓每个文法规则对应一个函数expr(),term(),factor()分别对应文法中的同名规则。函数调用链体现优先级expr()调用term()term()调用factor()。这意味着在解析时程序会先深入最底层的factor()数字或括号然后在返回过程中处理term()的乘除最后再处理expr()的加减。这自然实现了乘除优先于加减。eat()方法驱动流程它检查当前 Token 是否符合预期并“吃掉”它推进到下一个 Token。这是 Parser 向前看lookahead的基础通常我们只需要看一个 TokenLL(1)文法。循环处理同级操作while循环用于处理像1 2 3或4 * 5 * 6这样的连续运算构建出左结合的树形结构。测试 Parser 和 AST 生成# test_parser.py from lexer import Lexer from parser import Parser def test_parser(): tests [ 1 2, 3 * 4, 1 2 * 3, (1 2) * 3, 10 / 2 - 3, ] for text in tests: print(f\n输入: {text}) lexer Lexer(text) parser Parser(lexer) ast parser.parse() print(fAST: {ast}) if __name__ __main__: test_parser()运行这个测试你会看到类似下面的输出输入: 1 2 * 3 AST: BinOp(Num(1), PLUS, BinOp(Num(2), MUL, Num(3)))这棵树清晰地显示了2 * 3作为一个整体BinOp是加法PLUS的右子节点证明了优先级已被正确处理。4. 第三步验证与求值——让 AST “跑”起来生成 AST 不是终点我们还需要一个解释器Interpreter来遍历这棵树并计算结果。这是验证我们 Lexer 和 Parser 是否正确的最终标准。4.1 实现树遍历解释器我们实现一个访问者Visitor递归地遍历 AST。# interpreter.py from ast import BinOp, Num from token import TokenType class Interpreter: 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(fNo visit_{type(node).__name__} method) def visit_BinOp(self, node): 访问二元运算符节点 # 递归计算左右子树的值 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 visit_Num(self, node): 访问数字节点 return int(node.value) # 将字符串值转为整数 def interpret(self, ast_root): 解释执行的入口 return self.visit(ast_root)4.2 整合测试从字符串到结果现在我们把 Lexer, Parser, Interpreter 串联起来。# main.py from lexer import Lexer from parser import Parser from interpreter import Interpreter def calculate(expression: str): 计算一个表达式字符串 lexer Lexer(expression) parser Parser(lexer) ast parser.parse() interpreter Interpreter() result interpreter.interpret(ast) return result if __name__ __main__: while True: try: text input(calc ) if not text: continue if text.lower() in (exit, quit): break result calculate(text) print(result) except Exception as e: print(f错误: {e})运行main.py你就得到了一个简单的交互式计算器calc 1 2 * 3 7 calc (1 2) * 3 9 calc 10 / 2 - 3 25. 常见问题、扩展思路与生产级考量如果你能走到这一步已经成功实现了一个语言的核心前端。但在实际项目中你会遇到更多问题。5.1 调试与问题排查当你的解释器报错或结果不对时按这个顺序排查检查 Lexer 输出首先打印出 Token 序列确认字符串是否被正确切分。常见错误是整数识别、负数、小数或空白处理有问题。检查 Parser 流程在expr(),term(),factor()函数中打印当前 Token 和进入/退出信息看解析流程是否符合文法预期。括号不匹配是常见错误。检查 AST 结构打印生成的 AST。确保树的结构正确反映了优先级和结合性。BinOp节点的左右子树是否颠倒检查解释器遍历在visit_BinOp和visit_Num中打印节点信息确认遍历顺序和计算值。5.2 如何扩展这个语言这个框架很容易扩展增加 Token在TokenType枚举和Lexer.get_next_token()中添加对新字符如%,^的识别。增加运算符和优先级新优先级层级比如增加指数运算**优先级高于乘除。你需要在文法和 Parser 中增加一个新的层级例如power并调整调用关系expr - term - power - factor。同级新运算符比如增加取模%和乘除同级。只需在term()函数的while循环判断和操作处理中添加TokenType.MOD。支持浮点数修改 Lexer 的integer()方法为number()使其能识别小数点.。同时需要修改Num节点使其能存储浮点值。支持变量这需要引入符号表Symbol Table。Lexer 需要识别标识符如变量名AST 需要增加Var节点和赋值语句节点如Assign。解释器需要维护一个存储变量名和值的字典。支持语句目前我们只处理了表达式。要支持如print x;或if condition then ...这样的语句需要扩展文法区分表达式Expression和语句Statement并可能引入语句块Block的概念。5.3 从玩具到“真正”的语言还需要什么如果你想深入下去以下几个方向是必经之路更复杂的错误处理目前的error()只是抛出异常。需要记录行号、列号收集多个错误并给出友好的错误信息。语义分析在生成 AST 后进行类型检查、作用域分析、函数声明检查等。例如检查变量是否在使用前已声明。中间表示IR与优化AST 可以直接解释执行但效率不高。通常会将 AST 转换为一种更利于优化的中间表示如三地址码进行常量折叠、死代码消除等优化。目标代码生成将优化后的 IR 转换成特定平台的机器码编译型或者转换成另一种高级语言的代码转译型。标准库与运行时实现一些内置函数如print,sqrt和内存管理等运行时支持。5.4 关于“编程语言排行榜”和“最好的语言”在搜索材料里你可能会看到“编程语言排行榜”、“C是最好的编程语言”这类热词。从实现语言的角度看这些争论意义不大。每一门被广泛使用的语言其编译器/解释器都精妙地实现了我们上面走过的 Lexer、Parser、AST 构建等流程。C 语言编译器如 GCC、Clang极其复杂但基础原理相通。Python、JavaScript 的解释器CPython、V8同样如此只是增加了即时编译JIT等高级特性。学习实现一门小语言最大的价值不是造出另一个 Python而是获得一种“元能力”当你再使用任何编程语言时你能模糊地感知到背后的语法树是如何构建的当你需要解析日志、配置文件或领域特定语言DSL时你知道该从何下手是写正则、用现成的 Parser 生成工具还是自己写递归下降。这才是从“使用者”到“创造者”思维的关键一步。我建议你在成功运行这个计算器后尝试第一个扩展增加对浮点数和取模运算的支持。这个练习会强迫你修改 Lexer、Token、AST 和 Interpreter 的多个部分是对整个流程理解程度的一次完美检验。记住先让最简单的用例跑通再逐步增加复杂度。