从零手写表达式求值器：词法分析、递归下降与AST实战-嵌云网-嵌入式AI开发资源站

从零手写表达式求值器：词法分析、递归下降与AST实战

Wong Kosheng·2026-10-14·阅读 24 GEO检测（免费）

表达式求值词法分析递归下降

|难度：普通|阅读约 22 分钟

从给某后台系统做“公式规则配置”功能说起吧——运营人员要在输入框里写 (单价 - 成本) * 数量 > 1000 这种条件，我需要一个可靠的表达式求值模块。当时第一反应是直接用语言内置的 eval 一把梭，可真落地才发现，表达式求值这种事，一旦涉及变量替换、函数调用、错误定位、执行边界，eval 根本撑不住。后来我花了几天时间，从零手写了一个支持四则运算、括号、变量和少量函数的表达式求值器，把词法分析、语法解析、求值执行整条链路完整走了一遍，收获非常大。这篇文章就把当时的选型思路、完整实现和踩坑记录都摊开来聊聊，给准备自己做公式引擎、计算器、规则引擎的开发者一个可参考的完整样本。

1. 表达式求值背后那张看不见的语法树

很多人第一次接触“表达式求值”是在数据结构课上用两个栈模拟计算器，后来工作了要做真实功能，才发现当年那套东西只是冰山一角。要真正把一个字符串变成可计算结果，背后其实是三件完全不同的事：分词、建结构、执行计算。而这三件事的核心，是那张看不见的语法树。

1.1 中缀表达式的读取逻辑：人眼和计算机完全不同

我们写的 1 + 2 * 3 叫中缀表达式，运算符在两个操作数中间。人眼扫过去会下意识按“先乘除后加减”来读，但计算机从左往右一个字符一个字符扫描时，看到 1 之后只会知道下一个是 +，它并不知道 2 * 3 是一个整体。这就是优先级带来的歧义。

我常用的类比是读菜谱：“加3勺盐和2勺糖炒2分钟”——到底先加盐再炒两分钟，还是盐糖一起下锅炒两分钟？不同解读做出来的菜完全不一样。表达式也是，1 + 2 * 3 如果按照从左到右的顺序算，结果是 9；按照数学规则先乘除后加减，结果是 7。计算机不会像人一样“看整体”，它只能靠规则消除歧义。

这些规则一共三条：

规则	含义	例子
优先级	乘除高于加减	`1 + 2 * 3` 先算乘法
结合性	同优先级从左到右	`8 / 4 / 2` 先算左边除法，结果是1
括号	括号内容优先，且最内层先算	`(1 + 2) * 3` 先算加法

所以任何表达式的求值器，本质上都是在实现这三条规则。规则越复杂（比如加幂运算、逻辑运算、函数调用），解析器就要对应地处理更多层。

1.2 表达式与抽象语法树：求值就是后序遍历

真正把歧义消除之后，表达式会变成一棵树。以 3 + 4 * 2 为例，它的语法树长这样：

code复制        +
       / \
      3   *
         / \
        4   2

根节点是最后一个被计算的运算符 +，左子树是数字 3，右子树是另一个乘法节点 4 * 2。要对这棵树求值，做法是从最底层往上：

对根节点求值前，先递归求左子树——得到 3；
再递归求右子树——右子树是乘法节点，继续求它的左右子树，得到 4 和 2；
4 * 2 = 8；
回到根节点，3 + 8 = 11。

这个过程是标准的后序遍历：先算子树，再算根节点。所以“表达式求值”这个词拆开看，前半段“表达式”的任务是把字符流变成树的结构，后半段“求值”的任务就是对树做一次后序遍历。理解这一点，后面写代码就不会乱。

1.3 求值器必须拆开的三个职责边界

我见过很多从零手写求值器的同学，喜欢把“读字符、判断优先级、执行计算”全塞在一个循环里，二三十行写完，测试的时候全是坑。因为三个职责搅在一起，任何一个环节出错，你都分不清是分词错了、结构建错了，还是计算错了。

正确的做法是明确划分三个独立阶段：

词法分析：把字符串切成一串 Token（最小的词法单元），比如数字、运算符、括号、变量名；
语法分析：根据 Token 流构建语法树（或者边分析边求值），这一步专门处理优先级和结合性；
求值执行：对语法树进行后序遍历，返回结果。

三段之间通过 Token 流和树节点这两个数据结构解耦。哪怕你后面只想要“把表达式编译成字节码”，也只需要改第三段，前两段完全不动。我做的那个求值器就是按这个边界拆的，后面扩展函数支持时，确实只在第二段和第三段加代码，第一段几乎没动过。

需要模型API调用？免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。

2. 第一关：手工词法分析，把字符串切成词

语法树是抽象的，落在代码里第一个具体工作就是词法分析。词法分析做得好不好，直接决定了解析器的代码有多难受。

2.1 Token 设计与扫描循环的实现

Token 可以理解成给“词”贴的标签。我把表达式里可能出现的东西分成几类：数字、变量名、运算符、左右括号，另外还要留一个特殊类型给“结束”标记。在 Python 里可以用枚举加一个简单类：

python复制from enum import Enum
from dataclasses import dataclass

class TokenType(Enum):
    NUMBER = "NUMBER"
    IDENT = "IDENT"      # 变量名或函数名
    PLUS = "PLUS"
    MINUS = "MINUS"
    MUL = "MUL"
    DIV = "DIV"
    LPAREN = "LPAREN"
    RPAREN = "RPAREN"
    EOF = "EOF"

@dataclass
class Token:
    type: TokenType
    value: str
    position: int

position 这个字段后来帮了我大忙。报错时能直接告诉用户“第 8 个字符附近有个非法符号”，而不是丢一句“表达式错误”。早期版本没存这个字段，运维拿一段报错来问，我只能说“你再检查检查”，非常被动。

扫描循环本身不复杂，就是一个字符一个字符往下读，根据当前字符决定要生成什么 Token：

python复制class Lexer:
    def __init__(self, text: str):
        self.text = text
        self.pos = 0
        self.length = len(text)

    def skip_whitespace(self):
        while self.pos < self.length and self.text[self.pos].isspace():
            self.pos += 1

    def next_token(self) -> Token:
        self.skip_whitespace()
        if self.pos >= self.length:
            return Token(TokenType.EOF, "", self.pos)

        ch = self.text[self.pos]

        if ch.isdigit():
            return self._read_number()

        if ch.isalpha() or ch == "_":
            return self._read_ident()

        # 运算符和括号
        mapping = {
            "+": TokenType.PLUS,
            "-": TokenType.MINUS,
            "*": TokenType.MUL,
            "/": TokenType.DIV,
            "(": TokenType.LPAREN,
            ")": TokenType.RPAREN,
        }
        if ch in mapping:
            self.pos += 1
            return Token(mapping[ch], ch, self.pos - 1)

        raise ValueError(f"无法识别的字符 '{ch}'，位于位置 {self.pos}")

    def _read_number(self):
        start = self.pos
        while self.pos < self.length and (self.text[self.pos].isdigit() or self.text[self.pos] == "."):
            self.pos += 1
        return Token(TokenType.NUMBER, self.text[start:self.pos], start)

    def _read_ident(self):
        start = self.pos
        while self.pos < self.length and (self.text[self.pos].isalnum() or self.text[self.pos] == "_"):
            self.pos += 1
        return Token(TokenType.IDENT, self.text[start:self.pos], start)

2.2 数字、变量、运算符的识别细节

_read_number 里我顺手把小数点也放进了数字的识别范围，所以 3.14 和 0.5 都能正确切出来。但这里有个隐藏问题：如果用户输入 3.14.15，这个循环会把整串都当成一个数字，到后面语法分析阶段才会因为“数字后面跟了一个不该出现的数字”而报错。这个问题我在第 5.2 小节会详细说，结论是词法阶段可以宽松，但语法阶段必须严格兜底。

变量名的识别我用的是 isalpha() 加下划线开头，后面允许字母数字下划线。这个规则照搬了大多数编程语言的命名规则。之所以允许下划线，是因为后面要支持类似 total_count 这样的变量名，运营配置里很常见。

运算符部分目前是单字符匹配，简单直接。如果你后面要支持 >=、<=、== 这类双字符运算符，就需要在读到一个字符后“向前窥探”一个字符，判断是否组成双字符运算符。我实现比较运算符时就是改成 peek() 方式，代码稍微复杂一点，但思路没变。

2.3 词法阶段最容易忽略的三个问题

词法阶段踩坑不少，我挑三个印象最深的：

第一，负数不是词法问题。-3 里这个负号，到底是“负号”还是一个“减法运算符”？我的结论是，词法阶段不要试图区分，统一都切成 MINUS，让语法分析阶段根据上下文判断。因为 -3 和 1 - 3 里的 - 本质上是同一个 Token，只在语法位置上不同。词法阶段区分一元负号和二元减号，会让 Token 类型爆炸，非常难维护。

第二，合法的“无意义空格”要静默跳过。1 + 2 和 1+2 对用户来说没有任何区别，所以空格必须在词法层丢弃，绝不能留到语法层。但我见过有人为了“保留用户输入原样”把空格也存成 Token，结果语法分析里到处都是跳过空格的逻辑，纯属自找麻烦。你可以在报错信息里保留原始的 text 和 position，展示给用户看即可。

第三，非法字符要第一时间抛异常。3 # 4 这种输入，程序很明显不知道 # 是什么。词法阶段直接抛错并带上位置信息，是最友好的做法。如果拖到语法阶段，错误信息会变得特别绕：“期望数字，但遇到非法字符”。多做一步，少被骂一次。

3. 解析路线怎么选：递归下降、调度场、后缀栈

词法分析把字符串切成了 Token 流，接下来要考虑的就是怎么处理优先级和括号。这个环节有两条主流路线，我当初对比了很久，把决策过程写出来供参考。

3.1 调度场算法：两个栈把中缀换成后缀

调度场算法是 Edsger Dijkstra 提出的，核心思路是用两个栈（一个输出栈、一个运算符栈）把中缀表达式转成后缀表达式（即逆波兰表示法）。转完之后，后缀表达式用单独的栈就能一次遍历求值，不需要再考虑括号和优先级。

以 3 + 4 * 2 为例，调度场的工作过程：

读 3，输出；读 +，压入运算符栈；
读 4，输出；读 *，因为 * 优先级高于栈顶的 +，压入运算符栈；
读 2，输出；
读完了，把运算符栈里的 *、+ 依次弹出到输出。最终后缀是 3 4 2 * +。

后缀表达式求值就简单了：遇到数字压栈，遇到运算符弹出两个数计算后压回。3 4 2 * + 的求值过程是：压 3，压 4，压 2，遇到 * 弹出 4 和 2 算出 8 压回，遇到 + 弹出 3 和 8 算出 11。

这个算法的优点是可以完全不用递归，纯迭代循环，没有递归深度问题；缺点是代码写起来对“运算符优先级比较表”的依赖很强，而且如果你想基于后缀表达式进一步生成语法树，还得加一步转换，中间结构多。

3.2 递归下降：用文法直接驱动求值

递归下降是另一种思路，本质上是把一个递归文法直接翻译成相互调用的函数。文法用 BNF 描述就是：

code复制expr   := term   (('+' | '-') term)*
term   := factor (('*' | '/') factor)*
factor := NUMBER | IDENT | '(' expr ')' | '-' factor

这个文法天生体现了优先级：expr 在最上层处理加减，term 在中间层处理乘除，factor 在最底层处理括号、数字和一元负号。括号里的 expr 又会回到最上层递归，实现“括号内优先”。

递归下降的好处是代码结构和文法一一对应，读代码就是读文法，非常直白；函数调用天然就是树的后序遍历，写起来顺。缺点是递归调用有深度上限，极端嵌套的情况可能爆栈。但实际应用里，表达式嵌套几十层已经很不常见了，而且完全可以在词法阶段设置一个最大深度限制，超过就报错。

3.3 三种方案对比与最终选型

我列个表把常见路线摆一起，方便你按自己场景判断：

方案	核心思路	优点	缺点	适合场景
调度场算法	转后缀 + 栈求值	无递归，纯迭代，效率高	结构不够直观，扩展复杂语句能力弱	简单计算器、嵌入式环境
递归下降直接求值	文法驱动，边分析边算	可读性最好，扩展性最强	有递归深度上限	表达式引擎、规则引擎
外部表达式库	引入现成第三方	开发最快	黑盒难定制，包体积、安全面不可控	对依赖不敏感的小项目

我最终选了递归下降直接求值，原因很简单：这个表达式求值器后续要一直迭代，会加函数调用、比较表达式、逻辑运算，甚至可能生成字节码。递归下降的文法结构让我每一层加功能都非常清晰，犯错概率低。效率上，亿级规模的表达式求值场景极少见，大部分业务都是几百毫秒内求几百个表达式，这点开销完全可以忽略。

4. 完整实现：支持四则运算、括号与变量的求值器

下面是把前面所有思路落地的完整代码。为了减少噪音，我把词法分析封装成独立的 Lexer，语法分析用 RecursiveDescentParser，变量环境用一个普通字典传入。

4.1 Parser 核心逻辑：一层函数管一个优先级

递归下降的核心是“每个文法层对应一个函数”。parse_expr 管加减，parse_term 管乘除，parse_factor 管最基础的因子：

python复制class RecursiveDescentParser:
    def __init__(self, lexer: Lexer, env: dict):
        self.lexer = lexer
        self.env = env
        self.current_token = self.lexer.next_token()

    def _advance(self):
        self.current_token = self.lexer.next_token()

    def _expect(self, token_type: TokenType):
        if self.current_token.type != token_type:
            raise SyntaxError(f"期望 {token_type.value}，但遇到 {self.current_token.value}，位置 {self.current_token.position}")
        value = self.current_token.value
        self._advance()
        return value

    def parse(self):
        result = self._parse_expr()
        if self.current_token.type != TokenType.EOF:
            raise SyntaxError(f"表达式结束后还有多余内容：{self.current_token.value}")
        return result

    def _parse_expr(self):
        value = self._parse_term()
        while self.current_token.type in (TokenType.PLUS, TokenType.MINUS):
            op = self.current_token.type
            self._advance()
            right = self._parse_term()
            if op == TokenType.PLUS:
                value = value + right
            else:
                value = value - right
        return value

    def _parse_term(self):
        value = self._parse_factor()
        while self.current_token.type in (TokenType.MUL, TokenType.DIV):
            op = self.current_token.type
            self._advance()
            right = self._parse_factor()
            if op == TokenType.MUL:
                value = value * right
            else:
                if right == 0:
                    raise ZeroDivisionError("除数为零")
                value = value / right
        return value

    def _parse_factor(self):
        token = self.current_token

        if token.type == TokenType.NUMBER:
            self._advance()
            return float(token.value)

        if token.type == TokenType.IDENT:
            self._advance()
            if token.value not in self.env:
                raise NameError(f"未定义变量：{token.value}")
            return self.env[token.value]

        if token.type == TokenType.LPAREN:
            self._advance()
            value = self._parse_expr()
            self._expect(TokenType.RPAREN)
            return value

        if token.type == TokenType.MINUS:
            self._advance()
            return -self._parse_factor()

        raise SyntaxError(f"无法处理的 Token：{token.value}，位置 {token.position}")

调用入口：

python复制def evaluate(expression: str, env: dict = None) -> float:
    env = env or {}
    lexer = Lexer(expression)
    parser = RecursiveDescentParser(lexer, env)
    return parser.parse()

用这个求值器测一下那几条：evaluate("3 + 4 * 2") 返回 11.0；evaluate("(3 + 4) * 2") 返回 14.0；evaluate("total - cost", {"total": 100, "cost": 30}) 返回 70.0；evaluate("-3 + 5") 返回 2.0。基本行为都正常。

4.2 直接求值还是先建 AST 再求值

上面这份代码是“边分析边求值”的直接求值模式——递归下降的同时就把结果算出来了。好处是代码量少，读了就能懂。坏处是如果后面想“先编译后执行”或者做表达式的静态分析（比如提取所有用到的变量名），就得重新解析一遍。

我实际工作中做的是先建 AST 再单独求值的模式。也就是 _parse_expr、_parse_term、_parse_factor 里不直接计算，而是返回节点对象；所有节点都建完后，再写一个独立的 evaluate(node) 做后序遍历。这样要提取变量名，只要遍历一次 AST 即可；要实现“同一个表达式重复求值一万次”，也只要第一次建好 AST，后续每次都直接遍历树求值，省掉反复解析的开销。

如果你确定自己只是做一个简单计算器，直接求值模式完全够用。但如果你隐约觉得以后项目会变大，我建议还是多花半小时改成 AST 模式，后面的日子会舒服很多。数据结构这东西，早设计永远比晚重构便宜。

4.3 变量环境、错误提示与边界防护

做真实产品的人用求值器，输入往往不是规规矩矩的。我补充了几个边界：

空表达式：用户直接传空字符串，词法分析返回的第一个 Token 就是 EOF，这时候 parse() 应该明确报“表达式为空”。
未知变量：evaluate("a + 1", {}) 会触发 NameError，报错信息里带上变量名，用户才知道自己写错了什么。
除零：_parse_term 里我已经显式检查了 right == 0，抛出 ZeroDivisionError。别小看这一步，如果没有它，Python 会抛原始异常，错误信息里不会告诉你“哪个表达式里除了零”。
多余 Token：parse() 末尾检查 EOF，确保 3 + 4 5 这种输入不会静默通过。这一点我在第 5.2 小节会专门展开。

这一步做完，这个求值器已经能应付绝大多数常规场景了。但真实的坑往往不在“常规”里，而在“你以为不会发生”的输入里。

5. 真实翻车现场：我从踩坑里学到的三件事

写表达式求值器，光能处理理想情况是不够的。我在一个内部工具里跑了一周，遇到了好几个教科书上没写的问题，逐个排查下来挺有意思。

5.1 一元负号的优先级陷阱

第一次实现 -3 + 5 之后，我顺手测了 1 - -2，结果报错。原因是我的 _parse_expr 读到第二个 - 时，会认为这是一个减法运算符，然后调用 _parse_term，而 _parse_term 里的 _parse_factor 看到 - 并没有做一元负号处理（当时我实现里没有，后来才有）。

排查思路很直接：先看 Token 流，发现 1 - -2 被切成了 NUMBER(1) MINUS MINUS NUMBER(2)。第一个 MINUS 是二元减号，第二个 MINUS 应该作为一元负号处理。所以我给 _parse_factor 加了对 MINUS 的处理：读到 MINUS 后递归调用一次 _parse_factor() 并取负。这样 1 - -2 就能正确算出 3 了。

这个坑的教训是：一元负号本质上不是“词法问题”，而是“语法问题”。它的优先级比乘除高，比括号低，所以要放在 factor 这一层，而不是 term 层。如果把一元负号的优先级放错，会出现 -2 * 3 被解释成 -(2 * 3) 还是 (-2) * 3 的差别，虽然这俩碰巧结果一样，但遇到 -2 ^ 2（如果支持幂运算）就会出大问题。

5.2 表达式结尾悄悄多了个 token

另一个翻车案例是用户输入 100 元，或者 3 + 4 5。当时的解析器跑完 expr 后直接返回，完全没有检查后面还有没有内容，所以 3 + 4 5 被“成功”计算出 7，然后 5 被静默丢弃了。这在配置系统里极其危险：运营配了个规则 单价数量，本该是 单价 * 数量，结果因为空格漏写了 *，程序就把它当成“先算单价，然后忽略数量”，得到一个完全错误的结果。

排查方式是给 parse() 结尾强制加一段校验：如果当前 Token 不是 EOF，直接抛 SyntaxError("表达式结束后还有多余内容")。这样 3 + 4 5 就会被当场抓住。这条经验后来我写所有小语言解析器都习惯性带上，非常管用。

5.3 深层嵌套与浮点数精度问题

实际线上冒出来一个怪问题：某个配置在本地怎么测都对，一到线上就报 RecursionError。查了半天发现是用户贴了一个超长的 JSON 条件，层层嵌套了很多括号。递归下降的解析器天然递归，嵌套超过默认深度（Python 里通常是几百到一千层）就会爆栈。

我解决的办法不是调大递归限制，而是在词法分析时统计括号嵌套深度，设置一个上限（比如 100 层），超过就直接报“表达式嵌套过深”。这不是偷懒，而是刻意限制：正常业务表达式嵌套超过 30 层已经极其罕见，允许无限嵌套反而容易被恶意输入攻击。

浮点数精度问题则是另一个经典。0.1 + 0.2 在绝大多数编程语言里都无法精确表示，我的求值器算出来是 0.30000000000000004。如果不需要精确十进制结果，可以在输出层做 round(result, 10) 之类的处理；如果需要精确计算，就得考虑使用十进制类型。我当时做的是尾数截断到 10 位，用户对“金额计算的 0.00000000000000004 误差”这种信息完全能接受。

6. 下一步能玩出花：从求值器到迷你脚本引擎

四则运算和变量只是起点。表达式求值器往前再走一步，就是一个微型语言的解释器。很多同学问“学这里还有什么用”，我用自己的实践路径说说可以怎么玩。

6.1 不直接求值，改成生成字节码

如果你有大量相同的表达式要重复执行（比如规则引擎里反复判断几百个订单），每次都从头解析会很浪费。更合理的做法是：第一次解析时生成字节码指令序列，之后每次执行只是拿着指令列表走一遍虚拟机栈。

以 1 + 2 * 3 为例，后序遍历这棵语法树会生成类似这样的指令：

code复制PUSH 1
PUSH 2
PUSH 3
MUL
ADD
PRINT

执行时用一个值栈：遇到 PUSH 就压栈，遇到 MUL 弹出两个数相乘后压回，遇到 ADD 同理。这个“先把表达式编译成指令，再在虚拟机上执行”的思路，是理解编译器后端的基础。我做这个扩展的时候，只改动了 AST 模式下的“执行”部分，解析器完全没动。

6.2 扩展比较、逻辑与函数调用时怎么加优先级层

真正的规则引擎不能只有算术，还得支持 and、or、>、<、== 这类运算。这时递归下降的优势就体现出来了：你只需要在文法里继续往上层加。

优先级从高到低的层级就变成了：

code复制factor        # 数字、变量、括号、一元负号
term          # * /
expr          # + -
comparison    # > < >= <= == !=
and_expr      # and
or_expr       # or

每一层对应一个新的递归函数，代码模式和 _parse_term 完全一样。我加比较运算时，把 comparison 放在 expr 之上，这样 1 + 2 > 3 就会被解析成 (1 + 2) > 3，符合直觉。逻辑运算 and、or 则放在最上层，因为 a > 1 and b < 2 里的 and 是整棵树的根。

函数调用的解析稍微麻烦点。sin(x) 在词法阶段会被切成 IDENT(sin) LPAREN IDENT(x) RPAREN。语法分析时需要判断：当前 IDENT 后面跟的是不是 LPAREN，如果是，就按函数调用解析；如果不是，就当变量解析。我实现内置函数时维护了一个函数表，挨个实现 sqrt、round、abs 等，非常快。

6.3 内置常量与函数表：让表达式真正变得可用

等到变量、比较、逻辑、函数都有了，你的表达式求值器实际上就是一个很小的领域语言解释器了。这时候我会建议加一张常量表，比如 PI = 3.14159、E = 2.71828，再提供几个常用的数学函数。

我个人的习惯是常量不放进用户传入的 env 字典，而是单独维护一个“内置常量”字典，在变量查找时先从用户 env 查，再查内置常量。这样既允许用户覆盖默认值，又不会把内置名字污染到业务环境里。

最后再分享一个我一直沿用的调试技巧：给递归下降的有效递归函数加一个 depth 参数，每次进入时打印缩进和当前 Token。这样一旦表达式解析出错，你能一眼看到解析器在哪一层、卡在哪个 Token 上，比任何断点调试都直观。表达式求值看似是门基础课，但真把它完整做一遍，你就等于亲手写了一个编译器的缩影——从字符流到语法树到执行，每一步的取舍和设计决策，都是后面做任何语言类工具时都能直接用上的财富。