标题里的 rea是我最近在本地捣鼓一个内部小工具时随手起的代号全称是 Readable Expression Analyzer。它要干的事情很简单给定一串像3 5 * (2 - 1)这样的文本算式程序自己把字符串拆开、理解结构、算出结果。听起来毫不起眼但做起来会牵出一整条编译原理的极简链路——词法分析、语法分析、抽象语法树、递归求值每一步都能单独拿出来讲。这个项目特别适合想搞懂程序怎么理解公式的人也适合那些想给脚本、编辑器或后台配置加上公式输入框功能的朋友参考。今天就把这整套实现和踩坑过程完整扒开。1. 为什么我会写一个叫 rea 的解析小工具1.1 需求从哪来的起因是某次要给模拟项目X做一套轻量级的计算规则配置。业务方提了个需求希望后台能录入类似(基础价 * 折扣) 运费这样的算式系统要能读懂它并且用真实数据把结果算出来。第一反应当然是直接调 eval 不就行了但深入想一下就会发现这条路在一个需要长期维护、还要经常加变量的系统里走不通。如果公式里只有固定数字eval 确实够快。可业务方不可能一直写死数字他们想用price、rate、shipping这种变量。更进一步未来大概率还要支持round(price * rate, 2)这种函数调用。eval 能写字面量但一旦把变量名安全地替换进去等于把一个用户输入字符串直接交给脚本解释器执行这风险不是一句内网系统没关系就能带过的。我需要的是只计算算式结构不执行任意脚本的能力所以只能自己实现一个解析器。1.2 为什么不用系统自带的 evaleval 的问题不是它不能算而是它能算的东西太多。用户输入一个os字符串eval 就能把整个运行环境的上下文摸一遍。哪怕把可用符号砍到只剩数学运算符和变量只要某个环节漏掉一个名字就可能出现不可控行为。显然我的场景不要求算式语言再强大只需要数字、变量、四则运算、括号、小数点和少量函数。与其时刻提防 eval 的超能力不如从源头定义一个极小的安全子集。而且 eval 的另一个隐性问题是错误信息不可读。用户写了3 * 5eval 给出来的报错往往是invalid syntax这种对着干的话用户根本不知道错在哪个位置。自己写解析器我可以精确到在 token 的第 7 个字符附近期望一个数字但没有找到这种提示这对上层产品体验来说差别非常大。rea 这个名字也就是这个时候定下来的我要做一个可读的表达式分析器输出不仅是一个数值还有清晰的错误信息。1.3 项目代号 rea 到底在干什么rea 的整体流程可以用一条线串起来输入字符串先切成 token这是词法分析再把 token 按语法规则组装成 AST这是语法分析最后遍历 AST 求值。三步之间各自独立每一层都能单独测试。后面我会分别拆开讲并且把最容易踩的坑标出来。设计目标我记得很清楚只允许数字、变量、四则运算、括号和有限函数错误信息必须包含位置和原因核心逻辑不依赖任何第三方库全部手写整体代码控制在几百行以内别人拿去能直接读懂。下面开始逐步实现。2. 第一步把算式拆成一个个词素2.1 Token 类型设计词法分析的目的是把3 5 * (2 - 1)这种字符串变成有含义的 token 序列。可以先定一张词法表Token 类型示例说明NUMBER3、2.5、0.1整数和小数IDENTprice、round变量名或函数名OP、-、*、/四则运算LPAR / RPAR(、)左右括号COMMA,未来支持多参数函数NEG一元负号表示-3里的负号而不是减号这里有个关键区分也是新手最容易踩的第一个坑-在表达式里有两种身份。3 - 2中的-是二元减号-3或2 * -3中的-是一元负号。如果不在词法阶段把它们区分开后面语法分析会非常别扭。判断办法很简单看前一个 token。如果-出现在表达式开头或者前一个 token 是运算符、左括号、逗号那它就是一元负号否则就是二元减号。比如2 * -3中-前面是*所以是 NEG3 - 2中-前面是数字3所以是二元减号。2.2 词法分析器实现我用的 Python代码不复杂但每一处注释都有原因# token.py import re TOKEN_SPEC [ (NUMBER, r\d(\.\d)?), # 整数和小数 (IDENT, r[A-Za-z_][A-Za-z0-9_]*), # 变量名和函数名 (OP, r[\-*/]), # 四则运算符 (LPAR, r\(), (RPAR, r\)), (COMMA, r,), (WS, r\s), # 空白符直接跳过 ] def tokenize(text): tokens [] pos 0 prev None # 记录前一个 token用于区分负号和减号 while pos len(text): match None for name, pattern in TOKEN_SPEC: m re.match(pattern, text[pos:]) if m: match (name, m.group()) break if not match: raise SyntaxError(f位置 {pos}: 无法识别的字符 {text[pos]!r}) name, value match pos len(value) if name WS: continue if name OP and value -: # 如果前一个 token 不存在或者是 运算符/左括号/逗号 # 那么这个 - 应该当成一元负号 NEG if prev is None or prev[0] in (OP, LPAR, COMMA, NEG): name NEG tokens.append((name, value)) prev (name, value) # 补一个表示结束的 token方便后面 parser 判断 tokens.append((EOF, )) return tokens这套写法的优点是把空白符的处理放到正则循环里代码不需要手动判断空格。我在本地测试的时候因为偷懒没给负数加这个逻辑结果3 * -2一直解析成3 * (- 2)然后报错。加上 NEG 类型后一下就顺了。2.3 容易被忽略的空白与负号还有一个坑是浮点数。正则\d(\.\d)?看着正常但它不允许.5这样的写法也不允许1.这种实际用户公式里很少这样写所以我可以接受。但如果想做得更宽容可以把正则改成(?:\d\.\d|\d|\.\d)匹配顺序要放对否则1.5会被切成1和.5两个 token。建议从一开始就把正则写好这个我改过好几轮。另一个容易翻车的是多位数和小数点后的精度。词法分析阶段只负责切分不做任何数值转换。真正的 float 转换放到求值阶段这样 token 流里的编号始终保留原始文本调试时能看到用户到底输入了什么。词法这层完成后建议立刻写几个简单断言比如tokenize(2 * -3)应该得到[NUMBER(2), OP(*), NEG, NUMBER(3)]。这一步过了再往下走会省掉大量排错时间。3. 让乘除先算、括号最优先从调度场到递归下降的 AST 构建3.1 中缀、后缀与抽象语法树人眼习惯的1 2 * 3是中缀表达式乘法优先级高。程序有两种办法理解它一种是把中缀转成后缀再算另一种是直接根据优先级规则递归下降构建语法树。两种办法最终都会形成一棵树比如1 2 * 3的 AST 根节点应该是左子树是1右子树是*节点*的左子树是2右子树是3。只有遵循这个结构求值的时候才能先算2*3再算16。AST 是结果而生成 AST 的过程才是真正要花心思的地方。业界最常提的算法是调度场算法它用两个栈把中缀表达式转成后缀表达式RPN再由后缀表达式生成树。我的 rea 一开始就是用调度场写的因为这是教科书里的经典方案讲起来很唬人。但实际写完发现当功能扩展到函数调用、一元负号、多参数函数时调度场的规则会变得越来越繁琐容易在各种优先级边界上翻车。3.2 调度场算法一分钟理解调度场算法的核心规则不复杂遇到数字直接输出到结果列表。遇到运算符把栈顶优先级不低于当前运算符的运算符弹出到结果列表然后自己入栈。遇到左括号直接入栈。遇到右括号一直弹出到左括号为止。对于1 2 * 3输出的 RPN 是1 2 3 * 。求值时从左到右遍历先压1、2碰到*弹两个数算出6压回去再碰到弹出1和6得到7。我一直觉得调度场是很聪明的算法但它把优先级、结合性、括号、单目运算符全揉在一个循环里每加一个新特性就要反复推敲弹栈条件。比如一元负号的右结合性处理和常规二元运算符不同我在这一块花掉了整个下午。3.3 主递归下降 parser 实现后面我推倒重来换成了递归下降解析代码反而更贴近自然的语法描述。递归下降的核心是几个互相调用的函数每个函数对应一个语法层级。规则可以写成这样expr : term (( | -) term)* term : unary ((* | /) unary)* unary : (- | ) unary | factor factor : NUMBER | IDENT | IDENT ( args ) | ( expr ) args : expr (, expr)* | ε这种写法的好处是乘法优先级天然被term 调用 unary这个层级保证不需要显式去定义优先级数字。遇到函数调用时就在 factor 层判断标识符后面有没有左括号有就解析参数列表没有就当成变量名。每个函数都短小清晰。# parser.py from token import tokenize class ASTNode: __slots__ (type, value, children) def __init__(self, type_, valueNone, childrenNone): self.type type_ self.value value self.children children or [] def __repr__(self): return fASTNode({self.type}, {self.value!r}, {self.children!r}) class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def consume(self, expect_typeNone): t self.peek() if expect_type and t[0] ! expect_type: raise SyntaxError(f位置 {self.pos}: 期望 {expect_type}得到 {t[0]}) self.pos 1 return t def parse(self): node self.expr() if self.peek()[0] ! EOF: raise SyntaxError(f位置 {self.pos}: 有多余的 token {self.peek()}) return node def expr(self): node self.term() while self.peek()[0] OP and self.peek()[1] in (, -): op self.consume()[1] right self.term() node ASTNode(BINOP, op, [node, right]) return node def term(self): node self.unary() while self.peek()[0] OP and self.peek()[1] in (*, /): op self.consume()[1] right self.unary() node ASTNode(BINOP, op, [node, right]) return node def unary(self): if self.peek()[0] NEG: self.consume() return ASTNode(NEG, -, [self.unary()]) return self.factor() def factor(self): t self.peek() if t[0] NUMBER: self.consume() return ASTNode(NUMBER, float(t[1])) if t[0] IDENT: _, name self.consume() if self.peek()[0] LPAR: # 函数调用 self.consume(LPAR) args [] if self.peek()[0] ! RPAR: args.append(self.expr()) while self.peek()[0] COMMA: self.consume() args.append(self.expr()) self.consume(RPAR) return ASTNode(CALL, name, args) return ASTNode(VAR, name) if t[0] LPAR: self.consume() node self.expr() self.consume(RPAR) return node raise SyntaxError(f位置 {self.pos}: 期望数字、变量或左括号得到 {t})这个实现虽然行数不多但已经能处理四则运算、负号、变量、单参数和多参数函数调用。调试的时候最舒服的一点是expr、term、unary之间的递归调用顺序直接对应运算优先级出错时看调用栈就知道是哪一层出了问题。3.4 为什么我最终选了递归下降而不是调度场调度场和递归下降不是谁绝对优于谁要看扩展方向。如果你的表达式只做经典四则运算调度场代码量甚至更小而且天然可以直接在生成 RPN 的同时求值不需要 AST。可我的实际需求是后面还要不断加功能变量的存在、函数参数列表、一元负号每一个新增特性都让递归下降的重构成本明显低于调度场。递归下降也并非没有弱点它对括号的匹配处理依赖函数嵌套如果式子特别长几千层括号递归深度可能撞上 Python 的递归保护。但这种极端输入本来就该被当作异常拒绝。权衡下来递归下降带来的直观性、可测试性和易扩展性对 rea 这个项目来说是更合适的选择。4. 从 AST 到答案求值器的实现4.1 递归遍历 ASTAST 构建完毕求值变得非常简单因为节点类型已经覆盖了所有可能出现的语法结构。求值器只需要按节点类型分派# evaluator.py def evaluate(node, env): if node.type NUMBER: return node.value if node.type VAR: if node.value in env: return env[node.value] raise KeyError(f未知变量: {node.value}) if node.type BINOP: left evaluate(node.children[0], env) right evaluate(node.children[1], env) if node.value : return left right if node.value -: return left - right if node.value *: return left * right if node.value /: return left / right raise ValueError(f未知二元运算符: {node.value}) if node.type NEG: return -evaluate(node.children[0], env) if node.type CALL: args [evaluate(child, env) for child in node.children] return call_function(node.value, args) raise ValueError(f未知节点类型: {node.type})递归在这里的体验和语法分析完全一致。遇到二元运算先算左边再算右边然后用运算符合并遇到变量就去环境字典取值遇到函数调用就先算完参数再交给函数分发表。整个代码几乎不需要注释因为结构本身就是自解释的。4.2 错误处理策略求值阶段最常见的异常是除零、未知变量、函数参数数量不匹配。我决定不在 evaluator 内部强行捕获所有异常而是让异常向上冒泡到调用 controller由 controller 统一转换成用户可读的错误。这样做的原因是想让底层保持纯粹只关心数学计算至于这个错误该用什么文案提示属于上层产品逻辑。我实际在 controller 层做了这样一件事捕获ZeroDivisionError、KeyError、ValueError然后拼上当前算式的上下文。比如KeyError(未知变量: price)会变成第 8 个 token 附近引用了变量 price但当前参数里没有提供。定位到 token 位置需要 parser 在构造 AST 时给节点记录位置信息这个改造我在第二版才加上非常值得因为用户看到错误提示后几乎不需要再解释。4.3 精度问题数学上 0.1 0.2 不等于 0.3这是所有用二进制浮点数的语言都绕不开的问题。rea 刚跑通时用户反馈为什么 0.1 0.2 显示 0.30000000000000004我以为是自己解析写错了排查半天才发现是浮点表示问题。解决方案不是把所有数换成decimal因为性能和复杂度会上升。我的做法是计算结果在返回之前做一次格式化保留小数点后 10 位再去掉末尾多余的 0。日常金额计算一般够用如果将来需求是真的要记账精度再考虑全局切换decimal。这里贴一下格式化函数简单但很实用def format_result(value): if isinstance(value, float): return round(value, 10) return valueround(value, 10)不会完全消除浮点误差但能把 0.30000000000000004 收敛到 0.3对绝大多数展示场景已经足够。要说明的是round 之后再参与后续计算仍然会有误差累积好在 rea 只负责单次算式求值不是长链条累加这个方案稳得很。5. 从能算到好用变量、函数与安全边界5.1 变量替换变量支持是 rea 第一版就有的功能因为业务方明确要求用price、rate这样的名字写公式。实现上就是在 evaluator 里读取环境字典 env。调用方只需要这样env {price: 100, rate: 0.8, shipping: 10} result evaluate(ast, env)这里有个容易被忽略的细节变量名在词法阶段是和函数名混在一起的ID token 不一定代表变量。我的做法是让 parser 遇到 IDENT 时往后多看一个 token如果是(就按函数调用解析否则按变量解析。这样变量和函数可以在同一个表达式里共存用户写subtotal * rate和round(subtotal * rate, 2)都没有问题。5.2 内置函数扩展函数支持是通过一个分发表做的这比写一堆 if/elif 要干净得多FUNCTIONS { round: lambda args: round(args[0], int(args[1])), min: min, max: max, abs: abs, } def call_function(name, args): if name not in FUNCTIONS: raise ValueError(f未知函数: {name}) return FUNCTIONS[name](args)这里需要仔细处理函数参数的个数校验。比如round要求两个参数用户写了round(1.234)就要给出明确报错。我在 call_function 里检查了每个函数的 arity比直接调用然后等 Python 抛 TypeError 更友好。更讲究一点的实现会把变量参数和关键字参数也纳入类型系统但 rea 目前只是一个极简公式引擎分发表已经够用。5.3 安全性为什么不用 eval 也不怕注入一开始我就否定了 eval。现在有了 tokenizer、parser、evaluator 三层整个输入的处理路径里没有任何一个环节会去执行输入字符串本身。变量名只能在 env 字典里取值函数名只能在 FUNCTIONS 分发表里找到其他所有字符串都只会被当作位置错误或其他语法错误处理。换句话说用户能做的事情被限制在一个非常明确的边界内这从设计上根本杜绝了通过公式注入代码的风险。我后来还加了一个 token 数量上限和递归深度上限防止有人扔一个上万字符、几千层括号的表达式把服务打爆。这只是防御性编程但对任何可能面向用户输入的工具来说都很值得。rea 即使后来被部署到某个 HTTP 服务里我也只需要在外面包一层超时和长度限制就够了。6. 实测中最容易翻车的三个 case 与调试技巧6.1 三个实测边界用例我把开发过程中让我印象最深的三个 case 列出来。它们都不是复杂的数学问题但每一个都曾经让我对着代码愣了半天输入期望结果最初实现的问题2 * -3-6词法阶段没区分一元负号和二元减号parser 直接报语法错误(1 2) * (3 4))应该报错多了一个右括号程序却没有把它识别成位置错误1 / 0应返回除数为零当时直接抛了 ZeroDivisionError用户看到的是 Python 原始报错括号不匹配这个 case 值得多说一句。第一版实现里我在全部 token 解析完后只看栈是否为空没有精确记录是哪一只右括号多了。改进后的办法是右括号出现时如果栈里没有对应的左括号就立刻抛异常并带上当前位置。这个错误提示一下子从语法错误变成了位置 X 附近有一个多余的 )。对于不懂技术栈的用户来说这两句话的天壤之别做过产品的人应该都懂。6.2 调试工具把 token 流和 AST 打印出来整个开发过程里最有用的调试工具不是调试器而是两组打印函数。第一组打印 token 流第二组打印 AST。AST 打印的代码可以这样写def print_ast(node, indent0): prefix * indent if node.type in (NUMBER, VAR): print(f{prefix}{node.type}: {node.value}) elif node.type BINOP: print(f{prefix}{node.value}) for child in node.children: print_ast(child, indent 1) else: print(f{prefix}{node.type} ({node.value})) for child in node.children: print_ast(child, indent 1)打印出来长这样BINOP: NUMBER: 1.0 BINOP: * NUMBER: 2.0 NUMBER: 3.0这棵树的每一层都对应着运算优先级。只要看到 AST 的结构和人的直观判断一致就能确定语法分析没错。如果结果不对再看 evaluator 怎么遍历它。这种可视化中间产物的调试方式比到处打印中间变量要高效得多尤其是表达式比较复杂的时候。6.3 给后来者的一句话经验我现在已经形成了一套习惯任何用户输入的表达式先打印一遍 token 流确认词法层没问题再打印 AST确认语法层没问题最后才去怀疑求值逻辑。这个顺序看起来多此一举但能避免大量症状在求值、病根在词法的迷惑场景。如果你也在写类似的小工具强烈建议把 token 和 AST 的打印做成一个命令行调试入口你会发现排查速度提升非常明显。rea 这个项目没有用到任何高深理论核心就是词法分析、递归下降、AST 求值这三板斧。但正是这种小项目让我把编译原理里最基础的概念在真实场景里完整过了一遍也让我对什么情况该用什么解析策略有了更踏实的判断。它现在还在我的工具链里待着后续想给它加上科学计数法和更友好的错误定位不过那是下一个故事了。
