A two-level grammar is either one of two formal structures:
formal grammarfor a two-level formal language, which is a formal language specified at two levels, for example, the levels of words and sentences.Fact|date=February 2007
# A formal grammar that is used to generate another formal grammar [http://web.cs.wpi.edu/~jshutt/adapt/2level.html] , such as one with an infinite rule set [http://www.metanotion.net/misc/thesis.pdf#search=%22van%20Wijngaarden%20grammar%20Algol68%20ACM%20Portal%22] and such as how
Van Wijngaarden grammarwas used to specify Algol68 [http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm] . A context free grammarthat 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.
A well-known non-context-free language is:A two-level grammar for this language is the metagrammar:N ::= 1 | N1:X ::= a | btogether with grammar schema:Start ::= : ::= : ::= X
Van Wijngaarden grammar
* Petersson, Kent (1990), "Syntax and Semantics of Programming Languages", Draft Lecture Notes, [http://www.cs.chalmers.se/~kentp/proglang.pdf PDF text] .
Wikimedia Foundation. 2010.
Look at other dictionaries:
Grammar Explorer — is a language learning resource that was co funded by the European Commission as part of its [http://ec.europa.eu/education/programmes/socrates/lingua/index en.html Lingua programme] within the SOCRATES programme. The grammar is based on the… … Wikipedia
Grammar school — A grammar school is one of several different types of school in the history of education in the United Kingdom and other English speaking countries.In the modern United States, the term is synonymous with elementary school.The original purpose of … Wikipedia
grammar school — 1. an elementary school. 2. Brit. a secondary school corresponding to a U.S. high school. 3. (formerly) a secondary school in which Latin and Greek are among the principal subjects taught. [1350 1400; ME] * * * ▪ British education in Great… … Universalium
Grammar checker — In computing terms, a grammar checker is a program, or part of a program, that attempts to verify written text for grammatical correctness. Grammar checkers are most often implemented as a feature of a larger application, such as a word processor … Wikipedia
level — 1 / levFl/ noun (C) 1 AMOUNT a) the measured amount of something that exists at a particular time or in a particular place: Inflation had dropped to its lowest level in 30 years. (+ of): concern about the level of carbon monoxide in the air |… … Longman dictionary of contemporary English
level — lev|el1 W1S1 [ˈlevəl] n ▬▬▬▬▬▬▬ 1¦(amount)¦ 2¦(standard)¦ 3¦(height)¦ 4¦(floor/ground)¦ 5¦(rank of job)¦ 6¦(way of understanding)¦ 7 at local/state/national etc level 8 a level playing field 9 be on the level … Dictionary of contemporary English
Grammar of Assent — An Essay in Aid of a Grammar of Assent is John Henry Newman s seminal work. Though completed in 1870, Newman revealed to friends that it took him 20 years to write the book after many fits and starts.The Grammar was an apologia for faith. Newman… … Wikipedia
Two-source hypothesis — The Two Source hypothesis proposes that the authors of Matthew and Luke drew on the Gospel of Mark and a hypothetical collection of sayings of Jesus known as Q . The Two Source Hypothesis (or 2SH) is an explanation for the synoptic problem, the… … Wikipedia
Van Wijngaarden grammar — A Van Wijngaarden grammar (also vW grammar or W grammar) is a two level grammar which provides a technique to define potentially infinite grammars in a finite number of rules. It was invented by Adriaan van Wijngaarden to define rigorously some… … Wikipedia
Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… … Wikipedia