読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Higher Order PEG(HOPEG) のパーザおよび評価器を公開しました

Higher Order PEG(HOPEG)とは何かというと、Parsing Expression Grammar(PEG)の規則が引数を取れるように拡張したものです(ちなみに、引数を取る規則をRule Constructorと呼んでいます)。

後で考えると、0階のPEG = 普通のPEGとすると、1階のPEG = First Order PEGの方が近いような気がしますが、まあそれはそれとして。

PEGをHOPEGに拡張すると何が嬉しいかというと、どうも、PEGでは今のところ扱えないっぽいと思われている回文を表現できるようなのです。以下は、回文を表現する(と思われる)HOPEGのサンプルです

S = P("") !.; P(r) = "a" P("a" r) / "b" P("b" r) / r;

規則Pが引数rを取れるようになっているのが、HOPEGで書けるようになった部分ですね。このHOPEGに対して、回文の入力

aa
bb
baab
abba
aaaa
bbbb
aaaaaa
bbbbbb
abbbba
abaaba
abbbba
baaaab
babbab
bbaabb

はいずれもマッチします(普通のPEGでこれを表現する方法は今のところ思いつきません)。PEGをパラメタで拡張することで表現力が有意に増した(HOPEG > PEG?)ということで、これはなかなか興味深い結果です。ただ、こと実行効率に関しては、パラメタ付き規則の呼び出しの度に少なからずオーバーヘッドがかかるのでHOPEG全体に対して効率の良い評価器を作るのは難しそうではあります。

ともあれ、HOPEGのソースコードおよび使い方はここから参照できますので、Pull Requestや意見などお待ちしております。