Indexed Grammar - formallang.memo

"Indexed Grammars--An Extension of Context-Free Grammars" (1968)

文脈自由文法の拡張。OI Macro Grammar と等しい。

• Alfred V. Aho
• Journal of the ACM, vol. 15, pp. 647-671
• http://doi.acm.org/10.1145/321479.321488

どんなもの

非終端記号にスタック的にフラグを積める。フラグで分岐できる。

S → aA[f]c
A → aA[g]c
A → B
B[f] → b
B[g] → bB

で"a^n b^n c^n"。右辺の[f]はフラグをpushすることを示す。左辺の[f]はpopしてそのフラグだった場合の規則。

性質

• 構文解析はNP完全 [Rounds73, "Complexity of Recognition in Intermediate-Level Languages"] SATisfiableな論理式を全生成したりできる
• Full AFL
• emptinessは決定可能
• regularかどうか、context-freeかどうか、は決定不能
• 文脈依存言語には入る

Nested Stack Automaton

というタイプのオートマトンで受理できる言語クラスに等しい。要はスタックのスタックがある感じのオートマトン。

---