とりあえず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になることによって、表現力が向上することも、同じ言語をより簡潔に表現できることも自明ですが、同じ言語を表現するときの、簡潔さ、に関してこのようなオーダーレベルでの違いが出てくるのは面白いですね。