- These grammars are known as phrase structure grammars. Their productions are of the form
- where both α and β can be strings of the terminal and nonterminal symbols. Such productions permit arbitrary substitution of strings during derivation or reduction, hence they are not relevant to the specification of programming languages.
- Productions of Type-1 grammars specify that derivation or reduction of strings can take place only in specific contexts. Hence these grammars are also known as context-sensitive grammars. A production of a Type -1 grammar has the form
αAβ → απβ
- Here, a string π can replace by ‘A’ (or vice versa) only when it is enclosed by the strings α and β in a sentential form. These grammars are also not relevant for programming language specification since recognition of programming language constructs is not context sensitive in nature.
- These grammars do not impose any context requirements on derivations or reductions. A typical Type -2 production is of the form
- which can apply independently of its context. These grammars are therefore known as context-free grammars (CFG). CFGs ideally suited for programming language specification.
- Type-3 grammars characterized by productions of the form
A → tB|t or
A → Bt|t
- Note that these productions also satisfy the requirements of type-2 grammars. The specific form of the RHS alternatives—namely a single nonterminal symbol or a string containing a single terminal symbol and a single nonterminal symbol, gives some practical advantages in scanning. However, the nature of the productions restricts the expressive power of these grammars, e.g., nesting of constructs or matching of
parentheses cannot be specified using such productions. Hence the use of Type -3 productions restricted to the specification of lexical units, e.g., identifiers, constants, labels, etc. Type-3 grammars are also known as linear grammars or regular grammars.