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. Thus, the abandonment of the context 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 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.
In addition, the following 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.
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 every context; i.e. if X occurs somewhere 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 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 proceed from the definition of the syntax of the programming languages by a context-free grammar, by which a syntax analysis algorithm is specified.