"Grammars with Macro-like Productions" (1968)
文脈自由文法を拡張して、それぞれの非終端記号がパラメタを取れるようにしたもの。
"a^n b^n c^n" を生成する文法の例
S → R(,,)
R(x,y,z) → R(ax,by,cz)
R(x,y,z) → xyz
パラメタの評価戦略によって
- IO : Inside-Out, いわゆる call-by-value
- OI : Outside-In, いわゆる call-by-name
生成される言語が変わることがわかっている。IOとOIという用語の起源はここだろうか…。OI Macro Grammar は
Indexed Grammar に等しいことがこの論文で示されている。IOとOIはどちらもCFGより真に強く、uncomparable。どちらもも文脈依存言語には入る。IOで評価するかOIで評価するかを明示するQuoted Macro Grammarというクラスも提案されている（Lispのクオート/アンクオート的な意味で"Quoted"）。ただ、あんまりQuoted Grammarはその後研究されていないような気がする。QuotedがContext-Sensitiveかは1968時点ではopen。
IO Macro Grammar
かと思いきや、
に関して閉じていない
決定可能
構文解析
IOだけどOIじゃない言語
S → F(a)
F(x) → G(F(xa)) | G(x)
G(x) → xcx
非決定的に長い文字列を作ってからそれをコピーして回る、のがIOは得意。OIは不得意。
OI Macro Grammar
演算に関して閉じている
決定可能
構文解析
- NP完全 [Rounds73, "Complexity of Recognition in Intermediate-Level Languages"] SATisfiableな論理式のみを全生成する文法が書ける
OIだけどIOじゃない言語
S → F(A)
F(x) → F(xx)|xx
A → aA | Aa | b
ちょうど2^n個のbと、間に挟まりまくったa。非決定的に"似たような"文字列を大量コピーするのがOIは得意、IOは不得意
最終更新：2009年02月20日 16:04
