Two-level grammar
A two-level grammar is a formal grammar that is used to generate another formal grammar,[1] such as one with an infinite rule set.[2] This is how a Van Wijngaarden grammar was used to specify Algol 68.[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. 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.[4]
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 ::=
- ::=
- ::= X
References
- Shutt, John N. "Two-level Grammars".
- Estes, Matthew Scott (May 2005). "Properties of Infinite Languages and Grammars" (PDF). A Thesis Presented to the Faculty of the Graduate School Tennessee Technological University.
- van Wijngaarden, A.; et al. (eds.). "Revised Report on the Algorithmic Language ALGOL 68". Archived from the original on 24 January 2002.
- Sintzoff, M. (1967). "Existence of van Wijngaarden syntax for every recursively enumerable set". Annales de la Société Scientifique de Bruxelles. 2: 115–118.
External links
- Petersson, Kent (1990). "Syntax and Semantics of Programming Languages" (PDF). Draft Lecture Notes. Archived from the original (PDF) on 5 June 2001.
- Augusto, L. M. (2023). "Two-level grammars: Some interesting properties of van Wijngaarden grammars" (PDF). Omega - Journal of Formal Languages. 1: 3–34.