LALRPOPにおける生成規則の優先順位の定義方法

LALRPOP では、優先順位の定義precedence! ブロックと %prec ディレクティブを組み合わせて行います。これは yacc や bison に似ていますが、Rust のスタイルも取り入れられています。

✅ 方法一:precedence! ブロックによる優先順位の定義(推奨)

LALRPOP には precedence! マクロ構文があり、式に対して複数のサブルールを定義し、優先順位を上から下へ(上の方が低い優先順位)指定できます。

示例:加減乗除の優先順位と結合性の定義

Expr: i32 = {
    <l:Expr> "+" <r:Expr> => l + r,
    <l:Expr> "-" <r:Expr> => l - r,
    <l:Expr> "*" <r:Expr> => l * r,
    <l:Expr> "/" <r:Expr> => l / r,
    Num,
};

Num: i32 = {
    <n:r#"[0-9]+"#> => n.parse().unwrap()
};

上記のように記述すると、演算子に優先順位や結合性が定義されていないため、パーサーが衝突を起こす可能性があります。

precedence! を使用して以下のように修正します:

Expr: i32 = {
    precedence!{
        L {
            <l:Expr> "+" <r:Expr> => l + r,
            <l:Expr> "-" <r:Expr> => l - r,
        }
        L {
            <l:Expr> "*" <r:Expr> => l * r,
            <l:Expr> "/" <r:Expr> => l / r,
        }
        --
        Num,
    }
};

Num: i32 = {
    <n:r#"[0-9]+"#> => n.parse().unwrap()
};

✅ 説明:

  • precedence! は上から下に向かって、優先順位が低い順に定義されます。
  • 各グループは LR、または N で結合性を指定できます:
    • L:左結合(例:加算・減算)
    • R:右結合(例:代入・べき乗)
    • N:非結合(連続して出現できない)

✅ 方法二:%prec を使った明示的な優先順位指定(非推奨)

ルールの末尾に %prec を付けて優先順位を明示的に指定することも可能です。ただし、LALRPOP は %left%right といった宣言を内蔵しておらず、より低レベルなセマンティックアクションと組み合わせて使用されることが多いです。初心者向けにはお勧めしません。

🧠 実際の推奨事項

  • precedence! マクロの使用を推奨します。
  • 一度のルール内で複数の演算子をネストさせないようにし、shift/reduce コンフリクトを避けてください。
  • yacc/bison からの移行ユーザーの場合、precedence! は LALRPOP が提供する現代的な代替手段です。

実際の MDX 式や他の文法に対する precedence! のサンプルが必要であれば、ルールを提示してください。

タグ: lalrpop 文法解析 優先順位 結合性 プログラミング言語設計

7月26日 02:34 投稿