Two-level grammar

A two-level grammar is either one of two formal structures:
# 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.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 grammar was used to specify Algol68 [http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm] . A context free grammar that 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.

Example

A well-known non-context-free language is:{a^n b^n a^n | n ge 1}.A two-level grammar for this language is the metagrammar:N ::= 1 | N1:X ::= a | btogether with grammar schema:Start ::= langle a^N anglelangle b^N anglelangle a^N angle : langle X^{N1} angle ::= langle X^N angle X : langle X^1 angle ::= X

ee also

*Van Wijngaarden grammar

External links

* 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.