このネタは
でToshihiro Kogaさんに教えてもらったもので、私のオリジナルではないのですが、ちょっとおもしろいので貼ってみます。
まず、非負整数nについて、1の出現数によってエンコードします。
0 = 1 = 1 2 = 11 3 = 111 4 = 1111 ...
といった具合です。このようにエンコードされた非負整数について、
a_1 + a_2 + ... a_n = b
が真であるかどうかを通常のPEGで判定できるというお話です。
S <- A !. A <- "1" A "1" / "+" A / "=";
このようなPEGにおいて、Sは
=: 0 = 01+1=11: 1 + 1 = 211+1=111: 2 + 1 = 311+11+11=111111: 2 + 2 + 2 = 6
という文字列を受理しますが、
11+1=1: 2 + 1 = 1
という文字列を受理しません。とてもシンプルなPEGで（Macro PEGでなく）このような計算を表現できるのは少し面白いと思ったので、紹介してみました。
