context sensiteve grammar
A grammar of type 1 in the Chomsky hierarchy is called a context-sensitive grammar. These forms of grammars are not as efficiently manageable in terms of their complexity, so they do not play a role in the description of programming languages. For practical use, type 3 and type2 - regular and context-free - grammars - of the Chomsky hierarchy, which are not so complex, are sufficient.
In natural languages, the grammar associated with the language defines the set of correct sentences allowed in the language. Analogously, programming languages are also described with the help of grammars. Thus not only languages can be described, but also a classification of languages can be made regarding the characteristics essential for the development of programming languages. This leads to a hierarchy of language classes, the so-called Chomsky hierarchy.
Alphabet: An alphabet A is a finite set of characters.
Grammar: A grammar G is a 4-tuple (T,N,P,s). Here:
- T the set of terminal symbols, which are the basic elements of the language,
- N the set of non-terminals,
- P the set of productions of the form a?b, with whose help a syntax tree is developed. Each production consists of a left and a right side with respect to a derivation arrow. The right side of a production is derived from the non-terminal on the left side here. Example: Block "BEGIN statement list END;
- s denotes the start symbol of the grammar from which any sentence in a language can be derived,
- V = T(u)N denotes the union set of terminal and non-terminal symbols, and
- V* denotes the strings over V
The above definition has the following background: the terminal symbols are the basic elements of the language. In programming languages, for example, these are the keywords such as Begin, End, or the arithmetic operators. Terminal symbols can be used to construct sentences according to the construction rules. The construction rules are called productions in connection with grammars, since these indicate that from the left side of the production the right side can be derived.
Context-sensitive grammar, type 1 grammar: All productions have the following form:
Here the length of a is less than or equal to the length of b. For this reason these languages are called context sensitive, because on the left side of productions also terminal symbols can stand.