Rust用PEGパーサジェネレータのrust-pegの紹介 [1]

この記事では，Rust言語向けPEGパーサジェネレータであるrust-pegの基本的な使い方を，簡単な中置記法演算式のパーサー定義を通して紹介します．

PEGとは

四則演算の式やプログラミング言語のソースコードなどの文法を解析し構文木を作るパーサを作成したい場合，よくパーサジェネレータを利用します．パーサを構成する理論や技術は昔から研究されており，C言語向けのyaccやbisonがよく知られています．yaccはBNF風の文法規則定義ファイルを読み込み，LALR法を用いたパーサを生成します．

PEGはLALR法などと同列に分類される構文解析法の一種であり，これらの理論の中では新しく2004年にBryan Fordによって提案されました．PEGは文法定義から曖昧性を排除し，どのような文法に対しても線形時間で処理を終えることができるとしています．

rust-pegはレキサとパーサが一体になったタイプのパーサジェネレータで，追加のレキサライブラリは必要ではありません．また，文法定義はマクロによって行うため追加のビルド作業が不要であり，ソースコード内に手軽にパーサを定義できます．

https://docs.rs/peg/latest/peg/
GitHub – kevinmehall/rust-peg: Parsing Expression Grammar (PEG) parser generator for Rust

インストール

プロジェクト配下のCargo.tomlに下記の内容を追記してください．記事執筆時点(2023年11月)での最新バージョンは0.8.2です．

[dependencies]
peg = "0.8.2"

rust-pegのソースコードはGitHubで管理されています．最新の情報はReleaseかcrates.ioを参照してください．

依存のインストール後，peg::parser!{}マクロが使えるようになります．pegの文法は基本的にこのマクロのみを使って行います．

基本の使い方

基本的なパーサーを作成するコードを紹介します．

peg::parser! {
    pub grammer parser() for str {
        pub rule calc() -> f64
            = n:number() { n }
        
        pub rule number() -> f64
            = n:$(['0'..='9']+) {?
                n.parse().or(Err("Can't parse a number")
            }
    }
}

fn main() {
    dbg!(parser::calc("1").unwrap());
}

pub grammer parser() for strはstr型のデータを入力に持つparserという名前の文法を作ります．pubによって関数は公開されるため，そのままパーサを利用できます．
calc()ルールはnumber()ルールを参照し，number()ルールから返される値を返り値として直接返します．
number()ルールは正規表現のような形で連続した数字の列を探し，n:$()により，見つかった位置のスライスをparse()関数に渡します．

通常ルールの返り値になるブロックは返り値の型をそのまま返しますが，ルールの{}を{?}と書くことで内部でResult型の返り値が利用可能になります．n.parse()はOkかErrを返すため，or()を使ってErrの内容を書き換えます．
ルールがErrを返した場合，rust-pegはルールが失敗したとみなし，次のルールを試します．

ルールにpubをつけることで，ルールをgrammerの外に公開して呼び出せるようになります．上記例ではcalc()ルールとnumber()ルールを公開しているため，この二つのルールは両方ともパーサーとして呼び出せます．数字をパースするnumber()関数を単体で呼び出し動作をチェックするといったことが可能なため，テストがしやすくなります．

次に，number()を拡張して小数のパースができるようにします．

pub rule number() -> f64
    = n:$(['0'..='9']+ ("." ['0'..='9']+)?){?
        n.parse().or(Err("Can't parse a number")
    }

ルールnumber()は整数と少数をパースしf64の値を返します．
一つ目の['0'..='9']+が入力の整数部にマッチし，("." ['0'..='9']+)?で小数部にマッチします．この記法は正規表現に近いので比較的理解しやすいかと思います．
括弧で括り，$()を用いてstrのスライスとして加工します．?は任意のマッチであることから，このルールは"0"のような形でも"0.1"のような形でもパースできます．

パーサの動作は次のようにテストできます．

#[test]
fn test_number() {
    assert_eq!(1.0, parser::number("1").unwrap());
    assert_eq!(1.0, parser::number("1.0").unwrap());
}

次に優先度付きの二項演算子を定義します．
rust-pegにはこのような演算子を簡単に定義できるprecedence!{}マクロが用意されているのでこれを使いcalcルールを拡張します．

pub rule calc() -> f64
    = precedence! {
        l:(@) "+" r:@ { l + r }
        --
        l:(@) "*" r:@ { l * r }
        --
        n:number() { n }
        "(" c:calc() ")" { c }
    }

ルールは優先度別で優先度が低いものから順に書いていきます． @はルールそれ自身を表し，演算子が右結合か左結合かによって(@)と@を使い分けます．
例えば，累乗の演算子^はl:@ "^" r:(@)のように定義できます．

main()関数にコードを追加してcalc()関数の動作をチェックします．

dbg!(parser::calc("(1+2)*3").unwrap());
// [src/main.rs:5] parser::calc("(1+2)*3").unwrap() = 9.0

rust-pegに含まれる文法の一覧を下記に記します．

e1 / e2 / ...: それぞれの式を順番にマッチさせ，**最初**に成功した式の値が返される(yaccなどのパーサージェネレータと異なる挙動なので注意)
"w": 文字列wにマッチ
['0'..='9']: match式の文法で文字をマッチ
[^ '0'..='9']: match式の文法でマッチしない文字をマッチ
expression?: 0か1個のマッチ 値を受けとるとOption型になる
expression*: 0個以上のマッチ Vec型
expression+: 1個以上のマッチ
expression*<>: 個数指定のマッチ <>の中には <n>(n個) <n>(n個以上) <n>(n個以下) <n,m>(n個以上m個以下)の指定ができます
expression ** delim: delimで区切られた繰り返し
expression **<> delim: delimで区切られた繰り返し <>はexpression*<>と同様
expression ++ delim: delimで区切られた**一つ以上の**繰り返し
&e: 入力を消費しないでマッチ
!e: &と同様に入力を消費しない．eにマッチしない時マッチ

まとめ

PEGパーサは従来の構文解析と異なる部分があり多少の慣れが必要ですが、yacc/lexなどと違いプログラムに非常に簡単にパーサーを定義できるため、小規模・インクリメンタルに開発をする際など威力を発揮します。