Two-level grammar

From Wikipedia, the free encyclopedia

A two-level grammar is either one of two formal structures:

  1. 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.[citation needed]
  2. A formal grammar that is used to generate another formal grammar[1], such as one with an infinite rule set[2] and such as how Van Wijngaarden grammar was used to specify Algol68[3]. 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.

[edit] 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 | 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

[edit] See also

[edit] External links

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


Soft Eng logo This computer language-related article is a stub. You can help Wikipedia by expanding it.
Languages