🐕

[Rust] ボトムアップパーサを自前で書いてみる

2024/07/21に公開

Rust

「Rustで作るプログラミング言語」とはあまり関係ないですが、やってみたかったことの一つです。

構文解析の世界には LL と LR パーサと呼ばれる分類があります。LL パーサはソースを左からスキャンし、左から導出することを意味します。同様に LR パーサは左からスキャンし、右から導出することを意味します。「導出」というのはトークンの並びを構文の構造で置き換えることを意味します^[1]。

LL パーサはトップダウン、 LR パーサはボトムアップパーサとも呼ばれます。再帰下降パーサは LL(k) と呼ばれるパーサになります。 (k) は先読みするトークンの数を表し、再帰下降パーサはマッチに失敗した場合はバックトラックして他の構文を試すため、任意の数の先読みが必要とされることを (k) で示しています。注意深く構文を設計すれば先読みのトークンの数を減らすこともできます。

LR パーサは手で書くのが非常に難しいので、普通はパーサジェネレータが使われます。良く知られているのは Yacc や Bison で、これらは構文を記述する特殊なファイルを入力とし、パーサとして動作する C コードを出力するツールです。Yacc は元々 Unix 上で作られた Yet another compiler compiler の略で、 Bison はその GNU 版です。

Rust 界隈では、 LALRPOP をはじめとするいくつかのクレートが LR パーサ (正確には LALR パーサ)を提供していますが、 nom や pest などの LL パーサのほうが圧倒的に使われているようです。理由はよくわかりませんが、たぶん nom や pest が使いやすいのでしょう。

LR パーサのほうが一般に広い構文を解析できると言われていますが、個人的にはその差を感じたことはありません。

しかし、ツールを盲目的に使っているだけでは、内部でどう動いているのかわかりません。それに、 LR パーサを手で書くのがなぜ難しいのかも、やってみなければ上手く説明できません。

そんなわけで、自前で書いてみました。

コードは非常に簡単にしたので一つの Rust ソースファイルで完結します。 Gist に置いてあります。

データ構造

ここでは理解のための最低限の構文を設計します。演算は加算と積算のみで、値は数値リテラルのみです。 AST のデータ構造は次のように定義できます。

#[derive(Debug, Clone)]
enum Expression {
    Num(f64),
    Add(Box<Expression>, Box<Expression>),
    Mul(Box<Expression>, Box<Expression>),
}

ここではプッシュダウンオートマトンという、代表的な LR パーサ実装を使います。プッシュダウンオートマトンは入力がトークン列である(字句解析が済んでいる)ことを想定します。このため、トークンをデータとして定義しておきます。

#[derive(Debug, Clone, Copy)]
enum Token {
    Num(f64),
    Add,
    Mul,
}

プッシュダウンオートマトンは、データをスタックに保持します。スタックの要素として次の型を定義しておきます。

#[derive(Debug, Clone)]
enum StackElem{
    Expr(Expression),
    Token(Token),
}

ロジック

全体のパーサの構造は次のようになります。まず、簡単のためトークンは1文字とみなします。ループでこのトークンを読みながら、 stack を操作していき、ソースコードを読み終わったら、スタック最上位の値を結果として返します。


fn parse(src: &str) -> Option<Expression> {
    let mut stack: Vec<StackElem> = vec![];

    let mut chars = src.chars().peekable();
    while let Some(char) = chars.next() {
        // ...
    }

    stack.into_iter().last().and_then(|e| match e {
        StackElem::Expr(e) => Some(e),
        _ => None,
    })
}

ループの中でまず最初にすることは、次の文字を取得し、そのトークン種別を判定することです。ここでは +、 * を演算子と認識し、空白は読み飛ばし、それ以外は数字として解析します。一度に１文字しか読み取らないので、複数の桁を含む数値は読み取れないので注意してください。

    while let Some(char) = chars.next() {
        let token = match char {
            '+' => Token::Add,
            '*' => Token::Mul,
            ' ' => continue,
            c => Token::Num(c.to_string().parse::<f64>().expect("Could not parse num")),
        };
        // ...
    }

次に、このトークンをスタックにプッシュします。

    while let Some(char) = chars.next() {
        // ...
        stack.push(StackElem::Token(token));
        // ...
    }

次に、スタック最上位の値を見て、それが数値トークンであれば、それを AST の数値に置き換えます。データの内容としては同じですが、処理前が Token で、処理後が Expression として明確化しています。

    while let Some(char) = chars.next() {
        // ...
        if let Some(StackElem::Token(Token::Num(value))) = stack.last() {
            let value = *value;
            stack.pop();
            stack.push(StackElem::Expr(Expression::Num(value)));
        }
        // ...
    }

次に、スタック最上位の3要素を取り出し、それが演算であればその AST で置き換えるという処理をします。例えば、 3 + 4 というコードは Token::Num(3.), Token::Add, Token::Num(4.) というトークン列になりますので、Expression::Add(Box::new(Expression::Num(3)), Box::new(Expression::Num(4))) で置き換えることができます。

    while let Some(char) = chars.next() {
        // ...
        loop {
            if 3 <= stack.len() {
                if let [StackElem::Expr(lhs), StackElem::Token(Token::Add), StackElem::Expr(rhs)] = &stack[stack.len() - 3..] {
                    if chars.peek().is_none() {
                        let (lhs, rhs) = (lhs.clone(), rhs.clone());
                        stack.resize(stack.len() - 3, StackElem::Token(Token::Add));
                        stack.push(StackElem::Expr(Expression::Add(Box::new(lhs), Box::new(rhs))));
                        continue;
                    }
                }
                if let [StackElem::Expr(lhs), StackElem::Token(Token::Mul), StackElem::Expr(rhs)] = &stack[stack.len() - 3..] {
                    let (lhs, rhs) = (lhs.clone(), rhs.clone());
                    stack.resize(stack.len() - 3, StackElem::Token(Token::Add));
                    stack.push(StackElem::Expr(Expression::Mul(Box::new(lhs), Box::new(rhs))));
                    continue;
                }
            }
            break;
        }
        // loop
    }

ここで注目に値するのは、足し算は次のトークンが存在しないときにのみ行うという if chars.peek().is_none() という条件です。
これを入れないと、演算子の優先順位が正しくなくなってしまいます。

テスト

いくつかのテストケースについて解析結果を表示します。 AST はそのまま出力しても見にくいので、括弧を付けて優先順位を明確にした式として表現します。

1 * 3 -> (1 * 3)
1 + 2 + 3 -> (1 + (2 + 3))
1 + 2 * 3 -> (1 + (2 * 3))
1 * 2 + 3 -> ((1 * 2) + 3)
1 * 2 + 3 * 4 -> ((1 * 2) + (3 * 4))

掛け算の優先順位が足し算よりも高くなっていることが分かります。

LR パーサの難しさ

ここまで見たように、 LR パーサでは、スタック最上位の演算を見て、置き換え可能であれば構文木を構築していくという手法を取ります。この構文木は末端から構築されていくので、ボトムアップパーサと呼ばれます。しかし、置き換え可能なトークン列が現れたら、常に置き換えても良いというわけではなく、次の演算子の優先順位が重要になります。 if chars.peek().is_none() は、このためのチェックで、置き換えても良い条件を別途示す必要があります。

パーサジェネレータはこのような条件をテーブルとして生成し、パーサの一部に埋め込みます。このテーブルを手で求めるのは、全ての構文で優先順位の競合が起こりうるケースを網羅する必要があるため、複雑な構文になると人間には難しすぎます。

構文の曖昧さ

この問題の根底にあるのは、構文の曖昧さです。ソースコードの一部を切り取ってきて、それがどの構文の一部であるかを言い当てるのは、一般的にはできません。しかし、アルゴリズムはすべてのソースを読み込んで一度に理解することはできず、トークンや演算子などの単位で処理していく（局所論理）ことしかできません。そのため周囲のコードの情報をどれだけ局所的な論理に反映するかが難しいところです。

同じ問題は LL パーサ、例えば再帰下降パーサでも生じます。再帰下降パーサではこの曖昧さをバックトラック(再帰呼び出しの巻き戻し)によって処理しています。 LR パーサはバックトラックの代わりに、事前に構文解析用のテーブルを構築することによって処理します。これは同じ問題への異なる解決アプローチといえます。

結局、どちらを使えばよいのか？

結論から言うと、どちらもそれほど大きな違いはありません。 LL パーサでも同じ構文解析を繰り返さない Packrat parsing などの最適化手法がありますし、普通の設計の言語であればバックトラックがそこまで大きなパフォーマンス上のボトルネックになることはありません。使いやすいほうを選べばよいと思います。

それよりも、 AST を構築した後の意味(セマンティクス)解析のほうが現代では重要になってきています。「Rustで作るプログラミング言語」では、静的型チェックを紹介しましたが、それ以外にも最適化やコード生成においては AST の意味を処理することが重要になります。構文解析は言語設計の入り口ではありますが、入り口はさっさと通ってしまって、中身に時間を使った方が良いと思います。

脚注

あるいは、その場で演算を行って値で置き換えてしまうこともできます。電卓はそのような実装になるでしょう。 ↩︎

GitHubで編集を提案

データ構造

ロジック

テスト

LR パーサの難しさ

構文の曖昧さ

結局、どちらを使えばよいのか？

Discussion