Chomsky hierarchy
The Chomsky hierarchy goes back to the linguist Noam Chomsky, who founded it in 1956. In doing so, Chomsky defined a hierarchy of four types of formal grammars that produce formal languages. The original aspect of Chomsky for this work was to find a mathematical descriptor for natural language.
The essence of the Chomsky hierarchy is that, starting from an unconstrained basic grammar (the type-0 grammar), constraints are placed on the production rules to be used for the type. Thus, the type-1 grammar is a subset of the type-0 grammar, the type-2 grammar is a subset of the type-1 grammar, and finally the type-3 grammar is a special case of the type-2 grammar. Incomputer science, Type-1 and Type-2 languages are primarily used in compiler construction, among other things.
Thus, based on the definition of the equivalence of grammars and the hierarchy of Chomsky grammars, a systematization of formal languages is possible. A grammar is a finite system of rules. It allows to generate (generative grammar) and to recognize (analyzing grammar) the generally infinite set of sentences of a formal language. Furthermore, this system of grammatical rules defines a syntactic structure for the sentences of the language, which is needed to establish a mapping between syntax and semantics in an appropriate way during program translation. The basic grammar model goes back to Noam Chomsky, who originally used it to describe syntactic properties of natural language.
The Chomsky model
It was shown that programming languages are more amenable to a theoretical, formalized treatment than natural languages because the structural properties of programming languages are much simpler. The Chomsky model has proven to be a fundamental model in the theory of programming languages. There are a large number of publications on grammars. The original grammar model has been refined and extended according to various points of view, for example to two- level grammars. Apart from their theoretical meaning the models of the Chomsky grammars are important practical tools for the definition of programming languages and a basis of the developments in the compiler construction, since the characteristics of the used grammars have substantial influence on the structure of the syntax analysis part and the coupling of the semantics.
Formally expressed for it the following theorem can be fixed:
A language L is called of Chomsky type i (i=0,1,2,3) if there is at least one grammar G(i) of Chomsky type i that generates LThe Chomsky hierarchy classifies grammars into four types :
Type-0 grammars represent the most general case. The rules are not subject to any further constraints. This model is so general that it cannot serve as a useful descriptor for programming languages.
Type-1 g rammars are called context-sensitive grammars. Chomsky type-1 grammars produce languages for which it can be decided in finite time whether an arbitrary string of characters is a sentence of the language or not.
Type-2 grammars are called context-free grammars. Programming languages can be described in terms of essential syntactic properties by context-free grammars.
Type-3 grammars are called regular grammars and impose the strongest constraints on the structure of rules. Each type-3 grammar produces a regular language. All regular languages are also contextual languages. Each derivation of a production rule is conditioned only by the one immediately preceding it. The connection to the operation of finite abstract automata is obvious, so that type-3 grammars are often used to define the lexical structure of programming languages.
As the type number increases, the structures of the corresponding languages become poorer. The type classification is not only of technical concern, but also represents a gradation in the complexity of languages. The Backus-Naur form and the syntax diagrams for the definition of programming languages are based on type 2 languages.