是否有一种方法可以在Rust宏中匹配优先的infix操作？
是否有一种方法可以在Rust宏中匹配优先的infix操作？
提问于 2016-04-19 14:43:29
一个非常简单的例子是在Rust宏中实现基本的加法和乘法。
compute!(1 + 2 * 3) // should evaluate to 7我不完全确定这是可能的，因为Rust宏的语法有限。
这里的重点不是在编译时计算某些内容，而是能够以某种方式解析标记(具有优先级)：
(term, terms*) => { parse_mul!(term) + (parse_mul!(terms))* } // this is not actual Rust!回答 3
Stack Overflow用户
回答已采纳
发布于 2016-04-22 18:06:04
理论上，你可以做到。实际上，这是个坏主意。反正是我干的。我把这个贴在reddit上，被要求把它转到这里。
这样的宏必然是一个“time”，它是一个宏，它会递归到自己，每次解析其输入的一个令牌。这是必需的，因为正如在上面的注释中所指出的，这是拆分像a + b这样的表达式的唯一方法。这些所谓的“未来防伪限制”的存在是有充分理由的，而食客们则避开了它们.递归还意味着展开宏的时间至少与表达式的长度成线性关系。默认情况下，在递归64次之后，rustc将放弃扩展宏(但您可以更改稳定的限制)。
考虑到这些注意事项，让我们看看宏！我选择的策略是将infix表达式转换为后缀，然后计算后缀表达式，这非常简单。我非常模糊地记得如何做到这一点，但由于这里的目标是宏观疯狂，而不是算法技巧，我只是遵循了这个有用的页面底部的规则。
代码(可运行版本)没有进一步的详细说明：
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));
}我在这里使用的大多数宏技巧都可以在锈迹巨石小书中找到。您可以看到宏分为三个部分:infix到- postfix转换(所有以@cvt开头的规则)、后缀解释器(所有以@pfx开头的规则)和单个入口点(最后一个规则，没有前缀)。
转换器使用一个操作符堆栈，并在它咀嚼输入时生成后缀输出字符串。括号被转换为LP和RP，以将输入保持为令牌的线性流(通常，macro_rules要求圆括号保持平衡，并将括号大小的组匹配为单个令牌树)。所有运算符都被认为是正确关联的，而PEMDAS适用(*和/优先于+和-)。
解释器使用操作数堆栈，并以非常简单的方式计算表达式:将操作数推到堆栈上，当遇到运算符时，弹出两个操作数并应用运算符。后缀解释器的结果是一个非常类似于原始infix表达式的表达式，但是所有括号都可以模拟操作符优先级。然后，我们依赖rustc来执行实际的算术:)
代码末尾包含了一些示例。如果你发现什么虫子就告诉我！一个限制是每个操作数必须是一个单一的令牌树，所以像5.0f32.sqrt()这样的输入会导致解析错误，而像-2这样的多标记文字可能会导致错误的答案。您可以用大括号来修复这个问题，例如infix!({-2.0} - {5.0f32.sqrt()}) (也可以通过使宏复杂化来修复它)。
Stack Overflow用户
发布于 2016-04-19 15:48:20
对于使用宏可以做的事情有严重的限制。你不能有分析歧义。因此，您不可能有一个表达式期望它后面有一个+。这意味着我们需要用逗号来分隔解析标记。然后我们需要指定基本的二进制操作。最后是从infix到infix的括号或前缀之间的映射。使用infix to infix with方括号方法的一个示例是：
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)。
Stack Overflow用户
发布于 2022-11-06 08:32:08
基于锈迹巨石小书 (TT-咀嚼或内部规则)的思想。可以通过递归调用子树上的宏来解析表达式树。这使得代码比在表达式中线性扫描稍微简单一些。
// 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())),
)),
)))),
)),
)),
)),
)))代码是那里。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36721733
复制相关文章
相似问题
腾讯云开发者
