Macro PEGは、私が2016年頃に、PEGに対する拡張として提案したものです。2016年のプログラミング研究会で発表したスライドが
にあります。さて、当時考えたMacro PEGは、Macro PEGの引数付き規則を名前呼び出し（call by name）として評価するものでした。たとえば、
S = Twice("a")*;
Twice(A) = A A;
というMacro PEGがあったとき、Sから開始して、引数付き規則 Twice を引数 "a" で呼び出すと、Aは式"a"をそのまま束縛し、呼び出され側に展開される形になります。このため、これが受理する言語は、
L = {"aa", "aaaa", "aaaaaa", ...}
といったものになります。当時、値呼び出し（call by value）を検討したものの、あまり面白いことができなさそうだったので、名前呼び出しを採用したという経緯があったのですが、最近、改めて値呼び出しにした場合にどのようなことができるかを考えてみることにしました。
まず、PEGにおける「値」とは何かが曖昧なのですが、ここでは、ある式（parsing expression）に対してマッチした文字列だということにします。たとえば、
S = "a"*;
を入力 aaa に対して評価した場合、Sを評価した値はaaaになるものとします。このような考えに基づいて、Macro PEGの評価戦略として値呼び出しも選べるようにしました。
簡単な例で説明すると、
S = Twice("a")*;
Twice(A) = A A;
というMacro PEGは、値呼び出しの場合、先に、引数"a"と現在の入力文字列とのマッチが行われ、Aがその結果の文字列"a"を束縛して、Twiceを呼び出すものとします。ここで、さらに、
- 引数の評価の際に消費された文字列の続きから評価を続けるか
- 引数の評価の際に消費された文字列はいったん戻してから評価を続けるか
の二通りが考えられますが、まず、1.について考えてみます。
入力aaaに対して、1.の戦略で評価した場合、まず、引数の評価でaが消費され、残りの入力がaa、Aに"a"が束縛された状態で、評価が継続されます。その後、A Aとのマッチを続けるので、結果として、値はaaaになります。
一方、2.の戦略で評価した場合、まず、引数の評価の結果、Aに"a"が束縛された状態で、かつ、入力が消費されていない状態で、評価が継続されます。その後、A Aとのマッチを続けるので、結果として、値はaaになります。
さて、これだけだと値呼び出しにしてもあまり面白いことがないように思えますが、この「消費した文字列と引数を結びつけて、呼び出し先で使える」という性質を使って、XMLのタグの対応を書くことができます。
1.と2.のどちらでも実装できるのですが、1.の戦略だと、次のような感じになります。
S = F("<", [a-zA-Z_]+, ">");
F(LT, N, GT) = F("<", [a-zA-Z_]+, ">")* LT "/" N GT;
入力<a><b></b></a>に対して、マッチを試みてみます。
まず、XMLの開きタグをチェックするために、引数に "<", [a-zA-Z_]+, ">" を渡してマッチを行います（複数の引数がある場合は、前から順番に評価が行われるものとします）。引数の評価が終わった時点で、残りの文字列は<b></b></a>になります。
この状態で、LT=<、N=a、GT>としてFが呼び出されます。Fの中では再帰的にFを呼んでいます。一見左再帰のようにみえますが、引数の評価が失敗した場合、呼び出し自体も失敗するために左再帰になりません。F("<", [a-zA-Z_]+, ">")*の評価が終わった時点で、残りの入力文字列は</a>になっています。これは、LT "/" N GTとマッチするので全体が成功します。
このようにすることで、値呼び出しではXMLのタグの対応をチェック可能なことがわかりました。ちなみに、2.の戦略の場合でも、
S = "<" F([a-zA-Z_]+);
F(N) = N ">" ("<" F([a-zA-Z_]+))* "</" N ">";
とすることで、同じことを表現することができます。これをもう少し一般化した表現で考えると、Macro PEGの値呼び出しは、実質的に後方参照とほぼ等しい機能をもっていると言えそうに思います。
ちなみに、値呼び出しと名前呼び出しを組み合わせることで、次のように、「未宣言の変数の出現を構文エラーにする」といった強力な記述が可能になります（のはずです）。*は名前呼び出し、!は値呼び出しを表すプレフィックスとします。
Id <- [a-zA-Z_]+ Int <- [0-9]+ Statements(*table) <- "val " ValCont(table, Id) | Expression(table) ";" Statements(table) ValCont(*table, !id) <- id "=" Expression ";" Statements(table | id)? Expression(*table) <- &table Id | Int
このMacro PEGは、val x=1;x;1; やval x=1;val y=2;x;y;のような文字列を受理しますが、val x=1;z;のように、まだvalで宣言されていない変数が出現するような列を受理しません。
Macro PEGは名前呼び出しを使うことによって、引数に変数表のような役割を持たせることが可能で、一方で、値呼び出しによって、出現した名前を変数に入れておけるため、このような表現をすることが可能になりました。
名前呼び出しと値呼び出しを注釈によって使い分けられるMacro PEGの表現力はかなり強いのではないかと思えますが、どのくらいの言語が表現できるかはまだ未知ですが、色々面白い言語が表現できそうです。ちなみに、注釈はまだなものの、名前呼び出しと値呼び出し（２種類）は既に
GitHub - kmizu/macro_peg: Macro PEG: PEG with macro-like rules
