Элементы компиляции программ
Таким образом, предложение 8745 получается использованием правил вывода грамматики в следующей последовательности:
число › цифра число › 8 число › 8 цифра число › 87 число › 87 цифра число › 874 число › 874 цифра › 8745.
Важно отметить, что вывод предложения заканчивается лишь в том случае, если в нем содержатся только терминальные символы. Если этого сделать не удается, то это означает одно – целевое предложение недопустимо в этом языке. Для того чтобы отличить предложение, соответствующие промежуточному выводу, от конечного предложения, можно следовать общепринятой терминологии. В соответствии с нею любая строка терминалов и нетерминалов, которая получается из начального символа языка, называется сентенциальной формой. Предложением называется сентенциальная форма, не содержащая нетерминальных символов.
Для нашего примера сентенциальными формами являются все строки, которые получаются в процессе вывода:
цифра число, 8 число, 8 цифра число, 87 число, 87 цифра число, 874 число, 874 цифра, 8745.
Предложением языка является только одна из этих сентенциальных форм – строка 8745.
На правила грамматики обычно накладываются определенные ограничения. В зависимости от этих ограничений языки делятся на 4 класса.
- Класс 0. Грамматики без ограничений. Правила этих грамматик имеют форму: u › w. При этом не накладывается каких-либо ограничений на строки и и v в левой и правой частях правил вывода. Используя языки этого класса, можно моделировать естественный язык.
- Класс 1. Контекстно-чувствительные грамматики. Правила этих грамматик имеют форму: AuB › AwB. Замена и на v возможна лишь в контексте строк А и В (отсюда и название). При этом: ueVn; we(VnuVt)*; A, Be(VnuVt)+. Символы * и + обозначают множество всех строк, выводимых в рамках данной грамматики, включая ("*") и исключая ("+") пустую строку.
- Класс 2. Контекстно-свободные, или контекст}ю-нечувствительные, грамматики. Их правила имеют форму: u › w, где ueVn, we(VnuVt)*. Название данного класса грамматик отражает тот факт, что и можно заменить на w, не обращая внимания на контекст. Другая особенность грамматик этого класса в том, что в правой части всех правил грамматики стоит только один нетерминал. Отметим, что языки программирования моделируются с использованием грамматик именно этого класса.
- Класс 3. Регулярные, или автоматные, грамматики. Исходя из вида правил, которые используются в таких грамматиках, их делят на два подкласса.
- Грамматика, выравненная вправо. Ее правила имеют форму: u › Aw или и › А, где AeVt, u и weVn.
- Грамматика, выравненная влево. Ее правила имеют форму: u › \vA или и › А, где AeVt, u и weVn. Это очень важный класс грамматик, который наряду с грамматикой класса 2 используется для моделирования языков программирования.
Заметим, что рассмотренная выше грамматика языка целых чисел как раз и является грамматикой класса 3. Чтобы убедиться в этом, необходимо лишь немного подправить правила:
число:."¦ цифра число::*=0 число |1 число |2 число |3 число |4 число |5 число |6 число |7 число |8 число |9 число цифра:: = 0|1|2|3|4(5|6|7|8|9
Приведенная выше классификация языков была введена в 1959 году американским ученым-лингвистом Н. Хомским.
Выше, при изложении основ работы с двусвязными списками, мы ввели понятие конечного автомата. Язык, который воспринимает любой конечный автомат, относится к языкам класса 3, то есть является регулярным. Покажем это, сформулировав грамматику для языка вещественных чисел. Напомним соответствующее регулярное выражение: (+| – )dd*.dd*e(+| 0dd*), где d* обозначает цифру 0-9 или пусто.
Greal-{Vt-(.. +. – . е. 0. 1, 2, 3. 4. 5. 6. 7. 8. 9). VrHreal .s .m, n .k, t). P. Z-(< real >)}.
Множество правил P грамматики Greal:
real › +s|-s|Ds s › ds | .m m › Dn | D n › Dn | ek k › +t|-t|Dt|D T › dT|d
Попробуйте, используя данную грамматику, самостоятельно вывести следующие предложения языка вещественных чисел: 5.5, +0.6е-5. Покажите, что предложение "+.45е4" невыводимо в терминах данной грамматики. При необходимости посмотрите еще раз материал раздела "Сеть" данной главы, где было введено понятие конечного автомата и разработана программа, моделирующая его работу при распознавании строки с вещественным числом.
Анализ правил вывода грамматики Greal показывает, что генерируемый ею язык относится к языкам класса 3, а сама грамматика является грамматикой, выровненной вправо.