Pratt Parsingで式を構文解析する——演算子の優先順位をbinding powerで表現する

構文解析とは何か

字句解析（Lexing）は、ソースコードの文字列を「意味のある最小単位」であるトークンの列に変換する処理でした。しかしトークン列はあくまで平坦な1次元のリストです。例えば1 + 2 * 3は次のようなトークン列になります。

Int(1)
Plus
Int(2)
Star
Int(3)
Eof

この並びだけでは「2 * 3の方を先にまとめて計算すべきだ」という情報がどこにも表現されていません。構文解析（Parsing）は、この平坦なトークン列を文法規則に従って解釈し、演算の優先順位や結合の入れ子関係を反映した木構造——抽象構文木（AST, Abstract Syntax Tree）——に変換する処理です。1 + 2 * 3であれば、次のような木になります。

Binary {
    op: Add,
    left: Int(1),
    right: Binary {
        op: Mul,
        left: Int(2),
        right: Int(3),
    },
}

2 * 3がAddの右辺の中に埋め込まれることで、「掛け算を先にまとめてから、その結果を足し算の右辺として扱う」という優先順位の情報が、木の深さ（入れ子の深さ）として表現されています。今回はこの変換のうち、式（if/whileのような文・制御構造を除いた、値を生む式だけ）を対象にしたパーサをPratt Parsingという手法で実装しました。

ASTの設計

式を表すExprは、リテラル・識別子・配列リテラルに加えて、単項演算・二項演算・関数呼び出し・添字アクセスを持つ再帰的なenumとして定義しました。

#[derive(Debug, Clone, PartialEq)]
pub enum UnaryOp {
    Neg,
    Not,
}

#[derive(Debug, Clone, PartialEq)]
pub enum BinaryOp {
    Add,
    Sub,
    Mul,
    Div,
    Mod,
    Eq,
    NotEq,
    Lt,
    LtEq,
    Gt,
    GtEq,
    And,
    Or,
}

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Int(i64),
    Float(f64),
    Str(String),
    Bool(bool),
    Ident(String),
    Array(Vec<Expr>),
    Unary {
        op: UnaryOp,
        operand: Box<Expr>,
    },
    Binary {
        op: BinaryOp,
        left: Box<Expr>,
        right: Box<Expr>,
    },
    Call {
        callee: Box<Expr>,
        args: Vec<Expr>,
    },
    Index {
        object: Box<Expr>,
        index: Box<Expr>,
    },
}

Expr::Binaryのopフィールドには、字句解析のTokenKindをそのまま使わず、BinaryOpという専用のenumを用意しています。TokenKindはキーワードや区切り記号（Let・LParen・Comma・Eofなど）まで含む、字句解析全体を表す型です。もしそれをopにそのまま使うと、Expr::Binary { op: TokenKind::Let, .. }のような意味を成さない値まで型として作れてしまいます。BinaryOpは演算子だけの13ケースに絞ることで、「二項演算のopには演算子以外あり得ない」という制約自体を型で表現し、それ以外はコンパイルエラーになるようにしています。

TokenKindからBinaryOpへの変換は、この対応関係を明示する専用の関数にまとめました。

fn to_binary_op(kind: &TokenKind) -> BinaryOp {
    match kind {
        TokenKind::Plus => BinaryOp::Add,
        TokenKind::Minus => BinaryOp::Sub,
        TokenKind::Star => BinaryOp::Mul,
        TokenKind::Slash => BinaryOp::Div,
        TokenKind::Percent => BinaryOp::Mod,
        TokenKind::EqEq => BinaryOp::Eq,
        TokenKind::NotEq => BinaryOp::NotEq,
        TokenKind::Lt => BinaryOp::Lt,
        TokenKind::LtEq => BinaryOp::LtEq,
        TokenKind::Gt => BinaryOp::Gt,
        TokenKind::GtEq => BinaryOp::GtEq,
        TokenKind::AndAnd => BinaryOp::And,
        TokenKind::OrOr => BinaryOp::Or,
        other => unreachable!("infix_binding_power only returns Some for binary operators, got {other:?}"),
    }
}

Pratt Parsing: binding powerによる優先順位の表現

構文解析には様々な実装手法がありますが、演算子の優先順位を扱う定番の方法の1つに「優先順位のレベルごとに関数を分ける」再帰下降パース（precedence climbing）があります。parse_or → parse_and → parse_equality → parse_comparison → parse_additive → parse_multiplicative → parse_unary → parse_primaryのように、優先順位が低い方から高い方へ関数を積み重ねる実装です。この方法は理解しやすい一方、優先順位のレベルが増えるたびに関数を1つ追加する必要があり、コード量が優先順位のレベル数に比例して増えていきます。

今回はその代わりに、Vaughan Pratt が1973年に提案したPratt Parsingという手法を採用しました。各演算子に「binding power（結合力）」という数値のペア(l_bp, r_bp)を割り当て、たった1つの再帰関数parse_exprのループの中で全ての優先順位を処理します。

fn infix_binding_power(kind: &TokenKind) -> Option<(u8, u8)> {
    match kind {
        TokenKind::OrOr => Some((1, 2)),
        TokenKind::AndAnd => Some((3, 4)),
        TokenKind::EqEq | TokenKind::NotEq => Some((5, 6)),
        TokenKind::Lt | TokenKind::LtEq | TokenKind::Gt | TokenKind::GtEq => Some((7, 8)),
        TokenKind::Plus | TokenKind::Minus => Some((9, 10)),
        TokenKind::Star | TokenKind::Slash | TokenKind::Percent => Some((11, 12)),
        _ => None,
    }
}

この数値には2つの役割が同居しています。

  • 数値の大きさが優先順位を表す: Star(11,12)はPlus(9,10)より数値が大きいので、+より*の方が強く結びつく
  • ペア内の左右差が結合方向を表す: (n, n+1)のように右の数値の方が大きい場合、その演算子は左結合になる

そしてparse_expr本体は次のようになっています。

fn parse_expr(&mut self, min_bp: u8) -> Result<Expr, ParseError> {
    let mut lhs = self.parse_prefix()?;

    loop {
        if let Some(l_bp) = postfix_binding_power(self.peek_kind()) {
            if l_bp < min_bp {
                break;
            }
            lhs = self.parse_postfix(lhs)?;
            continue;
        }

        let Some((l_bp, r_bp)) = infix_binding_power(self.peek_kind()) else {
            break;
        };
        if l_bp < min_bp {
            break;
        }

        let op_token = self.advance();
        let op = to_binary_op(&op_token.kind);
        let rhs = self.parse_expr(r_bp)?;
        lhs = Expr::Binary { op, left: Box::new(lhs), right: Box::new(rhs) };
    }

    Ok(lhs)
}

min_bpは「この呼び出しでは、これ以上の結合力を持つ演算子だけを取り込む」という下限値です。次のトークンのl_bp（左結合力）がmin_bp未満なら、その演算子はこの階層では取り込まず、breakして呼び出し元に判断を委ねます。逆に取り込む場合は、右辺をparse_expr(r_bp)として再帰的にパースします。このときr_bpを次のmin_bpとして渡すことで、「今取り込んだ演算子より強い結合力を持つ演算子だけを右辺の中に埋め込み、同等以下の演算子は埋め込まない」という制御が実現されます。

1 - 2 - 3を例に追うと、次のように動きます。

  1. parse_expr(min_bp=0)がMinus(9,10)を発見。l_bp(9) >= min_bp(0)なので取り込み、右辺をmin_bp=10で再帰
  2. 内側のparse_expr(min_bp=10)は次のMinus(9,10)を発見するが、l_bp(9) < min_bp(10)なので取り込まずにbreak。Int(2)だけを返す
  3. 外側に戻り、lhs = (1 - 2)が確定。ループは継続し、まだ消費されていなかった2つ目のMinusを今度はmin_bp=0の階層で取り込む
  4. 右辺をmin_bp=10で再帰し、Int(3)を得る。最終的にlhs = (1 - 2) - 3

「取り込んだ後は、次の再帰呼び出しのハードルを1つ上げる」という単純な操作だけで、同じ演算子の連続が正しく左結合になっています。もし右結合にしたい演算子があれば、ペアを(n+1, n)のように逆にするだけで済みます。

前置演算子（単項マイナス・!）

単項演算子は、他のどの二項演算子よりも強く結びつく必要があります（-1 + 2は(-1) + 2であって-(1 + 2)ではありません）。そこで二項演算子の最大値（12）より大きい13を割り当てました。

fn prefix_binding_power(kind: &TokenKind) -> Option<u8> {
    match kind {
        TokenKind::Minus | TokenKind::Bang => Some(13),
        _ => None,
    }
}

前置演算子は数値が1つだけです。二項演算子と違って「同じ演算子が連続したときにどちらを先に計算するか」という問題（結合方向）を考える必要がないためです。--xのような連続も、内側から順にUnary{Neg, Unary{Neg, x}}と自然に組み上がります。

後置演算子（関数呼び出し・添字アクセス）

関数呼び出しf(...)と添字アクセスarr[...]は、前置演算子よりもさらに強く結びつく必要があります（-f(1)は-(f(1))であって(-f)(1)ではありません）。そのため全体の最大値である15を割り当てています。

fn postfix_binding_power(kind: &TokenKind) -> Option<u8> {
    match kind { TokenKind::LParen | TokenKind::LBracket => Some(15), _ => None }
}

リテラル・グルーピング・呼び出しの実装

parse_primaryは、前置演算子でも後置演算子でもない「式の始まり」を処理します。リテラル・識別子に加え、(が来た場合は中の式を再帰的にパースしてグルーピングを実現し、[が来た場合は配列リテラルとして要素を読み取ります。

fn parse_primary(&mut self) -> Result<Expr, ParseError> {
    let token = self.advance();
    match token.kind {
        TokenKind::Int(value) => Ok(Expr::Int(value)),
        TokenKind::Float(value) => Ok(Expr::Float(value)),
        TokenKind::Str(value) => Ok(Expr::Str(value)),
        TokenKind::True => Ok(Expr::Bool(true)),
        TokenKind::False => Ok(Expr::Bool(false)),
        TokenKind::Ident(name) => Ok(Expr::Ident(name)),
        TokenKind::LParen => {
            let expr = self.parse_expr(0)?;
            self.expect(TokenKind::RParen, "expected ')' after expression")?;
            Ok(expr)
        }
        TokenKind::LBracket => {
            let elements = self.parse_args(TokenKind::RBracket)?;
            Ok(Expr::Array(elements))
        }
        other => Err(self.error(token.line, token.column, format!("unexpected token in expression: {other:?}"))),
    }
}

(のケースを見ると分かる通り、パース結果のExprには(・)自体は一切残りません。(1 + 2) * 3をパースしても木の中にLParenは登場せず、「1 + 2を先にひとまとまりとして扱う」という構造だけが残ります。カッコはmin_bp=0から仕切り直すことで優先順位表を上書きするための記号であり、パース後は役目を終えて消えるという、抽象構文木の典型的な性質が表れています。

関数呼び出しと添字アクセスは、このlhs（左辺）に対して後置的に適用されるので、parse_postfixという別のメソッドに分けています。

fn parse_postfix(&mut self, lhs: Expr) -> Result<Expr, ParseError> {
    match self.peek_kind() {
        TokenKind::LParen => {
            self.advance();
            let args = self.parse_args(TokenKind::RParen)?;
            Ok(Expr::Call { callee: Box::new(lhs), args })
        }
        TokenKind::LBracket => {
            self.advance();
            let index = self.parse_expr(0)?;
            self.expect(TokenKind::RBracket, "expected ']' after index expression")?;
            Ok(Expr::Index { object: Box::new(lhs), index: Box::new(index) })
        }
        _ => unreachable!("parse_postfix is only called when postfix_binding_power matched"),
    }
}

引数リストと配列要素の読み取りはどちらも「カンマ区切りの式の並びを、閉じ記号まで読む」という同じ形なので、parse_argsという共通のヘルパーにまとめています。

テスト

優先順位・結合方向・グルーピング・関数呼び出し・添字アクセスのそれぞれについてユニットテストを書いています。

#[test]
fn left_associativity_of_same_precedence_operators() {
    assert_eq!(
        parse("1 - 2 - 3"),
        Expr::Binary {
            op: BinaryOp::Sub,
            left: Box::new(Expr::Binary {
                op: BinaryOp::Sub,
                left: Box::new(Expr::Int(1)),
                right: Box::new(Expr::Int(2)),
            }),
            right: Box::new(Expr::Int(3)),
        }
    );
}

#[test]
fn chained_calls_and_index() {
    assert_eq!(
        parse("f(1)[0]"),
        Expr::Index {
            object: Box::new(Expr::Call {
                callee: Box::new(Expr::Ident("f".to_string())),
                args: vec![Expr::Int(1)],
            }),
            index: Box::new(Expr::Int(0)),
        }
    );
}

動作確認

このフェーズではif・whileのような文をまだ扱えないため、Parser単体をコマンドラインから実行できるようにするのは次のフェーズ（文・制御構造の実装）まで見送り、cargo testでロジックの正しさを確認しました。

$ cargo test
running 19 tests
test lexer::tests::... (9 tests)
test parser::tests::array_literal_and_index ... ok
test parser::tests::chained_calls_and_index ... ok
test parser::tests::function_call_with_arguments ... ok
test parser::tests::left_associativity_of_same_precedence_operators ... ok
test parser::tests::logical_operators_precedence ... ok
test parser::tests::missing_closing_bracket_is_error ... ok
test parser::tests::missing_closing_paren_is_error ... ok
test parser::tests::parentheses_override_precedence ... ok
test parser::tests::precedence_of_arithmetic_operators ... ok
test parser::tests::unary_minus_binds_tighter_than_binary_operators ... ok

test result: ok. 19 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

優先順位・結合方向・明示的なグルーピングが同時に絡む例として、(1 + 4) == 5 && (3 + 2 * 4) != 20をパースした結果も載せておきます。

Binary {
    op: And,
    left: Binary {
        op: Eq,
        left: Binary { op: Add, left: Int(1), right: Int(4) },
        right: Int(5),
    },
    right: Binary {
        op: NotEq,
        left: Binary {
            op: Add,
            left: Int(3),
            right: Binary { op: Mul, left: Int(2), right: Int(4) },
        },
        right: Int(20),
    },
}

*が+より、+が==/!=より、==/!=が&&より、それぞれ深い場所にまとまっている様子が分かります。木の一番深いところ（葉に近い場所）から先に評価され、ルートに近いほど後で評価される、という優先順位の積み上げがそのまま木の形として表現されています。

備考

Resultを握りつぶすtypoを#[must_use]が検出した

写経の過程で、parse_postfixの添字アクセス（[...]）のケースで、閉じ]を検証する行の末尾に?を書き忘れるミスがありました。

// 誤り: ?が抜けている
self.expect(TokenKind::RBracket, "expected ']' after index expression");

expectはResult<Token, ParseError>を返す関数で、Resultには#[must_use]が付いているため、戻り値を無視するとcargo buildがunused Result that must be usedという警告を出します。この警告のおかげで気づけましたが、警告を見逃していた場合の実害を確認するために、閉じ]のない不正な入力"arr[0"を実際にパースしてみたところ、エラーにならずOk(Index { object: Ident("arr"), index: Int(0) })が返ってきました。閉じ括弧の検証結果を握りつぶしていたので、検証に失敗していても静かに成功扱いになっていたということです。

?を追加して修正した上で、このケースを再発防止のためのテスト（missing_closing_bracket_is_error）としても追加しました。既存のmissing_closing_paren_is_error（(のケース）と対になる形です。Resultを戻り値に持つ関数の呼び出し結果を捨てると必ず警告が出るというRustの仕様に、単純なtypoが実際に助けられた例です。

優先順位ごとに関数を分ける方式ではなくPratt Parsingを選んだ理由

先述の通り、演算子の優先順位を扱うにはPratt Parsing以外にも、優先順位のレベルごとに関数を積み重ねる再帰下降パース（precedence climbing）という定番の手法があります。今回Pratt Parsingを選んだのは、優先順位表（infix_binding_power）と実際にトークンを読み進めるループ（parse_expr）が完全に分離されるためです。優先順位のレベルを追加・変更したくなった場合、precedence climbingでは関数を1つ追加してその前後の呼び出し関係を繋ぎ直す必要がありますが、Pratt Parsingではinfix_binding_powerのmatchに1行追加するだけで済みます。加えて、前置演算子・後置演算子・中置演算子という3種類の異なる文法要素を、prefix_binding_power・postfix_binding_power・infix_binding_powerという対称的な3つの関数として統一的に扱えるのも、実装をシンプルに保てた理由です。