麻婆豆腐 - 解析器
type: channel
link: https://blog.mapotofu.cn/tag/%E8%A7%A3%E6%9E%90%E5%99%A8/
items: 通过AST语法树解析来实现一个简易的表达式求值器

通过AST语法树解析来实现一个简易的表达式求值器
type: item
date: 2026-04-07T18:01:00+08:00
description: 最近工作中需要搞一个简易的规则引擎，在翻了Github之后发现了danthedeckie/simpleeval这个库，用起来挺方便的，不过在查阅源码后发现，simpleeval原理是复用Python的ast库来解析计算的，依赖于Python语法，通过构建一个安全沙箱来隔离运行的。不过在工作业务中，考虑到后续极有可能有自定义语法的需求，所以想来想去，还是写一个简单的解析器比较合适。代码将基于Python实现。业务需求求值器需要支持以下能力：大小比较：整数、小数、负数的大小比较。布尔运算：and 、or 、... 这种逻辑运算。字符串比较：对字符串的“==”比较运算优先级：需支持括号优先计算。变量传入：需支持传入变量代入计算。整体架构整个求值器分为三个模块：词法解析器（Tokenizer）：将 expr 表达式字符串拆解成 Token 序列。语法解析器（Parser）：根据 Token 序列构建 AST。求值器（Evaluator）：递归遍历 AST，结合变量上下文 (names) 计算出最终布尔值。expr字符串 → Token列表 → AST → 求值结果词法解析词法解析器的输入是原始表达式 expr 字符串，输出是带有类型和值的 Token 列表。根据业务需求，在这里需要识别：关键字：and、or、not、True、False变量名：以字母或下划线开头，后跟字母、数字或下划线数字：支持整数、浮点数、科学计数法，以及合法的负数字符串：以双引号""包裹的字符串运算符：>、>=、<、<=、==括号：(、)其中，负数的处理需要特殊判断，避免与减号混淆（不过目前还不支持减法运算，因此单独的负号仅在表达式开头或运算符后出现时才被解析为数字的一部分）。核心部分代码：def tokenize(text: str) -> list[Token]: tokens = [] i = 0 while i < len(text): ch = text[i] if ch.isspace(): i += 1 continue # 识别标识符和关键字 if ch.isalpha() or ch == '_': # ... 收集并判断关键字 # 识别数字（含负数、科学计数法） if ch.isdigit() or (ch == '-' and 合法位置): # ... 收集数字字面量 # 识别字符串 if ch == '"': # ... 收集字符串字面量 # 识别运算符、括号等 # ... return tokens词法解析器最终返回一个 Tokens 列表语法解析语法解析器采用递归下降方法，根据运算符优先级定义解析函数（优先级从低到高）：优先级运算符解析函数最低or_parse_or and_parse_and not_parse_not 比较运算_parse_compare最高括号 / 原子项_parse_term每个解析函数会消费与之匹配的 Token，然后返回对应的 AST 节点。AST 节点类型（使用 dataclass 定义）：Constant：布尔值、数字、字符串Name：变量引用BoolOp：and / or 运算，包含多个子节点UnaryOp：not 运算Compare：两两比较运算（如 a > b）例如，表达式 not temperature >= 18.03 and state == "active" 生成的 AST 大概长下面这个样子：BoolOp(op=AND) ├── UnaryOp(op=NOT) │ └── Compare(left=Name('temperature'), op=GTE, right=Constant(18.03)) └── Compare(left=Name('state'), op=EQ, right=Constant("active"))求值器求值函数 eval_ast(node, names) 通过递归计算AST来，根据节点类型进行求值：Constant：直接返回值Name：从 names 字典中查找变量值，未定义则抛出 NameErrorBoolOp：短路求值（and 遇到 False 立即返回，or 遇到 True 立即返回）UnaryOp：对操作数取反Compare：比较左右子节点的值，返回布尔结果最后暴露一个便捷函数 evaluate_expression(text, names) 完成解析+求值。测试基础测试：让AI写了一段测试代码和少量测试用例，测试输出结果如下： 性能测试同样让AI写了一段与simpleeval对比的测试代码，上面一段是simpleeval，下面是我写的eval： 完整代码from dataclasses import dataclass class ParseErro…