Rust 宏进阶：用逆波兰记法（Reverse Polish Notation）实现编译期表达式求值

作者：Ingvar Stepanyan（原文链接：Writing complex macros in Rust: Reverse Polish Notation）
发布时间：2018‑01‑31

前言

Rust 的 宏系统（macro_rules!）能够在 编译期 生成代码，极大提升表达能力。但当需要处理 复杂的 token 列表（比如把一段后缀表达式转换为中缀表达式）时，很多人仍然会卡在 如何在宏里维护“状态”、如何写出易读的错误信息。

本文以 逆波兰记法（RPN） 为例，手把手演示：

  1. 用递归宏模拟运行时的 栈。
  2. 实现 四则运算 的编译期求值。
  3. 为用户提供 友好的编译错误。
  4. 通过 trace_macros! 展示宏展开的每一步，帮助调试。

文章假设你已经能够写出最基本的 macro_rules!，并了解 tt、expr 等 token 类型的区别。

1. 逆波兰记法回顾

后缀记法使用 栈 完成运算，示例：

2 3 + 4 *

等价于中缀表达式 (2 + 3) * 4，执行过程如下：

步骤操作栈状态
1把 2 入栈[2]
2把 3 入栈[2, 3]
3+ → 弹出 3、2，压入 2+3=5[5]
4把 4 入栈[5, 4]
5* → 弹出 4、5，压入 5*4=20[20]

最终栈中唯一的值即为表达式结果。

2. 宏实现的总体思路

步骤在宏里怎么做
栈的抽象用 [] 包裹的逗号分隔 expr 列表表示栈，例如 [ a, b, c ]。
递归调用每一次匹配消耗 一个 token（数字或运算符），随后把新的栈状态再次传给 rpn!。
运算符分支把栈顶两个元素弹出，拼成中缀表达式，再压回栈。
结束条件当所有 token 用完且栈只剩一个表达式时直接返回。
错误提示使用 compile_error!、concat!、stringify! 输出当前栈的可读信息。
调试trace_macros!（nightly）可以看到宏展开的每一步。

下面按照实现顺序逐步展开代码。

3. 把数字压入栈

宏本身没有变量，只能通过 token 序列 传递“状态”。
先实现最简单的情况：把单个 token 放到栈顶。

macro_rules! rpn {
    // 初始匹配：空栈 + 一个数字
    ([ $($stack:expr),* ] $num:tt) => {
        rpn!([ $num $(, $stack)* ])   // 把 $num 放在最前（实现 LIFO）
    };
}
  • tt（token tree）只匹配单个 token，避免把 2 + 3 当成一个整体。
  • $($stack:expr),* 捕获当前栈里的所有表达式，$(, $stack)* 把新数字放在最前，实现 后进先出。

4. 继续处理后续 token

要让宏能够递归处理剩余的 token，需要把 未消费的 token 列表 也传递下去：

macro_rules! rpn {
    // 匹配数字 + 任意数量的后续 token
    ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
        rpn!([ $num $(, $stack)* ] $($rest)*)
    };
}

此分支每次只消费一个 tt（数字），递归调用自身继续处理 $rest。

5. 为运算符预留分支

宏的匹配是 顺序尝试 的——先匹配到的分支会被优先使用。
为了防止 +、-、*、/ 被数字分支捕获，我们把 运算符分支放在数字分支前：

macro_rules! rpn {
    // 加法
    ([ $($stack:expr),* ] + $($rest:tt)*) => { /* 待实现 */ };
    // 减法
    ([ $($stack:expr),* ] - $($rest:tt)*) => { /* 待实现 */ };
    // 乘法
    ([ $($stack:expr),* ] * $($rest:tt)*) => { /* 待实现 */ };
    // 除法
    ([ $($stack:expr),* ] / $($rest:tt)*) => { /* 待实现 */ };

    // 数字（放在最后）
    ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
        rpn!([ $num $(, $stack)* ] $($rest)*)
    };
}

6. 实现运算符的具体逻辑

每个运算符需要 弹出栈顶两个元素，生成中缀表达式，再把结果压回栈。下面是直接写四个分支的代码（这里的 $b 为后弹出的元素，$a 为前面的元素）：

macro_rules! rpn {
    // 加法
    ([ $b:expr, $a:expr $(, $stack:expr)* ] + $($rest:tt)*) => {
        rpn!([ $a + $b $(, $stack)* ] $($rest)*)
    };
    // 减法
    ([ $b:expr, $a:expr $(, $stack:expr)* ] - $($rest:tt)*) => {
        rpn!([ $a - $b $(, $stack)* ] $($rest)*)
    };
    // 乘法
    ([ $b:expr, $a:expr $(, $stack:expr)* ] * $($rest:tt)*) => {
        rpn!([ $a * $b $(, $stack)* ] $($rest)*)
    };
    // 除法
    ([ $b:expr, $a:expr $(, $stack:expr)* ] / $($rest:tt)*) => {
        rpn!([ $a / $b $(, $stack)* ] $($rest)*)
    };

    // 继续压数字（与上面相同的数字分支）
    ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
        rpn!([ $num $(, $stack)* ] $($rest)*)
    };
}

为什么 $a $op $b 而不是 $b $op $a？
RPN 的运算符总是 先弹出右操作数 再弹出左操作数。这里 $b 对应右侧，$a 对应左侧，拼接成普通中缀形式保证运算顺序正确。

7. 用“@op”标记消除重复（推荐写法）

上面四段代码几乎完全相同，仅运算符字符不同。我们可以把 公共逻辑抽取到一个内部辅助分支，让宏更易维护。做法：

  1. 为每种运算符写 入口分支，把 栈 与 运算符 交给 @op 辅助分支。
  2. @op 负责弹栈、拼接表达式并递归调用主宏。
macro_rules! rpn {
    // --------- @op 辅助分支（核心） ----------
    // 正常二元运算：栈里必须有两个 expr
    (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => {
        rpn!([ $a $op $b $(, $stack)* ] $($rest)*)
    };

    // --------- 运算符入口分支 ----------
    ($stack:tt + $($rest:tt)*) => { rpn!(@op $stack + $($rest)*) };
    ($stack:tt - $($rest:tt)*) => { rpn!(@op $stack - $($rest)*) };
    ($stack:tt * $($rest:tt)*) => { rpn!(@op $stack * $($rest)*) };
    ($stack:tt / $($rest:tt)*) => { rpn!(@op $stack / $($rest)*) };

    // --------- 数字分支 ----------
    ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
        rpn!([ $num $(, $stack)* ] $($rest)*)
    };

    // --------- 结束分支 ----------
    // 只剩一个表达式 → 直接返回
    ([ $result:expr ]) => { $result };

    // --------- 入口分支 ----------
    // 用户只写 RPN，宏会自动补上空栈
    ($($tokens:tt)*) => {
        rpn!([] $($tokens)*)
    };
}

优势：

  • 代码量大幅下降：只写一次运算逻辑。
  • 易于拓展：想新增 %、^ 等，只需在“入口分支”加两行即可。

使用案例

fn main() {
    println!("{}", rpn!(2 3 + 4 *));               // 20
    println!("{}", rpn!(15 7 1 1 + - / 3 * 2 1 1 + + -)); // 5
}

8. 错误处理（让编译器给出更友好的提示）

8.1 初始错误示例

如果在中间插入多余的数字：

println!("{}", rpn!(2 3 7 + 4 *));

默认的编译错误信息类似：

error[E0277]: the trait bound `[integer; 2]: std::fmt::Display` is not satisfied

这对用户没有任何帮助。

8.2 使用 trace_macros! 调试

打开 trace_macros!（仅在 nightly 版可用）可以看到宏展开的每一步，帮助定位问题根源——往往是 匹配分支不够细致。

#![feature(trace_macros)]

macro_rules! rpn { /* ... */ }

fn main() {
    trace_macros!(true);
    let e = rpn!(2 3 7 + 4 *);
    trace_macros!(false);
    println!("{}", e);
}

运行结果：

note: trace_macro
  --> src/main.rs:39:13
   |
39 |     let e = rpn!(2 3 7 + 4 *);
   |             ^^^^^^^^^^^^^^^^^
   |
   = note: expanding `rpn! { 2 3 7 + 4 * }`
   = note: to `rpn ! ( [  ] 2 3 7 + 4 * )`
   = note: expanding `rpn! { [  ] 2 3 7 + 4 * }`
   = note: to `rpn ! ( [ 2 ] 3 7 + 4 * )`
   = note: expanding `rpn! { [ 2 ] 3 7 + 4 * }`
   = note: to `rpn ! ( [ 3 , 2 ] 7 + 4 * )`
   = note: expanding `rpn! { [ 3 , 2 ] 7 + 4 * }`
   = note: to `rpn ! ( [ 7 , 3 , 2 ] + 4 * )`
   = note: expanding `rpn! { [ 7 , 3 , 2 ] + 4 * }`
   = note: to `rpn ! ( @ op [ 7 , 3 , 2 ] + 4 * )`
   = note: expanding `rpn! { @ op [ 7 , 3 , 2 ] + 4 * }`
   = note: to `rpn ! ( [ 3 + 7 , 2 ] 4 * )`
   = note: expanding `rpn! { [ 3 + 7 , 2 ] 4 * }`
   = note: to `rpn ! ( [ 4 , 3 + 7 , 2 ] * )`
   = note: expanding `rpn! { [ 4 , 3 + 7 , 2 ] * }`
   = note: to `rpn ! ( @ op [ 4 , 3 + 7 , 2 ] * )`
   = note: expanding `rpn! { @ op [ 4 , 3 + 7 , 2 ] * }`
   = note: to `rpn ! ( [ 3 + 7 * 4 , 2 ] )`
   = note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }` # 问题所在
   = note: to `rpn ! ( [  ] [ 3 + 7 * 4 , 2 ] )`  # 问题所在
   = note: expanding `rpn! { [  ] [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [ [ 3 + 7 * 4 , 2 ] ] )`
   = note: expanding `rpn! { [ [ 3 + 7 * 4 , 2 ] ] }`
   = note: to `[(3 + 7) * 4, 2]`

展开过程会逐行显示宏如何把 []、数字、运算符堆叠起来，帮助发现“错误分支”匹配到了不该匹配的 token。
通过这些信息，你可以清晰看到每一次递归调用是怎样把栈与剩余 token 组合的，定位错误时非常有帮助。

8.3 改进：在栈不是单一值时给出明确错误

我们在 所有分支结束之前加入一个捕获 “栈长度不为 1” 的分支，并使用 compile_error! 报错：

macro_rules! rpn {
    // 正常返回
    ([ $result:expr ]) => { $result };

    // 栈中还有多余的元素 → 编译时报错
    ([ $($stack:expr),* ]) => {
        compile_error!(concat!(
            "Could not find final value for the expression, perhaps you missed an operator? \
            Final stack: ",
            stringify!([ $($stack),* ])
        ))
    };

    // 入口
    ($($tokens:tt)*) => {
        rpn!([] $($tokens)*)
    };
}

错误示例：

error: Could not find final value for the expression, perhaps you missed an operator?
Final stack: [ (3 + 7) * 4 , 2 ]

8.4 处理运算符参数不足的情况

当栈中不足两个数而尝试执行运算符时，我们同样给出可读的错误信息：

macro_rules! rpn {
    // 已经有完整的二元运算实现（见上文），下面是错误分支
    (@op $stack:tt $op:tt $($rest:tt)*) => {
        compile_error!(concat!(
            "Could not apply operator `",
            stringify!($op),
            "` to the current stack: ",
            stringify!($stack)
        ))
    };
    // 其他分支略 …
}

示例输出：

error: Could not apply operator `*` to the current stack: [ 2 + 3 ]

9. 完整宏（可直接拷贝使用）

macro_rules! rpn {
    // ==== 计算核心（@op） ====
    // 正常二元运算
    (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => {
        rpn!([ $a $op $b $(, $stack)* ] $($rest)*)
    };
    // 栈深度不足 → 友好报错
    (@op $stack:tt $op:tt $($rest:tt)*) => {
        compile_error!(concat!(
            "Could not apply operator `",
            stringify!($op),
            "` to the current stack: ",
            stringify!($stack)
        ))
    };

    // ==== 运算符入口 ====
    ($stack:tt + $($rest:tt)*) => { rpn!(@op $stack + $($rest)*) };
    ($stack:tt - $($rest:tt)*) => { rpn!(@op $stack - $($rest)*) };
    ($stack:tt * $($rest:tt)*) => { rpn!(@op $stack * $($rest)*) };
    ($stack:tt / $($rest:tt)*) => { rpn!(@op $stack / $($rest)*) };

    // ==== 数字分支 ====
    ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
        rpn!([ $num $(, $stack)* ] $($rest)*)
    };

    // ==== 结束分支 ====
    // 单一结果 → 直接返回
    ([ $result:expr ]) => { $result };
    // 多余元素 → 报错提示
    ([ $($stack:expr),* ]) => {
        compile_error!(concat!(
            "Could not find final value for the expression, perhaps you missed an operator? ",
            "Final stack: ",
            stringify!([ $($stack),* ])
        ))
    };

    // ==== 入口分支 ====
    // 用户调用只写 RPN，宏会自动补上空栈
    ($($tokens:tt)*) => {
        rpn!([] $($tokens)*)
    };
}

注意：如果你想使用 trace_macros! 调试，需要 nightly 编译器；实际发布时可以把 trace_macros! 相关代码删掉，宏本身不依赖任何 nightly 特性。

10. 小结

步骤关键技巧
栈的抽象用 [] 包裹的 expr 列表模拟运行时栈。
递归宏每一次匹配消耗一个 token，递归调用自身继续处理。
运算符分支顺序把运算符分支放在数字分支前，防止冲突。
@op 辅助分支把重复的二元运算逻辑抽离，代码更简洁、易维护。
错误信息compile_error! + concat! + stringify! 输出当前栈，帮助用户快速定位错误。
调试trace_macros! 让宏展开过程可视化，适合复杂宏的排查。

通过上述技巧，我们成功实现了一个 在编译期完成逆波兰表达式求值 的宏，并对常见错误给出了可读的提示。接下来，你可以：

  • 为宏添加更多运算符（%、^、位运算等）。
  • 实现一元运算符（负号、取反）。
  • 将宏封装成 crate，配上文档发布到 crates.io 与社区共享。

祝你玩得开心，玩转 Rust 的宏系统 🚀

参考链接