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.[citation needed]
Example
A well-known non-context-free language is
- [math]\displaystyle{ \{a^n b^n a^n | n \ge 1\}. }[/math]
A two-level grammar for this language is the metagrammar
- N ::= 1 | N1
- X ::= a | b
together with grammar schema
- Start ::= [math]\displaystyle{ \langle a^N \rangle\langle b^N \rangle\langle a^N \rangle }[/math]
- [math]\displaystyle{ \langle X^{N1} \rangle }[/math] ::= [math]\displaystyle{ \langle X^N \rangle X }[/math]
- [math]\displaystyle{ \langle X^1 \rangle }[/math] ::= X
See also
- Affix grammar
- Attribute grammar
- Van Wijngaarden grammar
References
- ↑ Shutt, John N.. "Two-level Grammars". http://web.cs.wpi.edu/~jshutt/adapt/2level.html.
- ↑ Estes, Matthew Scott (May 2005). "Properties of Infinite Languages and Grammars". A Thesis Presented to the Faculty of the Graduate School Tennessee Technological University. http://www.metanotion.net/misc/thesis.pdf#search=%22van%20Wijngaarden%20grammar%20Algol68%20ACM%20Portal%22.
- ↑ van Wijngaarden, A., ed. "Revised Report on the Algorithmic Language ALGOL 68". Archived from the original on 24 January 2002. https://web.archive.org/web/20020124152423/http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm.
- ↑ 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". Draft Lecture Notes. Archived from the original on 5 June 2001. https://web.archive.org/web/20010605175158/http://www.cs.chalmers.se/~kentp/proglang.pdf.
- Augusto, L. M. (2023). "Two-level grammars: Some interesting properties of van Wijngaarden grammars". Omega - Journal of Formal Languages 1: 3-34. https://philpapers.org/archive/AUGTGS-3.pdf.
 |
