Two-level grammar

A two-level grammar is either one of two formal structures:
# 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.Fact|date=February 2007
# A formal grammar 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] and such as how Van Wijngaarden grammar 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. Two-level grammars that can generate another context free grammar are more powerful than a single layer of context free grammar, because generative two-level grammars have actually been shown to be Turing complete.

Example

A well-known non-context-free language is:$\{a^n\; b^n\; a^n\; |\; n\; ge\; 1\}.$A two-level grammar for this language is the metagrammar:N ::= 1 | N1:X ::= a | btogether with grammar schema:Start ::= $langle\; a^N\; anglelangle\; b^N\; anglelangle\; a^N\; angle$:$langle\; X^\{N1\}\; angle$ ::= $langle\; X^N\; angle\; X$:$langle\; X^1\; angle$ ::= X

ee also

*Van Wijngaarden grammar

External links

* Petersson, Kent (1990), "Syntax and Semantics of Programming Languages", Draft Lecture Notes, [http://www.cs.chalmers.se/~kentp/proglang.pdf PDF text] .