Applying Classical Concepts to Parsing Expression Grammarを読んだのでまとめてみる
日本語タイトル：解析表現文法に対する伝統的手法の適用
Fordが提案したParsing Expression Grammarに対し、古典的な（CFGとかRE）文法スキーマで使用されていたFirst(x)やFollow(x)などの手法を適用してみて、どのよう助けを得られるだろうか？という論文。
導き出した条件から、その条件を満たしているかどうか判定するanalyzerを実装することを目指す。
PEGでもLL(1)と似たような条件を定義出来たが、条件が強力すぎるため、必要最小限の条件にとどめるようにする。
研究と関係があるので読んでいる。
Parsing Expression
w 入力文字列
E 非終端記号
e 非終端記号に含まれる部分式。解析表現ともいう。PEGの構文規則は以下の図のように書ける。
Σ 任意の終端記号の集合
使う記法
以後登場するx,y,uなどのアルファベット小文字はx,y,u∈Σ*を表す。つまり任意の終端記号列である。
x≦yはyがxのPrefixであることを表す。つまり、x=yuである。
w[p]はwのポジションpより後の部分（tail）を表す。つまりw=xyとしてpからyが始まっているなら、w[p]=yである。
c(e,w)=xとは、eが成功し、xを消費したことを表すとする。c(e,w)=Фは失敗を表す。この時、eの言語L(e)は
のように書ける。
- カーソルとポジションについて定義する。ポジションとはカーソルが今入力文字列のどこを読んでいるかを表す。以下は例である。
この入力があったら、Pは構文解析中P=1,2,3,4,5のどれかの値をとる。矢印がカーソルである（1から5まで移動する）。
解析結果の定式化
構文解析の結果はcを用いて以下のように定義できる。
- 0文字以上の終端記号列wのとき、eを読んで何も消費しなかったならそれはnulである。
- 0文字以上の終端記号列wのとき、eを読んで一文字以上消費したらそれはadvである。
- 0文字以上の終端記号列wのとき、失敗したらそれはfailである。
First
ペア(E,e)はEのFirstがeであることを表している。例えば一番上はe/e1のFirstがeであることが、任意のe1において成り立つことを表し、上から二番目はe1/eのFirstがeであることが、e1が失敗した時だけ成立することを表す。
- 定理1 ポジションpから呼ばれるEが同じポジションから直接eを呼んだら、e∈First(E)である。
例えばE← e e1 e2 においてはEを呼ぶポジションは0であり、eも0で直接呼ばれるのでe∈First(E)である。
- 定理2 ポジションpから呼ばれるEが同じポジションで直接か間接的にeを呼んだら、e∈First+(E)である。
例えばE← e ,e←e1e2 とするとeを呼ぶポジション0でe1を呼ぶので、e1∈First+(e)である。 このようなe1の集合を推移的閉包（transitive closure）という。文字を消費しない（同じポジション）で推移的に呼べる式を全て含めるということである。
- 定理3 . ポジションpで呼びされたeがカーソルを移動した時、u≤w[ p ]を満たすt∈FIRST(e)とu ∈ L(t)が存在する。pの位置より前の先頭文字になっていてFirst(e)である言語tに含まれるuが存在するということ。
例えばE← e ,e←h o g e とすると入力h o g eに対して成功し、カーソルがp=0からq=1に動く。w[p]はh o g eのu=h o gを含んでいる。この時First(e)にもh o gは含まれる。
互いに素な式
終端記号t1とt2がdisjointとはt_1≍t_2と表す。常にどちらのPrefixとなりえないことを表す。つまりx∈L(t1),y∈L(t2)はx≦yでも、y≦xでもない。またe1とe2がe1≍e2 であるとは、任意のt1∈First(e1)とt2∈First(e2)がt_1≍t_2である場合に成り立つ。
- 定理4 異なる二つの式が同じポジションpで呼び出され、カーソルを動かしたとする。この二つの式は互いに素ではない。
例えばE←e1/e2 e1←hoge,e2←horseとする。入力文字列horseに対してe1がhoまでカーソルを動かしたが失敗した。次にe2を試すが、e2ではカーソルを動かし成功するので、e1とe2はhoを持ち互いに素でない。
Follow
Followの定義に使用するLastの定義である。これらは大雑把にいえば以下のような意味である。
E=Last ss eもEも成功し、式全体が成功するようなペア(e,E)の集まり。
E=Last sf eは成功するがEは失敗した、式の全体が失敗するようなペア(e,E)の集まり。
E=Last fs eは失敗したがEは成功した、式eが失敗しそれ以外で成功するようなペア(e,E)の集まり。e∈failである。
E=Last ff eもEも失敗した、式全体が失敗するようなペア(e,E)の集まり。e∈failである。
また、FOLLOWの定義に利用するNextの定義について説明する。
- 命題7 eが位置pで終了した後、Eに戻ってe1を呼び出した時、次が成立する
定理7
Nextとは(e,e1)の組で表される関係であり、eが成功または失敗した時に次にe1を試行することを表す。例えば、ee1においてはeが成功したら、e1∈Nexts(e)である。e/e1においては、eが失敗したらe1∈Nextf(e)である。
最終的にFOLLOWの定義が以下のように導かれる。
- FOLLOWsの式の意味 eもEも成功したらEのNextsがFOLLOWsとなる。またeが成功し、Eが失敗したらEのNextfがFOLLOWsである。
- FOLLOWfの式の意味 eもEも失敗したらEのNextfがFOLLOWfとなる。eが失敗しEが成功したらEのNextsがFOLLOWfである。
Safe Choice
Safe ChoiceE=e1/e2は以下の条件を満たす。
Safe Choiceは条件が強すぎるためPrefix captureを起こさないより弱い定義が必要である。Safe Choiceよりは弱く、Prefix Captureを防ぐには強い条件としてgeneral-semi-disjointnessというものがある。
Safe Iteration
Choiceに限らず、繰り返し演算子でもPrefix Captureと似たようなケースがある。
"a"("ab"/"c")という式に"ab"という入力があった時、これは必ず失敗する。なぜならはgreedyに入力を消費するため、後に続く"ab"のマッチに必要な入力まで消費してしまうからである。ここでSafe Iterationを図のように定義する。
直感的には繰り返しの次に同じ文字は現れないということである。これよりPrefix Captureを防ぐために新たな条件を定義できる。
実装
PEGにおけるFirstやFollowの性質を用いた、Safeでない式を検出するanalyzerを実装した。二つの典型的な例で実験を行う。
一つ目の例は数字の文法である。
number内のrealとintegerが互いに先頭に[0-9]を持ちSafeでないという警告が出ている。
二つ目の例は加算を実現する多項式である。
もし、二つの変数名を並べた時にsapceが入っていなかった場合(sapceの定義が0以上の繰り返しであるから)、一つの変数名として解釈されてしまうため、警告が出ている。
この実装には問題がある。このようなkey（予約語）に対する先読み演算子の例だ。
nameを見ると!keyはnameとして解釈されるのを防ぐために導入しているが、name内で!keyと[a-z]には共に"plus"が含まれてしまう。これは誤った警告のタネになりうる。
結論
PEGにも古典的な手法を適用できた。LL(１)と似た条件（Safe ChoiceとSafe Iteration）をFIRSTとFOLLOWを用いて定義出来ることが分かった。これらの条件を確認することでPrefix capture等の検出が可能である。ここで得られた結果は条件として十分であるが、必要でない条件があるため誤った警告をすることがある。先読み演算子”！””は特に誤った警告を起こしやすく、今後の課題である。
