ptera 式 PEG パーサ生成法

PEG (Parsing Expression Grammar)

PEG は，非終端記号 $N$，終端記号 $\Sigma$，パース規則 $R = N \to E$，初期式 $e_S \in E$ で構成される．式は，以下の要素からなる．

この式は次のような意味論を持つ:

受理条件は $\llbracket (N, \Sigma, R, e_S)\rrbracket = \llbracket e_S\rrbracket = \{x \in\Sigma^* \mid \langle e_S, x\rangle \to \mathbf{s}(x)\}$ になる．特徴的なのは，分岐 $e_1 / e_2$ だろう．文脈自由言語の分岐は優先度は特にないが，PEG では1つ目が2つ目より必ず優先される意味論を持つ．後は，$\& e$，$! e$ といった先読み述語を原始構文として持つのも特徴の1つだろうか．ただ，基本的に上の規則をそのまま実装すれば，愚直な構文解析はできる．

さて，愚直な構文解析する場合，基本的に分岐を上から成功するまで順に解析してみてはバックトラックを繰り返すことになる．それぞれの分岐でさらに分岐することもあるわけで，例えば

に $\mathrm{a}$ が $n$ 個続く文字列を受理させるには，基本的には $n$ 回入力文字列を走査することになる．

まあ流石に入力文字列の長さに対して指数時間というのはちょっと微妙なので，線形時間にする Packrat Parsing という手法が提案されている．これもそれほど難しい手法ではない．さて，先ほどの PEG の例で問題だったのは分岐の中でどんどん分岐がネストしていくということだったが，文字列走査が増えることの本質は，同じ文字列走査を何度もやっていることによる．非終端記号 $A$ は一回走査すればどの地点から解析しようとしても失敗すると分かる．ところが愚直にやる場合，何度も同じ解析をすることになる．Packrat Parsing というのは，この同じ解析を何度もやるのを，一度目の解析結果をメモして二度目以降はそれを流用することで抑えようという手法だ．

Packrat Parsing では，入力文字列の全ての地点と非終端記号に対してメモ化領域を用意する．そして，非終端記号の解析に入る時，結果がメモされていればその結果を流用し，メモされてなければ解析してその結果をメモしておく．これにより，非終端記号の解析は最大でも入力文字列の長さと非終端記号の数の積だけとなる．この手法を用いれば，変数は入力文字列の長さ分だけで，他は文法を固定すると定数分で換算できるので，入力文字列の長さの定数倍分のメモリ領域は必要になるが，線形時間で解析が可能ということになる．

PEG vs LALR

とはいえ，まあメモリも線形分消費するわけで，そこら辺は好みが分かれるところだろう．特に，プログラミング言語の構文解析では LALR パーサが主流になっていて，そちらでは Packrat Parsing のようなバックトラックありの線形時間解析ではなく，バックトラックなしに本当に文字列を最初から一度だけ走査していくため，PEG パーサよりパフォーマンス面では優秀ということになるだろう．

エラー箇所の特定もある程度工夫しないと難しい．LALR パーサでは，失敗はそもそも一度しか起こらない為，失敗した地点での規則の候補からエラーの原因を特定しやすい．しかし，PEG の場合バックトラックしながらパースが進んでいく為複数地点で失敗が発生する．しかし，それらが全てエラーの本質とは限らない．例えば，多くのプログラムは複数の文から構成されているが，それぞれの文のパースは多くの場合独立している．そして，それを PEG で解析する場合，一つ一つの文の解析でバックトラックが発生するかもしれない．しかし，文自体のパースに成功したならバックトラック自体は本質的に起こるものであり，プログラムの構文エラーではないのだ．このように，PEG ではエラーの原因を特定しようとすると，失敗した地点の中で構文エラーと捉えるべき失敗を精査する仕組みが必要になる．

このように，実装面で見ると PEG はかなり扱いづらい文法でもある．しかし，PEG にはこのような事情を鑑みても LALR パーサに勝る大きな利点がある．それはパーサの動作が単純であると言う点だ．LALR パーサは，文法からどのようなパーサが生成されるかがかなり捉えづらい．そのため，エラーを起こす規則が分かったとしても，具体的に元の文法でどこの定義の仕方が悪いのかを調べるのは結構難しい．また，元の文法の問題の箇所が分かったとしても，それを自分の要望を満たすように改善する方法を見つけるのにまた手間がかかる．また，本質的に LALR パーサを使っている限りは改善できないといった場合もある．Haskell の do 構文を例に出してみよう．Haskell の do 構文は文脈自由言語で以下のように定義される構文だ:

$\mathit{exp}$ ，$\mathit{pat}$ ，$\mathit{decls}$ は定義は省略するが，それぞれ式，パターン，定義文の列を表す非終端記号だ．さて，この文のパーサを生成することを考える．しかし，この文をそのままちゃんと扱える LALR パーサジェネレータはおそらくないだろう．問題となるのは $\mathit{stmt}$ の最初の2つの選択肢だ．これらをそのまま LALR パーサで扱うとなると，例えば x のようなプログラム片において，$\mathit{exp}$ として reduce するか，$\mathit{pat}$ として reduce するかを決定する機構が必要になる．しかし，この文法を定義したものの意図は，後にくるであろう <- がある場合は $\mathit{pat} \mathrel{\text{\texttt{<-}}} \mathit{exp} \text{\texttt{;}}$ の文として，それ以外の時はもう一方の文としてパースしてほしいと言うことだろう．このように先をかなり見ないと前の決定ができないような文法は基本的に LALR では扱えない．もちろん，PEG ではそのまま素直に扱えることになる．

ところで，我らが GHC は LALR パーサジェネレータの Happy を使っているわけだが，そこから分かる通りこの問題は LALR で解決は可能だ．といっても，かなり力技になるが．GHC はここら辺の解決をどうしているかと言うと，$\mathit{exp}$ と $\mathit{pat}$ を一つの非終端記号にまとめ，パース結果からどう解釈するか決めてパース結果に対してバリデーションをかますと言う方法をとっている．具体的には，上の規則を以下のような規則に変更する:

こうしておけば，どの選択肢でも $\mathit{exppat}$ として reduce すれば良くなる為，reduce の衝突が起きなくなる．後は，それぞれの選択肢でパース結果を構成する際，式として解釈したい場所は式で使える構文要素だけかどうか，パターンとして解釈したい場所はパターンで使える構文要素だけかどうかをチェックするというわけだ．しかし，このような工夫が随所に散らばるとかなり文法の保守が面倒なものになり，構文木にも色々細工が必要になってきて結構面倒だ．

個人的に PEG に感じている魅力は，このような涙ぐましい工夫をせずとも，自然に文法を定義してそこから自然なパーサを生成することができ，かなり文法の保守が楽になるという点だ．その上で実用的にはある程度遜色ないパフォーマンスも出るはずという感じだ．実際，Python が最近 PEG パーサに乗り換えたことで有名だが [1]，そこでもやはり PEG によるパーサの書きやすさと，それに比べた LL パーサの複雑さと保守管理の手間が主なモチベーションとなっているようだ．

先読み付き PEG

ここからが本題．Packrat Parsing はかなり単純と言う話はしたが，この手法多くのメモは不要だし，入力もバックトラックが発生するので全部パースしないと捨てられないしで，実際問題としてメモリ消費の部分は結構杜撰な面がある．Packrat Parsing 提唱論文では遅延評価を利用してその辺うまく GC できるようにする実装も紹介されているが，正直それも本質的にはあまり寄与していないと思う．というのは，例えば以下の文法が与えられることを考えてみよう:

$\mathit{stmts}$ の定義は省略するが，こいつは文の列を表す非終端記号だ．さてこの文法から生成された PEG パーサでは，もしプログラムが { で始まる場合，本質的に入力が全て捨てられない．なぜなら，どっかでバックトラックが発生して一番最初に戻ってくることがあるかもしれないからだ．ただ，もし $\mathit{stmts}$ は絶対に { で始まらないように設計されていたとしたら，実際は一番目の選択肢に入った時点で二番目の選択肢は対象外になる．このような場合にも入力を全て保持し続けなければいけないと言うのはかなり微妙だし，それを考慮して注意深く文法を設計するのは PEG を使う動機からして本末転倒だ．

と言うわけで，この節のタイトルに繋がるわけだが，今回作ったライブラリ「ptera」の特徴は，

• PEG に先読みを付けてそもそもバックトラックを少なくしてやる
• バックトラックが発生する可能性がある地点を予め特定できる実行モデルを考え，適度に入力とメモを GC できるようにする機構を付ける

と言う感じ．まずは一つ目の詳細を紹介していく．といっても正規化して一文字先読みつけるだけだが．

ptera では，与えられる PEG 文法を，クラスは変えないがある程度制限された形で受け取る．まず，式を次の形に制限する:

また初期式 $e_S$ は非終端記号でなくてはいけないということにする．元の PEG のクラスと変わっていないことは，気合いで元の PEG からの正規化アルゴリズム書いて，生成言語が同じことを示せばよいが，今回はそこは省略する．さて，ptera はまず，この正規化された PEG 文法の非終端記号に対して，1文字目として許容しうるものを全て計算する．アルゴリズム自体はそこまで難しくなくて，次のような感じ:

なお，このアルゴリズムが fail する時は，全く文字を消費せずに同じ非終端記号に二度行き着くみたいな時で，つまり無限ループする可能性がある選択肢を含んでいる時．必ずしもその文法が無限ループするとは限らないが，その選択肢を除去しても文法の意味論は変わらないので，ptera ではそのような選択肢を取り除かないとエラーになるようにしている．

後，! (not) の時は先読みを諦めている．基本 not はやってみないと分かんないので，どっちにしろ先読みあんまり効かないケース多いし，そこまで手厚くサポートはしなくてよいかなという感じ．

こんな感じで先読みテーブルを作っておいて，先読み考慮して実行モデルを作ることで，バックトラックが少なくなるし，バックトラックがもう発生しないということも早めに分かるようになる．これにより，バックトラックするかしないかが分かれば，先読みつけない場合より早めにもう必要なくなった入力を解放することができるようになる．

もちろん，今回は1文字先読みしかしてないので，不要なバックトラックが全て事前に取り除けるわけではない．例えば，

みたいな文法があった場合，入力が $ab$ で始まっていれば，2文字パースした時点でもうバックトラックが起こらないことが確定する．しかし，今回は1文字しか先読みしていないので，このような場合もバックトラックが起こるものとしてパースは進んでしまう．あんまり深く考えていないが，まず完全にバックトラックが不要になる地点の先読みができるか問題は多分決定不能になる気がする．で，後は効果が良く先読みつける作業が妥当な時間で終わるところを探るという話になる気がするが，一文字先読みは効果が割と期待できアルゴリズムも簡単ということでやっている．ま，つまりあんまり考えてない．そんな感じ．

先読み付き PEG の実行モデル

さて，PEG に先読みを付けたはいいが，先読み付き PEG 文法からそのままバックトラック地点を考慮したパーサを直接生成するのは結構めんどくさい．そこで，ptera はパーサを生成する前に SRB というマシンに変換を行う．基本的に LR パーサの生成法にちょっと毛を生やしたようなもので，出力付き状態遷移機械にスタックを伴った意味論を付与するようなマシンになる．

SRB の遷移は，入力文字によりラベル付けされ，出力として以下の操作が指定できる:

シフト ($\mathrm{shift}$)

入力文字を1つ消費し，次の入力文字を見る

リデュース ($\mathrm{reduce}(\mathit{alt})$)

指定された選択肢を元に，スタックから今までのパース結果を取り出しアクションを行う

バックポイントの設置 ($\mathrm{pushback}(s)$)

バックトラック先の状態を伴ったバックポイントを，スタックにプッシュする

否定リデュースポイントの設置 ($\mathrm{pushnot}(\mathit{alt})$)

リデュースする否定がついた選択肢を伴ったバックポイントを，スタックにプッシュする

エンター ($\mathrm{enter}(s, A)$)

リデュース後の状態をスタックにプッシュし，非終端記号に対してパースを開始する

状態の集合 $S$ に対してこれらの操作の集合を $\Omega(S)$，文字列の終端を表す入力文字を $\bot \not\in \Sigma$ とすると，SRB は状態の集合 $S$，入力文字の集合 $\Sigma_\bot = \Sigma_\bot$，遷移規則を表す部分関数 $R = S \times \Sigma_\bot \rightharpoonup \Omega(S) \times S$，初期状態 $s_0 \in S$ の組で表現される．意味論は以下のようになる:

受理関数は，$\llbracket (S, \Sigma_\bot, R, s_0)\rrbracket = \{(x, t) \mid x \in \Sigma^*, \mathrm{c}\langle \emptyset, \epsilon, s_0, x\bot\rangle \to^* \mathrm{c}\langle m, \mathrm{arg}(t), s, \bot\rangle\}$ って感じだ．メタ変数はそれぞれ，$m$ は packrat parsing 用のメモリ，$\rho$ は実行スタック，$\alpha$ は実行結果の列，$t$ は実行結果を表す木，$x$ は入力文字列という感じ．SRB のパースは，3種類の実行状態を持つ:

シフト実行 $\mathrm{c}\langle m, \rho, s, x\rangle$

通常の実行状態で，SRB の遷移規則を元に状態を遷移させ，遷移時の出力から実行スタックを操作する

リデュース実行 $\mathrm{r}\langle m, \rho, \alpha, \mathit{alt}, x\rangle$

エンターの実行結果を決める操作．今までの実行結果を集めながら，エンターに行き着いたら実行結果を確定し，次のパース実行を始める

バック実行 $\mathrm{f}\langle m, \rho\rangle$

パース失敗から復帰地点まで戻る．復帰地点に行きあたったら，次のパース実行を始める

これが，この3つの実行状態の頭文字が SRB の名前の由来．否定リデュースポイントは，リデュース実行とバック実行を途中で逆転させるようなものになっている．この SRB を先読み付き PEG に対して，選択肢一つ一つをシフト実行，最後までパースできたらリデュース実行，失敗したらバック実行というように作成し，SRB の意味論に則ってパーサを生成するというのが ptera の残りの処理になる．さて，具体的にどう先読み付き PEG から SRB に変換するかだが，これも LR パーサの状態作成方法から着想を得ていて，アイテムと呼ばれる文法の選択肢とパース位置の組を定義し，基本的にはその集合を1つの状態として変換を行なっていく．具体的なアルゴリズムは，PEG 文法 $G = (N, \Sigma, R, A_0)$，先読み関数 $L: N \to 2^\Sigma$，終端文字 $\bot$ に対して，以下の感じになる:

ちょっと長いが，

1. 非終端記号に対して，入力文字それぞれに対してエンター遷移先のマップを作る
2. 状態それぞれに対して遷移を作成していく

が基本的な流れだ．遷移は，状態に入っている最初の選択肢によって決まる．選択肢のパース位置にあるのが終端記号ならシフト，非終端記号ならエンターを行う．もし，失敗した場合の選択肢があるならその操作を行う前にバックポイントをプッシュしておく．また，バックポイントのプッシュをできる限り少なく，また必要な位置に埋め込む為，他の選択肢でまとめられるものはまとめておく．

正当性は示していないが，成り立つはず:

健全性

正規化された PEG $G = (N, \Sigma, R, A_0)$，先読み関数 $L = \mathit{LookAHead}(G)$，終端文字 $\bot \not\in \Sigma$，SRB $M = \mathit{ConstructSRB}(G, L, \bot)$ について，$\llbracket G\rrbracket = \mathrm{dom}(\llbracket M\rrbracket)$ が成り立つ．

ptera ではこれらの変換アルゴリズムを使って，PEG から SRB への変換と SRB の実行器を提供している．

ptera の現状と今後

とりあえず，正当性は示していないが ptera は一通り変換と実行器の実装は終えていて，小さい言語で試しにパースしてみて問題なさそうなことも確認した．ただ，現状 ptera を使うにはパースする段階でパーサ生成しないといけない．この後，TemplateHaskell 用の API を作っていく予定で，それが済んだらパーサ生成を TemplateHaskell でやってコンパイル時に事前にパーサが生成できるようになるはずだ．そこまでやったら，一旦 Hackage に上げるかって感じ．その後はあんまり更新の予定はない．

デバッグ情報を出したりする機能は用意していないので，若干使いづらいのとまだバグがありそうという感じがある．多分今後もそれほど真面目にメンテする気はないので，あんまりプロダクション向けではないかなという感じはある．

PEG 自体は色々探求すればまだ面白いことが探せそう．例えば，PEG が他の文法と比べて面白いところとしてエラーハンドリングができるところがある．失敗した時の処理が書けるので，例えば非終端記号ごとにバックトラック先でエラーメッセージをパース結果にすれば，エラーメッセージのカスタマイズとかできたりするのかなあという．後は，Haskell のレイアウトルールパース失敗時の終了処理を，文法として正式に形式化できたりとかの応用が効きそう．時間があったらその辺も考えてみようかなという．とりあえず，備忘録だけ残しておく(結局，備忘録のみになりそうだが)．

まとめ

というわけで，備忘録兼ねて ptera のパーサ生成法を紹介した．ptera では，PEG に先読みつけて，SRB という実行モデルに変換することで，バックトラックを抑えつつ，素の PEG 文法より解析をしやすくしている．

興味があれば触ってみてほしい．後，もっと良い確立手法があればぜひ教えてほしいなあという感じ．では，今回はこれにて．