Two-level Grammars

This page is Copyright John N. Shutt 1996–2001, 2007.  Here's what you're allowed to do with it.
Last modified:  05-Jul-07.

Two-level grammars, as suggested by Adriaan van Wijngaarden in 1965 (and also described by Alfonso Caracciolo di Forino at about the same time), are a way of getting the power of Type 0 Chomsky Grammars using only context-free syntax rules.  The trick is to use a context-free metagrammar, whose sentences are the syntax rules of a context-free grammar that generates the target language.  Thus, the target language is defined by a context-free grammar that may have an infinite number of rules (because the set of rules is a context-free language generated by the metarules).  Two-level grammars are Turing-powerful.

Two-level grammars are not adaptive, according to the definition of the term I've chosen, because they do not manipulate rule sets explicitly, per se.  However, anyone designing metarules for a two-level grammar must be primarily concerned with the internal structure of the set of rules that will be generated; so two-level and adaptive grammars do share a central concern with the formation of rule sets.

It should not be surprising, then, that adaptive grammarists have sometimes dabbled in two-level grammars.

There is a detailed discussion of van Wijngaarden grammars in my Master's thesis.

Offline sources:  W-grammars: [Wijn 65] (also online here), [Clea 76], [Kost 91].  See also [Demb 78], [Cohe 88], [Kost 91].  Caracciolo's two-level grammars: [Cara 66].

Up: Adaptive Grammars