- Two-level grammar
A two-level grammar is either one of two formal structures:
# Aformal grammar for a two-levelformal 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 howVan Wijngaarden grammar was used to specify Algol68 [http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm] . Acontext 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 beTuring complete .Example
A well-known non-context-free language is:A two-level grammar for this language is the metagrammar:N ::= 1 | N1:X ::= a | btogether with grammar schema:Start ::= : ::= : ::= 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] .
Wikimedia Foundation. 2010.