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

kmizuの日記

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

PEGでa1 + a2 + ... + an = bを判定する

PEG Formal Language

このネタは

parser.connpass.com

で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 = 0
  • 1+1=11: 1 + 1 = 2
  • 11+1=111: 2 + 1 = 3
  • 11+11+11=111111: 2 + 2 + 2 = 6

という文字列を受理しますが、

  • 11+1=1: 2 + 1 = 1

という文字列を受理しません。とてもシンプルなPEGで(Macro PEGでなく)このような計算を表現できるのは少し面白いと思ったので、紹介してみました。