有没有办法在Rust宏中使用优先级模式匹配中缀操作？

Question

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

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

由于Rust宏的语法有限,我不能完全确定它是可能的.

这里的要点不是在编译时计算某些东西,而是能够以某种方式解析标记(优先级):

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

Answer 1

从理论上讲,你可以做到.在实践中,这是一个坏主意.无论如何,我做到了.我在reddit上发布了这个,并被要求将其转移到这里.

这样的宏必然是一个"tt muncher",一个宏,它一次递归到自己解析其输入的一个标记.这是必需的,因为正如上面的评论中指出的那样,它是拆分表达式的唯一方法a + b.这些所谓的"面向未来的限制"是有充分理由的,而且它们会绕过它们.递归还意味着扩展宏的时间至少在表达式的长度上是线性的.并且,在默认情况下(或者您可以更改稳定限制)后,rustc将在递归64次后放弃扩展宏.

记住这些警告,让我们看看宏!我选择的策略是将中缀表达式转换为后缀,然后评估后缀表达式,这很简单.我非常模糊地记得如何做到这一点,但由于这里的目标是宏观疯狂,而不是算法技巧,我只是遵循这个有用页面底部的规则.

不用多说,代码(runnable版本):

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));
}

我在这里使用的大多数宏观技巧都可以在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)*)
    }};
}

操场

您现在可以像在您的问题中一样调用此宏： compute!(1, +, 2, *, 3)