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

kmizuの日記

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

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"

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

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

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

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

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