rust
pest

pest で中置演算子を扱う

最近 pest を触り始めたのですが,公式の book に中置演算子の扱いが明記されておらず少し手間取ってしまったので対処法をメモしておきます.

pest について

pest は,Rust で PEG (Pasing Expression Grammar) に基づく構文解析を行うためのライブラリです.custom Derive を使用して外部ファイルから文法定義を読み込みコード生成を行うことが特長であり,nomcombine など Rust コード内でパーサ構築を行う従来のライブラリとは異なり

  • BNF ライクな直感的な文法定義の記述が可能
  • 文法定義のエラーメッセージが「人間が読める」形式で出力される

などの利点があります.

使い方は次のようになります.grammar.pest の文法に関する詳細は本筋ではないので,知りたい方は pest 公式の README やサンプルコードなどを参考にして下さい.

grammer.pest
ascii = { 'a'..'z' | 'A'..'Z' }
ident = { ascii+ }
ident_pair = _{ ident ~ " " ~ ident }
main.rs
extern crate pest;
#[macro_use]
extern crate pest_derive;

// grammar.pest が変更された後にコンパイルさせる(束縛する変数名は何でも良い)
const _GRAMMAR: &str = include_str!("grammar.pest");

// コード生成のエントリポイント
// #[grammar = "..."] で読み込む文法定義ファイルを指定する
#[derive(Parser)]
#[grammar = "grammar.pest"]
struct ExprParser;

// 生成されるコードに含まれるのは以下の通り:
// * ExprParser に対する pest::Parser の実装
// * 列挙型 Rule の定義(各ヴァリアントには grammar.pest 内の規則が入る)

fn main() {
    use pest::Parser;
    let input = "hello world";
    let mut pairs = ExprParser::parse_str(
        Rule::ident_pair, // マッチさせる規則
        input,
    ).unwrap_or_else(|err| {
        // pest:Error は fmt::Display を実装し,human-readable なエラーメッセージを出力することが出来る
        eprintln!("failed to parse:\n{}", err);
        std::process::exit(1);
    });

    // 解析結果は pest::iterators::Pairs で返るため,適宜自前の AST に変換する必要がある
    let fst = pairs.next();
    let snd = pairs.next();
    match (fst, snd) {
        (Some(fst), Some(snd)) => {
            assert_eq!(fst.as_rule(), Rule::ident);
            assert_eq!(fst.as_str(), "hello");
            assert_eq!(snd.as_rule(), Rule::ident);
            assert_eq!(snd.as_str(), "world");
        }
        _ => unreachable!(),
    }
}

本題

例題として,単純な四則演算のみの簡単な電卓のための構文解析を考えます.なお,今回は時間がなかったので評価部分の実装は行いませんでした.

なお,実用上は自前で抽象構文木の型を定義することが通例だと思いますが,この定義と pest 側の解析結果からの変換は自前で用意する必要があります.今回は,次のように AST を定義しました(変換処理については後述します).

enum Expression {
    Number(i32),
    Infix(InfixOp, Box<Expression>, Box<Expression>),
}

enum InfixOp {
    Plus,
    Minus,
    Times,
    Divide,
    Modulus,
    Power,
}

文法定義

こちらのテストコード をベースに文法定義を書き下すと,次のようになります.

grammar.pest
expression = { primary ~ (infix ~ primary)* }
primary    = { "(" ~ expression ~ ")" | number }
number     = @{ "-"? ~ ("0" | ('1'..'9' ~ '0'..'9'*)) }

// infix operators
plus = { "+" }
minus = { "-" }
times = { "*" }
divide = { "/" }
modulus = { "%" }
power = { "^" }
infix = _{ plus | minus | times | divide | modulus | power }

whitespace = _{ " " | "\r" | "\n" | "\t" }

ここでは,各演算子間の順序関係や演算子の結合関係を考慮していないことに注意して下さい.例えば,1 + 2 * 3primary と中置演算子の系列として [number(1), plus, number(2), times, number(3)] のようにパースされます.この文法定義を元に,まずは通常と同じ手順で構文解析を実行します.

prec_climber

演算子間の順序関係を解決するためのツールは,モジュール pest::prec_climber で定義されています.
この中で定義されている構造体 PrecClimber に演算子の順序と結合関係を登録することで,所望の順序関係を持つように AST を構築していくことが可能になります.具体的には,次のように演算子間の順序関係・結合関係を登録します.

let climber = PrecClimber::new(vec![...]);

PrecClimber のコンストラクタの引数には Operator の系列を渡します.Operator の第1引数に演算子の規則,第2引数に演算子の結合関係(左結合か右結合か)を指定します.結合の強さは系列内の順序で決まり,後ろに行くほど結合は強くなります.また,OperatorBitOr を実装しており結合の強さが同じであることを表すために用います.

今回の場合,結合順序は "+" | "-" < "*" | "/" | "%" < "^"power が右結合でそれ以外は左結合とすると,PrecClimber の初期化は次のようになります.

let climber = PrecClimber::new(vec![
    Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Left),
    Operator::new(Rule::times, Assoc::Left) | Operator::new(Rule::divide, Assoc::Left) |
    Operator::new(Rule::modulus, Assoc::Left),
    Operator::new(Rule::power, Assoc::Right)
]);

PrecClimber はメソッド climb(pairs, primary, infix) 持ち,これを用いて先述した primary と演算子の系列を AST に変換します.第1引数が入力である Pair のイテレータ,残りの引数はそれぞれ次のシグネチャを持つ関数(オブジェクト)を渡します:

  • primary : Pair -> Expression
  • infix : Expression * Pair<Rule, StrInput> * Expression -> Expression

具体的には,次のように使用します.

fn into_expression(pair: Pair<Rule, StrInput>) -> Expression {
    let climber = PrecClimber::new(...);
    consume(pair, &climber)
}

fn consume(pair: Pair<Rule, StrInput>, climber: &PrecClimber<Rule>) -> Expression {
    let primary = |pair: Pair<Rule, StrInput>| {
        consume(pair, climber)
    };

    let infix = |lhs, op: Rule<_, _>, rhs| -> Expression {
        match op.as_rule() {
            Rule::plus => Expression::Infix(InfixOp::Plus, Box::new(lhs), Box::new(rhs)),
            ...
        }
    };

    match pair.as_rule() {
        Rule::expression => {
            let pairs = pair.into_inner();
            climber.climb(pairs, primary, infix)
        },
        Rule::number => ...,
    }
}

おわりに

nom や combine に対し絶対的な優位性があるわけではありませんが(例えば今回のように,AST の構築は自前で実装する必要がある),それでも構文解析用のライブラリとしては十分使い勝手が良いので皆さんも使用してみてはいかがでしょうか?

今回の成果物は こちら に置いておきます.そちらもご参照下さい.


Appendix: 空白文字のスキップをスマートに行う方法

"foo bar""foobar" の両方を受理する規則を作ることを考える.

愚直に書くと次のような感じ:

foo = { "foo" }
bar = { "bar" }
rule = { foo ~ bar }

これだと "foo bar" にマッチしない.これは, "foo""bar" の間にある空白文字に対応する規則がないためである.
なので,次のように規則を追加すれば良い:

foo = { "foo" }
bar = { "bar" }
whitespace = _{ " " }
rule = { foo ~ bar }

逆に,~ で他の規則にマッチするのを防止するには @{ ... } を用いる:

rule = @{ foo ~ bar }

この場合,foo と bar の間に別の規則がマッチすることは禁止され,"foobar" のみが受理される.