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 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^ \rangle$ ::= $\langle X^N \rangle X$
:$\langle X^1 \rangle$ ::= X

See also

*Affix grammar
*Attribute grammar
*Van Wijngaarden grammar

References

External links

*
*

Formal languages

{{compu-lang-stub