kmizuの日記

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

Macro PEG 0.0.8 リリース

github.com

今回のリリースでは、いわゆる後方参照と呼ばれる拡張をパーザコンビネータに導入してみました。

Introduce backreference as `evalCC` method. · kmizu/macro_peg@91154c8 · GitHub

このコミットです。

使い方は

gist.github.com

こんな感じです。サンプルは、XMLのような開きタグと閉じタグ名が一致しているような言語です。後方参照の典型的な使用例ですね。

evalCCメソッドStringを引数にとる関数オブジェクトを渡す形になります。evalCCのレシーバが成功すれば、関数オブジェクトが、マッチした文字列を引数として呼び出され、そうでない場合失敗します。

さて、後方参照ことevalCCメソッドを思いつきで導入してみましたが、これは実際のところ結構「危うい」拡張だと思います。Macro PEGだけで既に結構強力になっているのにこれ以上能力を強化するとうっかりするとチューリング完全…はすぐにはいかないと思いますが、あまり無節操な拡張をしているとそのうちそうなる可能性も捨て切れず…。

なんでチューリング完全になってはいけないのかというと、Macro PEGを解析する問題が、結局、一般のプログラミング言語によるプログラムを解析するのと似たような問題になってしまうためです。よりパワフルな形式言語は取り扱いにくく、よりパワフルでない形式言語は取り扱いやすい的な。