Two-level grammar
# Two-level grammar

A two-level grammar is a formal grammar that is used to generate another formal grammar, such as one with an infinite rule set. This is how a Van Wijngaarden grammar was used to specify Algol 68. A context-free grammar that defines the rules for a second grammar can yield an effectively infinite set of rules for the derived grammar. This makes such two-level grammars more powerful than a single layer of context-free grammar, because generative two-level grammars have actually been shown to be Turing complete.

Two-level grammar can also refer to a formal grammar for a two-level formal language, which is a formal language specified at two levels, for example, the levels of words and sentences.

## Example

A well-known non-context-free language is

    $\{a^{n}b^{n}a^{n}|n\geq 1\}.$

A two-level grammar for this language is the metagrammar

    N ::= 1 | N1
    X ::= a | b

together with grammar schema

    Start ::= $\langle a^{N}\rangle \langle b^{N}\rangle \langle a^{N}\rangle$
    $\langle X^{N1}\rangle$ ::= $\langle X^{N}\rangle X$
    $\langle X^{1}\rangle$ ::= X
