ITWissen.info - Tech know how online

contextless grammar

A grammar analogous to the type-2 grammar of the Chomsky hierarchy is called a context-free grammar. Programming languages

can be described in essential syntactic properties by context-free grammars. The model of context-free grammars in language description allows to analyze or synthesize the sentences of the language

by decomposition into independent sections. Theabandonment of the context thus simplifies the structure of the grammar.

A grammar is a quadruple G = (N,T,R,S) with

  • the finite set of symbols, also called non-terminals, nonterminals or variables,
  • the finite set of language-forming terminal signs, the terminals T,
  • the finite set R of production rules, also called productions or rules, and
  • the initial symbol S of a sentence.
Here, moreover, holds:

  • the non-terminals N and the terminals are disjoint (which means element-unrelated),
  • the start symbol S is part of the set of nonterminals N and
  • for the total alphabet A = N u T holds.
Context-free grammar

Context-free grammar

This means that the production rules of a context-free grammar are characterized by the fact that there is always only one variable on its left-hand

side. The term context-free comes from the fact that the substitution of X by u is permissible in any context; i.e. if X occurs anywhere in a word w, it may be substituted by u. In contrast, say aXb by aub is a context-sensitive production, which allows substitution of X by u only in the context a..b. Context-free grammars are very significant for the theory of programming languages and the closely related questions of syntactic analysis because of their clear structure, and have already been widely studied. The known programming languages can be described in their essential syntactic properties by context-free grammars. The language implementations start from the definition of the syntax of the programming languages by a context-free grammar, by which a syntax analysis algorithm is specified.

Informationen zum Artikel
Englisch: contextless grammar
Updated at: 25.04.2010
#Words: 345
Links:
Translations: DE