Derivations from Two-Level Grammars have been defined only in terms of the infinite context-free grammars that can be generated from them. This fact has proven a severe theoretical obstacle to solving the parsing problem for two-level grammars. So far, partial solutions exist for Van Wijngaarden Grammars, Extended Affix Grammars, and Affix Grammars which allow parsing in a single pass from left to right, because these special cases could be handled without developing a full theory of parsing for two-level grammars.
https://link.springer.com/chapter/10.1007/BFb0022511
https://ru.wikipedia.org/wiki/Двухуровневая_грамматика
https://en.wikipedia.org/wiki/Two-level_grammar
https://en.wikipedia.org/wiki/Van_Wijngaarden_grammar
generative two-level grammars have actually been shown to be Turing complete.
Отредактировано Лис (2018-04-09 05:54:20)