PEGで四則演算を表現してみる - 取り急ぎブログです

前回PEGで整数をパースするパターンをやってみました：

NUMBER = (ZERO/NONZERO)
NONZERO = (DIGIT, DIGIT0*)
ZERO = 0!(DIGIT0)
DIGIT = (1/2/3/4/5/6/7/8/9)
DIGIT0 = (0/DIGIT)

これに加減乗除を追加して四則演算をパースするPEGを書いてみます。

まずは整数の表記がマイナス値も表現できるように単項演算氏のマイナスを取り扱えるようにします。マイナス記号はあっても無くてもよいので省略可能にします：

NUMBER=(ZERO/-?NONZERO)

こうすることで、0は許されても-0はエラーになるようになってます。

次に、足し算をやって見ましょう：

ADDITION=(NUMBER,+,NUMBER)

これで

1+1
1231+2343
1231+-2

はパース可能ですが、空白が途中にある文字列はパースできません。それを直すためにOPTBLANKを導入しましょう

ADDITION=(NUMBER, OPTBLANK, +, OPTBLANK, NUMBER)
OPTBLANK=(' '/'\t')*

こうすることで、数と演算子の間の任意個のタブ、空白文字をスキップできるようになります。
次に1+1+1などのような2項以上の式を取り扱えるようにします。PEGでは左再帰が必ず無限ループになってしまうので次のようにします：

ADDITION=(NUMBER,OPTBLANK,+,OPTBLANK,VALUE)
VALUE=(ADDITION\NUMBER)

こうすることで＋はleft associative(左結合)になりますね。

これを拡張して次のようにやるとどうなるでしょう？

COMPUTE=(NUMBER,OPTBLANK,(+/-/*/\//),OPTBLANK,VALUE)
VALUE=(COMPUTE\NUMBER)

これだと加減と乗除の間の優先順位の違いがうまく取り扱えません。なので、加減と乗除を行うPEGを分離します。加減のほうが乗除よりも優先順位は低いので：

ADDDEC=(MULDIVORNUM,OPTBLANK,(+/-),OPTBLANK,ADDDEC)
MULDIV=(NUMBER,OPTBLANK,(*/\//),OPTBLANK,MULDIV)
MULDIVORNUM=(MULDIV/NUMBER)

FORMULA=(ADDDEC/MULDIVORNUM)

とやってやれば、
1*2+3+4+5/2/1*3
なんていうのも
(1*2)+3+4+((5/2)/1)*3
という解釈をしてくれます。

最後におまけでカッコを使えるようにして出来上がったのがこれです：

OPTBLANK=(' '/'\t')*

DIGIT = (1/2/3/4/5/6/7/8/9)
DIGIT0 = (0/DIGIT)

NUMBER=(ZERO/-?NONZERO)

ZERO = 0!(DIGIT0)
NONZERO = (DIGIT, DIGIT0*)

BLOCK=(\(,OPTBLANK,FORMULA,OPTBLANK,\),OPTBLANK,)
BLOCKORNUM=(NUMBER/BLOCK)

ADDDEC=(MULDIVORNUM,OPTBLANK,(+/-),OPTBLANK,ADDDEC)
MULDIV=(BLOCKORNUM,OPTBLANK,(*/\//),OPTBLANK,MULDIV)
MULDIVORNUM=(MULDIV/BLOCKORNUM)

FORMULA=(OPTBLANK,(ADDDEC/MULDIVORNUM))

PEGは高々10個程度の文法要素でわりと簡単に、しかも結構簡潔に文法の記述ができますね。

今回参考にしているPackrat Parsing: a Practical Linear-Time Algorithm with Backtrackingという論文ではPappyというパーサージェネレーターライブラリについて解説しているのですが、Haskell上ではこの次の世代に当たるFrisbyというライブラリも開発されているようです。

FrisbyはPappyとは違って、Parsecに近いパーサーコンビネータ・ライブラリなようです。それでいて、Pappyと同じO(N)ドメインでパースをすることができるようです。僕はまだPEGの勉強をしているだけで、どちらも使ってみてはいないのですが…

今日はこの辺で。
ではでは。