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"です。これは、一度に1つの入力トークンを解析するために繰り返すマクロです。これは、上記のコメントで指摘されているように、a + bのような式を引き離す唯一の方法だからです。これらのいわゆる、"future-proofing restrictions"は正当な理由のために配置されています。また、再帰は、マクロを展開する時間が式の長さでは線形であることを意味します。そして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で始まる）、postfixインタープリタ（すべての規則が@pfxで始まる）、および単一のエントリポイント（最後の規則、接頭辞なし）。

コンバータは演算子スタックを使用し、入力を介して噛み込んだときに後置出力文字列を作成します。括弧はLPとRPに変換され、入力をトークンのリニアストリームとして保持します（通常、macro_rulesには括弧を入れてバランスをとる必要があり、括弧で囲まれたグループは単一のトークンツリーと一致させます）。すべての演算子は右結合とみなされ、PEMDASが適用されます（*および/が+および-より優先されます）。

インタープリタは、オペランドスタックを使用して、簡単な方法で式を評価します。つまり、オペランドをスタックにプッシュし、オペレータが2つのオペランドをポップしてオペレータをポップします。 postfixインタープリタの結果は、元の中置式と非常によく似た式ですが、演算子の優先順位をシミュレートするためにすべてがカッコで囲まれています。次に、実際の計算を行うためにrustcを使用します。

コードの最後にいくつかの例があります。あなたがバグを見つけたら教えてください！ 1つの制限は、各オペランドが単一のトークンツリーでなければならないことです。5.0f32.sqrt()のような入力は解析エラーを起こし、-2のようなマルチトークンリテラルは間違った答えを引き起こします。これは中括弧で修正できます。 infix!({-2.0} - {5.0f32.sqrt()})（マクロを複雑にすることで修正することもできます）。

Answer 2

は、あなたがマクロで何ができるかに重大な制限があります。例えば。解析のあいまいさを持つことはできません。したがって、それの後に+が必要な式を持つことはできません。これは、解析トークンを、例えば、カンマ。次に、基本バイナリ操作を指定する必要があります。最後に、中かっこ（infix）から中括弧（brackets）または接頭辞（prefix）へのマッピング。ブラケット方式で中置する中置を使用した例がある：あなたは今、ほとんどあなたの質問のように、このマクロを呼び出すことができます

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)