在Rust宏中,有没有一种方法可以模式匹配具有优先级的中缀操作?

yqlxgs2m  于 2022-11-12  发布在  其他
关注(0)|答案(3)|浏览(141)

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

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

由于Rust宏的语法有限,我不完全确定这是可能的。
这里的重点不是在编译时计算一些东西,而是能够以某种方式解析标记(具有优先级):

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

cetgtptt1#

理论上,你可以这么做。实际上,这是一个坏主意。我还是做了。我把这个贴在reddit上,并被要求转移到这里。
这样的宏必然是一个“tt muncher”,一个递归到自身的宏,一次解析一个输入的标记。这是必需的,因为正如上面的注解所指出的,这是分离像a + b这样的表达式的唯一方法。这些所谓的"future-proofing restrictions"是有充分理由的,而t munchers则会避开它们。递归还意味着扩展宏的时间至少在表达式的长度上是线性的。而rustc在递归64次后会给予扩展宏,默认情况下(但您可以更改稳定的限制)。
记住这些注意事项,让我们来看看宏!我选择的策略是将中缀表达式转换为后缀,然后计算后缀表达式,这是相当简单的。我依稀记得如何做,但由于这里的目标是宏的疯狂,而不是算法技巧,我只是遵循了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开头的规则)和单个入口点(最后一个规则,不带前缀)。
转换器使用运算符堆栈,并在处理输入时生成后缀输出字符串。括号被转换为LPRP,以使输入保持为线性标记流(通常macro_rules需要括号来保持平衡,并将带括号的组作为单个令牌树进行匹配)。所有运算符都被认为是右关联的,并且PEMDAS适用(*/优先于+-)。
解释器使用操作数堆栈,并以相当直接的方式计算表达式:将操作数压入堆栈,当遇到一个运算符时,弹出两个操作数并应用该运算符。后缀解释器的结果是一个与原始中缀表达式非常相似的表达式,但将所有内容都括起来以模拟运算符的优先级。然后,我们依靠rustc来执行实际的运算:)
代码末尾包含了一些示例。如果发现任何错误,请告诉我!一个限制是每个操作数必须是单个令牌树,因此像5.0f32.sqrt()这样的输入将导致解析错误,而像-2这样的多令牌文字可能会导致错误答案。您可以使用大括号来修复此问题,例如infix!({-2.0} - {5.0f32.sqrt()})(也可以通过使宏复杂化来解决)。

zynd9foi

zynd9foi2#

宏的使用有很大的局限性。例如,不能有解析歧义。因此,不能有一个期望后面有+的表达式。这意味着我们需要用逗号分隔解析标记。然后我们需要指定基本的二进制运算。最后是中缀到带括号的中缀或到前缀的Map。使用中缀来中缀方括号方法的示例如下:

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)

qc6wkl3g

qc6wkl3g3#

基于The Little Book of Rust Macros(TT-Munching或Internal Rules)的思想。可以通过在子树上递归调用宏来解析表达式树。这比线性扫描表达式要简单一些。

// Macro DSL for exprs
macro_rules! expr {
    (@expt $fun:ident($($t:tt)*)) => {Expr::$fun(Box::new(expr!($($t)*)))};
    (@expt $col:ident) => {Expr::Var(stringify!($col).to_string())};
    (@expt $val:literal) => {Expr::Lit($val)};
    (@expt $($t:tt)*) => {(expr!($($t)*))};
    // Look for * or /
    (@exp* ($($x:tt)*)) => {expr!(@expt $($x)*)}; // We are done, look for higher priority ops
    (@exp* ($($x:tt)*) * $($t:tt)*) => {Expr::Mul(Box::new(expr!(@expt $($x)*)), Box::new(expr!(@exp* $($t)*)))}; // Consume until the op
    (@exp* ($($x:tt)*) / $($t:tt)*) => {Expr::Div(Box::new(expr!(@expt $($x)*)), Box::new(expr!(@exp* $($t)*)))}; // Consume until the op
    (@exp* ($($x:tt)*) $h:tt $($t:tt)*) => {expr!(@exp* ($($x)* $h) $($t)*)}; // Consume the tokens until we find the right op
    (@exp* $($t:tt)*) => {expr!(@exp* () $($t)*)}; // Start consuming tokens
    // Look for + or -
    (@exp+ ($($x:tt)*)) => {expr!(@exp* $($x)*)}; // We are done, look for higher priority ops
    (@exp+ ($($x:tt)*) + $($t:tt)*) => {Expr::Add(Box::new(expr!(@exp* $($x)*)), Box::new(expr!(@exp+ $($t)*)))}; // Consume until the op
    (@exp+ ($($x:tt)*) - $($t:tt)*) => {Expr::Sub(Box::new(expr!(@exp* $($x)*)), Box::new(expr!(@exp+ $($t)*)))}; // Consume until the op
    (@exp+ ($($x:tt)*) $h:tt $($t:tt)*) => {expr!(@exp+ ($($x)* $h) $($t)*)}; // Consume the tokens until we find the right op
    (@exp+ $($t:tt)*) => {expr!(@exp+ () $($t)*)}; // Start consuming tokens
    // Look for low priority ops first
    ($($t:tt)*) => {expr!(@exp+ $($t)*)};
}

宏:

expr!(Exp(a*b + Cos(2.*z)*d - 2.*(y+3.) + t*Sin(c+3.*t)));

扩展为:

Expr::Exp(Box::new(Expr::Add(
    Box::new(Expr::Mul(
        Box::new(Expr::Var("a".to_string())),
        Box::new(Expr::Var("b".to_string())),
    )),
    Box::new(Expr::Sub(
        Box::new(Expr::Mul(
            Box::new(Expr::Cos(Box::new(Expr::Mul(
                Box::new(Expr::Lit(2.)),
                Box::new(Expr::Var("z".to_string())),
            )))),
            Box::new(Expr::Var("d".to_string())),
        )),
        Box::new(Expr::Add(
            Box::new(Expr::Mul(
                Box::new(Expr::Lit(2.)),
                Box::new(
                    (Expr::Add(
                        Box::new(Expr::Var("y".to_string())),
                        Box::new(Expr::Lit(3.)),
                    )),
                ),
            )),
            Box::new(Expr::Mul(
                Box::new(Expr::Var("t".to_string())),
                Box::new(Expr::Sin(Box::new(Expr::Add(
                    Box::new(Expr::Var("c".to_string())),
                    Box::new(Expr::Mul(
                        Box::new(Expr::Lit(3.)),
                        Box::new(Expr::Var("t".to_string())),
                    )),
                )))),
            )),
        )),
    )),
)))

代码为there

相关问题