formal grammar
Formal grammars are mathematical models which can subsequently be used to generate formal languages. Formal grammars are used, among other things, in computational linguistics and in compiler construction. The different types of grammars are classified analogously to the Chomsky hierarchy.
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.
- the non-terminals N and the terminals are disjoint (that means element-unrelated) and
- the start symbol S is part of the set of nonterminals N.
Basic concepts related to a formal grammar include:vocabulary: The vocabulary is the set of all terminal and nonterminal elements of a formal grammar.
Nonterminal: Nonterminals denote a syntactic category and are essentially auxiliary symbols used for the grammar's generation or recognition of the formal language 's sentences. For notation: nonterminals are usually represented by capital letters or in "parentheses".
Terminal: Terminals are those elements of which the words of the formal language to be generated are composed and thus characterize its alphabet. Regarding their notation: terminals are usually represented by lowercase letters.
Productions: The set of production rules is a two- digit relation (u,v). The left and right parts of this relation are sets of character sequences over the vocabulary, excluding that the left part of the relation contains only terminal elements. This restriction does not exist for the right part of the relation. Furthermore, the empty character string is allowed in the right part, but excluded in the left part of the relation.
Start symbol: The start symbol marks the beginning of the generation or recognition of sentences of the formal language by the grammar.
As an example, consider the following quadruple:
For the generation of a formal language there can always be several formal grammars.