Grammar
المؤلف:
Aho, A. V. and Ullman J. D
المصدر:
Theory of Parsing, Translation and Compiling, Vol. 1. Englewood Cliffs, NJ: Prentice Hall, 1972.
الجزء والصفحة:
...
24-1-2022
1159
Grammar
A grammar defining formal language 
is a quadruple 
, where 
is a finite set of nonterminals, 
is a finite set of terminal symbols, 
is a finite set of productions, and 
is an element of 
.
The set 
of terminal symbols is 
's alphabet. Nonterminals are symbols representing language constructs. The sets 
and 
should not intersect. 
is called the start symbol. Productions are rules of the form: 
, where both 
and 
are strings of terminals and nonterminals, 
contains at least one nonterminal.
Sentential forms for grammar 
are defined by the following rules: 
is a sentential form and if 
is a sentential form and production 
belongs to 
, then 
is a sentential form as well.
is the set of all strings which are sentential forms consisting entirely of terminal symbols. For a language defined by a grammar, recognition whether a given string (expression) belongs to that language is, in general, a non-trivial task. All languages defined by grammars are recursively enumerable sets.
1. A grammar 
is called right linear if all its productions have the form 
or 
, where 
and 
is a string of terminal symbols.
2. A grammar 
is called context-free if all its productions have the form 
, where 
and 
is a string of terminal and nonterminal symbols.
3. A grammar 
is called context-sensitive if all its productions have the form 
, where both 
and 
are strings of terminal and nonterminal symbols and the length of 
is not more than the length of 
.
4. A grammar 
is called unrestricted if it does not belong to categories 1 through 3.
This hierarchy of grammars was introduced by N. Chomsky. The set of languages defined by grammars of every category is a proper superset of that for the previous category. The languages defined by grammars of categories 1 through 3 are recursive sets. A language can be defined by a grammar of category 1 iff it is defined by a regular expression.
REFERENCES
Aho, A. V. and Ullman J. D. Theory of Parsing, Translation and Compiling, Vol. 1. Englewood Cliffs, NJ: Prentice Hall, 1972.
Aho, A. V. and Ullman J. D. Theory of Parsing, Translation and Compiling, Vol. 2. Englewood Cliffs, NJ: Prentice Hall, 1972.
الاكثر قراءة في المنطق
اخر الاخبار
اخبار العتبة العباسية المقدسة
