Higer Order PEGで「一度現れたら再出現しない修飾子」を表現してみる

gist.github.com

とりあえずHOPEGのコードを貼り付けます。表題のような言語をHOPEGで表現する方法ですが、「一度見た修飾子の集合」をどこかに取っておく必要があります。それがModifersの引数AlreadyLookedです。一度どれかの修飾子を読むたびに、AlreadyLooked | "public"のようにして、一度「読んだ」修飾子を/で渡すわけです。

さて、「一度現れたら再出現しない修飾子」は0階のPEGで表現できないのでしょうか。と言われれば、「文法の規模を考慮しなければ」出来る、という回答になります。おおざっぱに言えば、

S = "public" "static" "final"
  / "public" "final" "static"
  / "static" "final" "public"
  / "static" "public" "final"
  / "final" "public" "static"
  / "final" "static" "public"
  / "public" "static"
  / "public" "final"
  / "static" "public"
  / "static" "final"
  / "final" "public"
  / "final" "static"
  / "public"
  / "static"
  / "final"

これで、同じ言語が表現できます。と、ここまで書いて気づいたのですが、

FOPEGはPEGよりも、同じものをより簡潔に書ける、という事自体はかなり自明なのだが、ある数nに対して、O(n!)規模の文法がO(n)になるとかいう話として考えてなかった。

— 水島 宏太(Klassic作成中) (@kmizu) March 8, 2016

は厳密には間違いで、修飾子の数nに対して、通常のPEGでは、

nPn * nP(n-1)... * nP1

に比例する規模の文法になる、が正しいですね。

ともあれ、First Order PEGになることによって、表現力が向上することも、同じ言語をより簡潔に表現できることも自明ですが、同じ言語を表現するときの、簡潔さ、に関してこのようなオーダーレベルでの違いが出てくるのは面白いですね。