A two-level grammar is a formal grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 that is used to generate another formal grammar http://web.cs.wpi.edu/~jshutt/adapt/2level.html, such as one with an infinite rule set http://www.metanotion.net/misc/thesis.pdf#search=%22van%20Wijngaarden%20grammar%20Algol68%20ACM%20Portal%22. This is how a Van Wijngaarden grammar

Van Wijngaarden grammar

In computer science, a Van Wijngaarden grammar is a two-level grammar which provides a technique to define potentially infinite context-free grammars in a finite number of rules...

 was used to specify Algol68 http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm. 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

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

, 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 two-level grammar for this language is the metagrammar

N ::= 1 | N1

X ::= a | b

together with grammar schema

Start ::= ::= ::= X

External links

• Petersson, Kent (1990), "Syntax and Semantics of Programming Languages", Draft Lecture Notes, PDF text.