Adaptable Grammars for Non-Context-Free Languages

We consider, as an alternative to traditional approaches for describing non-context-free languages, the use

of grammars in which application of grammar rules themselves control the creation or modification of grammar rules.

This principle is shown to capture, in a concise way, standard example languages that are

considered as prototype representatives of non-context-free phenomena in natural languages.

We define a grammar formalism with these characteristics and show how it can be implemented in logic programming

in a surprisingly straightforward way, compared with the expressive power.

It is also shown how such adaptable grammars can be applied for describing meta-level architectures that include their own explicit meta-languages for defining new syntax