Parsing Expression Grammar

てっきり普通のBNFだと思って使ったboost::spirit::qiが実はParsing Expression Grammar（以下PEG）だったみたいなので，ちょっと調べてみた．結論から言うと難しい．見た目ならばBNFに似ていて，たとえば正しく並んでいる()はS = ("(" S ")") / ""と書ける．*1ここで / は優先順位付き「または」で，BNFでは通常 | を使うところ．この例だと割と直感的なのだが，A = ("a" A "a") / ""という例を考えるととたんに難しくなる．もしこれが A = ("a" A "a") | "a"というBNFならば「偶数個のaの並び」という直感的な結果となる．しかし，PEGでは「aの$2^k - 2$個の並び」を表す．たとえば"aaaa"はマッチしない．そう言われてもさっぱりだったので，少し真面目に考えてみた．

そもそもPEGは，言語（マッチする文字列の集まり）を定義しているというよりは，文字列をパースしていく方法を定義しているようだ．文字列全体を$\Sigma^*$と書くと，$A$は写像$\Sigma^*\to \Sigma^*\cup\{\mathrm{fail}\}$を与える．（$\mathrm{fail}$は文字列ではなく特別な値．）マッチする文字列を発見した時にはそのマッチせずに残った文字列*2を返し，失敗した場合は$\mathrm{fail}$となるような関数．PEGの構成要素は*3，結合$e_1\ e_2$（$e_1$の次に$e_2$が来る文字列を表す）と優先順位付き「または」$e_1 / e_2$（$e_1$がマッチしたら$e_1$を，そうでなければ$e_2$を表す）である．ただし$e_1,e_2$は既にあるPEG．これらと，単に文字列にマッチするPEG（"a"とか"("とか"abc"とか）を組み合わせて一般のPEGが作られる．これらに対しては，関数が次のように帰納的に定義される．結合に関しては \[ (e_1\ e_2)(x) = \begin{cases}\mathrm{fail} & (e_1(x) = \mathrm{fail}),\\ e_2(e_1(x)) & (\text{otherwise}) \end{cases}\] であり，「または」の方は \[ (e_1 / e_2)(x) = \begin{cases}e_2(x) & (e_1(x) = \mathrm{fail}),\\ e_1(x) & (\text{otherwise}). \end{cases}\] となる．ちなみに単なる文字列sに対しては（たとえば"a"のような），sで始まっていればそれを除いた文字列，そうでなければ$\mathrm{fail}$である．たとえば$\text{"ab"}(\text{abc}) = \text{c}$．*4

まずはB = ("a" B) / ""というPEGを考えてみる．$\varepsilon$を空文字列として，まず$B(\varepsilon)$を考えよう．$"\text{a}"(\varepsilon) = \mathrm{fail}$であるので，$("\text{a}"\ B)() = \mathrm{fail}$である．よって$B(\varepsilon) = \text{""}(\varepsilon) = \varepsilon$となる．$B(\text{a})$を考えると，$"\text{a}"(\text{a}) = \varepsilon$であるので，$(\text{"a"} B)(\text{a}) = B(\varepsilon) = \varepsilon$となる．以下機能的に$B(aa\cdots a) = \varepsilon$，つまり$B$は$a$の任意長さの並びを表すことがわかる．これは直感的．

さてこれを使って「一文字以上のaの並び」を作ろうとC = B "a"を考える．$C(aa)$を考えよう．$B(aa) = \varepsilon$であるので，$C(aa) = \text{"a"}(\varepsilon) = \mathrm{fail}$となる．このように，$C$は任意の文字列に対してfailを返す．Bが「貪欲」にaの並びをとってしまうわけだ．基本的にこの貪欲さが直感的にならない理由でもある気がする．

もともとのA = ("a" A "a") / ""を考えてみよう．$A(\varepsilon) = \text{""}(\varepsilon) = \varepsilon$，$A(a) = \text{""}(a) = a$はすぐわかる．次に$(\text{"a"}\ A\ \text{"a"})(aa) = (A\ \text{"a"})(a) = \text{"a"}(A(a)) = \text{"a"}(a) = \varepsilon$より$A(aa) = \varepsilon$，よって$(\text{"a"}\ A\ \text{"a"})(aaa) = (A\ \text{"a"})(aa) = \text{"a"}(A(aa)) = \text{"a"}(\varepsilon) = \mathrm{fail}$より$A(aaa) = \text{""}(aaa) = aaa$となる．（$A$はaaを受け付けるので，$A(aaa) = a$となりそうだがそうではない．）そして$(\text{"a"}\ A\ \text{"a"})(aaaa) = (A\ \text{"a"})(aaa) = \text{"a"}(A(aaa)) = \text{"a"}(aaa) = aa$となり，よって$A(aaaa) = aa$．つまり$A$は文字列aaaaの全体にマッチするわけではない．

一般に$A(a^n) = a^{p(n)}$として，$p(n)$を計算してみる．（$A$の後ろの$\text{""}$は$\mathrm{fail}$を返さないので，$A$が$\mathrm{fail}$をかえすことはない．）$(\text{"a"}\ A\ \text{"a"})(a^{n + 1}) = (A\ \text{"a"})(a^n) = \text{"a"}(a^{p(n)})$であるので，もし$p(n) > 0$ならば$A(a^{n + 1}) = a^{p(n) - 1}$，そうでなければ$(\text{"a"} A \text{"a"})(a^{n + 1}) = \mathrm{fail}$より$A(a^{n + 1}) = \text{""}(a^{n + 1}) = n + 1$となる．つまり， \[ p(n + 1) = \begin{cases} n + 1 & (p(n) = 0),\\ p(n) - 1 & (p(n) \ne 0)\end{cases} \] である．$2^k - 2 < n \le 2^{k + 1} - 2$となる$k$をとると， \[ p(n) = 2^{k + 1} - 2 - n \] となることが帰納法で示され，よってある$k\ge 1$に対して$n = 2^k - 2$の時のみ全てマッチと見なされることがわかる．

偶数文字のaとbの並びからなる回文を作ろうと思って，D = ("a" D "a") / ("b" D "b") / ""としてみても，同じような理由でこれは回文全体を表すわけではないようだ．（既に上でわかるようにaaaaにマッチしない．なおBNF D = ("a" D "a") | ("b" D "b") | ""は回文を表す．）んじゃぁどんな文字列にマッチするのかと言ってもよくわからなそう．更に「回文にマッチするようなPEGはあるか」という問題はopenのようだ．

*1

PEGでは結合よりも「または」の方が優先順位が低いので，この場合()で囲む必要は無い（さらにその方がよく使われる）のだが，優先順位を気にしなくて良いように括弧でくくることにする．

*2

原論文はマッチした方の文字列だったが，ここでは残りで定義しておく．

*3

他にもあるがこの二つが大事そう．

*4

定義に現れる以外の文字列は面倒なので""では囲まないことにする．