你是否曾好奇那些功能强大的编程语言如 Python、Java是如何从你写下的几行字符变成计算机能理解和执行的指令的当你写下print(Hello, World)时背后究竟发生了什么很多开发者对“编译原理”望而却步认为它深奥难懂只属于编译器开发者的领域。但真相是理解语言处理的核心三件套——词法分析器Lexer、语法分析器Parser和抽象语法树AST——不仅能让你更深刻地理解代码的运行机制更能显著提升你设计 API、解析配置文件、甚至构建领域特定语言DSL的能力。这篇文章要解决一个核心问题如何用最直观的方式从零开始理解并动手实现一个微型编程语言的“大脑”。我们将避开复杂的理论公式直接通过代码和场景带你走完从源代码字符串到结构化程序表示的全过程。读完本文你将不仅能清晰地说出 Lexer、Parser、AST 各自的作用更能亲手实现一个可以解析简单算术表达式如1 2 * (3 - 4)的完整流程。这对于想深入理解工具链如 Babel、ESLint、优化构建流程或 simply 想提升技术深度的开发者来说是一次绝佳的实践。1. 这篇文章真正要解决的问题为什么你需要关心 Lexer、Parser 和 AST在开始敲代码之前我们必须先达成共识学习这些底层知识到底能解决什么实际开发中的痛点很多人认为这是“屠龙之技”但以下几个场景会让你改变看法场景一自定义配置或规则引擎。你的项目需要一个灵活的规则配置文件用户可能写出cpu_usage 80% memory_usage 20%这样的表达式。你需要一个可靠的方式来解析并执行它而不是用一堆脆弱的字符串分割和正则表达式。场景二代码分析与自动化工具。你想写一个工具自动扫描项目中的代码找出所有调用某个特定函数的地方或者进行简单的代码风格转换。直接操作字符串几乎是不可能的任务。场景三理解现代前端工具链。Babel 如何转换 JS 语法ESLint 如何检查代码规则TypeScript 如何做类型推断它们的核心都始于将代码解析成 AST。理解 AST你就拿到了理解这些强大工具的钥匙。场景四设计内部 DSL。为了提升团队效率你可能需要设计一种更贴近业务的语言片段。比如测试人员写user.login(admin, 123456).expect(status200)这背后就需要一个轻量级的解析器。如果不理解 Lexer、Parser 和 AST你在面对上述需求时解决方案往往停留在“字符串处理”的层面代码冗长、易出错、难以维护。而一旦掌握了这套核心流程你就拥有了将“非结构化文本”转化为“可编程对象”的标准化能力。本文的目标就是帮你跨越从“字符串操作”到“语言解析”的认知鸿沟通过一个具体的算术表达式案例让你获得可迁移的实践能力。2. 基础概念与核心原理拆解“源代码到AST”的三步流水线让我们用“人类理解一句话”来类比计算机理解一段代码。假设有一行源代码result 42 (value * 2)第一步词法分析Lexical Analysis - 认出每个单词这个过程由Lexer词法分析器也叫 Scanner完成。它的任务很简单把一长串字符流拆分成一个个有意义的、不可再分的“单词”这些单词在编译原理中称为Token词法单元。输入字符流r e s u l t 4 2 ( v a l u e * 2 )输出Token 序列[Identifier(result), Operator(), Number(42), Operator(), Operator((), Identifier(value), Operator(*), Number(2), Operator())]关键Lexer 不关心语法结构它只负责识别“这是什么词”。它会忽略空格、换行等无关字符。第二步语法分析Syntactic Analysis - 理解句子结构这个过程由Parser语法分析器完成。它的任务是根据预定义的语法规则Grammar将 Token 序列组合成一个具有层次结构的树形表示。这个树就是抽象语法树Abstract Syntax Tree, AST。输入上一步的 Token 序列。输出一棵 AST。关键Parser 关心的是结构。它知道*的优先级比高()内的表达式要先计算。AST 抽象掉了某些细节如分号、括号的位置只保留程序逻辑的核心结构。第三步抽象语法树AST- 程序的骨架AST 是程序结构的抽象表示。对于42 (value * 2)一个简化的 AST 可能长这样BinaryExpression(operator) / \ Number(42) BinaryExpression(operator*) / \ Identifier(value) Number(2)这棵树清晰地表达了这是一个加法运算左操作数是字面量42右操作数是一个乘法运算而乘法的操作数是变量value和字面量2。核心关系总结Lexer负责“认字”产出 Tokens。Parser负责“组词造句”根据语法规则消费 Tokens产出 AST。AST是源代码逻辑结构的“地图”是后续所有操作如解释执行、代码转换、优化的基础。理解了这三者的分工与合作我们就有了清晰的实现路线图。3. 环境准备与前置条件我们将使用Python来实现这个微型语言处理器。选择 Python 是因为其语法简洁能让我们专注于逻辑本身而非复杂的类型系统或编译流程。任何高于 Python 3.6 的版本均可。你需要准备一台安装有 Python 的电脑Windows, macOS, Linux 均可。一个文本编辑器或 IDE如 VS Code, PyCharm。一个终端命令行窗口。项目结构 我们将创建三个核心文件对应三个核心模块expression_parser/ ├── lexer.py # 词法分析器 ├── parser.py # 语法分析器 └── ast_nodes.py # AST 节点定义不需要任何第三方库我们将从零构建。4. 核心流程拆解从定义 Token 到生成 AST我们的目标是解析简单的算术表达式支持整数如42变量如x,total二元运算符,-,*,/括号()用于改变优先级实现流程分为四个清晰的步骤4.1 第一步定义 Token 类型这是 Lexer 工作的依据。我们需要明确我们的语言里有哪些“单词”。4.2 第二步实现 Lexer编写一个类能够遍历输入字符串根据字符特征识别并生成对应的 Token 对象。4.3 第三步定义 AST 节点这是 Parser 的产出物也是我们后续处理程序的结构基础。我们需要定义各种语法结构对应的节点类。4.4 第四步实现 Parser编写一个类接收 Lexer 产生的 Token 流根据算术表达式的语法规则如乘除优先于加减递归地构建出完整的 AST。接下来我们进入具体的代码实现环节。5. 完整示例与代码实现5.1 定义 Token 类型 (ast_nodes.py)我们首先在ast_nodes.py中定义 Token 类型和基础的 AST 节点。虽然 Token 属于词法分析但将其定义与 AST 节点放在一起有助于理解整体结构。# 文件ast_nodes.py # 定义 Token 类型 from enum import Enum class TokenType(Enum): 词法单元类型枚举 INTEGER INTEGER # 整数如 123 IDENTIFIER IDENTIFIER # 标识符/变量名如 x, total PLUS PLUS # 加号 MINUS MINUS # 减号 - MUL MUL # 乘号 * DIV DIV # 除号 / LPAREN LPAREN # 左括号 ( RPAREN RPAREN # 右括号 ) EOF EOF # 文件结束符表示 Token 流结束 class Token: 词法单元类 def __init__(self, type_: TokenType, value: str): self.type type_ # Token 类型 self.value value # Token 的原始字符串值 def __repr__(self): return fToken({self.type}, {repr(self.value)})5.2 实现 Lexer (lexer.py)Lexer 的核心是一个状态机逐个读取字符根据当前字符决定生成何种 Token。# 文件lexer.py from ast_nodes 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 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() return 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.isalpha() or self.current_char _: return Token(TokenType.IDENTIFIER, self.identifier()) # 识别运算符和括号 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() # 所有字符处理完毕返回 EOF Token return Token(TokenType.EOF, )关键逻辑解释advance()方法像指针一样向前移动。skip_whitespace()确保 Lexer 忽略格式字符。integer()和identifier()方法会连续读取多个字符直到遇到非数字或非标识符字符这解决了多位整数和长变量名的问题。get_next_token()是主循环根据当前字符的特征返回对应的 Token。5.3 定义 AST 节点 (ast_nodes.py续)现在我们在ast_nodes.py中补充 AST 节点的定义。我们将定义两种节点表示数字/变量的叶子节点和表示二元运算的内部节点。# 文件ast_nodes.py (续) # 定义 AST 节点类 class ASTNode: 所有 AST 节点的基类 pass class Number(ASTNode): 数字字面量节点如 42 def __init__(self, token: Token): self.token token self.value int(token.value) # 将字符串转换为整数 def __repr__(self): return fNumber({self.value}) class Identifier(ASTNode): 标识符/变量节点如 x def __init__(self, token: Token): self.token token self.name token.value def __repr__(self): return fIdentifier({self.name}) class BinOp(ASTNode): 二元运算节点如 a b, c * d def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left left # 左表达式节点 self.op op # 运算符 Token (PLUS, MINUS, MUL, DIV) self.right right # 右表达式节点 def __repr__(self): return fBinOp({self.left}, {self.op.type}, {self.right})5.4 实现 Parser (parser.py)Parser 的实现是核心它需要理解运算符优先级和结合性。我们使用经典的递归下降解析法并为每种优先级层次定义一个方法。算术表达式的典型优先级是括号() 乘除* / 加减 -。# 文件parser.py from ast_nodes import TokenType, Number, Identifier, BinOp from lexer import Lexer 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): 解析最高优先级的因子整数、变量或括号表达式 token self.current_token if token.type TokenType.INTEGER: self.eat(TokenType.INTEGER) return Number(token) elif token.type TokenType.IDENTIFIER: self.eat(TokenType.IDENTIFIER) return Identifier(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): 解析乘除运算项优先级高于加减 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): 解析表达式加减运算优先级最低 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()关键逻辑解释factor(): 处理最基本的单元数字、变量、括号表达式。遇到括号时它递归调用expr()这实现了优先级的提升。term(): 处理乘法和除法。它先调用factor()获取左操作数然后循环检查后面是否跟着*或/如果是就继续获取右操作数并构建BinOp节点。这实现了乘除运算符的左结合性如a * b / c被正确解析为((a * b) / c)。expr(): 处理加法和减法逻辑与term()类似但优先级最低。它调用term()来确保乘除被优先组合。parse(): 是解析的起点。递归下降的精髓每个方法负责解析语法规则中的一个非终结符。高层方法如expr调用低层方法如term低层方法调用更底层的方法如factor从而自然地实现了运算符优先级。6. 运行结果与效果验证让我们创建一个主程序来测试整个流程。我们将编写一个简单的“解释器”它遍历 AST 并计算表达式的值假设变量已预先定义。# 文件main.py from lexer import Lexer from parser import Parser from ast_nodes import BinOp, Number, Identifier class Interpreter: 一个简单的 AST 解释器用于验证 def __init__(self, variable_mapNone): # variable_map 用于存储变量的值例如 {x: 5} self.variable_map variable_map or {} def visit(self, node): 访问 AST 节点的入口方法 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_Number(self, node): return node.value def visit_Identifier(self, node): if node.name in self.variable_map: return self.variable_map[node.name] else: raise Exception(fUndefined variable: {node.name}) def visit_BinOp(self, node): left_val self.visit(node.left) right_val self.visit(node.right) if node.op.type PLUS: return left_val right_val elif node.op.type MINUS: return left_val - right_val elif node.op.type MUL: return left_val * right_val elif node.op.type DIV: return left_val / right_val else: raise Exception(Invalid operator) def main(): # 测试用例 test_expressions [ 1 2, 3 * 4 5, 10 - 2 * 3, (10 - 2) * 3, a b * 2, ] # 定义变量值 variable_map {a: 5, b: 3} for expr in test_expressions: print(f\n解析表达式: {expr}) try: # 1. 词法分析 lexer Lexer(expr) print(f Tokens: , end) # 为了演示打印所有 Token lexer_for_display Lexer(expr) token lexer_for_display.get_next_token() while token.type.name ! EOF: print(token, end ) token lexer_for_display.get_next_token() print() # 2. 语法分析 parser Parser(Lexer(expr)) # 重新创建 Lexer ast parser.parse() print(f AST: {ast}) # 3. 解释执行 interpreter Interpreter(variable_map) result interpreter.visit(ast) print(f 结果: {result}) except Exception as e: print(f 错误: {e}) if __name__ __main__: main()如何运行与验证确保所有文件 (ast_nodes.py,lexer.py,parser.py,main.py) 在同一目录下。在终端中切换到该目录运行python main.py观察输出。预期输出示例解析表达式: 1 2 Tokens: Token(TokenType.INTEGER, 1) Token(TokenType.PLUS, ) Token(TokenType.INTEGER, 2) AST: BinOp(Number(1), PLUS, Number(2)) 结果: 3 解析表达式: 3 * 4 5 Tokens: Token(TokenType.INTEGER, 3) Token(TokenType.MUL, *) Token(TokenType.INTEGER, 4) Token(TokenType.PLUS, ) Token(TokenType.INTEGER, 5) AST: BinOp(BinOp(Number(3), MUL, Number(4)), PLUS, Number(5)) 结果: 17 解析表达式: 10 - 2 * 3 Tokens: Token(TokenType.INTEGER, 10) Token(TokenType.MINUS, -) Token(TokenType.INTEGER, 2) Token(TokenType.MUL, *) Token(TokenType.INTEGER, 3) AST: BinOp(Number(10), MINUS, BinOp(Number(2), MUL, Number(3))) 结果: 4 解析表达式: (10 - 2) * 3 Tokens: Token(TokenType.LPAREN, () Token(TokenType.INTEGER, 10) Token(TokenType.MINUS, -) Token(TokenType.INTEGER, 2) Token(TokenType.RPAREN, )) Token(TokenType.MUL, *) Token(TokenType.INTEGER, 3) AST: BinOp(BinOp(Number(10), MINUS, Number(2)), MUL, Number(3)) 结果: 24 解析表达式: a b * 2 Tokens: Token(TokenType.IDENTIFIER, a) Token(TokenType.PLUS, ) Token(TokenType.IDENTIFIER, b) Token(TokenType.MUL, *) Token(TokenType.INTEGER, 2) AST: BinOp(Identifier(a), PLUS, BinOp(Identifier(b), MUL, Number(2))) 结果: 11验证成功的关键点Token 序列正确空格被忽略数字、变量、运算符、括号被正确识别。AST 结构正确*的节点在树中比或-的节点更深体现了更高的优先级。括号()改变了默认的优先级使得10 - 2先被组合。计算结果正确解释器按照 AST 的结构正确计算出了表达式的值。7. 常见问题与排查思路在实现和扩展此类解析器时你可能会遇到以下典型问题问题现象可能原因排查方式解决方案Exception: Invalid character输入字符串中包含 Lexer 未定义的字符如$,,。检查 Lexer 的get_next_token方法看是否对所有可能字符都进行了处理。在错误处打印self.current_char。1. 清理输入。2. 在 Lexer 中增加对新字符类型的识别逻辑如果需要。Exception: Invalid syntax1. Token 流不符合语法规则。2. Parser 期望的 Token 类型与实际不符。1. 在 Parser 的error()方法中打印self.current_token。2. 检查表达式是否合法如括号不匹配、运算符缺失操作数。1. 检查输入表达式语法。2. 调试 Parser 的eat()方法调用确认当前 Token 状态。多位数如123被解析成多个单数字 TokenLexer 的integer()方法逻辑有误没有连续读取数字。在integer()方法中添加打印语句查看循环条件。确保while循环条件是self.current_char.isdigit()并在循环内调用self.advance()。运算符优先级错误如12*3算成9Parser 的优先级处理逻辑错误。expr和term的调用关系不对。打印生成的 AST观察树形结构。乘法节点*是否比加法节点更深确保expr()调用term()term()调用factor()。这是实现优先级的标准递归下降模式。括号不起作用Parser 的factor()方法中处理LPAREN的逻辑有误没有正确递归调用expr()。在factor()中遇到LPAREN时打印调试信息确认是否进入了该分支。确保factor()在遇到(时调用self.expr()解析括号内的表达式并消费对应的)。解释器报Undefined variable变量名不在传入的variable_map字典中。检查main.py中Interpreter初始化时的variable_map参数。确保为表达式中出现的所有变量在variable_map中提供值。8. 最佳实践与工程建议当你掌握了基础实现后以下建议能帮助你构建更健壮、更实用的语言处理工具分离关注点正如我们做的将 Lexer、Parser、AST 节点、解释器/编译器分离。这使代码更清晰易于测试和扩展。未来可以轻松替换 Lexer如支持更多 Token 类型或 Parser如改用其他算法而不影响其他部分。完善的错误处理与报告目前的error()方法过于简单。生产级工具需要记录位置信息在Token和ASTNode中增加lineno行号和col_offset列偏移字段在 Lexer 中维护它们。友好的错误信息提示期望什么 Token实际得到了什么 Token以及出错位置。例如SyntaxError at line 1, column 7: Expected ) after expression, but got 。支持更复杂的语法一元运算符如-5、!flag。需要在factor()方法前增加unary()方法处理。函数调用如max(a, b)。可以扩展factor()来识别标识符后的(。赋值语句如x 1 2。这需要引入新的语法规则和 AST 节点如Assign。控制流如if-else、while。这需要定义语句Statement和表达式Expression的区分。使用生成器或迭代器优化 Lexer目前的 Lexer 是“拉取”模式每次调用get_next_token。可以将其改为生成器一次性产出所有 Token便于调试和回溯。引入 Visitor 模式遍历 AST我们的解释器使用了简单的visit_方法分发。对于复杂的 AST 操作类型检查、代码优化、多后端代码生成标准的Visitor 模式是更优雅的选择。它允许你在不修改 AST 节点类的情况下定义多种操作。编写全面的测试用例覆盖各种边界情况空输入。单个数字/变量。复杂的嵌套括号。非法字符和语法错误。运算符结合性如a - b - c应为左结合。考虑性能与内存对于大规模源码文件一次性将整个文件读入内存可能不合适。Lexer 可以按需从流中读取。对于极其复杂的语言递归下降解析器可能栈溢出此时需要考虑迭代算法或 Parser 生成器如 ANTLR, Lark。9. 总结与后续学习方向通过这个从零实现的微型算术表达式解析器我们完整走过了现代编程语言处理器的核心前端流程源代码 - (Lexer) - Token流 - (Parser) - AST。你不再需要将“词法分析”、“语法分析”视为黑盒。你亲手实现了状态机去识别单词用递归函数去构建语法树。本文的核心价值在于祛魅将编译原理中看似高深的概念拆解为可理解的、可运行的代码。提供蓝图你获得了构建更复杂解析器的基本模式和信心。无论是解析 SQL 片段、配置文件还是自定义查询语言核心模式都是相通的。理解工具链你现在再看 Babel、ESLint、Prettier 等工具会明白它们首先必须将代码解析为 AST然后才能进行转换、检查或格式化。如果你想继续深入可以沿着以下方向探索扩展语言功能尝试实现变量赋值、比较运算、逻辑运算、函数定义与调用。每增加一个特性都是对 Parser 和 AST 设计的一次很好练习。实现一个真正的解释器为你的 AST 实现一个完整的解释执行环境包括变量作用域、函数调用栈、内置函数等。学习 Parser 生成器研究像LarkPython或ANTLR多语言这样的工具。它们允许你用一种更高级的“语法描述语言”EBNF来定义语法并自动生成 Lexer 和 Parser。这能极大提升开发效率。研究真实项目的 AST使用 Python 的ast模块解析 Python 代码或使用 JavaScript 的babel/parser来查看 JS 代码的 AST 结构。直观感受工业级 AST 的复杂与强大。动手实践找一个具体的需求比如为公司内部系统设计一个简单的报表过滤条件语言并用今天学到的知识去实现它。这是将知识转化为价值的最短路径。理解 Lexer、Parser 和 AST是你从“代码使用者”迈向“工具创造者”的关键一步。建议你将本文的代码保存下来作为未来相关项目的起点和参考。当你下次需要解析任何结构化文本时你知道该从哪里开始了。