A two-level grammar is a
formal grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...
that is used to generate another formal grammar, such as one with an infinite rule set. This is how a
Van Wijngaarden grammar
In computer science, a Van Wijngaarden grammar (also vW-grammar or W-grammar) is a two-level grammar which provides a technique to define potentially infinite context-free grammars in a finite number of rules. The formalism was invented by Adriaa ...
was used to specify
Algol 68
ALGOL 68 (short for ''Algorithmic Language 1968'') is an imperative programming language that was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and more rigorously ...
. A
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...
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
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
.
''Two-level grammar'' can also refer to a formal grammar for a two-level
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of s ...
, 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
See also
*
Affix grammar
An affix grammar is a kind of formal grammar; it is used to describe the syntax of languages, mainly computer languages, using an approach based on how natural language is typically described.Koster, Cornelis HA.Affix grammars for natural languages ...
*
Attribute grammar An attribute grammar is a formal way to supplement a formal grammar with semantic information processing. Semantic information is stored in attributes associated with terminal and nonterminal symbols of the grammar. The values of attributes are re ...
*
Van Wijngaarden grammar
In computer science, a Van Wijngaarden grammar (also vW-grammar or W-grammar) is a two-level grammar which provides a technique to define potentially infinite context-free grammars in a finite number of rules. The formalism was invented by Adriaa ...
References
External links
*
*
Formal languages
{{compu-lang-stub