有没有办法在Rust宏中优先匹配中缀操作？

Question

一个非常简单的例子就是在Rust宏中实现基本的加法和乘法。

compute!(1 + 2 * 3) // should evaluate to 7 

我不完全确定这是可能的，因为锈宏的语法有限。

这里的关键是不计算在编译时的东西，但要能以某种方式解析令牌（与优先顺序）：

(term, terms*) => { parse_mul!(term) + (parse_mul!(terms))* } // this is not actual Rust! 

Answer 1

在理论上，你可以做到这一点。在实践中，这是一个坏主意。无论如何，我做到了。我发布在reddit上，并被要求在这里转移。

这样的宏必然是一个“tt muncher”，它是一个宏，它一次递归地解析其输入的一个标记。这是必需的，因为正如在上面的评论中指出的那样，这是将a + b之类的表达式拉开的唯一方式。这些所谓的"future-proofing restrictions"是有充分理由的，并且让它们避开它们。递归也意味着扩展宏的时间至少在表达式的长度上是线性的。在默认情况下，在递归64次后，rustc会放弃扩展宏（但您可以更改稳定上的限制）。

考虑到这些警告，让我们看看宏！我选择的策略是将中缀表达式转换为后缀，然后评估后缀表达式，这非常简单。我非常模糊地记得如何做到这一点，但由于这里的目标是宏观疯狂，而不是算法技巧，我只是遵循this helpful page底部的规则。

事不宜迟，代码（runnable version）：

macro_rules! infix { 
    // done converting 
    (@cvt() $postfix:tt) => { infix!(@pfx() $postfix) }; 
    //        | |^postfix expression 
    //        | ^operand stack 
    //        ^postfix interpreter 

    // infix to postfix conversion using the rules at the bottom of this page: http://csis.pace.edu/~wolf/CS122/infix-postfix.htm 

    // at end of input, flush the operators to postfix 
    (@cvt ($ophead:tt $($optail:tt)*) ($($postfix:tt)*)) => { infix!(@cvt ($($optail)*) ($($postfix)* $ophead)) }; 

    // 2. push an operator onto the stack if it's empty or has a left-paren on top 
    (@cvt (    ) $postfix:tt + $($tail:tt)*) => { infix!(@cvt (+    ) $postfix $($tail)*) }; 
    (@cvt (    ) $postfix:tt - $($tail:tt)*) => { infix!(@cvt (-    ) $postfix $($tail)*) }; 
    (@cvt (    ) $postfix:tt * $($tail:tt)*) => { infix!(@cvt (*    ) $postfix $($tail)*) }; 
    (@cvt (    ) $postfix:tt/$($tail:tt)*) => { infix!(@cvt (/    ) $postfix $($tail)*) }; 
    (@cvt (LP $($optail:tt)*) $postfix:tt + $($tail:tt)*) => { infix!(@cvt (+ LP $($optail)*) $postfix $($tail)*) }; 
    (@cvt (LP $($optail:tt)*) $postfix:tt - $($tail:tt)*) => { infix!(@cvt (- LP $($optail)*) $postfix $($tail)*) }; 
    (@cvt (LP $($optail:tt)*) $postfix:tt * $($tail:tt)*) => { infix!(@cvt (* LP $($optail)*) $postfix $($tail)*) }; 
    (@cvt (LP $($optail:tt)*) $postfix:tt/$($tail:tt)*) => { infix!(@cvt (/ LP $($optail)*) $postfix $($tail)*) }; 

    // 3. push a left-paren onto the stack 
    (@cvt ($($operator:tt)*) $postfix:tt ($($inner:tt)*) $($tail:tt)*) => { infix!(@cvt (LP $($operator)*) $postfix $($inner)* RP $($tail)*) }; 

    // 4. see right-paren, pop operators to postfix until left-paren 
    (@cvt (LP   $($optail:tt)*) $postfix:tt  RP $($tail:tt)*) => { infix!(@cvt ($($optail)*) $postfix    $($tail)* ) }; 
    (@cvt ($ophead:tt $($optail:tt)*) ($($postfix:tt)*) RP $($tail:tt)*) => { infix!(@cvt ($($optail)*) ($($postfix)* $ophead) RP $($tail)*) }; 

    // 5. if an operator w/ lower precedence is on top, just push 
    (@cvt (+ $($optail:tt)*) $postfix:tt * $($tail:tt)*) => { infix!(@cvt (* + $($optail)*) $postfix $($tail)*) }; 
    (@cvt (- $($optail:tt)*) $postfix:tt * $($tail:tt)*) => { infix!(@cvt (* - $($optail)*) $postfix $($tail)*) }; 
    (@cvt (+ $($optail:tt)*) $postfix:tt/$($tail:tt)*) => { infix!(@cvt (/ + $($optail)*) $postfix $($tail)*) }; 
    (@cvt (- $($optail:tt)*) $postfix:tt/$($tail:tt)*) => { infix!(@cvt (/ - $($optail)*) $postfix $($tail)*) }; 

    // 6. if an operator w/ equal precedence is on top, pop and push 
    (@cvt (+ $($optail:tt)*) ($($postfix:tt)*) + $($tail:tt)*) => { infix!(@cvt (+ $($optail)*) ($($postfix)* +) $($tail)*) }; 
    (@cvt (- $($optail:tt)*) ($($postfix:tt)*) - $($tail:tt)*) => { infix!(@cvt (- $($optail)*) ($($postfix)* -) $($tail)*) }; 
    (@cvt (+ $($optail:tt)*) ($($postfix:tt)*) - $($tail:tt)*) => { infix!(@cvt (- $($optail)*) ($($postfix)* +) $($tail)*) }; 
    (@cvt (- $($optail:tt)*) ($($postfix:tt)*) + $($tail:tt)*) => { infix!(@cvt (+ $($optail)*) ($($postfix)* -) $($tail)*) }; 
    (@cvt (* $($optail:tt)*) ($($postfix:tt)*) * $($tail:tt)*) => { infix!(@cvt (* $($optail)*) ($($postfix)* *) $($tail)*) }; 
    (@cvt (/ $($optail:tt)*) ($($postfix:tt)*)/$($tail:tt)*) => { infix!(@cvt (/ $($optail)*) ($($postfix)* /) $($tail)*) }; 
    (@cvt (* $($optail:tt)*) ($($postfix:tt)*)/$($tail:tt)*) => { infix!(@cvt (/ $($optail)*) ($($postfix)* *) $($tail)*) }; 
    (@cvt (/ $($optail:tt)*) ($($postfix:tt)*) * $($tail:tt)*) => { infix!(@cvt (* $($optail)*) ($($postfix)* /) $($tail)*) }; 

    // 7. if an operator w/ higher precedence is on top, pop it to postfix 
    (@cvt (* $($optail:tt)*) ($($postfix:tt)*) + $($tail:tt)*) => { infix!(@cvt ($($optail)*) ($($postfix)* *) + $($tail)*) }; 
    (@cvt (* $($optail:tt)*) ($($postfix:tt)*) - $($tail:tt)*) => { infix!(@cvt ($($optail)*) ($($postfix)* *) - $($tail)*) }; 
    (@cvt (/ $($optail:tt)*) ($($postfix:tt)*) + $($tail:tt)*) => { infix!(@cvt ($($optail)*) ($($postfix)* /) + $($tail)*) }; 
    (@cvt (/ $($optail:tt)*) ($($postfix:tt)*) - $($tail:tt)*) => { infix!(@cvt ($($optail)*) ($($postfix)* /) - $($tail)*) }; 

    // 1. operands go to the postfix output 
    (@cvt $operators:tt ($($postfix:tt)*) $head:tt $($tail:tt)*) => { infix!(@cvt $operators ($($postfix)* ($head)) $($tail)*) }; 

    // postfix interpreter 
    (@pfx ($result:expr     ) (     )) => { $result }; 
    (@pfx (($a:expr) ($b:expr) $($stack:tt)*) (+  $($tail:tt)*)) => { infix!(@pfx ((($b + $a)) $($stack)*) ($($tail)*)) }; 
    (@pfx (($a:expr) ($b:expr) $($stack:tt)*) (-  $($tail:tt)*)) => { infix!(@pfx ((($b - $a)) $($stack)*) ($($tail)*)) }; 
    (@pfx (($a:expr) ($b:expr) $($stack:tt)*) (*  $($tail:tt)*)) => { infix!(@pfx ((($b * $a)) $($stack)*) ($($tail)*)) }; 
    (@pfx (($a:expr) ($b:expr) $($stack:tt)*) (/  $($tail:tt)*)) => { infix!(@pfx ((($b/$a)) $($stack)*) ($($tail)*)) }; 
    (@pfx ($($stack:tt)*     ) ($head:tt $($tail:tt)*)) => { infix!(@pfx ($head  $($stack)*) ($($tail)*)) }; 

    ($($t:tt)*) => { infix!(@cvt()() $($t)*) } 
    //      | | |^infix expression 
    //      | |^postfix expression 
    //      | ^operator stack 
    //     ^convert infix to postfix 
} 

fn main() { 
    println!("{}", infix!(1 + 2 * 3)); 
    println!("{}", infix!(1 * 2 + 3)); 
    println!("{}", infix!(((1 + 2) * 3) * 3)); 
    println!("{}", infix!((1 + 2 * 3) * 3)); 
    println!("{}", infix!(1 - 2 - 1)); 
} 

大多数我这里使用的宏观招数可以The Little Book of Rust Macros找到。您可以看到该宏分为三个部分：中缀到后缀的转换（所有以@cvt开头的规则），后缀解释器（所有以@pfx开头的规则）以及单个入口点（最后一个规则，没有前缀）。

转换器使用运算符堆栈并在咀嚼输入时建立后缀输出字符串。圆括号转换为LP和RP以将输入保持为线性码流流（通常macro_rules需要括号保持平衡，并将带括号的组匹配为单个标记树）。所有运营商都被认为是正确联合的，并且PEMDAS适用（*和/优先于+和-）。

解释器使用操作数堆栈并以相当直接的方式评估表达式：将操作数推入堆栈，并在遇到操作符时弹出两个操作数并应用操作符。后缀解释器的结果是一个与原始中缀表达式非常相似的表达式，但是其中的所有内容都用括号括起来以模拟运算符优先级。然后，我们依靠rustc来做实际的算术运算:)

代码结尾处包含了一些示例。让我知道如果你发现任何错误！一个限制是每个操作数都必须是单个标记树，因此输入如5.0f32.sqrt()将导致解析错误，并且多个标记文字（如-2）可能会导致错误答案。你可以用大括号来解决这个问题。 infix!({-2.0} - {5.0f32.sqrt()})（它也可以通过使宏复杂化来解决）。

Answer 2

有你可以用宏做什么严重的局限性。例如。你不能解析歧义。所以你不能有一个表达式，它后面会有一个+。这意味着我们需要通过例如分离我们的解析令牌。一个逗号。然后我们需要指定基本的二进制操作。最后一个从中缀到括号的中缀映射或前缀。使用中缀带括号的方法中缀的一个例子是：

macro_rules! compute { 
    ($a:expr, +, $b:expr) => {{ add($a, $b) }}; 
    ($a:expr, *, $b:expr) => {{ mul($a, $b) }}; 
    ($a:expr, +, $($rest:tt)*) => {{ 
     compute!($a, +, compute!($($rest)*)) 
    }}; 
    ($a:expr, *, $b:expr, $($rest:tt)*) => {{ 
     compute!(compute!($a, *, $b), $($rest)*) 
    }}; 
} 

Playground

您现在可以调用这个宏几乎就像在你的问题：compute!(1, +, 2, *, 3)