 |
Тип 3: регулярные грамматики
|
|
|
|
Леволинейные грамматики G (VT,VN, P, S), V = VN 
VT могут иметь правила ух видов: А→B 
или А→ , где A, B 
VN, VT*.
Праволинейные грамматики G(VT, VN, P, S), V = VN VT могут меть правила тоже двух видов: А→ В или А→ , где A, B VN, 
VT*.
Эти два класса грамматик эквивалентны и относятся к типу регулярных грамматик.
Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев т. д. Эти грамматики исключительно просты и удобны в использовании, поэтому в компиляторах на их основе строятся функции лексического анализа входного языка.
Типы грамматик соотносятся между собой особым образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика может быть отнесена к типу 0, поскольку он не накладывает никаких ограничений на правила. В то же время существуют укорачивающие КС-грамматики (тип 2), которые не являются ни контекстно-зависимыми, ни неукорачивающими (тип 1), поскольку могут содержать правила вида «А→ 
», недопустимые в типе 1.
Одна и та же грамматика в общем случае может быть отнесена к нескольким классификационным типам. Для классификации грамматики всегда выбирают максимально возможный тип, к которому она может быть отнесена. Сложность грамматики обратно пропорциональна номеру типа, к которому относится грамматика. Грамматики, которые относятся только к типу 0, являются самыми сложными, а грамматики, которые можно отнести к типу 3, – самыми простыми.
Рассмотренная в примере грамматика, определяющая язык целых десятичных чисел со знаком относится к контекстно-свободным грамматикам (тип 2). Следовательно, ее можно отнести и к типу 0 и к типу 1. Данная грамматика не может быть отнесена к типу 3, поскольку правило <чсл> → <чсл><цифра> недопустимо для него.
|
|
|
Языки классифицируются в соответствии с типами грамматик, с помощью которых они заданы. Сложность языка также убывает с возрастанием номера классификационного типа языка.
В основе большинства современных языков программирования лежат контекстно-свободные языки.
Контрольные вопросы
1. Как выглядит описание грамматики в форме Бэкуса-Наура?
2. Каковы составляющие формального описания грамматики?
3. Как классифицируются языки? Как их классификация соотносится с классификацией грамматик?
4. Почему язык программирования нельзя не является чисто формальным языком?
5. Какой тип грамматики самый сложный?
6. Грамматики G(VT,VN, P, S), V = VN VT, которые могут иметь правила двух видов: А → B или А → , где A, B VN, VT* относятся к типу:
а) праволинейных грамматик;
б) леволинейных грамматик;
в) контексно-свободных грамматик;
г) контексно-зависимых грамматик.
7. Выберите верное утверждение:
а) неукорачивающие грамматики имеют такую структуру правил, что при построении предложений языка, заданного грамматикой, любая цепочка символов может быть заменена цепочкой символов меньшей длины;
б) целевой символ грамматики – это всегда терминальный символ;
в) языки классифицируются в соответствии с типами грамматик, с помощью которых они заданы;
г)языки программированияявляются формальными языками.
8. Для любого языка, заданного какой грамматикой, можно построить неукорачивающую грамматику, которая будет задавать эквивалентный язык.
а) контекстно-свободной грамматикой
б) грамматикой с фразовой структурой
в) контексно-зависимой грамматикой
г) регулярной грамматикой
Задание
1. Определить тип указанных грамматик
|
|
|
1.1) G1 ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, – }, {A, B}, P, A):
P: A→ B | +B | –B
B→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0B | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B
1.2) G2 ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, – }, {S, B}, P, S):
P: B→ + | – |
S→ B0 | B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8 | B9 | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9
1.3) G3 ({0, 1}, {A, S}, P, S)
P: S→ 0A1
0A→00A1
A→
1.4) G4 ({0, 1}, {A, S}, P, S)
P: S→ 0A1 | 01
0A→00A1 | 001
A→
1.5) G5 ({0, 1}, { S}, P, S)
P: S→ 0S1 | 01
1.6) G5 ({f, g, h}, { G, H, E, S}, P, S)
P: S→ GH
G → fGgH | fg
Hg →gH
HE → Hh
gEh → ghh
fgE → fgh
2. Определить язык грамматики G ({+, –, *, /, (,), x, y}, {S}, P, S):
P: S → S+S | S–S | S*S | S/S | (S) | x | y
3. Поездом называется произвольная последовательность локомотивов и вагонов. Построить грамматику в форме Бэкуса-Наура для понятия «поезд», если
3.1) поезд всегда начинается с локомотива;
3.2) все локомотивы должны быть сосредоточены в начале поезда;
3.3) поезд начинается с локомотива и заканчивается локомотивом;
3.4) в поезде должны чередоваться через два локомотивы и вагоны;
3.5) поезд не должен содержать два локомотива или два вагона подряд;
3.6) поезд не должен содержать подряд два локомотива.
|
|
|
