はじめに
Rustのパーサコンビネータライブラリnomで左再帰を扱うライブラリnom_recursiveを作りました。ここではその仕組みと使い方を説明します。
左再帰とは
一般的に再帰降下パーサでは
Expr = Expr + Expr | Term
のような構文をそのまま扱うことができません。
nomで書くとこんな感じですね。
pub fn expr(s: &str) -> IResult<&str, String> {
alt((expr_plus_expr, term))(s)
}
pub fn expr_plus_expr(s: &str) -> IResult<&str, String> {
let (s, x) = expr(s)?;
let (s, y) = char('+')(s)?;
let (s, z) = expr(s)?;
let ret = format!("{}{}{}", x, y, z);
Ok((s, ret))
}
pub fn term(s: &str) -> IResult<&str, String> {
let (s, x) = char('1')(s)?;
Ok((s, x.to_string()))
}
expr関数が無限再帰呼び出しになっていて、実行するとスタックオーバーフローします。
例えば1+1を入力した場合のパーサ呼び出しは以下のようになり、入力を消費することなく、無限に呼び出し続けます。
input | parser
1+1 | expr
1+1 | expr_plus_expr
1+1 | expr
1+1 | expr_plus_expr
1+1 | expr
1+1 | expr_plus_expr
1+1 | expr
1+1 | expr_plus_expr
...
普通は構文を変形して左再帰を除去したりしますが、そういうことが簡単にできない場合もあります。
（単に構文が多すぎるとか、ものすごく深い間接左再帰とか）
そのような場合になんとか左再帰のまま扱いたい、という話です。
実装方針
無限再帰が問題なので、どこかで止めればよいはずです。単純に考えると同じパーサが二回呼ばれたら止めれば良さそうですが、そう簡単ではありません。
最初の例で、exprの2回目の呼び出しを止めてみます。するとexpr_plus_exprは受理されずに、termが受理されて+以降は残ってしまいます。
input | parser
1+1 | expr
1+1 | expr_plus_expr
1+1 | expr (2回目なので強制fail)
1+1 | term
+1 | (終了)
一方expr_plus_exprの2回目を止めることにするとうまくいきます。
input | parser
1+1 | expr
1+1 | expr_plus_expr
1+1 | expr
1+1 | expr_plus_expr (2回目なので強制fail)
1+1 | term
+1 | char('+')
1 | expr
1 | expr_plus_expr
1 | expr
1 | expr_plus_expr (2回目なので強制fail)
1 | term
| (終了)
これはexprがexpr_plus_exprとtermという複数の選択肢を持っているのに対し、expr_plus_exprは先頭が必ずexprである、という違いによります。
exprは複数の選択肢があるので、複数回呼ばれても無限再帰にならずに受理される可能性がありますが、expr_plus_exprは先頭が固定なので（何も受理せずに）2回目通過したら3回目も必ずやって来ます。
というわけで、先頭の選択肢が固定になっているパーサについて2回目の呼び出しを止めれば良さそうです。
呼び出しの記録
この記録をどう持つか、というのが次の問題です。単純に、グローバル変数的な領域にパーサ毎のフラグを持つ、というのが考えられますが、これは上手く行きません。
再帰降下パーサではバックトラックが発生します。つまりパーサを呼んでみて、ダメだったら呼ぶ前まで戻って別のパーサでやり直す、ということです。
この呼ぶ前まで戻ってというのが問題で、呼び出しフラグも巻き戻さないといけません。
グローバルなフラグをスタックにして巻き戻せるようにする方法も考えられますが、フラグをパーサへの入力データと共に流してやるのが簡単そうです。
この場合、巻き戻しはパーサ自体が面倒を見てくれる形になります。
例えばnomの拡張ライブラリにnom_locateがあります。これはトークンの位置（行数など）を保持するためのパーサ入力型を提供しますが、オプションで任意の型を付加することができます。
type Span<'a> = LocatedSpanEx<&'a str, u64>;
このようにu64を付加すれば、64個分のパーサ通過情報を記録することができます。
また、フラグを一度立てた後、どこまで維持するかも考える必要があります。検出したいのは何も受理せずに再帰してしまうケースなので、何か受理する度にクリアすれば良さそうです。
nom_recursive
ここまでで説明したものをライブラリにしたものが、nom_recursiveです。これはCustom attributeを使って、再帰検知のコードをパーサに挿入します。
最初の例では
pub fn expr(s: &str) -> IResult<&str, String> {
alt((expr_plus_expr, term))(s)
}
# [recursive_parser]
pub fn expr_plus_expr(s: &str) -> IResult<&str, String> {
let (s, x) = expr(s)?;
let (s, y) = char('+')(s)?;
let (s, z) = expr(s)?;
let ret = format!("{}{}{}", x, y, z);
Ok((s, ret))
}
pub fn term(s: &str) -> IResult<&str, String> {
let (s, x) = char('1')(s)?;
Ok((s, x.to_string()))
}
という感じで、再帰検知したいパーサに#[recursive_parser]を付ければOKです。