close

Вход

Забыли?

вход по аккаунту

?

914.Технологии трансляции Соколов В А

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П.Г. Демидова
В.А. Соколов, Д.Ю. Чалый
Технологии трансляции
Учебное пособие
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по специальности Математическое обеспечение и
администрирование информационных систем
Ярославль 2008
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК
ББК
004.4
В182я 73
С59
Учебное издание
Соколов Валерий Анатольевич
Чалый Дмитрий Юрьевич
Рекомендовано
редакционно-издательским советом университета
в качестве учебного издания. План 2008 года
Рецензенты:
Вейцман В.М., к.т.н., доцент, директор института информационных
технологий МУБиНТ;
кафедра прикладной математики и вычислительной техники Ярославского
государственного технического университета
С59
Соколов, В.А. Технологии трансляции: учебное пособие /
В.А. Соколов, Д.Ю. Чалый; Ярославский гос. ун-т
им. П.Г. Демидова. — Ярославль: ЯрГУ, 2008. — 124 c.
ISBN 978-5-8397-0630-9
Технологии трансляции
Учебное пособие
Редактор, корректор М.В. Никулина
Компьютерная верстка Д.Ю. Чалый
Пособие содержит систематическое изложение теоретических и практических подходов к созданию трансляторов для языков программирования.
Описываются алгоритмы и методики для построения различных компонентов
транслятора — лексического, синтаксического и семантического анализаторов,
а также методы для описания перевода.
Пособие предназначено для студентов, обучающихся по специальности
010503 Математическое обеспечение и администрирование информационных
систем (дисциплина ≪Технологии трансляции≫, блок ДС), очной формы обучения.
УДК
ББК
004.4
В182я 73
Подписано в печать 17.07.2008 г. Формат 60×84/16.
Бумага тип. Усл.-печ.л. 7,21. Уч. изд. л. 7,5.
Тираж 200 экз. Заказ
.
Оригинал-макет подготовлен в редакционно-издательском отделе ЯрГУ
Ярославский государственный университет
150004 Ярославль, ул. Советская, 14
ISBN 978-5-8397-0630-9
© Ярославский государственный университет
им. П.Г. Демидова, 2008
Отпечатано
ООО ≪Ремдер≫ ЛР ИД №06151 от 26.10.2001
г. Ярославль, пр. Октября, 94, оф. 37
тел. (4852) 73-35-03, 58-03-48, факс 58-03-49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
122
Список литературы
29. Unger, S.H. A global parser for context-free phrase structure
grammars / S.H. Unger // Communications of ACM. — 1968. —
Vol. 11, № 4. — pp. 240–247.
30. Yershov, A.P. The Alpha Automatic Programming System /
A.P. Yershov. — Academic Press, 1971. — 247 p.
31. Younger, D.H. Recognition and parsing of context-free languages in
time n3 / D.H. Younger // Inform. Control. — 1967. — Vol. 10, № 2. —
pp. 189–208.
ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Г л а в а 1. Элементы теории формальных языков . . . . . . . . .
7
1.1. Формальные языки и грамматики . . . . . . . . . . . . . . . . . . . .
7
1.1.1. Определение грамматики (8). 1.1.2. Классификация Хомского для формальных грамматик (10). 1.1.3. Описание грамматик на
практике (12).
1.2. Порождение строк с помощью грамматик . . . . . . . . . . . . . .
12
1.2.1. Левосторонние и правосторонние выводы (13). 1.2.2. Деревья разбора (14). 1.2.3. Неоднозначные языки и грамматики (15).
1.3. Эквивалентные преобразования грамматик . . . . . . . . . . . . .
17
1.3.1. Оптимизация грамматик (18). 1.3.2. Удаление ε-продукций (22). 1.3.3. Удаление цепных продукций (24). 1.3.4. Нормальная форма Хомского для КС-грамматик (24). 1.3.5. Нормальная форма Грейбах для КС-грамматик (26). 1.3.6. Устранение
левой рекурсии (26). 1.3.7. Левая факторизация (27).
Г л а в а 2. Лексический анализ . . . . . . . . . . . . . . . . . . . . . . . .
29
2.1. Роль лексического анализатора . . . . . . . . . . . . . . . . . . . . . .
29
2.2. Понятие токенов и лексем . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.2.1. Способы задания токенов (31).
нов (33).
2.2.2. Атрибуты токе-
2.3. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.3.1. Детерминированные конечные автоматы (34). 2.3.2. Недетерминированные конечные автоматы (35). 2.3.3. Эквивалентность ДКА и НКА (37). 2.3.4. Конечные автоматы с ε-переходами (39). 2.3.5. Минимизация конечных автоматов (40). 2.3.6. От
регулярных грамматик к НКА (41). 2.3.7. От регулярных выражений к НКА (43).
2.4. Алгоритмы распознавания токенов . . . . . . . . . . . . . . . . . . .
44
2.4.1. Распознавание лексем с помощью НКА (44). 2.4.2. Распознавание лексем с помощью ДКА (45). 2.4.3. Скорость работы (45). 2.4.4. Распознавание токенов (46).
2.5. Формирование таблиц имен . . . . . . . . . . . . . . . . . . . . . . . .
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4
Оглавление
Список литературы
Г л а в а 3. Синтаксический анализ . . . . . . . . . . . . . . . . . . . . .
52
3.1. Обзор методов разбора КС-грамматик . . . . . . . . . . . . . . . . .
52
3.2. Универсальные методы синтаксического анализа . . . . . . . . .
53
3.2.1. Метод Ангера для грамматик без циклов и ε-продукций (53).
3.2.2. Метод Ангера для произвольных КС-грамматик (57).
3.2.3. Метод Кока—Янгера—Касами (59).
3.3. Синтаксический анализ с использованием магазинных автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
3.3.1. Магазинные автоматы (62). 3.3.2. Построение эквивалентного МП-автомата для заданной КС-грамматики (65). 3.3.3. Методы детерминированного моделирования работы МП-автомата (67).
3.4. Метод рекурсивного спуска . . . . . . . . . . . . . . . . . . . . . . . . .
72
3.4.1. Общие принципы (73). 3.4.2. Исчерпывающий рекурсивный
спуск с возвратами (76).
3.5. Алгоритм разбора для LL-грамматик . . . . . . . . . . . . . . . . . .
82
3.5.1. Выбор продукции с помощью таблиц (83). 3.5.2. Построение
разбора для LL(1)-грамматик (83). 3.5.3. Разбор строк с использованием LL(k)-грамматик (88).
3.6. Синтаксический анализ для LR-грамматик . . . . . . . . . . . . .
89
3.6.1. Анализатор для LR(0)-грамматик (91). 3.6.2. Построение
анализаторов для LR(1)-грамматик (96). 3.6.3. Построение управляющей таблицы LR-анализатора (97). 3.6.4. LR(k > 1)-грамматики и их анализ (100).
3.7. Обнаружение и обработка ошибок . . . . . . . . . . . . . . . . . . . . 100
3.7.1. Обнаружение и обработка лексических ошибок (102).
3.7.2. Обнаружение синтаксических ошибок (102). 3.7.3. Обработка ошибок в глобальном контексте (104). 3.7.4. Обработка
ошибок в локальном контексте (106).
Г л а в а 4. Основы теории перевода . . . . . . . . . . . . . . . . . . . . 109
4.1. Формальное определение перевода . . . . . . . . . . . . . . . . . . . 109
4.2. Схема синтаксически управляемого перевода . . . . . . . . . . . . 110
4.3. Атрибутные грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.3.1. Графы зависимости (114). 4.3.2. S-атрибутные грамматики (116). 4.3.3. L-атрибутные грамматики (116). 4.3.4. Применение атрибутных грамматик (117).
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
121
14. Fischer, C.M. Efficient LL(1) error correction and recovery using
only insertions / C.M. Fischer, D.R. Milton, S.B. Quiring // Acta
Informatica — 1980. — Vol. 13, № 2 — pp. 141–154.
15. Graham, S.L. Pracical syntactic error recovery / S.L. Graham,
S.P. Rhodes // Communications of ACM. — 1975. — Vol. 18, № 11. —
pp. 639–650.
16. Grune, D. Parsing Techniques. A Practical Guide / D. Grune,
C.J.H. Jacobs. — Second Edition. — Springer, 2008. — 664 p.
17. Grune, D. Modern Compiler Design / D. Grune, H.E. Bal,
C.J.H. Jacobs, K.G. Langendoen. — Jon Wiley & Sons, 2000. —
736 p.
18. Greibach, S. A new normal form theorem for context-free context
phrase structure grammars / S. Greibach // Journal of ACM. —
1965. — Vol. 12, № 1. — pp. 42–52.
19. Horning, J.J. What the compiler should tell the user / J.J. Horning //
Lecture Notes in Computer Science — 1976. — Vol. 21. — pp.525–548.
20. Kasami, T. A syntax-analysis procedure for unambigous contextfree grammars / T. Kasami, K. Torii // Journal of ACM. — 1969. —
Vol. 16, № 3. — pp. 423–431.
21. Knuth, D.E. On the translations of languages from left to right /
D.E. Knuth // Inform. Control. — 1965. — Vol. 8. — pp. 607–639.
22. Knuth, D.E. Semantics of context-free languages / D.E. Knuth //
Math. Syst. Theory — 1968. — 2(2) — pp. 127–145.
23. Knuth, D.E. Top-down syntax analysis / D.E. Knuth // Acta
Informatica — 1971. — № 1 — pp. 79–110.
24. Lyon, G. Syntax-directed least-errors analysis for context-free
languages: a practical approach / G. Lyon // Communications of
ACM. — 1974. — Vol. 17, № 1. — pp. 3–14.
25. McKenzie, B.J. Error repair in shift-reduce parsers / B.J. McKenzie,
C. Yeatman, L. De Vere // ACM Trans. Programming Languages and
Systems. — 1995. — Vol. 17, № 4. — pp. 672–689.
26. Mickunas, M.D. Automatic error recovery for LR parsing /
M.D. Mickunas, J.A. Modry // Communications of ACM. — 1978. —
Vol. 21, № 6. — pp. 459–465.
27. Sheil, B. Observations on context-free parsing / B. Sheil // Statistical
methods in linguistics. — 1976. — pp. 71–109.
28. Stirling, C.P. Follow set error recovery / C.P. Stirling // Software —
practice and experience. — 1985. — Vol. 15, № 3. — pp. 239-257.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
120
Список литературы
Список литературы
1. Ахо, А. Компиляторы: принципы, технологии и инструменты /
A. Ахо, Р. Сети, Дж. М. Ульман. — М.: ≪Вильямс≫, 2003. — 768 c.
2. Ахо, А. Построение и анализ вычислительных алгоритмов / A. Ахо,
Дж. Хопкрофт, Дж. М. Ульман. — М.: ≪Мир≫, 1978. — 536 c.
3. Ахо, А. Теория синтаксического анализа, перевода и компиляции.
Том 1. Синтаксический анализ / А. Ахо, Дж. М. Ульман. — М.:
≪Мир≫, 1978. — 613 с.
4. Ахо, А. Теория синтаксического анализа, перевода и компиляции.
Том 2. Компиляция / А. Ахо, Дж. М. Ульман. — М.: ≪Мир≫,
1978. — 487 с.
5. Хопкрофт, Дж. Введение в теорию автоматов, языков и вычислений / Дж. Хопкрофт, Р. Мотвани, Дж. М. Ульман. — 2-е изд. —
М.: ≪Вильямс≫, 2002. — 528 c.
6. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин / Д. Грис. — М.: ≪Мир≫, 1975. — 544 c.
7. Гинзбург, С. Математическая теория контекстно-свободных языков
/ С. Гинзбург. — М.: Мир, 1970. – 326 с.
8. Кнут, Д. Искусство программирования. Том 2. Получисленные
алгоритмы / Д. Кнут. — М.:≪Вильямс≫, 2007. — 832 с.
9. Пентус, А.Е. Теория формальных языков: учебное пособие /
А.Е. Пентус, М.Р. Пентус. — М.: Изд. ЦПИ при мехмате МГУ,
2004. — 80 c.
10. Серебряков, В.А. Лекции по конструированию компиляторов /
В.А. Серебряков. — М.: ВЦ РАН, 1994. — 175 с.
11. Соколов, В.А. Формальные языки и грамматики. Задачи и упражнения / В.А. Соколов, О.Б. Кушнаренко, Н.М. Бадин. — Ярославль:
ЯрГУ, 1993. — 55 с.
12. Фостер, Дж. Автоматический синтаксический анализ / Дж. Фостер. — М.: Мир, 1975. — 72 c.
13. Хантер, Р. Проектирование и конструирование компиляторов /
Р. Хантер. — М. : Финансы и статистика, 1984. — 232 с.
ПРЕДИСЛОВИЕ
В наиболее общей форме компилятор представляет собой программу, которая считывает текст, написанный на одном языке, и на основе
его производит текст, выраженный на другом языке, сохраняя смысл
исходного текста. Сам процесс называется трансляцией и представляет собой процесс перевода с исходного языка на целевой. Следует
ожидать, что эти языки обычно значительно различаются. Зачастую
исходный язык является языком программирования высокого уровня,
таким как Паскаль, либо C, а целевой представляет некоторый машинный язык, например, набор инструкций процессора, либо байт-код Java.
При этом сам компилятор может быть реализован на каком-нибудь
другом языке программирования и оттранслирован в исполняемый код
при помощи третьего компилятора.
К настоящему времени создание компиляторов является достаточно
хорошо изученным разделом информатики и обладает особенностями,
которые мы рассмотрим далее.
Структурирование задачи компиляции. В процессе своей работы
компилятор осуществляет анализ входных данных, создает их внутреннее представление, а потом на основе этого представления производит синтез выходных данных. Стадия анализа включает несколько
этапов работы. Задачей лексического анализатора является проведение
начальной обработки входных данных и выделение отдельных смысловых единиц. Синтаксический анализатор производит группировку
этих смысловых единиц в отдельные фразы, строя их иерархическое
представление, и проверяет соответствие входных данных синтаксису
исходного языка. Стадия семантического анализа позволяет проверить
наличие смысловых, семантических ошибок в исходных данных. На
этапе синтеза вся накопленная информация о структуре исходных
данных преобразуется в код на целевом языке программирования и
может включать такие стадии, как генерацию промежуточного кода,
его оптимизацию и генерацию целевого кода. Такое разделение проблемы построения компилятора на несколько относительно небольших
задач позволяет подходить к решению поэтапно, что значительно увеличивает скорость и качество разработки. Взаимосвязь между этапами
показана на рисунке. На этом рисунке также выделены два важных
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6
Оглавление
Исходная программа
Лексический
анализ
Таблица
имен
Синтаксический
анализ
Семантический
анализ
119
4.3. Атрибутные грамматики
Обработка
ошибок
Генерация и
оптимизация кода
Целевая программа
компонента компилятора — таблица имен, где содержится вспомогательная информация об идентификаторах, и обработчик ошибок, который осуществляет обнаружение и вывод сообщений об ошибках в
исходной программе.
Применение формальных методов. На некоторых стадиях работы
компилятора используются хорошо известные формализмы. Например,
на стадии лексического анализа используются регулярные выражения и
конечные автоматы, а для стадии синтаксического анализа подходящим
средством являются контекстно-свободные грамматики. Это позволяет
применять разработанную теоретическую базу для выполнения задач,
решающихся на соответствующих стадиях.
Использование автоматических средств. Использование математического аппарата позволяет создавать алгоритмы, которые потом
могут быть успешно запрограммированы, а следовательно, позволять
автоматизировать некоторые стадии построения компиляторов. Более
того, оказалась возможной генерация компилятора из его формальных
описаний при помощи программных средств.
Средства, которые используются при создании компиляторов могут
быть с успехом применены также в других областях. Рассматриваемые
методы оказываются полезными при создании программ для преобразования файлов из одного формата в другой, программ для чтения
структурированной информации, например, записанной при помощи
языков разметки HTML и XML.
LOAD $d;
STORE $E[2];
LOAD $c;
ADD $E[2];
STORE $E[1];
LOAD $b;
ADD $E[1];
STORE $a;
STORE $a
T
a
LOAD $b
S
=
T
b
LOAD $c
E
LOAD $d;
STORE $E[2];
LOAD $c;
ADD $E[2];
STORE $E[1];
LOAD $b;
ADD $E[1]
+
E
LOAD $d;
STORE $E[2];
LOAD $c;
ADD $E[2]
T
+
E
LOAD $d
T
LOAD $d
c
d
Рис. 4.5. Генерация кода
переменной. В том случае, если для нетерминала E использовалась
продукция E → T , код из нетерминала T переносится в значение атрибута code. При использовании продукций для нетерминала E также
вычисляется атрибут side для нетерминала T , который указывает, в
какой части выражения находится этот символ — левой или правой.
В зависимости от атрибута side вычисляется значение атрибута code
для нетерминала T . Если нетерминал находится в левой части исходного выражения, происходит вызов команды STORE, которая сохраняет
в переменной значение из регистра сумматора. В противном случае
значение переменной, соответствующей T , считывается в регистр сумматора с использование команды LOAD.
Пример перевода для строки a = b + c + d проиллюстрирован на
рис. 4.5. Значение атрибута code для каждого нетерминала изображено
рядом с соответствующей вершиной.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
118
Гл. 4. Основы теории перевода
совершать следующие команды (указание переменной для каждой команды начинается со знака $):
Команда
LOAD $a;
STORE $a;
ADD $a;
Семантика
r:=a
a:=r
r:=r+a
Тогда следующая атрибутная грамматика производит перевод арифметических выражений с операцией сложения в корректную последовательность команд для этого вычислителя (нетерминал E ′ здесь введен
для того, чтобы можно было различать атрибут нетерминала E в левой
и правой частях продукции):
S
→
T =E
E
→
T + E′
E
→
T
T
→
<id>
E.level:=1
T.side:=left
S.code:=E.code "; " T.code ";"
E’.level:=E.level+1
T.side:=right
E.code:=E’.code "; "
"STORE $E[" E.level "]; "
T.code "; ADD $E[" E.level "]"
T.side:=right
E.code:=T.code
if (T.side==right) then
T.code:="LOAD $" id.name
else
T.code:="STORE $" id.name
В этой грамматике нетерминал S имеет единственный атрибут code,
где по окончании анотирования дерева разбора будет содержаться код
для рассматриваемого вычислителя, который считает сумму слагаемых
в правой части исходного выражения и помещает ее в переменную,
указанную в левой части.
Нетерминал E имеет два атрибута. Первый атрибут нетерминала
E, code, используется для хранения кода, соответствующего подвыражению, которое разворачивается из этого нетерминала. Код формируется следующим образом. Сначала записывается последовательность
команд, соответствующая нетерминалу E ′ , которая вычисляет значение подвыражения, разворачивающегося из E ′ . Далее мы сохраняем
это значение во временной переменной $E[i], записываем в регистр
сумматора значение из переменной T и прибавляем к нему сохраненное значение $E[i]. В результате в регистре сохраняется значение
подвыражения, сопоставленного нетерминалу E. Второй атрибут, level,
содержит информацию об уровне нетерминала E в дереве разбора. Это
значение необходимо нам для указания корректного имени временной
Глава 1
ЭЛЕМЕНТЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ
В настоящее время формальный подход, основанный на использовании грамматик, широко применяется для описания языков программирования и форматов данных. Математически точное описание конструкций языка программирования является основой для разработки
компиляторов, помогает однозначно поставить задачу трансляции, а
также предлагать и исследовать алгоритмы для решения этой задачи.
В данной главе вводятся основные определения и поясняются термины,
которые мы будем использовать далее.
1.1. Формальные языки и грамматики
Для человечества язык является важнейшим средством коммуникации, с помощью которого, в частности, производят описания различных
объектов и явлений. Коммуникация осуществляется при помощи составления и передачи сообщений. Каждый язык, например, английский
или русский, имеет алфавит, слова и правила, используя которые
составляются корректные предложения. Информатика предлагает более
абстрактный взгляд на язык. Язык представляется в виде множества
предложений, сконструированных по некоторым правилам, где каждое
предложение — это последовательность символов, составляющих в совокупности конечный алфавит языка.
Таким образом, с точки зрения информатики, важным элементом
языка является алфавит, представляющий конечный набор символов.
Из символов алфавита составляются последовательности, где символы
перечислены в однозначно заданном порядке, который нельзя нарушать. Эти последовательности называются словами, или цепочками.
Допустимое множество цепочек формирует язык. Это множество может
быть бесконечным, однако имеет структуру, которая определяется с
помощью правил формирования.
С практической точки зрения язык (даже бесконечный) должен
определяться с помощью конечных элементов, которые бы задавали
алфавит и правила составления корректных слов. Таким средством
являются формальные грамматики.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8
Гл. 1. Элементы теории формальных языков
1.1.1. Определение грамматики
Описание языка c помощью грамматик заключается в определении
ряда компонентов. Во-первых, необходимо задать конечное множество
символов, из которых будут состоять цепочки определяемого языка,
т.е. алфавит. Примерами алфавита может служить множество {Иван,
Петр, Семен}. Во-вторых, определяется конечное множество промежуточных символов, которые называются синтаксическими категорями.
Каждая синтаксическая категория представляет некоторое множество
цепочек, являющееся ≪кирпичиком≫, из которого строится язык. Например, можно определить синтаксическую категорию Работники, куда будут входить элементы алфавита {Иван, Петр} и синтаксическую
категорию Начальник, в которую войдет элемент алфавита {Семен}.
При определении одних синтаксических категорий могут использоваться другие. Например, можно определить категории Список как
≪элемент из категории Работники, за которым следует Список≫ и
Бригада, задаваемую в виде правила ≪первым идет один элемент из
категории Начальник, а затем идет категория Список≫. В-третьих,
может задаваться конечное число правил преобразования, например
≪категория Список, за которой следует категория Работник, может
заменяться категорией Работник≫. В-четвертых, задается начальная
синтаксическая категория, из которой начинается процесс вывода всех
цепочек, принадлежащих языку. Зададим в качестве начальной категорию Бригада, а остальные категории будут взимосвзаны так:
Начальник
Работник
Работник
Список
Список Работник
Бригада
→
→
→
→
→
→
Семен
Иван
Петр
Работник Список
Работник
Начальник Список Работник
Каждое правило из этого списка состоит из левой и правой частей,
расположенных соответственно до и после знака ≪→≫. Правая часть
задает варианты, на которые может быть заменена левая часть.
Для того чтобы получить цепочки, принадлежащие языку, необходимо проделать следующую процедуру. Начиная с начальной, необходимо последовательно заменять каждую синтаксическую категорию
на одно из ее определений до тех пор, пока не получится цепочка,
состоящая из одних символов алфавита. Например:
Бригада→Начальник Список Работник→
→Семен Список Работник→Семен Работник Список Работник→
→Семен Работник Работник→Семен Петр Иван
4.3. Атрибутные грамматики
117
1. Атрибутов символов X1 X2 . . . Xj−1 , расположенных слева от Xj .
2. Наследуемых атрибутов A.
На синтезируемые атрибуты никаких ограничений не накладывается,
поэтому справедливо, что S-атрибутное определение является также и
L-атрибутным. Обратное также верно, но доказывается нетривиально
и ведет к значительному увеличению размера атрибутной грамматики,
поэтому рассматриваться здесь не будет.
На псевдоязыке процесс вычисления атрибутов для L-атрибутных
грамматик может быть описан в виде следующего алгоритма:
procedure d f v i s i t ( n : node ) ;
begin
f o r m , где m потомок узла n do
begin
вычислить наследуемые атрибуты m ;
d f v i s i t (m ) ;
end ;
вычислить синтезируемые атрибуты n ;
end .
Этот алгоритм работает рекурсивно и начинает работу с корневой
вершины дерева разбора.
4.3.4. Применение атрибутных грамматик
Атрибутные грамматики могут применяться как на стадии семантического анализа, так и на стадии генерации кода. Например, вычисление атрибутов для грамматики с рис. 4.2 в процессе аннотирования
дерева разбора происходило вычисление типов переменных, что может
рассматриваться как семантическое действие. Очень часто необходимо
вычислять области видимости переменных, что также можно сделать
при помощи введения дополнительного атрибута, который указывал бы,
на каком уровне определена та или иная переменная — на глобальном,
т.е. доступна из любой части программы, локальном, т.е. на уровне
отдельной процедуры или функции, либо на уровне некоторого блока
операторов.
Во время трансляции в промежуточный код с каждой вершиной
графа зависимости можно сопоставить фрагмент этого кода при помощи введения соответствующего атрибута. Код для вершины n строится
на основе фрагментов, находящихся в потомках этой вершины и,
возможно, некоторых других вершинах. Рассмотрим пример генерации
кода. Допустим, у нас есть вычислитель, который имеет один рабочий
регистр r, используемый как сумматор. Пусть этот вычислитель может
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
116
Гл. 4. Основы теории перевода
Таким образом, при использовании атрибутных грамматик трансляция проходит через несколько стадий:
1. С помощью алгоритма синтаксического анализа строится дерево
разбора для входной строки.
2. С использованием дерева разбора и определений атрибутной
грамматики происходит построение графа зависимости.
3. В том случае, если граф зависимости не имеет контуров, осуществляется его топологическая сортировка, которая дает порядок вычисления атрибутов.
4.3.2. S-атрибутные грамматики
Польза атрибутов состоит в том, что с их помощью можно переносить информацию между вершинами дерева разбора. Однако изза их универсальности возможно возникновение контуров в графе
зависимости и, как следствие, невозможность вычисления значений
атрибутов. Если атрибутная грамматика содержит определения только
синтезируемых атрибутов, то она называется S-атрибутной грамматикой. Однако такое ограничение оставляет грамматику довольно
выразительной.
Так как теперь все атрибуты могут быть вычислены, если двигаться
от листьев дерева разбора к его корню, то становится возможным
легко реализовывать восходящие парсеры. Если для некоторой вершины A дерева разбора вычислены все атрибуты дочерних вершин
B1 , B2 , . . . , Bk , то становится возможным расcчитать все атрибуты
для A и запомнить их. Эти атрибуты потребуются для вычисления
атрибутов предка вершины A.
4.3.3. L-атрибутные грамматики
В процессе синтаксического анализа дерево разбора строится слева
направо. Для нисходящих парсеров происходит построение корневой
вершины, потом ее потомков слева направо. Для восходящих парсеров
наоборот — сначала потомков слева направо, а потом строится сама
корневая вершина. Поэтому логичным представляется рассмотрение
атрибутных грамматик, для которых вычисление атрибутов может быть
осуществлено за один проход дерева разбора в глубину слева направо.
Такие грамматики накладывают условия на зависимости между наследуемыми атрибутами и называются L-атрибутными грамматиками.
Каждый наследуемый атрибут символа Xj , 1 6 j 6 n из правой части
продукции A → X1 X2 . . . Xn зависит только от:
1.1. Формальные языки и грамматики
9
Дадим теперь формальное определение грамматики:
Определение 1. Порождающей грамматикой (или просто грамматикой) называется четверка (N , T , P , S) такая, что
• N и T являются конечными множествами символов;
• N ∩ T = ∅;
• P — это множество продукций R → Q таких, что
R ∈ (N ∪ T )+ и Q ∈ (N ∪ T )∗ ;
• S ∈ N — это начальный символ грамматики.
В этом определении множество T задает алфавит, из которого
состоят цепочки, принадлежащие языку, определяемому грамматикой.
Символы из этого множества также называют терминальными. Иногда
в множество терминальных символов включают пустую строку, которая
обозначается как ε. Синтаксические категории задаются с помощью
символов из множества N , которые называются нетерминальными.
Множества T и N не пересекаются. Конечное множество правил
вывода, или продукций, описывается с помощью множества P , где
каждая продукция имеет вид R → Q. R является непустой строкой
из нетерминальных и терминальных символов и называется головой
продукции. Q называется телом продукции и также состоит из нетерминальных и терминальных символов, однако в отличие от R может
быть пустой строкой. Среди нетерминальных символов выделяют стартовый символ — S.
Примером может служить следующая грамматика, которая задает
определение переменных a, b или c типа int в языке C:
N = {V ar, DefS , List, End}, T = {a, b, c, int,≪,≫,≪;≫}, S = DefS ,
множество продукций P :
(0)
(1)
(2)
(3)
V ar
DefS
List
, V ar End
→
→
→
→
a|b|c
int V ar | int List End
V ar | V ar , List
, V ar;
В этом примере мы использовали более компактную форму записи
множества продукций, где несколько правых частей для одной и той же
левой части разделяются с помощью вертикальной черты ≪|≫, которая
по смыслу похожа на связку ≪или≫. В том случае, если в левой части
продукции находится один нетерминал, то ее удобно рассматривать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
10
Гл. 1. Элементы теории формальных языков
как принадлежащую этому нетерминалу. Далее мы будем пользоваться терминами продукции для A, или A-продукции, для обозначения
продукций, головой которых является переменная A.
Попробуем вывести в данной грамматике строку ≪int a, b, c;≫:
Промежуточная форма
DefS
int List End
int V ar, List End
int V ar, V ar, List End
int V ar, V ar, V ar End
int V ar, V ar, V ar;
int a, b, c;
Правило вывода
DefS → int List End
List → V ar List
List → V ar List
List → V ar
, V ar End →, V ar;
Номер правила
Нач. символ
(1)
(2)
(2)
(2)
(3)
Три раза (0)
Промежуточные формы, состоящие из нетерминальных и, возможно, терминальных символов, называются сентенциальными формами.
Если сентенциальная форма состоит только из терминальных символов, то она называется сентенцией и принадлежит языку, задаваемому
грамматикой. Для грамматики G как L(G) будем обозначать язык, задаваемый этой грамматикой. Переход от одной строки вывода к другой
называется шагом вывода, а сам процесс выводом, или порождением.
1.1.2. Классификация Хомского для формальных грамматик
Определение некоторого языка посредством грамматик является
нетривиальной задачей. С точки зрения теории если язык может быть
в принципе задан с помощью конечных описаний, то его можно задать
с помощью генерирующей грамматики. Однако нет никакой гарантии,
что эту грамматику будет легко записать и понять. Кроме этого существуют фундаментальные и практические проблемы, связаные с тем,
что не существует общего алгоритма, который бы автоматически сформировал вывод некоторой строки из произвольно заданной грамматики.
Это привело к созданию классификации грамматик, которая была
выполнена Н. Хомским. Он выделяет 4 класса грамматик, пронумерованные от 0 до 3. На грамматики класса 0 не накладывается никаких
ограничений, однако на конструкцию правил вывода для следующих
классов устанавливаются дополнительные условия, что влечет за собой
понижение их выразительной способности. Тем не менее эти ограниченные грамматики остаются достаточно выразительными для задания
языков программирования.
Грамматики типа 0. Характеристикой грамматик этого типа является правило, которое гласит, что каждая продукция может переводить
произвольное (но ненулевое) количество символов в произвольное (возможно нулевое) количество символов.
115
4.3. Атрибутные грамматики
type=int
value=3
S
type=int
type=int
T
value=3
E
type=int
int
value=2
F
value=1
+
type=int
E
value=2
<const>
type=int
F
entry
<const>
entry
Рис. 4.4. Дерево разбора и граф зависимости для грамматики с рис. 4.2 и
входной строки int 1 + 2.
топологическая сортировка отличается от обычной сортировки тем, что
вершины графа могут не образовывать всюду упорядоченное множество, например, если граф состоит из нескольких несвязных компонент.
Алгоритм топологической сортировки достаточно прост и может быть
выполнен за время, пропорциональное O(n + d), где n — количество
вершин в графе, а d — количество дуг.
Алгоритм 28. Топологическая сортировка бесконтурного ориентированного графа
Вход: Граф G = (V , E), где V — множество вершин, а E — множество ребер
Выход: Упорядоченная последовательность вершин P
Пусть A(v) — это множество вершин, предшествующих вершине v,
т.е. u ∈ A(v) ⇔ (u, v) ∈ E. Тогда до тех пор пока число элементов
последовательности P меньше количества вершин V , выполнять следующие шаги:
1. Выбрать любую вершину v, для которой A(v) = ∅.
2. Добавить v в конец последовательности P .
3. Удалить v из всех A(u), u 6= v.
Этот алгоритм работает только для бесконтурных графов. Наличие
хотя бы одного контура приведет к тому, что на определенной итерации
будет невозможно выбрать вершину v.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
114
Гл. 4. Основы теории перевода
вершины A и наследуемые атрибуты вершин B, C и D. Аналогичные
правила могут применяться при установке атрибутов для вершин B,
C и D. Так, процедура, соответствующая продукции для B, может
в качестве аргумента использовать наследуемые атрибуты вершины
B для установки синтезируемых атрибутов этой же вершины. Такие
неявные зависимости отражены на рис. 4.3 с помощью пунктирных
стрелок.
Нашей целью будет являться вычисление всех атрибутов для каждой вершины дерева разбора. Этот процесс называется аннотированием, а получившееся в результате дерево — аннотированным деревом.
4.3.1. Графы зависимости
При проведении аннотирования дерева разбора мы должны быть
уверены, что этот процесс завершится за конечное число шагов. В
определении этого факта помогает конструирование и анализ свойств
графа зависимости, который строится по следующему алгоритму.
Алгоритм 27. Построение графа зависимости
Вход: Дерево разбора T и атрибутная грамматика G
Выход: Граф зависимости D
1. Вершинами графа зависимости являются все возможные пары
(x, a), где x — вершина дерева разбора T , a — атрибут грамматического символа в этой вершине.
2. Для каждой вершины x дерева разбора T производим следующие
операции. Для каждого семантического правила, сопоставленного
продукции, использованной в x, и представленному в виде формулы b := f (c1 , c2 , . . . , ck ) проводим k дуг в графе зависимости,
направленных от вершин, соответствующих атрибутам ci , к вершине (x, b), где 1 6 i 6 k.
Вернемся к рассмотрению грамматики с рис. 4.2. Пусть дана строка
int 1 + 2. Тогда дерево разбора вместе с графом зависимости показано
на рис. 4.4. Можно видеть, что полученный граф является бесконтурным, следовательно, существует такой порядок обхода вершин, при котором перед вычислением каждого атрибута будут вычислены те атрибуты, от которых он зависит. Для того чтобы найти такой обход, можно
воспользоваться топологической сортировкой, которая упорядочивает
вершины m1 , m2 , . . . , mk бесконтурного ориентированного графа таким
образом, что если mi → mj — дуга в графе, то mi встречается раньше
mj в упорядоченной последовательности. Необходимо заметить, что
1.1. Формальные языки и грамматики
11
Грамматики типа 1. Грамматики этого типа получаются из грамматик типа 0 путем наложения ограничений на структуру продукций.
Существуют два эквивалентных определения грамматик типа 1:
• Грамматика типа 1 называется монотонной, если она не содержит продукций, в которых левая часть содержит больше символов, чем правая часть.
• Грамматика типа 1 называется контекстно-зависимой, если она
содержит контекстно-зависимые продукции. Продукция называется контекстно-зависимой, если в действительности только один
символ из левой части заменяется другим символом в правой
части продукции, а остальные символы из левой части остаются
неизменными и в том же порядке. Сентенциальные формы, расположенные слева и справа от изменяемого символа, называются
левым и правым контекстом соответственно.
Монотонные и контекстно-зависимые грамматики являются одинаково выразительными: для любой монотонной грамматики существует
эквивалентная контекстно-зависимая грамматика, генерирующая тот
же самый язык.
Грамматики типа 2. Контекстно-свободные грамматики (далее
мы их будем также обозначать как КС-грамматики) являются грамматиками типа 2. Если для контекстно-зависимой грамматики поставить
условие, чтобы левый и правый контексты отсутствовали (были пустыми), то получается как раз класс контекстно-свободных грамматик.
Таким образом, контекстно-свободная грамматика может содержать
продукции, которые имеют единственный нетерминал в левой части.
Основным свойством грамматик этого типа является возможность описания вложенных конструкций. Например, можно задать контекстносвободную грамматику, которая порождает строки, где правильно расставлены скобки.
Грамматики типа 3. Грамматики типа 3 получаются из грамматик
типа 2 с помощью введения новых ограничений на формат продукций.
Правая часть продукций для грамматик этого типа может содержать
ноль и более терминалов либо ноль или более терминалов, заканчивающихся одним нетерминалом. Грамматики этого типа также называют
регулярными.
Для нужд описания реальных языков программирования используются грамматики 2 и 3 типов — их выразительной силы достаточно
для того, чтобы описать необходимые синтаксические конструкции.
Соответственно далее мы будем рассматривать только контекстносвободные и регулярные грамматики.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
12
Гл. 1. Элементы теории формальных языков
1.1.3. Описание грамматик на практике
Существует несколько различных стилей нотации (и их вариаций)
для КС-грамматик, которые используются для определения синтаксиса
языков программирования. Классической нотацией является форма
Бэкуса-Наура (Backus-Naur form, BNF), которая впервые была использована для определения языка Алгол-60. Вот пример:
<Var>
<Def_S>
<List>
::=
::=
::=
<SomeSeq>
::=
<Seq> | <Seq><SomeSeq>
Такие конструкции задают циклическое включение символа грамматики <Seq> в нетерминал <SomeSeq>. При расширенной записи
мы можем написать <Seq>+ , что будет означать одно или более
последовательных включений <Seq>. Другими примерами операций
для расширенной записи являются операторы ≪∗ ≫, ≪? ≫, ≪+n ≫ (см.
рис. 1.1). Нотация, в которой используются эти операторы, называет<Something>∗
<Something>?
<Something>+
<Something>+n
Наследуемые
атрибуты A
0 или более включений <Something>
0 или одно включение <Something>
1 или более включений <Something>
от 1 до n включений <Something>
Рис. 1.1. Дополнительные операторы для записи грамматик
ся расширенной формой Бэкуса-Наура (Extended Backus-Naur form,
EBNF). Расширенная форма Бэкуса-Наура имеет ту же самую выразительную силу, что и обычная, но добавляет читабельности.
1.2. Порождение строк с помощью грамматик
До настоящего момента мы рассматривали грамматики как способ
описания некоторого языка, т.е. множества цепочек символов конечной
длины. Рассмотрим теперь подробнее процесс порождения строк в
рамках контекстно-свободных грамматик.
Для того чтобы убедиться, что данная цепочка принадлежит языку,
задаваемому грамматикой, можно попытаться вывести эту цепочку из
A
Синтезированные
атрибуты A
Процедуры
A → BCD
a|b|c
int <Var>; | int <List>;
<Var> | <Var>, <List>
При такой форме записи нетерминалы заключаются в угловые скобки, а знак ::= обозначает выводимость.
Запись КС-грамматик часто делают более компактной за счет введения сокращений для задания наиболее часто встречающихся конструкций. Так, при определении грамматик встречаются конструкции вроде:
113
4.3. Атрибутные грамматики
Насл.
атр. B
B
Синт.
атр. B
Насл.
атр. D
Насл.
атр. C
C
D
Синт.
атр. D
Синт.
атр. C
Рис. 4.3. Процесс вычисления атрибутов
нетерминалов S и E (нетерминал E ′ эквивалентен E и предназначен
для того, чтобы можно было различать эти нетерминалы в левой и
правой частях продукции) существуют атрибуты type и value, которые
задают тип выражения и его значение. Нетерминал T имеет только
лишь атрибут type, задающий тип. Каждой продукции соответствует
процедура, причем она может быть довольно сложной и написанной
на удобном для программиста языке. Необходимо особо отметить выражение settype(<const>.entry, F.type), которое не возвращает
значения, хотя до сих пор мы утверждали, что в процедуре обязательно происходит вычисление некоторого атрибута. В таких случаях
можно считать, что вычисляется некоторый фиктивный атрибут. В
рассматриваемом примере функции settype и getvalue используются
для задания типа константы в таблице имен и получения оттуда ее
значения соответственно.
Если в дереве вывода есть фрагмент, соответствующий применению продукции A → P1 P2 . . . Pn , то процедуры для этого фрагмента могут полагаться на значения синтезированных атрибутов в
вершинах P1 , P2 , . . . , Pn и обязаны установить значения наследуемых
атрибутов этих вершин. Если рассмотреть продукцию A → BCD, то
проиллюстрировать зависимость между различными классами атрибутов можно с помощью рис. 4.3. Каждая процедура, сопоставленная
этой продукции, в качестве аргументов использует синтезированные
атрибуты вершин B, C и D, а также наследуемый атрибут вершины
A. Результатом вычислений могут служить синтезированный атрибут
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
112
Гл. 4. Основы теории перевода
4.3. Атрибутные грамматики
Атрибутные грамматики получаются при помощи обобщения
формализма КС-грамматик путем введения следующих конструкций.
Пусть каждый грамматический символ имеет связанное с ним множество атрибутов. Каждый атрибут имеет свое имя и тип, который
задает множество допустимых значений атрибута. После построения
дерева разбора каждая вершина этого дерева будет иметь свой экземпляр атрибута, который хранит семантическую информацию об
этой вершине дерева. Таким образом, если дерево разбора содержит
несколько вершин, помеченных символом A, то каждая из этих вершин
будет иметь атрибуты с одними и теми же названиями, но значения
соответствующих атрибутов могут быть различными.
Каждой продукции A → P1 P2 . . . Pn поставим в соответствие процедуры, каждая из которых имеет вид b := f (c1 , c2 , . . . , ck ), где b — вычисляемый атрибут, f — функция, которая его вычисляет, а c1 , c2 , . . . , ck —
атрибуты, на основе которых производится вычисление b. При этом b
может принадлежать любому из символов A, P1 , P2 , . . . , Pn .
Разделим связанные с символом P атрибуты на два подмножества —
синтезированные и наследуемые атрибуты. Значения синтезированных атрибутов некоторой вершины дерева разбора вычисляются на
основе атрибутов дочерних вершин. Наследуемые атрибуты вычисляются на основе значений атрибутов родительской и/или дочерних по
отношению к родительской вершин.
S.type:=T.type
S.value:=E.value
E.type:=T.type
T → int
T.type:=int
T → f loat
T.type:=float
E.value:=F.value+E’.value
E → F + E′
F.type:=E.type
E’.type:=E.type
E.value=F.value
E → F
F.type=E.type
settype(<const>.entry, F.type)
F → <const>
F.value:=getvalue(<const>.entry)
Рис. 4.2. Атрибутная грамматика для сложения констант с учетом типа выражения
S
→
TE
На рис. 4.2 изображена простая атрибутная грамматика, которая задает сложение нескольких констант, причем выражение имеет
тип — целый (int) либо вещественный (f loat). В этой грамматике у
13
1.2. Порождение строк с помощью грамматик
начального символа грамматики. В этом случае мы применяем одну
из продукций для стартового символа, затем разворачиваем получившуюся сентенциальную форму, заменяя один из нетерминалов телом
некоторой продукции для него, и повторяем процесс до тех пор, пока
не получим нужную нам сентенцию.
Введем новый символ отношения ≪⇒≫. Пусть G = (N , T , P , S) —
КС-грамматика, αAβ — некоторая сентенциальная форма, порожденная
из начального символа этой грамматики, где A это нетерминал, а α и
β — цепочки из (N ∪ T )∗ . Пусть A → γ — это продукция из G. Тогда
будем говорить, что αAβ ⇒ αγβ. Один шаг вывода заменяет любую
переменную в сентенциальной форме телом одной из ее продукций.
Для представления нескольких последовательных шагов порождения
∗
используется отношение ⇒, которое задается по индукции:
∗
1. Любая сентенциальная форма порождает саму себя, т.е. α ⇒ α.
∗
∗
2. Если α ⇒ β и β ⇒ γ, то справедливо, что α ⇒ γ.
Таким образом, язык, порождаемый грамматикой G, может быть
∗
задан как множество таких сентенций α, для которых S ⇒ α.
1.2.1. Левосторонние и правосторонние выводы
На каждом шаге вывода мы можем выбрать и заменить любой
из нетерминалов, входящих в текущую сентенциальную форму. Для
ограничения выбора можно потребовать, чтобы мы заменяли только
крайний слева нетерминал. Такой вывод называется левосторонним.
Аналогично можно потребовать, чтобы на каждом шаге заменялся
крайний справа нетерминал. В таком случае вывод называется правосторонним.
(0)
(1)
(2)
E
T
P
→
→
→
E+T |T
T ×P |P
0P | 1P | 0 | 1 | (E)
Рис. 1.2. Контекстно-свободная грамматика для простых выражений
Рассмотрим грамматику, изображенную на рис. 1.2 и терминальную
цепочку 0 + 1 × 1. Тогда левосторонний вывод из начального символа
данной грамматики для этой цепочки будет следующим:
E ⇒ E +T ⇒ T +T ⇒ P +T ⇒ 0+T ⇒
⇒ 0+T ×P ⇒ 0+P ×P ⇒ 0+1×P ⇒ 0+1×1
В свою очередь правосторонний вывод для этой же самой строки будет
представлять собой следующую последовательность шагов:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
14
Гл. 1. Элементы теории формальных языков
E ⇒ E +T ⇒ E +T ×P ⇒ E+T ×1 ⇒ E +P ×1⇒
⇒ E +1×1⇒ T +1×1⇒ P +1×1 ⇒ 0+1×1
Далее мы будем обозначать с помощью символов ≪⇒l ≫ и ≪⇒r ≫ очередной шаг левостороннего и правостороннего выводов соответственно
там, где это не ясно из контекста.
В [5] доказывается, что наличие вывода, когда нетерминалы заменяются в любом порядке, эквивалентно наличию левостороннего и
правостороннего вывода. То есть если w — это терминальная цепочка,
а G = (N , T , P , S) является контекстно-свободной грамматикой, то
∗
S ⇒ w тогда и только тогда, когда существует левосторонний вывод
этой цепочки, что эквивалентно наличию правостороннего вывода этой
цепочки в грамматике G.
1.2.2. Деревья разбора
Существует более наглядный и удобный способ для представления
выводов цепочек в виде дерева. Удобство состоит в том, что при
построении вывода нам не приходится каждый раз переписывать неизменяющуюся часть сентенциальной формы. Наглядность выражается в
представлении синтаксической структуры выводимой цепочки в графической форме, где явно показано, из какого нетерминала выводится
каждая часть входной строки. Построение такого дерева облегчает
трансляцию исходной программы в исполняемый код, так как оно ясно
задает синтаксическую структуру программы.
Определение 2. Деревом разбора для грамматики G = (N , T , P , S)
является дерево, обладающее следующими свойствами:
1. Каждый внутренний узел отмечен переменной из множества
нетерминальных символов N .
4.2. Схема синтаксически управляемого перевода
111
Если A → α, β представляет собой некоторое правило СУ-схемы,
то каждому вхождению нетерминала в цепочку α соответствует вхождение этого же нетерминала в цепочку β. Однако если нетерминал
B входит в α несколько раз, то соответствие не будет очевидным.
Например, для правила A → aBbBc, abBcB непонятно, нетерминалы
B переводятся в том же порядке либо меняются местами. Поэтому
можно пользоваться верхними индексами для указания порядка перевода. Например, правило A → aB 1 bB 2 c, abB 2 cB 1 переводит первый
встретившийся нетерминал B в цепочке aBbBc во второй нетерминал
B в цепочке abBcB.
Определим теперь выводимую пару цепочек схемы T .
Определение 11. Выводимая пара цепочек схемы T = (N , Σ, ∆, P , S)
определяется по индукции следующим образом:
1. (S, S) — выводимая пара, в которой символы S соответствуют друг другу.
2. Если (αAβ, α′ Aβ ′ ) является выводимой парой, в которой два
выделенных вхождения нетерминала A соответствуют друг
другу и A → γ, γ ′ — правило из P , то (αγβ, α′ γ ′ β ′ ) — выводимая
пара.
Рассмотрим СУ-схему c рис. 4.1 и цепочку 001, тогда (001, 100)
является выводимой парой этой схемы. Непосредственная связь между
двумя выводимыми парами обозначается символом ≪⇒≫, а при помо∗
щи ≪⇒≫ обозначает выводимость за ноль и более шагов. Тогда для
рассмотренной схемы и цепочки можно записать следующий вывод:
(S, S) ⇒ (0S, S0) ⇒ (00S, S00) ⇒ (001S, S100) ⇒ (001, 100)
2. Каждый лист отмечен элементом множества N ∪ T ∪ {ε}.
Введенные обозначения позволяют нам определить перевод, задаваемый СУ-схемой.
3. Если внутренний узел отмечен нетерминалом A и его сыновья
отмечены слева направо X1 , X2 , . . . , Xk соответственно, то
A → X1 X2 . . . Xk является продукцией из P .
Определение 12. Cхема T = (N , Σ, ∆, P , S) определяет перевод,
∗
задаваемый множеством {(x, y) | (S, S) ⇒ (x, y), x ∈ Σ∗ , y ∈ ∆∗ }.
Если у дерева разбора выписать отметки вершин-листьев, то получится цепочка, которая называется кроной дерева. Эта цепочка всегда
является выводимой из нетерминала, отмечающего корень. Интересны
деревья разбора, у которых крона является терминальной цепочкой, т.е.
все листья отмечены терминалами либо ε, а корень отмечен стартовым
Описание перевода, задаваемого СУ-схемой осуществляется довольно простым образом. Более подробно свойства СУ-схем описаны
в [3], где демонстрируется их тесная связь с формализмом магазинных
преобразователей, которые похожи на магазинные автоматы, однако
могут не только распознавать цепочки, но еще их формировать.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
110
Гл. 4. Основы теории перевода
Транслятором называется устройство, которое реализует некоторый перевод τ . По практическим соображениям транслятор должен по
возможности осуществлять перевод эффективно, в идеале за линейное
от длины входной цепочки время и иметь небольшой объем, чтобы его
было несложно запрограммировать.
В этой главе рассматриваются два подхода к построению трансляторов: с использованием схем синтаксически управляемого перевода и
атрибутных транслирующих грамматик.
15
1.2. Порождение строк с помощью грамматик
1
1
E
E
5
2
E
6
T
3
6
T
8
T
P
T
7
P
7
4
2
E
T
8
P
3
4
T
P
5
P
P
4.2. Схема синтаксически управляемого перевода
Схема синтаксически управляемого перевода (СУ-схема) интуитивно представляет собой грамматику, каждой продукции которой приписывается элемент перевода. В процессе построения вывода цепочки
параллельно строится и ее перевод. Формально СУ-схема определяется
следующим образом.
Определение 10. Схемой синтаксически управляемого перевода называется пятерка T = (N , Σ, ∆, P , S), где:
• N — конечное множество нетерминальных символов;
• Σ — конечный входной алфавит;
• ∆ — конечный выходной алфавит;
• P — конечное множество правил вывода, которые имеют вид
A → α, β, где α ∈ (N ∪ Σ)∗ , β ∈ (N ∪ ∆)∗ , и вхождения
нетерминалов в цепочку β образуют перестановку вхождений
нетерминалов в цепочку α;
• S — начальный символ грамматики.
Примером СУ-схемы может служить схема перевода, представленная на рис. 4.1, которая преобразует цепочку из нолей и единиц
в цепочку, записанную в обратном порядке, что формально можно
записать как отношение {(x, xR ) | x ∈ {0, 1}∗ }.
S
S
S
→
→
→
0S, S0
1S, S1
ε, ε
Рис. 4.1. Пример СУ-схемы.
0
+
1
а)
×
1
0
+
1
×
1
б)Ѕ)
Рис. 1.3. Построение дерева разбора при левостороннем (а) и правостороннем (б) выводах
символом грамматики. Кроны таких деревьев разбора представляют собой цепочки языка рассматриваемой грамматики. На рис. 1.3 показаны
деревья разбора для грамматики с рис. 1.2 и цепочки 0 + 1 × 1. Порядок построения дерева при левостороннем и правостороннем выводе
изображен с помощью чисел, расположенных рядом с вершинами.
В [16] показано, что количество вершин в дереве разбора для
цепочки длины n не может превышать значение C × n, где C —
это константа, значение которой зависит от грамматики при условии,
что грамматика не имеет циклов. Грамматика имеет циклы, если для
некоторого нетерминала A возможно снова вывести его через конечное
число шагов, т.е. A → . . . → A. В этом случае очевидно, что дерево
разбора может быть сколь угодно большим.
Все определенные ранее способы описания выводимости цепочек из
начального символа грамматики являются эквивалентными. В [5] доказывается, что для любой грамматики G = (N , T , P , S) и нетерминала
∗
A ∈ N равносильно наличие некоторого вывода A ⇒ α, левостороннего
вывода α из A, правостороннего вывода α из A и существование дерева
разбора с корнем A и кроной α.
1.2.3. Неоднозначные языки и грамматики
Как мы уже видели, допускается возможность вывода цепочки в
некоторой грамматике несколькими способами. В том случае, если мы
задаемся вопросом о принципиальной выводимости некоторой цепочки,
это не является проблемой. Однако при трансляции из одного языка
в другой необходимо не только ответить на вопрос, правильно ли
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
16
Гл. 1. Элементы теории формальных языков
записана исходная строка, но также корректно отразить ее семантику.
Деревья разбора как раз могут адекватно представлять структуру этой
строки и помогают определить ее смысл.
Рассмотрим следующий пример грамматики:
E
D
→
→
E +E | E ×E |D
0 | 1 | ... | 9
ОСНОВЫ ТЕОРИИ ПЕРЕВОДА
Рассмотрим цепочку 2 + 4 × 6. Для нее можно записать два различных вывода в данной грамматике:
1. E ⇒ E + E ⇒ D + E ⇒ 2 + E ⇒ 2 + E × E ⇒ 2 + D × E ⇒
⇒ 2+4×E ⇒ 2+4×D ⇒ 2+4×6
2. E ⇒ E × E ⇒ E + E × E ⇒ D + E × E ⇒ 2 + E × E ⇒ 2 + D × E ⇒
⇒ 2+4×E ⇒ 2+4×D ⇒ 2+4×6
Оба вывода являются левосторонними, а существенная разница
между ними состоит в выборе первой продукции. Для первого вывода выбирается продукция E → E + E, а для второго используется
продукция E → E × E. Первому выводу соответствует дерево разбора,
изображенное на рис. 1.4а, а второму — на рис. 1.4б. Эти выводы поразному трактуют смысл выражения, заданного цепочкой 2 + 4 × 6. В
первом случае можно сгруппировать аргументы как 2 + (4 × 6) = 26,
тогда как во втором группировка имеет вид (2 + 4) × 6 = 36.
26
36
E
E
2
24
E
6
E
2
6
E
E
D
+
а)
×
2
D
D
D
6
2
2
4
4.1. Формальное определение перевода
Итак, наша задача состоит в исследовании процесса, который
управляет преобразованием одной цепочки языка в другую цепочку,
записанную согласно правилам другого языка. Будем называть вторую
цепочку результатом перевода. Формально перевод определяется следующим образом.
D
Определение 9. Пусть Σ является входным, а ∆ выходным алфавитом. Переводом с языка L1 ⊆ Σ∗ на язык L2 ⊆ ∆∗ называется
отношение τ ⊆ Σ∗ × ∆∗ , для которого L1 — область определения, а
L2 — множество значений.
6
Таким образом, перевод τ задает множество пар (α, β), которое
указывает, что цепочка α должна быть преобразована в цепочку β.
В общем случае одному значению α может соответствовать несколько
различных значений β1 , β2 , . . . , βn . Однако с точки зрения практики
отношение τ должно быть функциональным, т.е. каждому элементу из
области определения должен сопоставляться один элемент из множества значений.
4
+
Основной задачей компиляторов является перевод текста программы, записанного на языке программирования, в объектый код, который по сути является программой, записанной на другом языке
программирования. Можно считать, что каждая стадия компилятора
(лексический, синтаксический анализаторы либо генерация кода) является переводом. Так, на стадии лексического анализа происходит
перевод строки символов, представляющей исходную программу, в
последовательность лексем, на стадии синтаксического анализа эта последовательность переводится в дерево разбора. Основной задачей этой
главы является рассмотрение методов, которые помогают осуществить
преобразование построенного дерева разбора в объектный код.
6
4
E
6
4
E
E
4
2
6
E
4
D
Глава 4
×
б)
Рис. 1.4. Деревья разбора, соответствующие цепочке 2 + 4 × 6
Рассмотренная грамматика может давать цепочкам как арифметическим выражениям правильную группировку, также, как и неправильную. Следовательно, для практических целей она не подходит, и нам
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
108
Гл. 3. Синтаксический анализ
символы входной строки до того, как встретится символ из допускающего множества, пусть это будет символ a ∈ F IRST (Xi ). Далее мы
не рассматриваем символы X1 . . . Xi−1 и переходим к рассмотрению
символа Xi .
Ошибочные продукции. Смысл этого метода состоит в том, чтобы
расширить исходную грамматику таким образом, что возможные ошибки описывались бы с помощью продукций, и, следовательно, принадлежали бы языку, задаваемому грамматикой. Например, если задана
следующая конструкция языка Паскаль:
if
else_part
→
→
IF bool_exp T HEN statement else_part
ELSE statement | ε
то можно считать, что наиболее часто встречающейся ошибкой является вставка символа ≪;≫ перед конструкцией ELSE. Следовательно,
такую ошибку можно описать конструкцией:
else_part
→
1.3. Эквивалентные преобразования грамматик
17
необходимо предложить такое преобразование грамматики, которое бы
обеспечивало только правильную трактовку цепочек как арифметических выражений.
Неоднозначное определение смысла цепочки не является следствием возможности построения нескольких выводов. Например, для цепочки 2 + 4 можно построить следующие два вывода:
1. E ⇒ E + E ⇒ D + E ⇒ 2 + E ⇒ 2 + D ⇒ 2 + 4
2. E ⇒ E + E ⇒ E + D ⇒ D + D ⇒ 2 + D ⇒ 2 + 4
Однако интерпретация цепочки от этого не изменится. Следовательно, неоднозначность происходит не от множественности выводов цепочки, а от существования двух и более деревьев разбора. На основе этого
замечания формулируется определение неоднозначной грамматики.
Определение 3. КС-грамматика G = (N , T , P , S) является неоднозначной, если для некоторой цепочки α ∈ L(G) существует более
одного дерева вывода с корнем, отмеченным S, и кроной α.
ELSE statement | ε |; ELSE statement
• Могут быть распознаны только описанные с помощью продукций
ошибки.
Контекстно-свободные языки также могут быть неоднозначными.
Например, язык L = am bn cn ∪ ap bp cq является неоднозначным, так
как для него не существует однозначной грамматики. Формальное
доказательство этого факта выходит за рамки настоящего пособия.
Итак, неоднозначность грамматики является нежелательным свойством при определении языка программирования. К сожалению, алгоритма исключения неоднозначности не существует. Более того, в [5]
доказывается, что не существует алгоритма, способного различить,
является ли КС-грамматика неоднозначной.
• Выбранный метод синтаксического анализа может быть не применим к расширенной грамматике.
1.3. Эквивалентные преобразования грамматик
Теперь с ошибочными продукциями можно ассоциировать семантические действия, которые выводили бы сообщения об ошибках.
Преимуществом этого метода обработки ошибок является возможность выдавать очень своевременные и адекватные ситуации соообщения об ошибках. Однако имеются следующие недостатки:
Тем не менее метод расширения грамматики ошибочными продукциями
может использоваться в совокупности с другими методами обработки
ошибок. Полезно бывает описать с помощью продукций те ошибки,
которые другие методы обрабатывают плохо.
На практике очень полезно обладать возможностью преобразования
и оптимизации грамматик, описывающих языки программирования.
Это существенно помогает, когда грамматика описана с ошибками.
Например, в грамматике присутствуют недостижимые либо непродуктивные нетерминалы. Некоторые методы синтаксического анализа,
например метод Кока-Янгера-Касами, работают с грамматиками, приведенными к определенному виду. Следовательно, необходимо иметь
возможность приведения произвольной грамматики к нужной форме.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
18
Гл. 1. Элементы теории формальных языков
1.3.1. Оптимизация грамматик
Грамматика, предназначенная для описания языка программирования и используемая для создания транслятора, может содержать
продукции и нетерминалы, которые бесполезны с точки зрения вывода
строк. Так, вывод может закончиться неуспешно, если для достигнутой на некотором шаге сентенциальной формы невозможно привести
последовательность продукций, с помощью которой можно было бы
заменить все нетерминальные символы на терминальные. Рассмотрим
типичные случаи, когда может быть полезным осуществить приведение
грамматики к более оптимальному виду.
Неопределенные нетерминалы. Тело продукции может содержать
нетерминальные символы, для которых не определены правила вывода.
Такие продукции могут быть удалены из грамматики. Вместе с ними
мы можем удалить все правила вывода для нетерминала, являющегося
головой продукции, который, в свою очередь, может стать неопределенным.
Недостижимые нетерминалы. Нетерминал A называется достижимым, если он входит в сентенциальную форму, выводимую
из начального символа грамматики, т.е. возможно построить вывод
∗
S ⇒ αAβ для некоторых α, β ∈ (N ∪ T )∗ . В противном случае
нетерминал называется недостижимым, и продукции для него могут
быть удалены.
Непорождающие продукции и нетерминалы. Предположим, что
для нетерминала X имеется только одна продукция X → aX и сам
нетерминал X достижим из начального символа грамматики. Тем не
менее нетерминал X не может участвовать в выводе никакой цепочки.
Действительно, если сентенциальная форма включает X, то в дальнейшем от него невозможно избавиться. Нетерминальный символ X
∗
называется порождающим, если X ⇒ w, где w — цепочка, состоящая
из терминальных символов. Если это условие не выполняется, нетерминальный символ называется непорождающим. Продукция называется
непорождающей, если после ее применения образуется сентенциальная
форма, из которой невозможно вывести терминальную цепочку.
Циклы. Существует еще один вид продукций, которые может
потребоваться убрать. Эти продукции могут иметь вид A → A. Такие продукции называются циклами. Циклы могут быть косвенными: A → B, B → C, C → A, а также скрытыми: A → P AQ,
∗
∗
P ⇒ ε, Q ⇒ ε, что оставляет возможность циклического вывода
A ⇒ P AQ ⇒ . . . A . . . ⇒ A. Цикл может входить в некоторый вывод
строки из начального символа грамматики. Если это происходит, то
существует вывод этой строки без участия цикла. Циклы не обогащают
3.7. Обнаружение и обработка ошибок
107
Метод паники. Этот метод является достаточно простым и эффективным. Согласно ему допустимое множество определяется автором
парсера и является фиксированным во время синтаксического анализа. Очень часто это множество составляют символы, являющиеся
конечными символами синтаксических конструкций. Например, если
создается парсер для языка программирования C, то такими символами
могут быть ≪;≫ и ≪}≫. Когда обнаруживается ошибка, пропускаются
все символы входной строки до первого символа, принадлежащего
допускающему множеству. После этого парсер должен перейти в состояние, которое делает этот символ корректным следующим символом, ожидаемым с точки зрения алгоритма синтаксического анализа.
Восстановление от ошибок, осуществляемое с помощью метода паники, работает достаточно хорошо, однако большое количество ошибок
может быть не обнаружено, так как значительные фрагменты входной
строки пропускаются.
Попробуем более эффективную модификацию метода паники, которая применима для LL-грамматик. Пусть допускающее множество
описывается для каждого нетерминала отдельно: для каждого нетерминала A допускающим множеством будет F OLLOW (A). Пусть на
некотором шаге синтаксического анализа осуществляется попытка применить продукцию A → X1 X2 . . . Xn и встретилась ошибка после распознавания i-го символа тела этой продукции. Тогда пропускаются все
символы входной строки до первого вхождения символа из множества
F OLLOW (A). После этого необходимо исключить из рассмотрения
все оставшиеся символы продукции. То есть в случае применения
метода рекурсивного спуска не вызывать процедуры, соответствующие
символам Xi+1 . . . Xn . Однако мы не можем быть уверены, что текущий символ входной строки является допустимым в данном контексте
использования нетерминала A. Поэтому лучшей идеей является использование части множества F OLLOW (A), которая соответствуют
конкретному контексту.
Существует несколько вариаций этого метода, одна из которых
состоит в следующем. Пусть парсер встретил ошибку во входном
потоке символов, когда находился в следующем состоянии:
...
...
a...
X1 . . . Xn ♯
Тогда допускающее множество может состоять из объединения множеств F IRST (X1), F IRST (X2 ), . . . , ♯. После этого пропускаются все
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
106
Гл. 3. Синтаксический анализ
также две возможности отредактировать строку ×+, то мы придем
к двум другим синтаксически корректным строкам: i × i, которая
образуется вставкой i в начало и заменой символа + на i, а также
корректной строке, состоящей из одного символа i, что получается
благодаря замене × на i и удалению символа +. Решение о конкретном
наборе редактирующих операций остается на совести программиста.
Метод наименьшей корректировки требует проведения значительного объема вычислений, так как приходится генерировать и рассматривать большее количество разбиений. Однако универсальные парсеры и
так весьма трудоемки, так что это добавление не является критичным
по скорости работы.
Лайон в своей работе [24] предложил использование метода наименьшей корректировки для алгоритма Кока—Янгера—Касами, которая
использует операцию замены символа. Эта версия для каждого нетерминала в таблице распознавания сопоставляет счетчик, указывающий
на количество ошибок, которое встретилось в подстроке, выводящейся
из этого нетерминала. В самой нижней строке таблицы распознавания располагаются нетерминалы, из которых выводятся терминальные
символы. Если символ входной строки совпадает с терминалом, находящимся в теле продукции, то счетчик ошибок равен 0 для нетерминала
из головы этой же продукции. В противном случае счетчик устанавливается равным 1, т.е. необходимо произвести одну операцию замены.
Все последующие строки заполняются по следующему принципу: если
некоторый нетерминал A должен быть записан в некоторую ячейку на
основании наличия продукции для него A → BC, то счетчик ошибок
для него устанавливается равным сумме счетчиков для нетерминалов
B и C, кроме того случая, когда нетерминал A уже записан в эту
ячейку, но с меньшим значением счетчика.
3.7.4. Обработка ошибок в локальном контексте
При использовании методов обработки ошибок в локальном контексте предполагается, что парсер способен локализовать позицию во
входной строке, где встретилась ошибка. После нахождения ошибки,
в зависимости от состояния парсера рассчитывается множество символов, которое мы будем называть допустимым множеством. Далее
пропускаются все символы входной строки до первого символа, принадлежащего допустимому множеству. После этого состояние парсера
адаптируется таким образом, что этот символ является допустимым с
точки зрения синтаксиса. Рассмотрим теперь техники, которые входят
в класс алгоритмов, обрабатывающих ошибки в локальном контексте.
1.3. Эквивалентные преобразования грамматик
19
язык, задаваемый грамматикой, новыми цепочками. Кроме того, если
вывод цепочки содержит цикл, то для данной цепочки существует
бесконечно много деревьев разбора. Различные методы синтаксического анализа по-разному обращаются с возможностью циклических
выводов. Некоторые методы пытаются честно построить бесконечное
множество деревьев разбора, другие останавливаются при построении
первого найденного дерева, остальные указывают, что грамматика
задана некорректно. Мы будем рассматривать случаи наличия циклических выводов в грамматике для каждого метода синтаксического
анализа отдельно.
Цепные продукции. В грамматиках иногда встречаются продукции вида A → B, где A и B являются нетерминальными символами.
Такие продукции называются цепными. Эти продукции могут быть
полезными, например, при исключении неоднозначности из грамматик,
однако они же могут создавать дополнительные шаги в порождениях.
Рассмотрим теперь алгоритмы, которые помогают избавляться от
этих недостатков для класса контекстно-свободных грамматик.
Алгоритм 1. Алгоритм удаления непорождающих продукций и
неопределенных нетерминалов
Вход: КС-грамматика G = (N , T , P , S)
Выход: КС-грамматка G′ = (N ′ , T , P ′ , S), свободная от непорождающих правил и неопределенных нетерминалов, причем L(G) = L(G′ )
1. В начале работы алгоритма все нетерминалы и продукции грамматики G помечаются как непорождающие.
2. Помечаем все продукции вида A → a, где A ∈ N , a ∈ T ,
как порождающие. Так же помечаются нетерминалы, являющиеся
головой таких продукций.
3. Если продукция имеет вид A → α, где A ∈ N , α ∈ (N ∪ T )∗ , то
помечаем ее и нетерминал A как порождающие в том и только
том случае, если все нетерминалы, входящие в α, являются
порождающими.
4. Повторяем шаг 3 до тех пор, пока возможно пометить новые
продукции и нетерминалы.
5. Грамматика G′ будет содержать все нетерминалы и продукции,
которые помечены как порождающие. Необходимо отметить, что
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
20
Гл. 1. Элементы теории формальных языков
неопределенные нетерминалы будут помечены как непорождающие, следовательно, грамматика G′ не будет их содержать. Можно рассматривать неопределенность нетерминала как частный
случай непорождаемости.
S
A
B
C
D
E
F
→
→
→
→
→
→
→
AB | DE
a
bC
c
dF
e
fD
строке для разбиения еще сопоставляется число, которое указывает
максимально допустимое количество редактирующих операций. Там,
где пишется знак ≪?≫, это количество еще неизвестно. Для частей,
представленных терминальным символом, можно сразу же расчитать
точное число редактирующих операций. Необходимо также отметить,
что даже если грамматика не содержит ε-продукций, необходимо рассматривать пустые подстроки в разбиении, так как может понадобиться
осуществить одну или несколько операций вставки символов.
На данном этапе парсер рассматривает первую строку, где осуществляется попытка вывести пустую строку из нетерминала S с максимальным количеством редактирующих операций, равным 1. Первой
рассматривается продукция S → S + T :
Рис. 1.5. Пример КС-грамматики для проведения оптимизации
Если применить этот алгоритм к грамматике, изображенной на
рис. 1.5, то получится следующая последовательность действий:
1. Все нетерминалы и продукции помечены как непорождающие.
2. Согласно условиям, приведенным в шаге 2, порождающими становятся нетерминалы A, C и E, а также продукции A → a, C → c
и E → e.
S
+
1
S
?
5. Шаг 3 более не может пополнить множество порождающих нетерминалов и продукций. Грамматика G′ изображена на рис. 1.6.
S
T
F
i
→
→
→
→
→
AB
a
bC
c
e
Рис. 1.6. КС-грамматика с рис. 1.5 после удаления непорождающих правил
вывода и неопределенных терминалов
возврат
max:1
max:1
max:1
max:1
1
В итоге, после рассмотрения всех возможных вариантов развития
событий, мы получим следующие заключения:
S
+
S
Рассмотрим теперь алгоритм, который при помощи индукции осуществляет преобразование исходной грамматики в такую, у которой
S
A
B
C
E
max:2
T
×+
?
Это ведет к немедленному возврату, так как с помощью одного
исправления невозможно построить вывод синтаксически корректной
строки. Следовательно, необходимо рассмотреть следующую продукцию для S — S → T . Далее будет рассмотрена продукция T → T × F ,
которая тоже приведет к возврату, и алгоритм перейдет к продукции
T → F . Алгоритм при рассмотрении продукции F → (S) также
промоделирует возврат, и в итоге будет использована продукция F → i:
3. На основе этих заключений можно сделать вывод, что нетерминал B и продукцию B → bC можно пометить как порождающие,
так как нетерминал C является порождающим.
4. Следующая итерация шага 3 дает нам основание считать продукцию S → AB и нетерминал S порождающими.
105
3.7. Обнаружение и обработка ошибок
×
×
×+
1
1
1
1
1
?
×
×+
+
1
1
1
1
0
1
max:2
T
×+
>0
+
1
1
+
1
1
1
слишком
слишком
слишком
слишком
много
много
много
много
операций
операций
операций
операций
возврат
Таким образом, ≪×≫ должен быть отредактирован, ≪+≫ остается,
и в конец строки необходимо добавить один символ. Очевидно, что
получится корректная строка i + i.
В том случае, если алгоритм Ангера продолжит поиск других
выводов, используя в качестве первой продукции S → T , используя
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
104
Гл. 3. Синтаксический анализ
3.7.3. Обработка ошибок в глобальном контексте
В том случае, если парсер затрудняется локализовать позицию
ошибки, очень часто применяется стратегия обработки ошибок в глобальном контексте, когда рассматривается вся входная строка целиком.
Очень часто эта стратегия используется вместе с методами Ангера и
Кока—Янгера—Касами, потому что локализация ошибок не является
их сильной стороной, следовательно, необходимо рассматривать всю
входную строку целиком.
Наиболее часто используемым методом обработки ошибок, рассматривающим всю строку целиком, является метод наименьшей корректировки. Его основной идеей является попытка сформировать синтаксически корректную строку из той, которая подается на вход, с использованием как можно меньшего числа операций редактирования. К таким
операциям относятся вставка нового символа, удаление символа либо
изменение символа.
Для любой входной строки можно оценить сверху количество операций редактирования, которые необходимо совершить, чтобы преобразовать ее в синтаксически корректную строку. Действительно, можно
найти самую короткую цепочку, выводимую из грамматики. Пусть она
будет иметь размер m. Тогда если входная строка имеет размер n, то
оценка сверху для количества требующихся операций редактирования
равна максимуму из m и n. Это очень грубая оценка, которая однако
показывает, что задача разрешима за конечное число операций.
Продемонстрируем теперь, как метод наименьшей корректировки
работает для парсера, построенного по методу Ангера. Будем рассматривать грамматику, приведенную на рис. 3.2, и входную строку
×+. Наименьшей выводимой цепочкой является i. Таким образом,
максимальное количество операций редактирования, которое требуется
для приведения входной строки к синтаксически корректной цепочке,
равно 2. Первой используется продукция S → S + T , что приводит в
следующим разбиениям:
S
+
S
×
×
×+
?
?
?
?
?
?
×
×+
+
1
1
1
1
0
1
max:2
T
×+
?
+
?
?
+
?
?
?
Существенное различие между представленной таблицей и теми,
что были рассмотрены в п. 3.2.1, состоит в том, что каждой под-
1.3. Эквивалентные преобразования грамматик
21
все нетерминальные символы являются достижимыми от начального
нетерминала.
Алгоритм 2. Алгоритм удаления недостижимых нетерминалов
Вход: КС-грамматика G = (N , T , P , S)
Выход: КС-грамматка G′ = (N ′ , T , P ′ , S), свободная от недостижимых нетерминалов, причем L(G) = L(G′ )
1. В начале работы алгоритма все нетерминалы, кроме начального
символа S грамматики, помечаются как недостижимые.
2. Для каждой продукции A → α, где A — достижимый нетерминал,
помечаем все нетерминалы из α как достижимые.
3. Повторяем шаг 2 до тех пор, пока возможно пометить новые
нетерминалы. В противном случае переходим к шагу 4.
4. Грамматика G′ будет содержать все нетерминалы, которые помечены как достижимые. Множество P ′ будет состоять из продукций, определенных для этих нетерминалов.
Грамматика с рис. 1.6 преобразуется с помощью алгоритма удаления недостижимых нетерминалов следующим образом. Сначала пометится как достижимый только нетерминал S. На следующем шаге из-за
наличия продукции S → AB достижимыми станут символы A и B. И,
наконец, продукция B → bC влечет достижимость нетерминала C. На
этом процесс завершается, и можно сделать вывод, что нетерминал E
не является достижимым. Окончательный вариант грамматики можно
видеть на рис. 1.7.
S
A
B
C
→
→
→
→
AB
a
bC
c
Рис. 1.7. Окончательный вид КС-грамматики с рис. 1.5 после оптимизации
Удаление недостижимых символов не может сделать некоторый
нетерминал A непорождающим. Для оптимизации грамматики необходимо сначала применить алгоритм 1, а к получившейся грамматике
алгоритм 2. Если изменить последовательность применения алгоритмов, то возможно появление недостижимых символов, и грамматика с
рис. 1.5 является таким примером. Оставляем проверку этого факта в
качестве самостоятельного упражнения.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
22
Гл. 1. Элементы теории формальных языков
Возможна также ситуация, когда после оптимизации из грамматики
будут удалены все нетерминалы и продукции. В этом случае грамматика описывает пустой язык.
1.3.2. Удаление ε-продукций
Продукции, тело которых содержит ε, символ пустой строки, являются удобным средством для описания грамматик языков программирования, однако их применение может усложнить разработку синтаксического анализатора либо увеличить объем производимых им
вычислений. В этом разделе рассматривается, как для произвольной
грамматики с ε-продукциями, которая задает КС-язык L, составить
грамматику без таких продукций, порождающую язык L \ {ε}. Очевидно, что если в грамматике нет продукции с телом ε, то она не может
породить пустую строчку.
Для того чтобы описать алгоритм, осуществляющий такое преобразование, необходимо ввести понятие ε-порождающей переменной.
∗
Переменная A называется ε-порождающей, если A ⇒ ε. Если такая
переменная встречается в теле некоторой продукции грамматики, например, B → CAD, то из нее можно (но не обязательно) вывести ε.
Следовательно, рассматриваемая продукция имеет версию B → CD,
куда переменная A не входит. Так что, если мы не ≪разрешим≫ вывод
ε из переменной A, нам необходимо дополнить множество продукций
для B этой альтернативой.
Однако прежде чем начинать преобразование исходной грамматики,
необходимо осуществить поиск всех ε-порождающих нетерминалов.
Это делается с помощью следующего алгоритма.
Алгоритм 3. Алгоритм поиска ε-порождающих нетерминалов
Вход: КС-грамматика G = (N , T , P , S)
Выход: Множество Nε , которое содержит все ε-порождающие символы грамматики G
1. Если A → ε является продукцией в G, то A — ε-порождающий
символ, который должен быть помещен в множество Nε .
2. Если грамматика G содержит продукцию B → C1 C2 . . . Ck , то
нетерминал B помещаем в множество Nε в том и только том
случае, если каждый символ Ci является ε-порождающим.
Теперь рассмотрим алгоритм, который используется для удаления
ε-продукций из заданной грамматики:
3.7. Обнаружение и обработка ошибок
103
αa не может быть префиксом никакой цепочки, принадлежащей языку,
определяемому грамматикой. Рассмотрим, как обнаруживают ошибки
различные методы синтаксического анализа, описанные в настоящем
пособии.
На каждом шаге метод Ангера пытается для некоторой продукции
найти подходящие разбиения рассматриваемой части входной строки.
В том случае, если в строке есть одна или более ошибок, парсер,
построенный по методу Ангера, осуществит перебор всех возможных
разбиений для всех альтернатив текущего нетерминала и не найдет
ни одного подходящего разбиения. Для метода Кока—Янгера—Касами
ситуация складывается похожая. Если верхний элемент таблицы распознавания не содержит начального нетерминала грамматики, то ясно,
что входная строка содержит ошибки. Таким образом, универсальные
методы синтаксического анализа могут лишь определить, что входная
строка содержала одну или несколько ошибок, однако не могут ни их
локализовать, ни обнаружить точное количество.
Перейдем теперь к рассмотрению парсеров, в основе которых лежит
моделирование работы магазинного автомата (и примыкающего к ним
метода рекурсивного спуска). Метод, основанный на моделировании
работы магазинного автомата в ширину, обладает свойством корректного распознавания префикса. Моделирование останавливается, как
только достигается шаг, когда вычеркиваются все строки из таблицы
конфигураций. Действительно, в этом случае терминал в правой части
таблицы (где хранятся прогнозируемые сентенциальные формы) не
совпадает с очередным символом входной строки. При этом корректный
префикс находится в первой строке левой части таблицы.
Однако парсеры, основанные на моделировании работы магазинного
автомата с использованием метода поиска в глубину, не обладают свойством корректного распознавания префикса. Причиной является то,
что такой парсер осуществляет операцию возврата, когда с помощью
рассматриваемой продукции невозможно вывести оставшуюся часть
входной строки. Таким образом, исследовав несколько альтернативных
выводов, после каждого из которых следует возврат, можно уйти на
различную ≪глубину≫ распознавания. Однако существует простой метод для исправления этого недостатка: достаточно завести глобальную
переменную, в которой хранится наибольший номер символа входной
строки, до которого мы дошли перед тем, как произвести возврат. Эти
же соображения справедливы и для метода рекурсивного спуска.
LL- и LR-парсеры обладают свойством корректного распознавания
префикса, так как они останавливаются, когда начинается некорректный участок входной строки.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
102
Гл. 3. Синтаксический анализ
случае восстановления от ошибок необходимо изменять внутреннее
состояние парсера, следовательно, непрерывно производимый семантический анализ может производиться не в том порядке, который
характерен для синтаксически корректного входа. Обработка ошибок
является процедурой, в значительной мере использущей эвристические
методы для решения задачи.
Вывод сообщений об ошибках необходим для упрощения работы
программиста. Очевидно, что сообщения об ошибках должны быть
понятными, информативными и адекватными. Однако определение того, какое сообщение вывести, основывается на эвристическом подходе.
Несомненно, можно описать с помощью продукций значительную часть
ошибочных цепочек языка программирования с указанием ошибочного
сообщения, которое необходимо выводить, однако этот подход является
трудоемким.
3.7.1. Обнаружение и обработка лексических ошибок
На первом этапе работы компилятора происходит выделение лексем. Это делается при помощи конечных автоматов. Конечные автоматы
сразу же распознают некорректный символ. Положение этого символа
как раз и является местом, где была совершена ошибка. Например,
если распознается строка 3var и имеется в виду грамматика языка C,
то сначала она будет распознаваться как число, однако второй символ
распознан не будет. Лежащий в основе конечный автомат либо не
сделает перехода (в случае НКА), либо ≪умрет≫ (в случае с ДКА).
Ни один из этих вариантов не является подходящим, так как в конце
концов автомат не придет в допускающее состояние.
Выйти из создавшегося положения предлагается следующим образом. Введем специальный тип лексемы, который назовем ≪нераспознанная лексема≫. Если распознающий конечный автомат не приходит в
допускающее состояние, то можно все символы, которые привели этот
автомат в текущее состояние, а также все последующие, которые не
являются разделителями либо пробелами, записать именно как ≪нераспознанную лексему≫. При такой обработке лексических ошибок их
фактическая обработка будет происходить на стадии синтаксического
анализа.
3.7.2. Обнаружение синтаксических ошибок
Методы синтаксического анализа обнаруживают ошибки во входном потоке лексем по-разному. Будет говорить, что парсер обладает
свойством корректного распознавания префикса, если был успешно
распознан некоторый префикс α входной строки αaβ, а попытка распознавания очередного символа a завершается выводом о том, что строка
1.3. Эквивалентные преобразования грамматик
23
Алгоритм 4. Алгоритм удаления ε-продукций
Вход: КС-грамматика G = (N , T , P , S) и множество Nε , содержащее ε-порождающие символы этой грамматики
Выход: КС-грамматика G′ = (N ′ , T , P ′ , S), свободная от ε-продукций, причем L(G) \ {ε} = L(G′ )
1. Помещаем в P ′ продукции из P , которые не содержат ε-порождающих символов и не являются ε-продукциями.
2. Пусть C → α1 X1 α2 X2 . . . αk Xk — это некоторая продукция из P ,
которая содержит k ε-порождающих нетерминалов, т.е. для всех
1 6 i 6 k выполняется Xi ∈ Nε , αi ∈ (N ∪ T )∗ . Тогда поместим
в P ′ множество продукций, получающихся удалением одного или
нескольких символов Xi из тела продукции для C, причем если
тело этой продукции состоит только из таких нетерминалов, все
одновременно они удалены быть не могут.
Рассмотрим пример работы этого алгоритма. Пусть дана следующая
грамматика:
S
A
B
C
→
→
→
→
AB | aC
ε
bBB | ε
a | aS | ε
Множество ε-порождающих символов состоит из всех нетерминальных символов грамматики — Nε = {S, A, B, C}. Построим множество
продукций грамматики G′ . Согласно условиям из первого шага, помещаем в P ′ продукцию C → a. Далее рассмотрим продукцию S → AB,
у которой все символы тела являются ε-порождающими, поэтому есть
четыре способа выразить присутствие или отсутствие A и B. Способ,
когда оба символа отсутствуют, мы рассмотреть не можем, так как в
этом случае получится ε-продукция для S. Получаем, что P ′ теперь
содержит:
S
C
→
→
AB | A | B
a
Продукции для A мы не рассматриваем в качестве кандидатов на
помещение в P ′ , так как все множество продукций для A состоит
из единственной ε-продукции. Аналогично тому, как делали для S,
рассматриваем множество продукций для B и C и в итоге получаем
грамматику G′ :
S
B
C
→
→
→
AB | A | B
bBB | bB | b
a | aS
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
24
Гл. 1. Элементы теории формальных языков
Теперь можно удалить непорождающие продукции и нетерминалы
из этой грамматики:
S
B
C
→
→
→
B
bBB | bB | b
a | aS
1.3.3. Удаление цепных продукций
Цепные продукции имеют вид A → B, где A и B являются нетерминальными символами. Иногда цепные продукции могут усложнять
анализ грамматики и создавать излишние шаги в порождениях. В этом
разделе мы приведем алгоритм, который помогает привести исходную
грамматику к эквивалентной, но уже без цепных продукций. Однако
прежде чем переходить к определению этого алгоритма, введем понятие
цепной пары:
3.7. Обнаружение и обработка ошибок
101
анализатора, делает невозможным построение вывода с учетом правил
грамматики. Другая причина состоит в том, что представленные методы синтаксического анализа эффективно обнаруживают синтаксические ошибки. Определение присутствия семантических и логических
ошибок является гораздо более трудной задачей и выходит за рамки
настоящего пособия.
Методы синтаксического анализа, которые мы до сих пор рассматривали, позволяют лишь ответить на вопрос: ≪Есть ли в программе
ошибка?≫. Однако они не позволяют локализовать ее, ни сообщить
разработчику, где эта ошибка находится. Фактически при написании
обработчика ошибок необходимо достигнуть следующих целей:
• Обработчик ошибок должен указывать место в исходной программе, где находится ошибка.
1. (A, A) является цепной парой для любого нетерминала, т.е.
∗
A ⇒ A за ноль шагов.
• Необходимо производить восстановление после ошибок с целью
продолжения обработки остальной части входа.
2. Если (A, B) цепная пара и B → C — это цепная продукция, тогда
(A, C) — цепная пара.
• Обработка ошибок не должна существенно замедлять работу
компилятора.
Способ построения множества цепных пар прост: рассматриваем
базисные цепные пары и, применяя к ним все возможные цепные
продукции, пытаемся построить остальные. Процесс заканчивается,
когда мы больше не можем поместить в множество цепных пар новые
элементы.
• Необходимо избегать сообщений о так называемых ≪наведенных
ошибках≫, то есть сообщениях, в действительности не говорящих
о присутствии ошибок в программе, а являющихся следствием
продолжения работы синтаксического анализатора после не совсем удачно проведенного этапа восстановления после ошибок.
Алгоритм 5. Алгоритм удаления цепных продукций
Вход: КС-грамматика G = (N , T , P , S)
Выход: КС-грамматика G′ = (N ′ , T , P ′ , S), свободная от цепных
продукций, причем L(G) = L(G′ )
Таким образом, обработка ошибок компилятором состоит из двух
составных частей: локализация ошибки и восстановление после
ошибки. Методы синтаксического анализа эффективно обнаруживают
наличие ошибки, однако часто не позволяют указать позицию во
входной цепочке, где встретилась эта ошибка. При этом большинство
методов останавливает построение дерева разбора при возникновении
ошибки и не просматривает оставшуюся часть входной цепочки. Следовательно, возникает необходимость в способе, который бы позволял это
делать с помощью коррекции внутреннего состояния синтаксического
анализатора. Алгоритм, который это осуществляет, как раз и является
механизмом восстановления после ошибок. Другим вариантом работы
этого механизма является не подстройка внутреннего состояния анализатора, а использование методов корректирования входной цепочки
с помощью удаления, вставки либо модификации символов. Такое
поведение имеет существенное преимущество: мы можем проводить
семантический анализ входной строки непрерывно. Действительно, в
1. Формируем множество цепных пар грамматики G.
2. Для каждой цепной пары (A, B) добавим к P ′ все продукции
вида A → α, где B → α — нецепная продукция из P . При A = B
все нецепные продукции для B из P добавляются к P ′ .
1.3.4. Нормальная форма Хомского для КС-грамматик
Нормальная форма Хомского накладывает определенные условия на
продукции КС-грамматик. Эта форма КС-грамматик не имеет бесполезных символов, ε-продукций, цепных правил и определяется следующим
образом.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
100
Гл. 3. Синтаксический анализ
3.6.4. LR(k > 1)-грамматики и их анализ
Как и в случае LL-грамматик, для того чтобы увеличить выразительную силу LR-грамматик, логичным представляется следующее
расширение: определение очередной основы будет производиться с
использованием просмотра не одного символа вперед, а k символов.
Однако в этом случае резко возрастает объем управляющих таблиц
Action и Goto и при практическом применении зачастую бывает, что
если грамматика не оказалась LR(1)-грамматикой, то шансы, что она
окажется LR(k>1)-грамматикой невелики. Более подробные рассуждения на эту тему можно найти в [16].
3.7. Обнаружение и обработка ошибок
До сих пор мы предполагали, что программы, подаваемые на вход
транслятору, являются корректными — не содержат лексических и синтаксических ошибок. На практике входные данные имеют ошибки,
например опечатки, и компилятор должен помочь программисту их
обнаружить. Любая программа может потенциально содержать ошибки
самого разного уровня, которые могут быть классифицированы следующим образом.
Лексические ошибки. Эти ошибки часто возникают из-за опечаток в названиях ключевых слов, идентификаторов или операторов.
Следствием таких ошибок является невозможность для лексического
анализатора распознать очередную лексему.
Синтаксические ошибки. Даже если лексический анализатор распознал все лексемы, это еще не значит, что программа написана
корректно. Программист мог нарушить правила синтаксиса языка программирования, которые задаются грамматикой. Примером синтаксической ошибки может быть арифметическое выражение с неправильно
расставленными скобками.
Семантические ошибки. Примерами семантических ошибок может
служить применение операторов к несовместимым по типу операндам.
Логические ошибки. Даже если программа написана корректно с
точки зрения определения языка программирования, она может содержать ошибки в своей логике и выполнять не то, что было задумано
программистом. К этому виду ошибок также относят, например, бесконечные циклы или бесконечную рекурсию.
Очень часто выявление и восстановление после ошибок реализуют
на стадии синтаксического анализа. Основная причина этого заключается в том, что большинство ошибок являются синтаксическими по
природе, т.е. последовательность лексем, поступающая от лексического
1.3. Эквивалентные преобразования грамматик
25
Определение 4. Грамматика G = (N , T , P , S) находится в нормальной форме Хомского, если она не имеет бесполезных символов и все
ее продукции построены по одному из двух шаблонов:
1. A → BC, где A, B, C ∈ N .
2. A → a, где A ∈ N , a ∈ T .
Известно, что любая ε-свободная грамматика может быть преобразована к эквивалентной грамматике, находящейся в нормальной форме
Хомского. Приведем алгоритм такого преобразования.
Алгоритм 6. Преобразование грамматики к нормальной форме Хомского
Вход: КС-грамматика G = (N , T , P , S)
Выход: КС-грамматика G′ = (N ′ , T , P ′ , S) в нормальной форме
Хомского, для которой выполняется L(G) \ {ε} = L(G′ )
1. Используем алгоритм 4 для удаления ε-продукций из грамматики
G.
2. Удалим цепные правила из получившейся грамматики с помощью
алгоритма 5.
3. К полученной грамматике последовательно применим алгоритмы 1 и 2 для удаления бесполезных и непорождающих символов.
4. Продукции в полученной грамматике имеют вид либо A → a,
где A является нетерминалом, а a терминальным символом, либо
имеют тело длиной не менее 2. Правила первого типа допускаются по определению, а для каждого из правил второго типа
совершим следующие действия:
(a) Для каждого нетерминала a создаем новую переменную,
например, A, которая будет иметь единственную продукцию
A → a. Используем переменную A вместо a везде в телах
продукций длины 2 и более.
(b) Рассмотрим теперь продукции вида A → X1 X2 . . . Xk , где
A, X1 , X2 , . . . , Xk являются нетерминальными символами.
′
и заменим
Введем k − 2 новых переменных X2′ , . . . , Xk−1
исходную продукцию на k − 1 следующих продукций:
′
A → X1 X2′ , X2′ → X2 X3′ , . . . , Xk−1
→ Xk−1 Xk
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
26
Гл. 1. Элементы теории формальных языков
Грамматики в нормальной форме Хомского могут использоваться
при построении трансляторов. Так, один из универсальных алгоритмов
синтаксического анализа, метод Кока-Янгера-Касами, работает с грамматиками в этой нормальной форме.
1.3.5. Нормальная форма Грейбах для КС-грамматик
Нормальная форма Грейбах представляет собой еще одну форму для
записи КС-грамматик, которая определяется следующим образом.
Определение 5. Грамматика G = (N , T , P , S) находится в нормальной форме Грейбах, если все ее продукции имеют вид A → aα, где
a ∈ T , а α ∈ N ∗ — цепочка из ноля или более нетерминалов.
Преимущество грамматик, находящихся в нормальной форме Грейбах, состоит в том, что первый терминальный символ в теле продукции
может помочь при построении вывода заданной цепочки. Действительно, необходимо сравнить этот символ с очередным символом на входе
для принятия решения об использовании продукции.
В [18] показано, что любая КС-грамматика может быть представлена в нормальной форме Грейбах, однако этот перевод является
достаточно трудоемкой операцией, даже если исходная грамматика
представлена в нормальной форме Хомского.
1.3.6. Устранение левой рекурсии
В том случае, если для некоторого нетерминала A выполняет+
ся A ⇒ αAβ, то такой нетерминал называется рекурсивным. Если
α = ε, то A называется леворекурсивным. В случае β = ε нетерминал
A называется праворекурсивным. Грамматика, имеющая хотя бы один
леворекурсивный нетерминал, называется леворекурсивной. По аналогии определяется праворекурсивная грамматика.
Использование грамматик с леворекурсивными нетерминалами может значительно затруднять разработку синтаксических анализаторов.
К счастью, существует алгоритм, который позволяет устранять левую
рекурсию.
Алгоритм 7. Алгоритм удаления левой рекурсии
Вход: КС-грамматика G = (N , T , P , S)
Выход: КС-грамматика G′ = (N ′ , T , P ′ , S), свободная от леворекурсивных нетерминалов, причем L(G) = L(G′ )
99
3.6. Синтаксический анализ для LR-грамматик
Action
s1
s2
s3
s4
s5
s6
s7
s8
s9
s10
перенос
E→T
T →n
перенос
S → E♯
перенос
перенос
E →E−T
перенос
T → (E)
s1
s2
s3
s4
s5
s6
s7
s8
s9
s10
Goto
(
)
s6
ош.
n
s3
−
ош.
ош.
s7
ош.
ош.
s5
s3
s3
ош.
ош.
s6
s6
ош.
ош.
ош.
ош.
ош.
s7
ош.
s10
ош.
♯
ош.
E
s4
T
s2
s9
s2
s8
Рис. 3.22. Таблицы Action и Goto для LR(0)-грамматики с рис. 3.15
Для LR(0)-анализа эти таблицы проиндексированы состояниями, а
у таблицы Goto еще и столбцы поименованы символами, принадлежащими алфавиту LR(0)-автомата. Например, для грамматики с рис. 3.15
таблицы представлены на рис. 3.22. Таблицы используются следующим
образом:
1. Находясь в состоянии s, смотрим на элемент в таблице Action и
выполняем действие, которое там отображается.
2. Выбираем элемент s′ в таблице Goto, стоящий на пересечении
строки с индексом s и столбца, помеченного очередным символом
сентенциальной формы. Переходим в состояние s′ .
Часто на практике элементы, располагающиеся в таблице Action,
указывают на процедуры, ответственные за семантические действия.
Можно заметить, что таблицы, показанные на рис. 3.22, содержат
достаточно много пустого места, поэтому часто используют различные
техники для сжатия этих таблиц.
Для LR(1)-анализаторов таблицы Action и Goto строятся несколько
иначе. Строки в обеих таблицах, так же, как и для LR(0)-грамматик,
поименованы состояниями. Однако теперь столбцы таблицы Action
проиндексированы с помощью терминальных символов грамматики и
символа ♦. При определении очередного действия символы, именующие столбцы этой таблицы, сравниваются с просмотренным вперед
очередным символом входной строки. Столбцы таблицы Goto обозначены символами из алфавита N ∪T ∪{♦}. Другим отличием LR(1)-таблиц
от LR(0)-таблиц является перенос проверок на ошибочные ситуации
из таблицы Goto в таблицу Action. Это имеет смысл, так как теперь
мы можем проверить очередной символ на корректность уже на шаге
определения действия.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
98
Гл. 3. Синтаксический анализ
1.3. Эквивалентные преобразования грамматик
27
Будем предполагать, что все нетерминалы грамматики G пронумерованы числами от 1 до n, т.е. N = {A1 , A2 . . . An } и выполняется
равенство S = A1 . Тогда наша цель состоит в том, чтобы преобразовать множество продукций этой грамматики таким образом, чтобы
произвольная продукция Ai → α начиналась либо с терминала, либо с
такого символа Aj , что j > i. Положим i = 1.
•S ♦
•E ♦
ε
ε
S →•E ♦
ε
E →•E − T ♦
E
S → E• ♦
ε
E →•T ♦
E
E → E•−T ♦
ε
T →•(E) ♦
T →•n ♦
T
1. Пусть Ai → Ai α1 | . . . | Ai αm | β1 | . . . | βp . При этом ни одна
из цепочек βj не начинается с Ak , если k 6 i. Поместим в G′
следующее множество продукций, построенных из Ai -продукций:
•T ♦
ε
ε
n
ε
E → T• ♦
Ai
A′i
(
T → (•E) ♦
T → n• ♦t
−
E
ε
)
T
ε
E → E − T• ♦
T → (E)• ♦
ε
•E −
ε
•E )
•T −
ε
ε
ε
ε
•T )
ε
ε
ε
ε
ε
ε
ε
E →•E − T −
E
E →•T −
T →•n −
T
E → E•−T −
ε
E → T• −
n
T → n• −
−
T →•(E) −
(
T → (•E) −
E
T → (E•) −
E → E−•T −
)
T
T → (E)• −
E → E − T• −
E →•E − T )
E
E → E•−T )
E →•T )
T
E → T• )
T →•n )
ε
T →•(E) )
n
T → n• )t
(
T → (•E) )
−
E → E−•T )
E
T → (E•) )
)
T
E → E − T• )
β1 | . . . | βp | β1 A′i | . . . | βp A′i
α1 | . . . | αm | α1 A′i | . . . | αm A′i
где A′i — новый нетерминал, который помещается наряду с Ai в
N ′ . Правые части всех Ai -правил начинаются теперь с терминала
либо с Ak для некоторого k > i.
T → (E•) ♦
E → E−•T ♦
→
→
2. Если i = n, полученную грамматику G′ считать построенной и
остановиться. В противном случае, положить i = i + 1 и j = 1.
3. Вместо каждого правила вида Ai → Aj α поместить в P ′ множество продукций Ai → β1 α | . . . βm α, где Aj → β1 | . . . | βm — все
Aj -продукции. Так как тело каждой продукции для Aj начинается уже с терминала либо с Ak , для которого выполняется k > j,
то и правая часть каждой Ai -продукции будет теперь обладать
этим свойством.
4. Если j = i − 1, перейти к шагу 1, иначе положить j = j + 1 и
перейти к шагу 3.
T → (E)• )
ε
Рис. 3.21. ε-НКА для распознавания основ LR(1)-грамматики
Таким образом, любой КС-язык определяется нелеворекурсивной
грамматикой. С доказательством этого факта более подробно можно
ознакомиться в [3].
1.3.7. Левая факторизация
Очень часто при описании языков в КС-грамматиках используются
правила вида A → αβ | αγ. Наличие таких правил влечет за собой
следующий недостаток. При построении вывода некоторой непустой
цепочки может быть непонятно, какую из продукций для нетерминала
A необходимо выбрать, так как продукции A → αβ и A → αγ
начинаются с одного и того же терминального символа.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
28
Гл. 1. Элементы теории формальных языков
Для решения этой неоднозначности используют метод, который
называется левая факторизация. Этот метод каждому неоднозначному
правилу вида
A → αβ1 | αβ2 | . . . | αβn
ставит в соответствие следующую пару правил:
A
B
→
→
αB
β1 | β2 | βn
Здесь B является новым нетерминалом, включаемым в грамматику.
Алгоритм 8. Левая факторизация грамматики
Вход: КС-грамматика G = (N , T , P , S)
Выход: Левофакторизованная грамматика G′ = (N ′ , T , P ′ , S), причем L(G) = L(G′ )
1. Рассмотрим некоторый нетерминал A. Найдем самый длинный
префикс α, который является общим для двух и более альтернатив для A. Если α 6= ε, т.е. префикс непуст, то заменяем все
правила для A вида
A → αβ1 | αβ2 | . . . | αβn | γ1 | . . . γk ,
где γi — это альтернативы, не начинающиеся на α, на
A
B
→
→
αB | γ1 | . . . | γk
β1 | β 2 | βn ,
где B — новый нетерминал.
2. Повторяем преобразование, приведенное в предыдущем шаге до
тех пор, пока никакие две альтернативы для некоторого нетерминала A′ не будут иметь общего префикса.
3.6. Синтаксический анализ для LR-грамматик
97
совершить свертку. Это приводит нас к классу анализаторов, которые
называются LR(1)-анализаторами.
Попробуем построить ε-НКА для распознавания основ нашей грамматики. Введем символ ♦. Тогда запись •E♦ будет означать, что
следующим за E ожидается конец строки.
Алгоритм 26. Построение автомата для распознавания основ
LR(1)-грамматик
Вход: КС-грамматика G = (N , T , P , S)
Выход: ε-НКА для распознавания основ A = (Q, Σ, δ, q0 , F )
1. Согласно алгоритму 24 строим ε-НКА для грамматики G. Пусть
это будет автомат A′ .
2. Для каждой продукции вида P → . . . •QR . . ., где выполняется
Q ∈ N , R ∈ N ∪ T , создаем множество состояний первого
типа, которые имеют вид •Qy, где y ∈ F IRST (R). Символ
y не несет особой смысловой нагрузки, а используется лишь
для различия состояний. Соединяем состояние, соответствующее
P → . . . •QR . . ., c •Qy при помощи ε-переходов.
3. Для каждого нового состояния первого типа •Qy строим состояния второго типа и отмечаем их суффиксом y. Построение и
соединение производится по принципу, описанному в алгоритме 24. При этом возможно придется некоторые их них соединить
с состояниями первого типа, построенными на предыдущем шаге.
Полученный автомат и будет являться искомым.
Для рассматриваемой грамматики ε-НКА для распознавания основ показан на рис. 3.21. Для того чтобы получить LR(1)-автомат, применяем
к построенному ε-НКА для распознавания основ алгоритм 9, который
строит эквивалентный детерминированный автомат. Если этот автомат
не имеет конфликтов, то грамматика является LR(1)-грамматикой.
3.6.3. Построение управляющей таблицы LR-анализатора
Итак, основным компонентом рассмотренных алгоритмов LR-анализа являются конечные автоматы, которые помогают найти основу
в сентенциальной форме. На практике удобно представлять эти ДКА
в виде двух таблиц Action и Goto. Первая таблица задает действия,
которые необходимо выполнять на очередном шаге анализа — перенос
очередного символа в стек, осуществить свертку либо осуществить допуск строки. Вторая таблица указывает, в какое состояние необходимо
перейти после распознавания очередного символа.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
96
Гл. 3. Синтаксический анализ
Необходимо отметить, что грамматики, содержащие ε-продукции,
не являются LR(0)-грамматиками. Действительно, если в грамматике
есть продукции X → . . . A . . . и A → ε, то дуги, помеченные символом
ε, будут выходить из состояния X → . . . •A . . . в состояния A → • и •A,
что после приведения ε-НКА к ДКА даст конфликт перенос/свертка.
Однако существуют подходы (см. [16]), которые позволяют проводить
LR-анализ даже для таких грамматик.
3.6.2. Построение анализаторов для LR(1)-грамматик
Рассмотрим грамматику с рис. 3.15, из которой мы уберем
символ конца строки ≪♯≫. Тогда получим следующую грамматику:
→
→
→
→
→
S
E
E
T
T
E
E−T
T
n
(E)
s6
s1
(
s2
T
n
T → n•
E
T → (•E)
E →•E −T
E →•T
T →•n
T →•(E)
T
E → T•
n
s3
S → E•
E → E•−T
(
n
s4 ×
−
(
s9
−
s7
T → (E•)
E → E•−T
)
s10
s8
E → E − T•
Стадия лексического анализа является начальным этапом работы
транслятора. В этой главе мы рассмотрим основные принципы, по
которым производится этот этап.
T → (E)•
Рис. 3.20. LR(0)-автомат, содержащий конфликт
Роль лексического анализатора заключается в чтении входного
файла и формировании списка лексем, которые потом подаются на вход
синтаксическому анализатору. Лексический анализатор также решает
следующие задачи:
1. Удаление из входного файла не несущих смысловой нагрузки
символов. К таким символам могут относиться повторяющиеся
пробелы, комментарии, символы табуляции и перевода строки.
2. Согласование сообщений об ошибках компиляции и текста исходной программы. Например, лексический анализатор может помочь
установить строку в исходном файле, где встретилась ошибка.
3. В том случае, когда исходный язык поддерживает макросы и
директивы препроцессора, реализация этой функциональности
может быть выполнена на стадии лексического анализа.
E
E → E−•T
T →•n
T →•(E)
T
ЛЕКСИЧЕСКИЙ АНАЛИЗ
2.1. Роль лексического анализатора
Эта грамматика уже не будет являться LR(0)-грамматикой. Действительно, если построить для нее LR(0)-автомат, то он будет содержать
конфликт перенос/свертка (таким будет состояние s4 , отмеченное
символом ≪×≫ на рис. 3.20). Таким образом, на основе построенного
автомата невозможно решить, осуществлять ли нам перенос либо
делать свертку. Однако ситуация может быть исправлена, если бы мы
знали, какой символ во входной строке будет следующим. Если это
символ ≪−≫, то необходимо сделать перенос, в противном случае надо
S →•E
E →•E −T
E →•T
T →•n
T →•(E)
Глава 2
Существует ряд причин, по которым работа транслятора разделяется на стадии лексического и синтаксического анализа. Первая причина
является следствием применения принципа ≪разделяй и властвуй≫ —
создание отдельных модулей лексического и синтаксического анализа,
между которыми есть простой и четко определенный интерфейс, значительно упрощает разработку и увеличивает эффективность работы
транслятора. Так, лексический анализатор может работать параллельно
с синтаксическим, накапливая лексемы в некотором промежуточном
буфере, откуда они уже поступают на вход синтаксическому анализатору. Второй причиной является улучшение переносимости транслятора
на другие платформы, где могут быть свои особенности входного
алфавита и иные специфичные характеристики устройств ввода.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
30
Гл. 2. Лексический анализ
3.6. Синтаксический анализ для LR-грамматик
95
2.2. Понятие токенов и лексем
2. Если в стеке остался единственный нетерминал S, то успешно
завершить алгоритм.
Как мы уже говорили, главной задачей лексического анализатора
является разбиение входного файла на список лексем. Фактически
каждая лексема представляет собой ≪слово≫, которое встретилось во
входном файле и которое подходит по определению языка программирования. Эти наборы ≪слов≫ делятся на подмножества, которые называются токенами. Неформально описание токена можно представить
как задание шаблона, которому удовлетворяет некоторое множество
строк. Примеры токенов можно увидеть на рис. 2.1.
Токены рассматриваются как терминальные символы грамматики,
описывающей синтаксические конструкции исходного языка. В большинстве языков программирования в качестве токенов выступают
ключевые слова, идентификаторы, константы, символы пунктуации.
Лексемы, соответствующие шаблонам токенов, представляют во входной программе строки символов, которые рассматриваются вместе как
лексическая единица.
Шаблоны представляют собой правила, описывающие набор лексем,
которые могут встретиться во входном файле. Для точного описания сложных по структуре токенов можно использовать регулярные
выражения или регулярные грамматики (грамматики 3-го типа по
классификации Хомского). Эти два формализма являются одинаково
мощными и задают множество регулярных языков. С их помощью
можно описывать конкатенацию и повторение строк, выбор различных
альтернатив из конечного множества, но нельзя задавать конструкции,
описывающие, например, вложенность.
Основной задачей, стоящей при решении задачи распознавания
лексем, является создание некоторого устройства, которое это делает.
Так, если описание токенов производится с помощью регулярных грамматик или регулярных выражений, порождающих регулярные языки, то
логично предложить в качестве такого устройства конечные автоматы,
которые распознают в точности то же самое множество языков. Далее
мы рассмотрим, что такое конечные автоматы, как регулярные грамматики и регулярные выражения могут быть преобразованы в конечный
3. На вершине стека теперь находится символ T , который является
нетерминалом (если мы действовали согласно п. 1b) либо терминалом (если были совершены операции, приведенные в п. 1a) и
состояние s под ним. Попытаться найти состояние s′ = δ(s, T ).
Токен
const
relation
id
num
Примеры
const
<, >, ==, <=, >=, <>
i, j, num5, vol
0.1, 0.2E3, 12
Описание
Ключевое слово const
Отношения
Идентификаторы
Константы
Рис. 2.1. Примеры токенов
4. Если s′ существует, то поместить его в стек, в противном случае
выдать ошибку.
5. Перейти к шагу 1.
Рассмотрим теперь класс грамматик, для которых применим метод
LR(0)-анализа. Действительно, ε-НКА может быть построен для любой
КС-грамматики, после чего можно построить эквивалентный ДКА.
Время, которое требуется парсеру, действующему согласно алгоритма 25, изменяется линейно в зависимости от длины входа. На первый
взгляд кажется, что мы получили универсальный парсер, применимый
для любой КС-грамматики и действующий за линейное время. Однако
это не так. Существуют два типа конфликтов, проиллюстрированных
на рис. 3.19. Первый тип конфликтов, который называется конфликт
перенос/свертка, возникает, когда LR(0)-автомат имеет допускающее
состояние, из которого идет дуга. Смысл состояния в этом случае
неоднозначен — можно совершить свертку, а можно и сделать перенос
символа в стек. Другой тип конфликта называется конфликт свертка/свертка. В этом случае в состоянии находятся две продукции,
по которым можно совершить свертку. Однако нет никакой дополнительной информации, какую же продукцию необходимо предпочесть.
Необходимо заметить, что не существует конфликтов перенос/перенос.
Это исключено самим использованием ДКА — из состояния может
выходить только единственная дуга, помеченная некоторым символом.
Грамматики, по которым строится LR(0)-автомат, не имеющий конфликтов, называются LR(0)-грамматиками.
E → T •+E
E → T•
E → E −T •
E → T•
+
конфликт перенос/свертка
при распознавании ≪+≫
конфликт свертка/свертка
Рис. 3.19. Типы конфликтов
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
94
Гл. 3. Синтаксический анализ
Обратим внимание, что все состояния ДКА для распознавания
основ имеют свои имена. Тогда при рассмотрении сентенциальной
формы E − n − n♯, мы получим следующее вычисление:
E
−
n
−n♯
s1 → s4 → s7 → s3 → ×
Состояние s3 является допускающим и соответствует основе T → n.
После отсечения основы получим сентенциальную форму E − T − n♯ и
попробуем снова повторить процесс поиска:
E
−
T
−n♯
s1 → s4 → s7 → s8 → ×
Что соответствует найденной основе E → E − T . Однако, если внимательно посмотреть на эти два процесса вычислений, можно заметить,
что их начальные отрезки, от s1 до s7 включительно, совпадают. Следовательно, можно было бы более оптимально организовать поиск, если
бы мы сохраняли эти префиксы путей и пользовались этим знанием при
поиске очередной основы. Это приводит нас к следующему алгоритму
синтаксического анализа.
Алгоритм 25. LR(0)-анализ
Вход: LR(0)-автомат A = (Q, Σ, δ, q0 , F ), распознающий основы для
КС-грамматики G = (N , T , P , S), входная строка α = a1 a2 . . . an
Выход: если α ∈ L(G), то обратный правый вывод строки α, в
противном случае сообщение об ошибке
Пусть имеется стек, в котором содержатся строки вида
s0 X1 s1 . . . Xm sm , где si — это состояние LR(0)-автомата, причем
Xj ∈ (N ∪ T ). Будем считать, что голова стека находится справа. В
самом начале работы там находится единственное состояние q0 .
2.2. Понятие токенов и лексем
31
автомат и, наконец, как по этому конечному автомату можно построить
программу на языке высокого уровня.
2.2.1. Способы задания токенов
Регулярные грамматики (грамматики 3-го типа) являются самыми
простыми по классификации Хомского, однако их выразительной силы достаточно для того, чтобы описывать лексические конструкции
языков программирования. Примером задания токенов может служить
грамматика, описывающая множество корректно построенных идентификаторов:
(0)
(1)
(2)
(3)
Id
R
Letter
Digit
→
→
→
→
Letter | Letter R
Letter R | Digit R | ε
a | b | ... | z
0 | 1 | ... | 9
Другим популярным методом для задания лексических конструкций являются регулярные выражения. Эта нотация представляет собой алгебраический способ описания формальных языков. Фактически каждый токен задает некоторое подмножество строк, которое
является формальным языком. Так, токен, задающий идентификатор,
определяется как буква, за которой следует буква или цифра. С
помощью регулярных выражений этот шаблон можно записать как
letter(letter|digit)∗. Вертикальная черта обозначает логическую связку ≪или≫, скобки используются для группирования подвыражений,
а непосредственное соседство letter с оставшейся частью выражения
означает конкатенацию. Каждое регулярное выражение строится из
более простых выражений при помощи набора регулярных операций.
К таким операциям (над алфавитом Σ) относятся:
1. ε представляет собой регулярное выражение, определяющее одну
пустую строку, т.е. множество {ε}.
1. Состояние sm на вершине стека является либо допускающим для
LR(0)-автомата, либо нет:
2. Если a является символом из Σ, то a представляет регулярное
выражение, содержащее строку a, т.е. множество {a}.
(a) Если sm не является допускающим, то помещаем очередной
символ входной строки ai на вершину стека.
3. Если r и s — регулярные выражения, определяющие формальные
языки L(r) и L(s), то:
(b) Если sm допускающее и ему соответствует основа X → β,
то необходимо свернуть β к X. Для этого мы извлекаем
2 × |β| символов из вершины стека, так как необходимо
еще извлекать символы, соответствующие состояниям, и
помещаем туда символ X. Вывести продукцию X → β в
качестве результата.
(a) (r)|(s) обозначает регулярное выражение, задающее объединение языков, т.е. L(r) ∪ L(s).
(b) (r)(s) обозначает регулярное выражение, задающее конкатенацию языков L(r)L(s), т.е. множество цепочек, которые
можно образовать путем дописывания к любой цепочке из
L(r) любой цепочки из L(s).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
32
Гл. 2. Лексический анализ
(c) (r)∗ представляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества (ноль и более) цепочек из L(r).
(d) (r) обозначает любую цепочку из L(r) (это правило гласит,
что регулярное выражение при необходимости можно поместить в дополнительные скобки).
Произвольные регулярные выражения определяются с помощью
индукции. Правила 1 и 2 определяют базис индукции, а правило 3
обеспечивает индуктивный переход. Рассмотрим теперь приоритет регулярных операций. Оператор ≪звездочка≫ (правило 3c) имеет самый
высокий приоритет и применяется к наименьшей последовательности
символов, находящейся слева от него и являющейся правильно построенным регулярным выражением. Далее по порядку приоритетности следует оператор конкатенации. Наименьший приоритет имеет оператор
объединения. Скобки в регулярных выражениях можно использовать
для того, чтобы самостоятельно сгруппировать операнды.
Кроме рассмотренного набора регулярных операторов существует
ряд сокращений для часто используемых конструкций в регулярных
выражениях:
1. (r)+ обозначает регулярное выражение, задающее язык, который
можно образовать конкатенацией одной или более цепочек из
языка L(r).
2. (r)? обозначает регулярное выражение, представляющее сокращенную запись выражения (r|ε), т.е. множество строк, состоящее
из одной или ноля строк языка L(r).
•S
S →•E♯
•E
E → E−•T
E →•E − T
S → E•♯
•T
n
−
E
→ T → n• −n♯
→ E → E−•T →
E →•T
T →•n
•T
T →•(E)
T →•n
T →•(E)
Рис. 3.17. Поиск основы при помощи автомата с рис. 3.16 для сентенциальной
формы E − n − n♯
сконструированного ε-НКА, считая эту форму его входной строкой, то
в итоге автомат придет в финальное состояние T → n• (см. рис. 3.17),
и это будет состояние, соответствующее искомой основе. Отсечение
этой основы даст нам новую сентенциальную форму E − T − n♯, для
которой мы заново повторяем описанный процесс.
Моделирование работы ε-НКА можно провести при помощи алгоритма 14. Однако такое моделирование может быть менее эффективным, чем использование детерминированного автомата. Поэтому можно
использовать алгоритм 10 для преобразования ε-НКА в эквивалентный
ДКА. Для автомата, изображенного на рис. 3.16, эквивалентный ДКА
показан на рис. 3.18. В дальнейшем ДКА для распознавания основ
будем называть LR(0)-автоматом.
s6
s1
(
S →•E♯
E →•E −T
E →•T
T →•n
T →•(E)
3. [abc], где a, b, c ∈ Σ, обозначает сокращение регулярного выражения (a|b|c). Иногда используют нотацию вроде [a − z] для задания
множества символов (a|b|c| . . . |y|z).
Специальные операторы ≪+ ≫, ≪? ≫ такой же приоритет, что и ∗ .
Иногда для удобства записи регулярным выражениям присваивают
имена и определяют новые выражения с использованием этих имен.
Такая нотация называется регулярными определениями и имеет вид:
d1 → r1
d2 → r2
...
dn → rn ,
где каждое di представляет индивидуальное имя, а ri — это регулярное
93
3.6. Синтаксический анализ для LR-грамматик
s2
T
T
E → T•
n
n
T → n•
E
s3
S → E•♯
E → E•−T
♯
T → (•E)
E →•E −T
E →•T
T →•n
T →•(E)
(
n
s4
−
E
s9
E → E−•T
T →•n
T →•(E)
s5
−
s7
T
T → (E•)
E → E•−T
)
s10
s8
S → E♯•
E → E − T•
(
T → (E)•
Рис. 3.18. ДКА, эквивалентный приведенному на рис. 3.16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
92
Гл. 3. Синтаксический анализ
2.2. Понятие токенов и лексем
3. Σ = N ∪ T .
выражение над символами Σ ∪ {d1 , d2 , . . . , di−1 }, т.е. символами исходного алфавита и уже определенными именами. Например, множество
идентификаторов может быть описано следующим образом:
4. Функция δ будет строиться по следующим правилам:
• Включаем состояние вида X → •X1 . . . Xn в δ(•X, ε) (связь
между состояниями первого и второго типов).
• Включаем состояние вида X → X1 . . . Xi Xi+1 •Xi+2 . . . Xn в
δ(X → X1 . . . Xi •Xi+1 Xi+2 . . . Xn , Xi+1 ) (связь между состояниями второго типа).
• Включаем состояние •Xi+1 в δ(X → X1 . . . Xi •Xi+1 . . . Xn , ε)
(связь между состояниями второго и первого типов).
5. Начальным состоянием объявляем состояние •S.
6. В множество F входят состояния вида X → X1 X2 . . . Xn •.
Для грамматики с рис. 3.15 такой автомат изображен на рис. 3.16.
Состояния первого типа мы изобразили прямоугольниками, а состояния второго типа изображены традиционно — эллипсами. Пусть нам
дана сентенциальная форма E − n − n♯. Если промоделировать работу
ε
•E
•S
ε
ε
S →•E♯
E
S → E•♯
♯
S → E♯•
•T
ε
ε
ε
ε
ε
ε
E →•E − T
E
E → E•−T
−
E → E−•T
T
E → E − T•
E →•T
T
E → T•
T →•n
ε
n
T → n•
33
T →•(E)
(
T → (•E)
E
T → (E•)
)
T → (E)•
Рис. 3.16. ε-НКА, распознающий основы для грамматики с рис. 3.15
letter
digit
id
→
→
→
[a-zA-Z]
[0-9]
letter(letter|digit)∗
2.2.2. Атрибуты токенов
Если шаблону соответствует некоторое множество лексем, то лексический анализатор обязан предоставить дополнительную информацию
о лексемах для последующих фаз компиляции. Например, шаблону,
задающему идентификаторы, могут соответствовать несколько различных идентификаторов и на дальнейших стадиях крайне важно знать
имя каждого конкретного идентификатора.
Таким образом, лексический анализатор должен не просто распознавать типы токенов, но еще и хранить о них дополнительную
информацию, связанные с ними атрибуты. Атрибуты токенов в меньшей степени рассматриваются на стадии синтаксического анализатора
и в большей степени на стадии трансляции. Обычно на практике
токены имеют один-единственный атрибут — указатель на запись в
таблице имен (про организацию таблиц имен см. п. 2.5), в которой
хранится информация о токене. Для различных целей (например, при
выводе ошибок) нам могут понадобиться как лексемы идентификаторов, так и их атрибуты (например, номера строк, где они встретились в исходном тексте). Так, если дана инструкция на языке C
return(a-2*b);
то список соответствующих ей пар <токен, указатель> может быть
записан как
<keyword, индекс элемента return в таблице ключевых слов>
<l_bracket>
<id, указатель на запись в таблице идентификаторов для a>
<minus_op>
<const, указатель на запись в таблице констант для 2>
<mult_op>
<id, указатель на запись в таблице идентификаторов для b>
<r_bracket> <semicolon>
Здесь keyword обозначает токен, определяющий ключевые слова, id
является токеном, соответствующим идентификаторам, а const — константам. Токены r_bracket и l_bracket задают открывающую и закры-
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
34
Гл. 2. Лексический анализ
3.6. Синтаксический анализ для LR-грамматик
вающую скобки соответственно. Арифметические операции сложения
и умножения определяются токенами minus_op и mult_op.
Формирование такого списка, который называется лексической
сверткой, — основная цель лексического анализатора. Именно его содержимое является исходными данными для проведения синтаксического анализа и трансляции.
2.3. Конечные автоматы
Конечный автомат представляет собой устройство, которое обладает
памятью, представленной в виде конечного множества состояний. В
любой момент времени автомат может находиться только в одном из
этих состояний. Назначением состояния является запоминание определенного момента в истории работы системы. Преимущества конечности
числа состояний заключается в том, что систему можно реализовать,
имея ограниченные ресурсы. Автомат воспринимает некоторую входную последовательность воздействий и переходит из одного состояния
в другое. Из множества состояний выделяют специальное подмножество заключительных (допускающих) состояний, попав в которые автомат может сделать вывод, что входная последовательность воздействий
является допустимой. На рис. 2.2 изображен конечный автомат, распознающий ключевое слово case языка C и который может служить
частью лексического анализатора. Здесь и далее начальное состояние
автомата указывается с помощью ведущей в него стрелки с надписью
Начало, а допускающее состояние будем обозначать двойным кружком.
Путь от начального состояния до допускающего иллюстрирует процесс
распознавания входной цепочки символов.
2.3.1. Детерминированные конечные автоматы
Введем теперь понятие конечного автомата формально. Начнем
наше рассмотрение с детерминированных конечных автоматов. Термин
≪детерминированный≫ говорит о том, что если рассмотреть любую
последовательность входных воздействий, то автомат будет всегда находиться в одном состоянии.
Начало
c
c
a
ca
s
cas
e
case
Рис. 2.2. Конечный автомат, моделирующий распознавание слова case
91
Рассмотрим теперь сам алгоритм LR-анализа (см. [21]), который
базируется на рассмотренных принципах и является эффективным
методом построения восходящих анализаторов. Этот алгоритм имеет
следующие преимущества:
• LR-анализаторы могут быть построены для распознавания практически всех конструкций языков программирования, описываемых КС-грамматиками.
• Метод LR-анализа является наиболее общим методом, в основе
которого лежит поиск и обрезка основ и который можно реализовать без возвратов.
• Метод обнаруживает ошибки сразу же, как только это становится
возможным, при чтении входной строки. При этом парсер останавливается и не производит никаких операций.
Однако парсеры, построенные с помощью этого метода, не являются широко распространенными из-за значительного объема подготовительной работы, которую требуется выполнить перед написанием
программы.
3.6.1. Анализатор для LR(0)-грамматик
Итак, основной задачей восходящего синтаксического анализатора
является эффективный поиск основы во входной строке. Для решения
этой задачи в LR-анализаторах используются конечные автоматы. Такой автомат по заданной сентенциальной форме осуществляет в ней
поиск основы и построить его можно с использованием следующего
алгоритма.
Алгоритм 24. Построение автомата для распознавания основ
Вход: КС-грамматика G = (N , T , P , S)
Выход: ε-НКА для распознавания основ A = (Q, Σ, δ, q0 , F )
1. Включаем в множество Q состояния, которые будут соответствовать нетерминальным символам грамматики. Пусть они будут
иметь вид •A, где A ∈ N . Далее для краткости будем их называть
состояниями первого типа.
2. Включим в множество Q состояния, соответствующие продукциям грамматики. Каждой продукции X → X1 X2 . . . Xn сопоставим
n + 1 состояние вида X → X1 . . . Xi •Xi+1 . . . Xn . Такие состояния
будем называть состояниями второго типа.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
90
Гл. 3. Синтаксический анализ
этой грамматики является то, что мы включили символ конца строки
≪♯≫ в определение грамматики. Попробуем свести цепочку n − (n − n)♯
к начальному символу:
n − (n − n)♯ → T − (n − n)♯ → E − (n − n)♯ →
→ E − (T − n)♯ → E − (E − n)♯ → E − (E − T )♯ →
→ E − (E)♯ → E − T ♯ → E♯ → S
При выполнении этого сведения мы сканируем входную цепочку
слева направо в поисках подстроки, соответствующей телу некоторой
продукции, а после нахождения заменяем эту подстроку нетерминалом
из головы продукции. Такая операция называется сверткой.
Теперь если мы посмотрим на процесс сведения в обратном
порядке и выпишем продукции, использовавшиеся при каждой
свертке, то мы получим правосторонний вывод входной цепочки:
S ⇒r E♯ ⇒r E − T ♯ ⇒r E − (E)♯ ⇒r E − (E − T )♯ ⇒r
⇒r E − (E − n)♯ ⇒r E − (T − n)♯ ⇒r E − (n − n)♯ ⇒r
⇒r T − (n − n)♯ ⇒r n − (n − n)♯
Назовем основой такую подстроку входной строки, которая совпадает с телом некоторой продукции грамматики, и ее свертка к голове
этой продукции представляет собой один шаг обращенного правостороннего вывода. Фактически алгоритм синтаксического анализа во
многом зависит от того, насколько эффективно мы находим основы
во входной строке. Более формально основу сентенциальной формы γ
можно определить как продукцию A → β и позицию подстроки β в
γ такую, что β может быть заменена на A для получения предыдущей сентенциальной формы в правостороннем выводе γ. То есть если
∗
S ⇒r αAω ⇒r αβω, то продукция A → β в позиции после подстроки α
представляет собой основу.
Сам метод построения обращенного правостороннего вывода называется обрезкой основ. Он заключается в следующем. Пусть имеется w = γn — входная строка из терминальных символов, которая является n-й сентенциальной формой при правостороннем выводе
S ⇒r γ1 ⇒r . . . ⇒r γn−1 ⇒r γn = w, который нам неизвестен. Однако
для его восстановления необходимо найти основу βn в γn и заменить
ее головой продукции An → βn для получения сентенциальной формы γn−1 . Затем повторяем процесс поиска и обрезки основы для γn−1 .
Действуем аналогичным образом до тех пор, пока сентенциальная
форма не будет состоять только из начального символа грамматики.
Заметим, что метод поиска основ нам пока неизвестен. Обращенная
последовательность продукций, использованная в свертках, и будет
являться правосторонним выводом.
2.3. Конечные автоматы
35
Определение 6. Детерминированный конечный автомат — это пятерка (Q, Σ, δ, q0 , F ), где
• Q является конечным множеством состояний;
• Σ — это конечное множество входных символов;
• δ : Q × Σ → Q представляет функцию переходов автомата;
• q0 — это начальное состояние автомата;
• F ⊆ Q — это множество финальных, или допускающих, состояний.
В дальнейшем детерминированный конечный автомат будет обозначаться как ДКА. Рассмотрим принцип, по которому ДКА решает,
допускать ли входную цепочку символов или нет. Пусть a1 , a2 , . . . , an —
это входная последовательность символов. ДКА начинает работу в
начальном состоянии q0 . После обработки первого символа a1 автомат
перейдет в состояние, определяемое функцией δ. Предположим, что
δ(q0 , a1 ) = qi . Для следующего входного символа a2 находим δ(qi , a2 ).
Пусть это будет состояние qj . Аналогично находятся и другие состояния. Допустим, что после прочтения последнего символа an автомат
перешел в состояние qn . В том случае, если qn ∈ F , то входная строка
допускается автоматом, в противном случае — ≪отвергается≫ как недопустимая.
2.3.2. Недетерминированные конечные автоматы
Другим вариантом конечного явтомата является недетерминированный конечный автомат, который далее будет обозначаться как НКА.
В отличие от детерминированного варианта, недетерминированные конечные автоматы могут находиться в нескольких состояниях одновременно. Эта особенность проявляется потому, что этот класс конечных
автоматов допускает переход из одного состояния в несколько других
по одному и тому же входному символу. Такое поведение автомата
можно мысленно представить как попытку ≪догадаться≫, в какое
состояние необходимо перейти, чтобы допустить входную строчку. Так,
если мы пытаемся найти определенные цепочки символов (например,
ключевые слова) в строчке большой длины, то в начале поиска полезно
≪догадаться≫, что мы находимся в начале одной из этих цепочек,
а затем использовать некоторую последовательность состояний для
простой проверки того, что символ за символом появляется данная
цепочка. Формально недетерминированный конечный автомат определяется следующим образом:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
36
Гл. 2. Лексический анализ
3.6. Синтаксический анализ для LR-грамматик
Определение 7. Недетерминированный конечный автомат — это
пятерка (Q, Σ, δ, q0 , F ), где
• Q является конечным множеством состояний;
• Σ — это конечное множество входных символов;
• δ : Q × Σ → 2Q представляет функцию переходов автомата;
• q0 — это начальное состояние автомата;
• F ⊆ Q — это множество финальных, или допускающих, состояний.
Единственное различие в определении ДКА и НКА состоит в типе
функции δ. В ДКА в качестве результата возвращается одиночное
состояние, а в НКА — множество состояний. Примером НКА может
служить автомат, изображенный на рис. 2.3. Этот автомат распознает
0, 1
Начало
q0
1
q1
0
q2
Рис. 2.3. НКА, допускающий цепочки, которые оканчиваются на 10
множество цепочек, состоящих из 0 и 1, которые оканчиваются на
10. Начальным является состояние q0 и автомат находится в этом
состоянии до тех пор, пока не ≪догадается≫, что на входе началась
замыкающая цепочка 10. Если очередной входной символ 1, то НКА
может сделать предположение, что это замыкающая последовательность, и перейти из состояния q0 в q1 . Однако символом 1 помечены две
дуги, выходящие из q0 , и фактически НКА переходит в оба состояния.
Заметим, что из состояния q1 не выходит дуги, помеченной символом
1, а состояние q2 вообще не имеет выходных дуг. Если на вход
подается какой-либо символ, когда автомат находится в состоянии q2 ,
то этот путь ≪умирает≫. В этом основное отличие от ДКА, который
имеет в каждом состоянии ровно одну выходящую дугу для каждого
выходного символа. На рис. 2.4 показано, как рассмотренный автомат
распознает цепочку 11010. Эта цепочка допускается, так как в процессе
чтения этой цепочки можно выбрать хотя бы одну последовательность
переходов в следующие состояния так, чтобы прийти из начального
состояния q0 в одно из допускающих. В нашем случае это состояние q2 .
Тот факт, что при распознавании некоторой цепочки мы можем выбрать
89
где A — это некоторый нетерминал грамматики:
[
∗
F OLLOWk (A) =
F IRSTk (x♯k ) для любого S ⇒ Ax
Теперь после того, как мы определили множества F IRSTk и
F OLLOWk , можно построить управляющую таблицу. Эта таблица
проиндексирована парой, состоящей из нетерминала и терминальной
строки длины k. Заполнение таблицы происходит следующим образом.
Каждую продукцию вида A → α мы помещаем в ячейку (A, w) для
каждой строки w ∈ F IRSTk (αF OLLOWk (A)). Если в результате
получается таблица, где в каждой ячейке располагается один элемент,
то говорят, что грамматика является сильно LL(k)-грамматикой. При
рассмотрении LL(1)-грамматик мы не разделяли их на подклассы, так
как классы сильно LL(1)-грамматик и LL(1)-грамматик совпадают. Однако это не верно для LL(k>1)-грамматик. Примером может служить
следующая LL(2)-грамматика:
→
→
S
A
aAaa | bAba
b|ε
На практике LL(k>1)-грамматики используются редко. Отчасти изза того, что увеличение значения k не влечет значительного повышения выразительной силы грамматик, а подобный эффект может быть
достигнут при помощи методов разрешения конфликтов. Другой причиной является большой размер управляющих таблиц, которые, однако,
могут быть записаны в более компактной форме при использовании
методов сжатия информации.
3.6. Синтаксический анализ для LR-грамматик
Рассмотренный в предыдущем разделе алгоритм для проведения
синтаксического анализа с использованием LL(1)-грамматик является
представителем нисходящих методов. В этом разделе мы представим
алгоритм, который может действовать в восходящем стиле, следовательно, дерево разбора будет строиться, начиная от листьев к корню.
Рассмотрим грамматику c рис. 3.15. Отличительной особенностью
S
E
E
T
T
→
→
→
→
→
E♯
E−T
T
n
(E)
Рис. 3.15. Грамматика для задания выражений с операцией вычитания
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
88
Гл. 3. Синтаксический анализ
Единственным существенным недостатком парсеров, действующих по
методу рекурсивного спуска, является зачастую больший размер программы, чем у анализаторов, построенных с использованием управляющей таблицы.
3.5.3. Разбор строк с использованием LL(k)-грамматик
При определении языка программирования возможно возникновение ситуации, когда выразительной силы LL(1)-грамматик недостаточно. Например, следующая конструкция не может быть определена с
помощью LL(1)-грамматики:
37
2.3. Конечные автоматы
q0
1
q0
q1
1
q0
0
q0
q1
×
1
q0
0
q0
q1
q2
q2
×
Рис. 2.4. Процесс распознавания цепочки 11010 автоматом с рис. 2.3
умирающую≫ последовательность переходов, не говорит о том, что
эта цепочка является недопустимой для НКА в целом.
≪
def → id | id(parameters) | id[indexes]
Очевидно, что в этом случае возникает конфликт, который может
быть разрешен динамически. Существует еще один способ увеличения
выразительной силы LL-грамматик. Так, можно заглядывать вперед не
на один символ, чтобы выбрать продукцию, а на k > 1 символов. Это
приводит нас к рассмотрению LL(k)-грамматик.
Пусть дана КС-грамматика G. Введем множество F IRSTk (x), где
x — сентенциальная форма, выводимая из G. Тогда F IRSTk (x) — это
множество терминальных строк w, таких что:
∗
• Если |w| < k, то x ⇒ w.
∗
• Если |w| = k, то x ⇒ wy, где y это некоторая сентенциальная
форма.
Теперь можно дать определение LL(k)-грамматики: грамматика является LL(k)-грамматикой, если для любой строки вида Ax♯k , где A
является нетерминальным символом с правыми частями α1 , . . . , αn ,
множества F IRSTk (α1 x♯k ), . . . , F IRST (αn x♯k ) попарно не пересекаются. Здесь ≪♯k ≫ представляют k символов конца строки ♯, которые
необходимы для того, чтобы можно было заглянуть на k символов
вперед при рассмотрении конца входной строки.
Можно заметить, что для любого k справедливо, что LL(k)-грамматики являются строгим подмножеством LL(k+1)-грамматик. Например,
следующая грамматика для любого k является LL(k+1)-грамматикой,
но не принадлежит классу LL(k):
S
→
ak b | ak a
Основной задачей при конструировании парсера для LL(k)-грамматики является построение управляющей таблицы. В случае LL(1)-грамматик эта задача решалась с помощью введения множества F OLLOW .
Поэтому для LL(k)-грамматики определим множество F OLLOWk (A),
2.3.3. Эквивалентность ДКА и НКА
Для многих языков построить соответствующий НКА гораздо легче, чем ДКА. Однако классы языков, распознаваемые детерминированными и недетерминированными автоматами, совпадают. Как правило,
ДКА, распознающий некоторый регулярный язык, имеет примерно
столько же состояний, что и соответствующий ему НКА, хотя часто содержит больше переходов. В худшем случае ДКА может содержать 2n
состояний, в то время как НКА для того же самого языка имеет
всего n состояний. Для преобразования НКА в эквивалентный ему
ДКА можно использовать следующий алгоритм.
Алгоритм 9. Построение ДКА, эквивалентного заданному НКА
Вход: НКА N = (QN , Σ, δN , q0 , FN )
Выход: ДКА D = (QD , Σ, δD , {q0 }, FD ), распознающий язык L(N )
Отметим, что алфавиты автоматов N и D совпадают. Состояниями автомата D будут являться подмножества состояний автомата
N . Начальное состояние автомата D есть множество, содержащее
только начальное состояние N . Остальные компоненты D строятся
следующим образом:
1. QD = 2QN , т.е. QD является множеством всех подмножеств
множества QN . Если QN содержит n состояний, то QD будет
содержать 2n состояний. Однако часто бывает, что не все состояния из множества QD бывают достижимы из начального
состояния автомата D. Такие недостижимые состояния можно
отбросить, поэтому фактически число состояний D может быть
меньше, чем 2n .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
38
Гл. 2. Лексический анализ
3.5. Алгоритм разбора для LL-грамматик
Элементы QD
0
1
∅
∅
∅
{q0 }
{q0 , q1 }
→ {q0 }
{q1 }
{q2 }
∅
∗
∅
∅
{q2 }
{q0 , q1 } {q0 , q2 } {q0 , q1 }
∗
{q0 }
{q0 , q1 }
{q0 , q2 }
∗
{q2 }
∅
{q1 , q2 }
∗
{q0 , q1 , q2 } {q0 , q2 } {q0 , q1 }
Рис. 2.5. Таблица переходов для автомата с рис. 2.3
2. FD = {S ∈ QD | S ∩ FN 6= ∅}. То есть FD содержит те
состояния автомата D, которые как множества содержат хотя бы
одно допускающее состояние автомата N .
3. Для каждого S ⊆ QN и входного символа a ∈ Σ
[
δD (S, a) =
δN (p, a)
p∈S
Для того чтобы найти, в какое состояние перейти из состояния S
по символу a в автомате D, необходимо рассмотреть все состояния автомата N , являющиеся элементами множества, задаваемого
состоянием S, и найти, в какие состояния мы можем перейти по
этому символу. А затем взять объединение найденных состояний.
Рассмотрим, как происходит процесс конструирования ДКА на
примере НКА с рис. 2.3. Исходный автомат содержит три состояния, следовательно, ДКА может состоять из 23 = 8 состояний. На
рис. 2.5 показана таблица переходов для для полученных состояний,
в которой символом ≪→≫ обозначено начальное состояние автомата,
а звездочками отмечены допускающие состояния. Полностью ДКА
приведен на рис. 2.6. Заметим, что он содержит всего три состояния,
однако переходов у него шесть против четырех у исходного НКА. Это
происходит потому, что ряд состояний ДКА не являются достижимыми
от начального состояния.
0
Начало
{q0 }
{q0 , q1 }
Тогда подпрограмма, реализующая распознавание нетерминала A, будет иметь следующую структуру.
procedure A :
begin
i f l o o k _ a h e a d ∈ F IRST (α1F OLLOW (A)) then
код для α1 . . .
e l s e i f l o o k _ a h e a d ∈ F IRST (α2F OLLOW (A)) then
код для α2 . . .
..
.
e l s e i f l o o k _ a h e a d ∈ F IRST (αn F OLLOW (A)) then
код для αn . . .
e l s e ERROR ;
end ;
Здесь переменная look_ahead содержит символ, который должен идти
следующим во входной строке. Код для правых частей αi представляет
собой последовательные вызовы подпрограмм, построенных для символов, из которых эти альтернативы состоят. Процедуры для остальных
нетерминалов строятся аналогично, а для всех терминалов существует
единственная процедура M atch, листинг которой приведен ниже.
procedure Match ( sym ) :
begin
i f l o o k _ a h e a d=sym then
l o o k _ a h e a d := nextsym ;
e l s e ERROR ;
end ;
Здесь nextsym производит считывание из входного потока очередного
терминала. Процедура ERROR выводит сообщение об ошибке и останавливает парсер.
Таким образом, на практике LL(1)-парсеры строятся с помощью метода рекурсивного спуска, хотя ничто не мешает использовать управляющую таблицу для создания программы. Использование рекурсивного
спуска имеет следующие существенные преимущества:
• Анализ семантики входной строки может быть легко внедрен в
код парсера.
1
1
87
0
{q0 , q2 }
1
0
Рис. 2.6. ДКА, построенный по НКА с рис. 2.3
• Парсеры, построенные по методу рекурсивного спуска, зачастую
являются более эффективными, чем построенные с использованием управляющей таблицы.
• Нетрудно динамически разрешать конфликты.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
86
Гл. 3. Синтаксический анализ
3. В том случае, если для некоторой продукции A → α справедливо,
что ε ∈ F IRST (α) и ♯ ∈ F OLLOW (A), то добавить эту продукцию к T (A, ♯).
Построение управляющей таблицы может быть выполнено для любой КС-грамматики. Однако существуют грамматики, например, леворекурсивные и неоднозначные, в некоторых ячейках управляющей
таблицы которых будет находиться более одной продукции (далее будем говорить о такой ситуации, что возник конфликт). Следовательно,
такая таблица не сможет подсказать однозначный выбор очередной
продукции. Мы же ограничимся такими грамматиками, для которых на
основе таблицы может быть сделан однозначный выбор, следовательно,
парсер будет действовать детерминированно. Грамматики, для которых
может быть построена такая таблица, называются LL(1)-грамматиками.
Можно сформулировать критерий для LL(1)-грамматики. Если дана
КС-грамматика G = (N , T , P , S), то она является LL(1)-грамматикой
тогда и только тогда, когда для любых двух продукций A → α и A →
→ β из P выполняются следующие условия:
1. F IRST (α) ∩ F IRST (β) = ∅.
2. Если ε ∈ F IRST (α), то F IRST (β) ∩ F OLLOW (A) = ∅.
Для леворекурсивных грамматик, а также грамматик, в которых
для одного и того же нетерминала существует несколько правых частей, начинающихся с одной и той же последовательности символов,
невозможно построить управляющую таблицу без конфликтов. Следовательно, их необходимо преобразовать к эквивалентным грамматикам,
но не обладающим этими свойствами. Это можно сделать, пользуясь
алгоритмами, изложенными в п. 1.3.6 и 1.3.7 соответственно. Однако
существуют КС-языки, для которых невозможно построить порождающую их LL(1)-грамматику. Для таких грамматик иногда используют
эвристический подход, примером которого может служить следующее
правило: ≪в случае конфликта в ячейку управляющей таблицы записывается только первая найденная продукция≫. Такой подход может
быть применен на стадии разработки парсера. Более гибкой стратегией
является динамическое разрешение конфликтов во время исполнения с
помощью эвристических методов.
Рассмотрим теперь принципы, по которым может быть создана
программа, реализующая синтаксический анализ для LL(1)-грамматик.
Пусть имеется нетерминал A, для которого есть несколько продукций:
A → α1 | . . . | αn
2.3. Конечные автоматы
39
2.3.4. Конечные автоматы с ε-переходами
Наличие ε-переходов, переходов по пустой цепочке, является обобщением понятия конечного автомата, которое, однако, не добавляет
этому формализму новых фундаментальных свойств, но позволяет несколько удобнее создавать автоматные модели. Еще одной причиной,
заставившей нас рассмотреть этот класс автоматов, является тесная
связь между НКА с ε-переходами и регулярными выражениями. Далее
такие автоматы будем называть ε-НКА.
ε-НКА можно представлять точно так же, как и НКА, с той лишь
разницей, что функция переходов должна содержать информацию о
переходах по символу ε, который обозначает пустую строку. Если задан
НКА A = (Q, Σ, δ, q0 , F ), то аргументами δ теперь являются состояние
из множества Q и элемента Σ ∪ {ε}, т.е. некоторый входной символ
либо ε.
При рассмотрении ε-НКА очень часто используется понятие ε-замыкания. Говоря нестрого, ε-замыкание некоторого состояния q — это
множество состояний, в которые мы можем попасть из q, используя
только ε-переходы. Формально ε-замыкание, ECLOSE, определяется
по индукции следующим образом.
1. ECLOSE(q) содержит состояние q.
2. Если p ∈ ECLOSE(q), то δ(p, ε) ∈ ECLOSE(q).
Это определение нам потребуется при описании алгоритма, строящего по произвольному ε-НКА эквивалентный ему ДКА. Этот алгоритм во многом похож на алгоритм построения ДКА, эквивалентного
НКА.
Алгоритм 10. Построение ДКА, эквивалентного заданному ε-НКА
Вход: ε-НКА E = (QE , Σ, δE , qE , FE )
Выход: ДКА D = (QD , Σ, δD , qD , FD ), распознающий язык L(E) \ {ε}
1. QD = {S ⊆ QE | S = ECLOSE(S)}. Для D допустимыми
состояниями являются те множества состояний S автомата E,
которые являются ε-замкнутыми, т.е. каждый ε-переход из состояния, принадлежащего S, приводит нас снова в состояние из S.
2. qD = ECLOSE(qE );
3. FD = {S ∈ QD | S ∩ FE 6= ∅}, т.е. FD содержит такие множества
состояний, которые содержат хотя бы одно допускающее состояние автомата E.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
40
Гл. 2. Лексический анализ
3.5. Алгоритм разбора для LL-грамматик
4. Определим функцию переходов δD (S, a) для всех a ∈ Σ и состояний S ∈ QD :
(a) пусть S = {p1 , . . . , pk };
Sk
Пусть это
(b) вычислим
i=1 δ(pi , a).
{r1 , r2 , . . . , rm };
Sm
(c) тогда δD (S, a) = j=1 ECLOSE(rj ).
будет
множество
2.3.5. Минимизация конечных автоматов
При разработке трансляторов значительное внимание уделяется эффективности их работы. Одним из способов повышения эффективности
является минимизирование ДКА, который производит распознавание
токенов. Под минимальным ДКА будем понимать такой ДКА, который
распознает тот же самый язык, что и исходный, но обладает наименьшим возможным числом состояний.
Алгоритм 11. Минимизация числа состояний ДКА
Вход: ДКА D = (QD , Σ, δD , qD , FD )
Выход: ДКА M = (QM , Σ, δM , qM , FM ), распознающий язык L(D) и
имеющий наименьшее возможное количество состояний
1. Построить начальное разбиение Π для множества состояний автомата D: заключительные состояния FD и незаключительные
состояния QD \ FD ;
2. Применить следующую процедуру для построения нового разбиения Πnew :
(a) Для каждой группы состояний G ∈ Π проделать следующие
операции.
(b) Разделить группу G на подгруппы таким образом, что два
состояния s и t находятся в одной подгруппе, когда для всех
входных символов a состояния s и t имеют переходы по a в
состояния одной и той же группы в Π.
(c) Заменить элемент G ∈ Π множеством созданных подгрупп.
3. Если Πnew = Π, то Πf inal = Π, и перейти к шагу 4. В противном
случае повторить шаг 2 с Π = Πnew .
4. Выбрать одно состояние в каждой группе разбиения Πf inal в
качестве представителя этой группы. Представители образуют
множество состояний автомата M — QM .
85
2. Последовательно включить в F IRST (α) множества F IRST (Ai ),
за исключением символа ε, для которых ε ∈ F IRST (Ak ), для
каждого k < i.
3. Включить в F IRST (α) символ ε, если ε ∈ F IRST (Ai ) для
любого i.
Множество F IRST может включать любой терминальный символ
грамматики либо символ пустой строки, ε. Конструкция множества
F OLLOW отличается тем, что его элементом не может быть ε, однако
возможно включение символа конца строки ≪♯≫. Рассмотрим алгоритм
построения множества F OLLOW для нетерминалов КС-грамматик.
Алгоритм 22. Вычисление множеств F OLLOW для нетерминальных символов грамматики
Вход: КС-грамматика G = (N , T , P , S)
Выход: Множество F OLLOW (X) для каждого X ∈ N
1. Установить F OLLOW (X) = ∅ для каждого X ∈ N .
2. Положить F OLLOW (S) = {♯}.
3. Для каждой продукции A → αBβ, где α, β ∈ (N ∪ T )∗ , все элементы F IRST (β), за исключением ε, добавляем к F OLLOW (B).
4. Пока возможно добавление элемента хотя бы в одно множество
F OLLOW (X), выполнять следующее. Если A → αBβ и α, β ∈
∈ (N ∪ T )∗ , где F IRST (β) содержит ε, то все элементы из
F OLLOW (A) добавить к F OLLOW (B).
Построим теперь управляющую таблицу для LL(1)-анализатора, в
основе которой лежат множества F IRST и F OLLOW .
Алгоритм 23. Построение управляющей таблицы предсказывающего анализатора
Вход: КС-грамматика G = (N , T , P , S)
Выход: Таблица T (A, a), где A ∈ N , a ∈ T ∪ {♯}
1. Добавить в ячейку T (A, a) продукцию A → α для каждого
символа a ∈ F IRST (α).
2. Если ε ∈ F IRST (α), добавить A → α к T (A, b) для каждого
терминала b ∈ F OLLOW (A).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
84
Гл. 3. Синтаксический анализ
требуется знать один терминальный символ для принятия решения о
выборе очередной продукции.
В основе парсера лежит управляющая таблица, которая строится
при участии специальных множеств F IRST и F OLLOW . Пусть да∗
на грамматика G = (N , T , P , S) и S ⇒ α. Тогда F IRST (α) будет
определять множество терминальных символов, с которых начинаются
∗
строки, выводимые из α. В том случае, если α ⇒ ε, то ε также
включается в F IRST (α). Множество F OLLOW (A), где A ∈ N , задает
множество всех терминальных символов грамматики, которые могут
непосредственно следовать за нетерминалом A в некоторой сентенциальной форме, выводимой из начального символа грамматики. То есть
∗
это множество терминалов a таких, что существует вывод S ⇒ αAaβ,
∗
где α, β ∈ (N ∪ T ) .
Алгоритм 20. Вычисление множеств F IRST для всех нетерминалов
КС-грамматики
Вход: КС-грамматика G = (N , T , P , S)
Выход: Множество F IRST (X) для каждого символа X ∈ (N ∪ T )
1. Если X является терминалом, то F IRST (X) = {X}, иначе
полагаем, что F IRST (X) = ∅.
2. В том случае, если в грамматике присутствует продукция X → ε,
то помещаем в множество F IRST (X) символ ε.
3. Пока возможно добавлять новые элементы хотя бы к одному
множеству F IRST (X), выполнять следующие действия. Если в
грамматике существует продукция вида X → Y1 Y2 . . . Yk , причем
∗
ε ∈ F IRST (Yi ) для всех 1 6 i 6 m, т.е. Y1 Y2 . . . Ym ⇒ ε, тогда
добавить в F IRST (X) все элементы множеств F IRST (Yi ), а
также F IRST (Ym+1 ).
Алгоритм 21. Вычисление множества F IRST для произвольной
сентенциальной формы
Вход: КС-грамматика G = (N , T , P , S) и выводимая из этой грамматики сентенциальная форма α = A1 A2 . . . An , где Ai ∈ (N ∪ T )
Выход: Множество F IRST (α)
1. При помощи алгоритма 20 вычислить множества F IRST для
каждого символа грамматики G и присвоить F IRST (α) = ∅.
2.3. Конечные автоматы
41
5. Определим теперь множество переходов автомата M . Пусть s ∈
∈ QM и δD (s, a) = t и r является представителем группы, куда
входит t. Тогда δM (s, a) = r.
6. Стартовым состоянием автомата M будет то состояние, которое
является представителем группы, куда входит состояние qD .
7. Заключительными состояниями FD будут состояния, являющиеся
представителями групп, куда входят состояния из FD .
8. Если автомат M имеет недостижимые или тупиковые состояния,
удалим их.
2.3.6. От регулярных грамматик к НКА
При порождении строк с использованием регулярной грамматики
необходимо знать только один факт: какой нетерминал будет следующим. Проиллюстрируем эту и другие концепции на примере простой
грамматики (рис. 2.7), которая порождает строки, начинающиеся с
символа a, за которым идут произвольное количество чередующихся
символов b или c и заканчивающиеся на a.
Построим устройство, которое назовем распознавателем, отвечающее на вопрос, принадлежит ли заданная строка языку, определяемому
нашей грамматикой или нет. Можно заметить, что любая сентенциальная форма, порожденная из начального символа регулярной грамматики может содержать только один нетерминальный символ, остальные
символы будут терминалами. Поэтому состояние, в котором находится
вывод, можно задать с помощью этого единственного нетерминального
символа. Кроме состояний необходимо указать правила, по которым
будет работать этот распознаватель. Допустим, мы находимся в состоянии, помеченном нетерминалом A, и выбираем правило A → bC. Тогда
мы распознаем символ b и переходим в состояние C. В том случае,
если выбирается правило без нетерминала в конце, например, C → a,
тогда мы переходим в заключительное состояние, которое означает,
S
S
A
A
B
B
C
→
→
→
→
→
→
→
aA
aB
bB
bC
cA
cC
a
Рис. 2.7. Пример простой регулярной грамматики
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
42
Гл. 2. Лексический анализ
3.5. Алгоритм разбора для LL-грамматик
что строка распознана. На рис. 2.8 представлена диаграмма переходов
этого распознавателя.
a
b
A
c
b
S
C
F
c
B
a
a
Рис. 2.8. Распознаватель для грамматики с рис. 2.7
Алгоритм 12. Построение НКА по регулярной грамматике
Вход: регулярная грамматика G = (N , T , P , S)
Выход: НКА A = (Q, Σ, δ, q0 , qf ), распознающий язык L(G)
a ∈ T,
Регулярные грамматики могут быть описаны с ошибками, например,
в грамматике могут присутствовать неопределенные, непорождающие
или недостижимые нетерминалы. Так, мы получим систему переходов,
показанную на рис. 2.9, если расширим исходную грамматику с помощью следующих продукций:
→
→
→
→
→
cD
cE
eE
fA
h
неопределенный нетерминал D
непорождающий нетерминал E
недостижимый нетерминал G
f
a
a
D
c
b
C
B
c
h
b
A
S
G
c
c
→
→
aB
b | aBb
Рис. 3.13. Грамматика для порождения строк, где за символами a располагается
такое же количество символов b
2. Для каждой продукции вида A → aB, где A, B ∈ N , a ∈ T ,
включаем B в подмножество состояний, возвращаемое δ(A, a).
B
B
E
G
G
3.5.1. Выбор продукции с помощью таблиц
Рассмотрим класс простых грамматик, у которых тело каждой
продукции начинается с терминального символа. В этом случае легко
сократить трудоемкость выбора очередной продукции, так как шаг выбора следует непосредственно за шагом сравнения очередного символа
входной строки и того, с которого начинается правая часть продукции. Если они совпадают для некоторой правой части, то выбирается
именно она. Так, если мы рассмотрим грамматику, изображенную на
рис. 3.13, то для нее мы можем построить таблицу (см. рис. 3.14), в
S
B
1. Σ = T , Q = N ∪ {qf }, q0 = S.
3. Для каждой продукции вида A → a, где A ∈ N ,
включаем qf в δ(A, a).
83
a
F
e
E
Рис. 2.9. Система переходов для грамматики с ошибками
Чтобы убрать из грамматики эти ошибки, может использоваться
алгоритм, который предложен в п. 1.3.1 для КС-грамматик.
которой столбцы поименованы терминальными символами грамматики,
строки — нетерминальными, а в каждой ячейке находится некоторое
подмножество продукций исходной грамматики. Такую таблицу далее будем называть управляющей и обозначать через T (A, a) ячейку
таблицы, находящуюся на пересечении строки, помеченной нетерминалом A, и столбца, помеченного терминалом a. Эта таблица задает
зависимость между терминальным символом, который обозревается на
входе, нетерминалом, входящим в очередную сентенциальную форму,
и продукцией, которую необходимо выбрать на очередном шаге. Когда
управляющая таблица построена, парсер может принимать решения,
основываясь исключительно на ней, грамматика как таковая не является больше необходимой. В общем случае каждая ячейка таблицы
может содержать более одной продукции. Это происходит, например,
в том случае, когда для некоторого нетерминала имеется несколько
продукций с телами, начинающимися с одного и того же терминального
символа.
S
B
a
S1 → aB
B2 → aBb
b
♯
B1 → b
Рис. 3.14. Управляющая таблица для грамматики с рис. 3.13
3.5.2. Построение разбора для LL(1)-грамматик
Такие грамматики, как представленная на рис. 3.13, называют
LL(1)-грамматиками. Этот класс грамматик допускает построение
парсера, считывающего строку слева направо (Left to right), строящего
левостронний (Leftmost) вывод этой строки, причем этому парсеру
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
82
Гл. 3. Синтаксический анализ
43
2.3. Конечные автоматы
2.3.7. От регулярных выражений к НКА
Часто токены описывают при помощи аппарата регулярных выражений. Перевод регулярного выражения в НКА выполняется с использованием следующего алгоритма.
>aabc
Вывод:
S -> AB
A -> aA
A -> a
B -> bc
>abbc
>abc
Вывод:
S -> DC
D -> ab
C -> c
Вывод:
S -> AB
A -> a
B -> bc
Алгоритм 13. Построение ε-НКА по регулярному выражению
Вход: регулярное выражение r над алфавитом Σ
Выход: ε-НКА A = (Q, Σ, δ, q0 , qf ), распознающий язык L(r)
1. Для ε строим следующий НКА:
Начало
i
ε
f
2. Для a ∈ Σ строим НКА:
Начало
i
a
f
Рис. 3.12. Пример работы парсера для грамматики с рис. 3.9
3.5. Алгоритм разбора для LL-грамматик
В разделе 3.3 мы рассматривали две переборные стратегии поиска
вывода входной строки: поиск в ширину и в глубину. Однако из-за
того, что на каждом шаге магазинный автомат может иметь несколько
возможностей перехода и необходимости последовательно рассмотреть
их все, эти стратегии не являются эффективными. В этом разделе мы
остановимся на рассмотрении детерминированных парсеров, которые
на каждом шаге имеют одну-единственную возможность. Детерминированные парсеры имеют несколько существенных преимуществ:
они быстрее, в качестве результата возвращают единственное дерево
разбора, которое создается ≪на лету≫ при чтении входной строки,
следовательно, они работают прямо. Однако такие парсеры могут быть
разработаны для более узкого класса грамматик.
Основной проблемой при построении очередного шага вывода является выбор тела продукции для замещаемого нетерминала. Для
одного нетерминала может быть несколько продукций, следовательно,
несколько различных правых частей. Нам необходимо предложить
условие, которое поможет однозначно выбрать такую продукцию и
приведет нас к построению вывода, а в том случае, если это построение
вывода потерпит неудачу, то корректной трактовкой такой ситуации
является то, что входная строка не принадлежит языку, порождаемому
грамматикой.
3. Пусть N (s) и N (r) — это НКА, построенные для выражений s
и r. Причем si и ri являются начальными состояниями этих
автоматов, а финальные обозначены как sf и rf соответственно.
(a) Для регулярного выражения s | r строим следующий составной автомат:
ε
Начало
si
S
sf
ε
f
i
ε
ri
R
rf
ε
(b) Для регулярного выражения sr строим составной автомат:
Начало
si
S
sf
ε
ri
R
rf
(c) Для регулярного выражения s∗ строим следующий автомат:
ε
Начало
i
ε
si
S
sf
ε
f
ε
(d) Для регулярного выражения (s) в качестве НКА используем
автомат N (s).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
44
Гл. 2. Лексический анализ
3.4. Метод рекурсивного спуска
Построение НКА происходит по индукции. Первые два шага задают
базис индукции и показывают, как можно выполнить построение для
элементарных регулярных выражений. Третий шаг обеспечивает индуктивный переход и демонстрирует, как создаются автоматы для выражений, построенных с помощью регулярных операций. Построение
НКА в случае использования дополнительных регулярных операций,
таких как ≪? ≫, ≪+ ≫ и других, может быть осуществлено с помощью
рассмотренных операций и соответствующих им построений.
В том случае, если язык программирования не допускает определение одних процедур внутри других либо не позволяется передавать
процедуру в качестве параметра, можно использовать следующий трюк.
Объявляется массив указателей на функции, моделирующий стек вызовов этих функций:
typedef void (*pf)(void);
pf fstack[MAXSIZE];
/* Стек указателей на функции */
int fp;
/* Указатель на вершину стека*/
Функции, моделирующие распознавание терминального символа, изменяются так:
2.4. Алгоритмы распознавания токенов
2.4.1. Распознавание лексем с помощью НКА
Итак, теперь мы можем конструировать НКА для каждого из токенов и наша задача сводится к написанию программы, которая бы
производила эмуляцию работы этого автомата. Это можно сделать с
использованием следующего алгоритма.
Алгоритм 14. Моделирование работы НКА
Вход: НКА A = (Q, Σ, δ, q0 , F ) и входная строка α
Выход: Ответ ≪да≫, если автомат A допускает α, и
противном случае
81
≪
нет≫ в
Приведем работу алгоритма в виде кода на псевдоязыке:
S:=ECLOSE( {q0 } ) ;
a := n e x t c h a r ;
while a6= e o f do
begin
S:=ECLOSE( δ(S, a) ) ;
a := n e x t c h a r ;
end ;
i f S ∩ F 6= ∅ then
r e t u r n " да "
e l s e r e t u r n " нет " ;
Здесь функция nextchar используется для чтения очередного символа
входной строки α. Логическое условие a 6= eof проверяет, достигли
ли мы конца этой строки. Функции ECLOSE и δ здесь используются
несколько нетрадиционным образом. Если раньше мы определяли их
для отдельных состояний, то здесь они применяются поэлементно к
подмножеству состояний автомата и возвращают также подмножество
состояний.
static void a() {
if (buffer[tp] == ’a’) {
pf r;
tp++; r=fstack[fp--]; (*r)(); fstack[++fp]=r; --tp; }}
То есть вместо вызова функции tail, управление передается функции с
вершины стека. Когда она отработает, то снова помещается на вершину
стека. Моделирование распознавания нетерминального символа отличается отсутствием определения дополнительных процедур. Функции,
соответствующие символам из тела продукции, помещаются в стек в
обратном порядке:
static void B() /* распознавание B */
{
pushrule("B −> bc"); fstack[++fp]=&c; b();
fp--; poprule();
pushrule("B −> bBc"); fstack[++fp]=&c; fstack[++fp]=&B;
b();fp--; fp--; poprule(); }
То есть мы помещаем функции, соответствующие символам из тела
продукции, в стек f stack и передаем управление функции, моделирующей распознавание первого символа тела продукции. Последнее, что
требует изменений, это функция parser, которая модифицируется так:
static void parser(void) {
tp = plp = fp = 0; fstack[fp]=&endmark; S(); }
Пример работы парсера для грамматики с рис. 3.9, построенного
согласно любой из приведенных конструкций — с использованием локальных процедур либо с применением стека, показан на рис. 3.12.
Таким образом метод рекурсивного спуска имеет значительную
практическую ценность. Однако он не применим при использовании
леворекурсивных грамматик и грамматик с циклами, так как в этом
случае парсер может попасть в бесконечный цикл.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
80
Гл. 3. Синтаксический анализ
static void a(void (*tail)(void))
/* Распознать a */
{ if (buffer[tp] == ’a’) { tp++; tail(); --tp; } }
static void b(void (*tail)(void))
/* Распознать b */
{ if (buffer[tp] == ’b’) { tp++; tail(); --tp; } }
static void c(void (*tail)(void))
/* Распознать c */
{ if (buffer[tp] == ’c’) { tp++; tail(); --tp; } }
static void A(void (*tail)(void)) {
/* Распознать A */
pushrule("A −> a"); a(tail); poprule();
void A_t(void) { A(tail); }
pushrule("A −> aA"); a(A_t); poprule();
}
static void B(void (*tail)(void)) {
/* Распознать B */
void c_t(void) { c(tail); }
pushrule("B −> bc"); b(c_t); poprule();
void Bc_t(void) { B(c_t); }
pushrule("B −> bBc"); b(Bc_t); poprule();
}
static void D(void (*tail)(void)) {
/* Распознать D */
void b_t(void) { b(tail); }
pushrule("D −> ab"); a(b_t); poprule();
void Db_t(void) { D(b_t); }
pushrule("D −> aDb"); a(Db_t); poprule();
}
static void C(void (*tail)(void)) {
/* Распознать C */
pushrule("C −> c"); c(tail); poprule();
void C_t(void) { C(tail); }
pushrule("C −> cC"); c(C_t); poprule();
}
static void S(void (*tail)(void)) {
/* Распознать S */
void C_t(void) { C(tail); }
pushrule("S −> DC"); D(C_t); poprule();
void B_t(void) { B(tail); }
pushrule("S −> AB"); A(B_t); poprule();
}
/* Проверка на конец входной строки и печать вывода */
static void endmark(void)
{ if (buffer[tp] == ’#’) parsing_found(); }
static void parser(void) { tp = plp = 0; S(endmark); }
int main(void) { while ( getline()) parser(); return 0; }
Рис. 3.11. Код парсера для неоднозначной грамматики с рис. 3.9
45
2.4. Алгоритмы распознавания токенов
2.4.2. Распознавание лексем с помощью ДКА
До сих пор мы рассматривали в качестве распознавателя для регулярных грамматик и языка регулярных выражений недетерминированные конечные автоматы. Однако любой НКА может быть преобразован
в эквивалентный ему ДКА. Рассмотрим алгоритм, который позволяет
моделировать работу ДКА.
Алгоритм 15. Моделирование работы ДКА
Вход: ДКА A = (Q, Σ, δ, q0 , F ) и входная строка α
Выход: Ответ ≪да≫, если автомат A допускает α, и
противном случае
≪
нет≫ в
Приведем работу алгоритма в виде кода на псевдоязыке:
s :=q0 ;
a := n e x t c h a r ;
while a 6= e o f do
begin
s :=δ(s, a) ;
a := n e x t c h a r ;
end ;
i f s ∈ F then
r e t u r n " да "
e l s e r e t u r n " нет " ;
Функция nextchar имеет тот же самый смысл, что и в алгоритме 14.
Условие a 6= eof аналогичным образом проверяет, закончилась строка
α или нет. Определение функции δ берется непосредственно из определения автомата.
2.4.3. Скорость работы
Рассмотрим эффективность работы двух приведенных алгоритмов
распознавания лексем. Пусть множество лексем задается с помощью
регулярного выражения regexp и на вход подается строка x. Первый подход состоит в применении алгоритма 14, который использует
недетерминированные конечные автоматы. НКА N , распознающий то
же множество строк, что и регулярное выражение regexp, может
быть построен с использованием алгоритма 13 за время O(|regexp|),
где |regexp| — длина выражения regexp. Автомат N имеет количество
состояний, не более чем в 2 раза превосходящее |regexp|, и не более
двух переходов для каждого состояния. В результате под таблицу
переходов необходимо отвести памяти не более чем O(|regexp|). Затем
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
46
Гл. 2. Лексический анализ
с помощью алгоритма 14 можно определить, допускает ли N строку x.
Это делается за время O(|regexp| × |x|).
Другой подход подразумевает использование ДКА для распознавания токенов. В этом случае необходимо для заданного регулярного выражения либо регулярной грамматики сначала построить НКА,
который после этого преобразуется в ДКА и минимизируется. Полученный минимальный ДКА позволяет производить распознавание
токенов очень быстро, на это требуется порядка O(|x|) времени, где
x — это входная строка. Однако, как уже было замечено, ДКА может
содержать число состояний, экспоненциально большее, чем изначальный НКА, т.е. порядка O(2|regexp| ). Следовательно, объем памяти,
который требуется для хранения в памяти состояний и переходов ДКА
может быть значительным. Тем не менее часто используют именно
детерминированные автоматы, так как очень редко в практических
задачах ДКА содержит экспоненциально большее число состояний, чем
НКА. Другим практическим соображением может служить тот факт,
что преобразование НКА в ДКА нужно совершить один раз, а потом
многократно использовать при работе транслятора.
2.4.4. Распознавание токенов
Каждый токен представляет собой шаблон, которому соответствует
некоторое множество строк. В языках программирования примерами
таких шаблонов могут служить шаблон для идентификаторов, констант
или ключевых слов. Как мы уже рассматривали, этот шаблон может
задаваться с помощью регулярной грамматики (возможно расширенной) или аппарата регулярных выражений. В любом из этих случаев,
с помощью рассмотренных алгоритмов строится автомат (ДКА или
НКА) для распознавания каждого из токенов.
Пусть в языке программирования определено множество токенов
p1 , . . . , pn . Построим НКА для распознавания шаблона p1 | p2 | . . . | pn ,
который задает любую допустимую в этом языке лексему. Это делается
путем создания НКА для каждого из шаблонов pi и объединения
построенных автоматов в один с использованием идей, представленных
в алгоритме 13, как показано на рис. 2.10.
Необходимо отметить, что могут существовать два шаблона pi и pj ,
для которых L(pi ) ∩ L(pj ) 6= ∅. Например, если первый шаблон задает
множество ключевых слов, а второй — множество идентификаторов.
Очевидно, что в случае распознавания строки, принадлежащей множеству ключевых слов, алгоритм должен выдать, что она имеет именно
этот тип и не является идентификатором. Чтобы это реализовать, упорядочим множество шаблонов таким образом, что при распознавании
3.4. Метод рекурсивного спуска
79
Отметим несколько особенностей реализации метода рекурсивного спуска с точки зрения современных языков программирования.
Служебные процедуры, которые определяются внутри тех, которые
соответствуют отдельным нетерминалам, должны быть локальными.
Другое требование, которое должно удовлетворяться, — необходимо
иметь возможность передавать процедуры в качестве параметров. Таким требованиям удовлетворяют компиляторы функциональных языков
программирования и компилятор GNU C. Часть программы для неоднозначной грамматики с рис. 3.9, в которой подключаются стандартные
библиотеки и происходит объявление служебных функций, представлена на рис. 3.10. Код парсера для этой грамматики можно увидеть на
рис. 3.11.
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
char buffer[MAXSIZE];
/* Входная строка */
int length;
/* Длина входной строки */
int tp;
/* Указатель на текущий символ */
static int getline(void) {
int ch;
printf(">"); length = 0;
while ((ch = getchar()), ch >= 0 && ch != ’\n’) {
buffer[length++] = ch;
}
buffer[length] = ’#’; return ch == ’\n’;
}
/* Массив для записи вывода входной строки */
const char *parse_list[MAXSIZE];
/* Указатель на последнее правило */
int plp;
static void pushrule (const char *s)
{ parse_list[plp++] = s; }
static void poprule(void) { --plp; }
static void parsing_found(void) {
int i;
printf("Вывод:\n");
for (i = 0; i < plp; i++)
printf("%s\n", parse_list[i]);
}
Рис. 3.10. Служебный код парсера для неоднозначной грамматики с рис. 3.9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
78
Гл. 3. Синтаксический анализ
Здесь происходит объявление дополнительной локальной процедуры Ytail , которая моделирует распознавание остатка входной
строки после того, как ее начало будет распознано процедурой,
соответствующей символу X.
• Если продукция имеет вид A → X1 X2 . . . Xk , то ей будет соответствовать такая процедура:
procedure A( t a i l ) :
begin
procedure Xntail : begin Xn ( t a i l ) end ;
...
procedure X3 Xntail : begin X3 (X4 Xntail ) end ;
procedure X2 Xntail : begin X2 (X3 Xntail ) end ;
X( X2 Xntail ) ;
end ;
Здесь построение похоже на предыдущий случай. Действительно,
мы рассматриваем продукцию A → X1 X2 . . . Xn в виде A → XY ,
где X = X1 , а Y = X2 . . . Xn . Далее переходим к построению локальных процедур для Y → X2 . . . Xn , где действуем по аналогии.
• В том случае, если нетерминал A имеет k альтернатив, процедура
для A содержит последовательно k сегментов кода, по одному для
каждой альтернативы, которые построены согласно рассмотренным правилам.
Для распознавания маркера конца строки создается специальная
процедура:
procedure end_marker :
begin
i f ( конец_строки ) then
write ( " Вывод завершен ! " ) ;
end ;
end ;
Если S — начальный символ грамматики, а S() является процедурой
для этого символа, то вызов парсера будет осуществляться так:
S ( end_marker ) ;
Можно заметить, что функция tail выполняет роль стека, в который
помещаются процедуры, соответствующие нетерминалам грамматики.
Причем на дне этого стека находится процедура, предназначенная для
проверки того, что входная строка закончилась.
47
2.5. Формирование таблиц имен
s1
N (p1 )
f1
s2
N (p2 )
f2
ε
ε
Начало
...
s0
ε
sn
N (pn )
fn
Рис. 2.10. Объединенный НКА для распознавания токенов
строки несколькими шаблонами будем считать, что она принадлежит
шаблону с наименьшим номером. Далее предполагается, что множество
p1 , . . . , pn уже упорядочено таким образом.
В основе работы алгоритма распознавания токенов лежит модификация алгоритма 14, которая гарантирует, что автомат распознает
самый длинный префикс из входного потока, соответствующего шаблону. В полученном НКА существует заключительное состояние для
каждого шаблона pi . При моделировании работы НКА с помощью
алгоритма 14 создается последовательность множеств состояний, в
котором мог бы находиться объединенный конечный автомат после
считывания очередного символа из входного потока. В том случае, если
на очередном шаге это множество состояний содержит допускающее
состояние, для поиска наиболее длинного префикса необходимо продолжать моделирование работы НКА, пока не будет достигнуто множество состояний, из которого нет переходов для очередного символа.
Далее выбирается допускающее состояние, соответствующее шаблону
с наименьшим индексом, и полагается, что был распознан именно этот
токен.
2.5. Формирование таблиц имен
Одним из важных компонентов компилятора является диспетчер
таблиц имен. Этот компонент позволяет помещать и осущствлять
эффективный поиск встретившихся в исходной программе идентификаторов, констант и других типов лексем. В процессе работы компилятора
происходит интенсивное использование таблиц имен. Так, на стадии
лексического анализа в таблицу идентификаторов добавляются распознанные идентификаторы. На следующих стадиях записи о найденных
идентификаторах могут обновляться, например, с помощью добавления
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
48
Гл. 2. Лексический анализ
информации о типе идентификатора. Эта информация потом используется на стадии семантического анализа.
При работе с таблицами имен используются две функции:
• insert(name), которая добавляет имя name в таблицу имен и
возвращает индекс записи либо −1 в случае ошибок (например,
если таблица имен заполнена);
• lookup(name), которая возвращает индекс имени name в таблице имен либо −1, если имя не найдено в таблице имен.
Механизм работы с таблицей имен должен обеспечивать эффективный поиск и добавление новых элементов. При работе с таблицей
имен полезно иметь возможность ее динамического роста в процессе
работы компилятора. В случае фиксированного размера таблица имен
должна быть достаточно большой, чтобы компилятор мог обработать
практически любой исходный текст.
Неупорядоченная таблица. При таком подходе новое найденное
имя помещается в конец таблицы, поиск имени осуществляется полным перебором. Трудоемкость функции insert равна единице, так
как добавление имени осущствляется за одно действие. Поиск имени осуществляется в среднем за n/2 действий, или O(n), где n —
количество элементов в таблице. Этот подход позволяет представлять
таблицы в виде связного списка, таким образом, размер таблицы может
увеличиваться динамически в процессе работы компилятора.
Упорядоченная таблица. В этом случае можно осуществлять
эффективный поиск по таблице имен с помощью метода бинарного
поиска. Трудоемкость этого метода составляет O(log2 n). Однако добавление новых элементов не должно нарушать упорядоченности таблицы. В худшем случае после добавления имени таблицу необходимо
сортировать, а это требует O(n log2 n) операций.
Использование хеш-функций. В этом случае таблица имен представляется в виде массива фиксированного размера N . Для того чтобы
узнать, есть ли имя name в таблице, мы вычисляем хеш-функцию h
от строки name, возвращающую целое число от 0 до N − 1. Если имя
name есть в таблице, то оно находится в ячейке с индексом h(name).
Если эта ячейка пустая, то имени нет в таблице, и оно может быть
занесено в эту ячейку. По сути трудоемкость поиска и добавления
имени в таблицу становится константой. При создании хеш-функции
особое внимание должно быть уделено тому, чтобы она была достаточно быстрой, а также по возможности равномерно распределяла имена
по таблице.
3.4. Метод рекурсивного спуска
77
символов. Переменная tp является также глобальной и указывает на
очередной считываемый символ из этой строки.
Самым простым случаем является распознавание терминального
символа. Процедура, которая моделирует проверку очередного входного
символа некоторому терминальному символу a, абстрактно может быть
записана так:
procedure a ( t a i l ) :
begin
i f b u f f e r [ t p ]= ’ a ’ then
begin
t p := t p + 1 ;
tail ();
t p := t p − 1 ;
end ;
end ;
В том случае, если терминальный символ a совпадает с очередным
входным символом, мы перемещаем указатель tp на одну позицию
дальше и вызываем процедуру tail, с помощью которой производится
попытка распознать остаток входной строки. Необходимо заметить, что
процедура tail передается в качестве аргумента.
Для нетерминального символа, допустим A, процедура строится
сложнее:
• Если для нетерминала в грамматике содержится единственная
продукция A → ε, то ему соответствует процедура, которая
ничего не считывает, а просто передает управление дальше:
procedure A( t a i l ) : begin t a i l ( ) ; end ;
• Если для нетерминала существует единственная цепная продукция A → X, то ему соответствует процедура, которая вызывает
дальше по цепочке процедуру для X:
procedure A( t a i l ) : begin X( t a i l ) ; end ;
• В том случае, если продукция имеет вид A → XY , производится
следующее построение процедуры:
procedure A( t a i l ) :
begin
procedure Ytail : begin Y( t a i l ) end ;
X( Ytail ) ;
end ;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
76
Гл. 3. Синтаксический анализ
алгоритм остановится после распознавания первого символа c. В то же
время aabc выводится следующим образом:
S → AB → aAB → aaB → aabc
Анализ предложенного метода показывает, что в процессе разбора
цепочки aabc мы никогда не попробуем альтернативу A → aA, так
как успешно распознали первый символ с использованием продукции
A → a. Подобная трудность возникает, когда существует несколько
тел продукций, каждая из которых успешно распознает один и тот же
префикс входной цепочки. Таким образом, метод действует излишне
оптимистично, полагая, что если с помощью некоторой продукции
распознался префикс входной строки, то эта продукция обязательно
должна присутствовать в выводе. Алгоритм не позволяет нам вернуться
назад и попробовать альтернативную продукцию, которая распознает
тот же самый префикс входной цепочки. Эта проблема является особенно серьезной для грамматик с ε-продукциями, так как они всегда
могут быть успешно применены для распознавания пустого префикса.
Еще одно свойство предложенного алгоритма состоит в том, что он
останавливается, когда найден первый вывод строки, а в случае неоднозначных грамматик таких выводов может быть несколько и возможно
потребуется построить их все, чтобы позднее осуществить выбор более
корректного вывода с точки зрения семантики.
Поэтому критерием правильности выбора очередной продукции является не способность с помощью нее распознать префикс входной
цепочки, а возможность успешного распознавания строки в целом.
При этом даже если мы получили вывод строки, должно оставаться
возможным продолжать поиск альтернативных выводов.
3.4.2. Исчерпывающий рекурсивный спуск с возвратами
Итак, одним из основных выводов, следующих из предыдущих
рассуждений, является необходимость аккуратно выбирать очередную
продукцию. Продукция может быть принята в том и только том случае,
если ее использование ведет к построению вывода входной строки.
Рассмотрим принципы, по которым могут быть сконструированы
элементы программ, реализующих стратегию рекурсивного спуска. Основной принцип прост — каждому символу грамматики сопоставляется
подпрограмма, которая может вызывать другие подпрограммы, соответствующие остальным символам. Далее мы будем использовать термин
≪процедура≫ как синоним подпрограммы.
Допустим, что входная строка хранится в переменной buf f er, которая является глобальной переменной и представляет собой массив
2.5. Формирование таблиц имен
49
Перечислим примеры составления хеш-функций для некоторого
произвольного имени name, состоящего из последовательности символов c1 , c2 , . . . , cn :
1. Сложим коды символов c1 , c2 , . . . , cn , полученную сумму поделим
на N и возьмем остаток от деления. Взятие остатка лучше
работает в случае простого N .
2. Несколько лучший результат дает умножение старого значения h
на константу α перед прибавлением следующего символа. Таким
образом, h0 = 0, hi = αhi−1 + ci , h = hn mod n, где n — длина
строки. Простое сложение чисел представляет собой частный
случай α = 1. Вместо операции сложения можно использовать
другие операции, например, операцию ≪исключающего или≫,
ci xor αhi−1 .
3. Неплохие результаты показывает метод разбиения на части.
Предположим, что размер таблицы имен N = 2k . Тогда можно рассматривать имя name как последовательность k-битовых
чисел, к которым можно, например, последовательно применить
операцию ≪исключающего или≫.
Тем не менее возможна ситуация, когда для двух различных имен,
допустим, a и b, значения хеш-функций совпадают, т.е. h(a) = h(b). В
том случае, если одно из них (например, a) уже записано в таблицу,
возникает ситуация, называемая коллизией. Очевидно, что если в
таблице имен есть свободное место, то должен быть предложен детерминированный алгоритм, с помощью которого будет найдено место
для записи имени b.
Для разрешения коллизий был предложен метод рехеширования.
Этот метод заключается в том, что хеш-функция дополняется рядом проб h0 , h1 , h2 , . . . , hm , где h0 — это начальная хеш-функция, а
h1 , h2 , . . . , hm — это функции, которые предназначены для разрешения
коллизий. Очевидны следующие свойства, которыми должны обладать
пробы и исходная хеш-функция:
• m < N , где N — это размер таблицы имен. Другими словами,
количество проб не превышает размер таблицы имен;
• для любых i 6= j справедливо,что hi (a) 6= hj (a), т.е. одна и та же
ячейка не проверяется дважды.
Приведем теперь алгоритм, использующий оригинальную хешфункцию и фиксированный набор проб:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
50
Гл. 2. Лексический анализ
Алгоритм 16. Алгоритм рехеширования
Вход: Исходная хеш-функция h0 , набор проб h1 , h2 , . . . , hm , таблица
имен T и имя α
Выход: индекс имени в таблице либо сообщение об ошибке
1. i = 0.
2. Если T [hi (α)] является пустой ячейкой, то T [hi (α)] = α, и алгоритм завершает работу с возвратом hi (α) в качестве результата.
3. Если T [hi (α)] = α, то имя найдено, и алгоритм завершает работу
с возвратом hi (α) в качестве результата.
4. Если i < m, то i = i + 1, и переходим к шагу 2, иначе возвращаем
−1 как сообщение об ошибке.
Очевидно, что этот алгоритм может использоваться для реализации
функции insert и с небольшой модификацией для реализации функции lookup (в этом случае, во-первых, не надо записывать искомое
имя в талицу имен, а, во-вторых, если очередная проба вернула ссылку
на пустую ячейку, то можно сразу выдавать сообщение о том, что имя
не найдено).
Рассмотрим теперь, каким образом можно построить набор функций
для использования в качестве проб.
1. Линейное рехеширование. Пробы строятся с помощью формулы
hi (α) = (h0 (α) + i) mod N . В случае коллизии выбирается непосредственно следующая за проверяемой ячейка. После проверки
последней ячейки таблицы, просмотр продолжается с первой.
2. Случайное рехеширование. Построение проб происходит по формуле hi (α) = (h0 (α) + ri ) mod N , где ri — это элемент псевдослучайной последовательности (см. подробнее [8]), которая может
быть сгенерирована следующим образом. Введем переменную R,
которая перед началом генерации последовательности принимает
значение 1. Остальные числа генерируются согласно следующего
алгоритма:
(a) R = 5 × R.
(b) R = R mod 4N .
(c) выдать в качестве значения целую часть от R/4.
75
3.4. Метод рекурсивного спуска
Подстрока на входе полностью соответствует телу продукции, следовательно, по окончании распознавания можно выйти из подпрограммы, соответствующей D, и передать управление подпрограмме,
созданной для нетерминала C:
Активный вызов
1: S•♯
2: S → DC•| AB
4: C →•c | cC
Входная цепочка
•abc♯
ab•c♯
ab•c♯
1:
2:
3:
4:
Вывод
S
S → DC
D → ab
C→c
Терминал c из тела продукции C → c соответствует очередному
терминалу входной цепочки, и мы последовательно выходим из подпрограмм, соответствующих нетерминалам C и S:
Активный вызов
1: S•♯
Входная цепочка
abc•♯
1:
2:
3:
4:
Вывод
S
S → DC
D → ab
C→c
Сравнение символов ≪♯≫ происходит успешно, и столбец Вывод
позволяет построить левосторонний вывод входной цепочки:
S → DC → abC → abc
Такой способ поиска вывода исходной цепочки называется рекурсивным спуском. Фактически происходит ≪спуск≫ от начального
нетерминала грамматики к терминальным символам, т.е. реализуется стратегия нисходящего разбора. Рекурсия выражается в том, что
каждый нетерминал задается в виде подпрограммы, которая может
напрямую либо через другие подпрограммы вызывать саму себя. В том
случае, если работа по распознаванию очередного терминала зашла в
тупик, осуществляется возврат и производится попытка попробовать
следующую альтернативу для нетерминала.
Несмотря на внешнюю простоту этого подхода, выраженную в
том, что мы используем грамматику в качестве прототипа программы,
описанный метод работает не всегда. Очевидно, что он не работает
для грамматик с левой рекурсией. Действительно, в этом случае подпрограмма будет вызывать саму себя бесконечно. Рассмотрим другой
тонкий момент, который нужно учитывать при реализации этого метода. Так, в рамках описанного выше алгоритма невозможно построить
вывод цепочки aabc и abcc, хотя очевидно, что они выводимые. Построение вывода для aabc ≪застрянет≫ после первого символа a, а для abcc
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
74
Гл. 3. Синтаксический анализ
2.5. Формирование таблиц имен
Эта структура данных разделена на три части. В первом столбце
записывается подпрограмма, которая используется при выводе входной
цепочки. Нетерминальные и терминальные символы слева от ≪•≫ являются уже проанализированными, а те, которые расположены справа,
еще нет. Второй столбец содержит входную цепочку, которая по аналогии с первым разделяется маркером ≪•≫ на две части — прочитанную
часть цепочки и ту, которую еще предстоит прочитать. В третьем
столбце последовательно записываются все шаги, из которых состоит
вывод входной цепочки. Таблица может содержать несколько строк,
последняя строка будет обозначать подпрограмму, которая выполняется
в настоящий момент времени.
Рассмотрим неоднозначную грамматику, которая порождает язык
am bn cn ∪ ap bp cq , приведенную на рис. 3.9, и продемонстрируем, как
метод рекурсивного спуска может использоваться для выведения цепочки abc. Метод начинает работу с уже ранее показанной структуры
данных. В этом состоянии существует одна возможность продолжения
вычислений — вызвать подпрограмму для нетерминала S, тогда получим:
Активный вызов
1: S•♯
2: S →•DC | AB
Входная цепочка
•abc♯
•abc♯
Вывод
1: S
2: S → DC
Необходимо отметить, что мы продвинули указатель в первой строке для подпрограммы S. Это означает, что, когда мы выйдем из подпрограммы во второй строке, необходимо будет продолжить выполнение с
отмеченного места. Далее мы пытаемся применить первую продукцию
S → DC и рассматриваем первую альтернативу для D:
Активный вызов
1: S•♯
2: S → D•C | AB
3: D →•ab | aDb
Входная цепочка
•abc♯
•abc♯
•abc♯
Вывод
1: S
2: S → DC
3: D → ab
В настоящий момент выполняется подпрограмма, которая изображена в третьей строке таблицы. Она успешно последовательно сравнивает
терминалы a и b, составляющие тело продукции D → ab с первыми
двумя символами входной цепочки. Получаем:
1:
2:
3:
Активный вызов
S•♯
S → D•C | AB
D → ab•| aDb
Входная цепочка
•abc♯
•abc♯
ab•c♯
1:
2:
3:
Вывод
S
S → DC
D → ab
51
3. Рехеширование сложением. Для вычисления значений проб можно использовать следующие хеш-функции:
hi (α) = [i(h0 (α) + 1)] mod N либо
hi (α) = [h0 (α) + ai2 + bi] mod N , a, b — подходящие константы
Существует более простой вариант поиска и помещения элементов
в таблицу имен, который называется открытое хеширование. Структура данных, применяемая в этом подходе, состоит из двух частей —
хеш-таблицы и блоков. Хеш-таблица представляет собой массив фиксированного размера. Элементами этого массива являются указатели
на отдельные блоки, которые представляют собой связные списки.
Схема структуры данных для открытого рехеширования представлена
на рис. 2.11.
Поиск элемента a при использовании открытого хеширования заключается в вычислении значения хеш-функции h(a) и поиске с помощью перебора имени a в блоке с индексом h(a). Добавить новый
элемент a можно, поместив его в голову списка с индексом h(a).
Массив заголовков
0
1
...
5
...
200
Рис. 2.11. Структура данных, используемая в методе открытого хеширования
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
73
3.4. Метод рекурсивного спуска
будет работать исключительно для выбранной грамматики, однако
будет более эффективно выполнять дополнительные действия, такие
как построение таблицы имен.
Глава 3
СИНТАКСИЧЕСКИЙ АНАЛИЗ
В этой главе рассматриваются алгоритмы, с помощью которых
строятся синтаксические анализаторы, или парсеры. Основной задачей парсера является построение дерева разбора для входной строки.
Это позволяет убедиться в том, что эта строка принадлежит языку,
задаваемому с помощью грамматики. Одновременно с этим решается
задача выявления синтаксической структуры строки, которая помогает
понять ее семантику и использовать на этапе трансляции.
3.1. Обзор методов разбора КС-грамматик
В настоящее время известно много методов для проведения синтаксического анализа. Однако бывает трудно понять их взаимосвязь и
выделить общие черты, которые им присущи. Практически все методы
используют КС-грамматики как средство для задания синтаксиса языка программирования, для которого необходимо построить транслятор.
Этому есть несколько причин:
1. Анализ строк при использовании КС-грамматик строит для них
дерево разбора, с помощью которого возможно легко оперировать
с семантикой конструкций заданного языка программирования.
2. КС-грамматики позволяют описать значительное множество языков, которые можно разобрать автоматически и которые используются на практике.
3. Существуют достаточно эффективные алгоритмы построения деревьев разбора для этого класса грамматик.
Существуют две основные стратегии построения дерева разбора —
стратегия нисходящего разбора, когда дерево строится начиная с начального символа грамматики, и стратегия восходящего разбора, когда
дерево строится сведением исходной строки к начальному символу.
Парсеры могут использовать различные стратегии считывания символов входной строки. Говорят, что парсер работает прямо, если алгоритм синтаксического разбора, лежащий в его основе, считывает
3.4.1. Общие принципы
В первом приближении каждую продукцию исходной грамматики
можно рассматривать как подпрограмму для распознавания нетерминального символа, находящегося в голове этой продукции. Например,
правило S → aB | bA можно представить как подпрограмму для
распознавания нетерминала S:
S распознано успешно если
прочитано a и B распознано успешно
или
прочитано b и A распознано успешно
Попробуем определить данные, которые необходимы для работы подобной программы. Конечно же, необходимо хранить входную строку,
которая будет являться глобальной переменной. Мы должны отмечать,
на какой стадии рассмотрения тела продукции мы находимся. Если
рассматривается продукция S → aB, необходимо знать, был ли проанализирован терминальный символ a и можно ли уже переходить к
нетерминалу B. Так как мы реализуем продукции в виде подпрограмм,
этот указатель обычно моделируется средой исполнения, которая имеет
представление о том, какую инструкцию языка программирования надо
выполнить следующей. Также необходимо знать позицию рассматриваемого символа во входной строке. Если указатель в теле текущей
продукции указывает на терминальный символ, который совпадает с
очередным символом во входной строке, то оба счетчика необходимо
увеличить на единицу. Это моделирует переход к анализу следующего
символа тела текущей продукции и чтение символа из входного потока
данных. Также необходимо помнить значение указателя на текущий
символ входной строки при старте распознавания нетерминального
символа. Действительно, необходимо запомнить позицию указателя на
текущий символ входной строки перед началом распознавания продукции S → aB, так как в случае неуспеха необходимо вернуться
обратно для того, чтобы попытаться построить вывод с использованием
следующей альтернативы, которой является продукция S → bA.
Все перечисленные параметры можно задать с помощью структуры
данных, представленной в виде следующей таблицы:
Активный вызов
1:
•S♯
Входная цепочка
•abc♯
Вывод
1: S
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
72
Гл. 3. Синтаксический анализ
3.2. Универсальные методы синтаксического анализа
Когда последним символом в левой части таблицы стал нетерминал, переходим к шагу 5.
5. Если последним символом слева таблицы является нетерминал
Ak и таблица конфигураций имеет следующий вид:
a1 a2 . . . a i
τ Ak
ai+1 . . . an ♯
βk γ♯
то нам необходимо попробовать следующий по порядку переход
МП-автомата — (q, ai+1 . . . an , Aγ) ⊢ (q, ai+1 . . . an , βk+1 γ). Таким
образом, получится следующее преобразование таблицы конфигураций:
a1 a2 . . . ai
τ Ak
ai+1 . . . an ♯
βk γ♯
−→
a1 a2 . . . a i
τ Ak+1
ai+1 . . . an ♯
βk+1 γ♯
После этого перейти к шагу 2. Если k + 1-го варианта перехода
для МП-автомата не существует, то нетерминал переходит из
левой части таблицы в правую:
a1 a2 . . . ai
τ Ak
ai+1 . . . an ♯
βk γ♯
−→
a1 a2 . . . a i
τ
ai+1 . . . an ♯
Ak γ♯
Если при этом τ = ε, то все возможные варианты вывода были
рассмотрены, однако вывод был не найден, следовательно, можно
остановить алгоритм с возвратом ошибки. В противном случае
переходим к шагу 4.
Алгоритм останавливается в случае нахождения некоторого вывода
исходной строки. Если мы хотим построить все возможные выводы,
то после успешного сравнения символов ♯ в правой части таблицы
необходимо продолжить работу, моделируя возврат. В конце концов
мы переберем все возможные переходы автомата и остановимся тогда,
когда левая часть таблицы будет пустой.
3.4. Метод рекурсивного спуска
Если мы хотим построить парсер для заданной контекстно-свободной грамматики, то можно применить два подхода. Во-первых, можно
построить программу на основе ранее рассмотренных алгоритмов, таких как метод Ангера и метод Кока—Янгера—Касами, либо одного
из рассмотренных способов эмуляции МП-автоматов. В этом случае
грамматика и цепочка будут являться входными данными этой программы. Во-вторых, остается возможность написать парсер, который
53
входную строку по порядку, символ за символом, и одновременно
строит дерево вывода. Преимущество прямых методов состоит в том,
что синтаксический анализ может стартовать до того, как считан последний символ входной строки, и работать параллельно с лексическим
анализатором. Обычно прямые методы, явно или неявно, моделируют
работу некоторого распознавателя. Непрямо работающий парсер считывает символы не по порядку. В этом случае входная строка (вся
или некоторая ее часть) должна находиться в памяти, следовательно,
лексический анализатор должен закончить работу до запуска парсера.
Обычно непрямые парсеры используют некоторую структуру данных,
где хранится информация о грамматической структуре входной строки.
Эта структура данных потом используется для построения дерева
разбора.
Итогом работы любого парсера, прямого или непрямого, реализующего стратегии восходящего либо нисходящего разбора, является
представление входной строки в виде одного или нескольких деревьев
разбора.
3.2. Универсальные методы синтаксического анализа
В этом разделе рассматриваются методы синтаксического анализа,
применимые к широкому классу КС-грамматик. Однако наряду с универсальностью они имеют недостатки, прежде всего выражающиеся в
относительно низкой скорости работы. Яркими представителями этого
класса алгоритмов являются метод Ангера, реализующий стратегию
нисходящего разбора, и метод Кока—Янгера—Касами, который действует согласно восходящей стратегии.
3.2.1. Метод Ангера для грамматик без циклов и ε-продукций
Метод Ангера [29] является представителем класса синтаксических
анализаторов, которые работают непрямо. Вывод некоторой входной цепочки α = t1 t2 . . . tk строится от начального символа грамматики, пусть
это будет символ S, т.е. этот метод реализует стратегию нисходящего
разбора. Справедливо утверждение, что вывод входной строки, если он
существует, должен начинаться одной из S-продукций, пусть это будет
продукция S → A1 A2 . . . Am . Это в свою очередь означает, что несколько первых символов строки α должны выводиться из A1 , следующая
порция символов из A2 и так далее. Это наглядно продемонстрировано
на рис. 3.1, где каждая порция символов представляется подстрокой
ai . Таким образом, проблема построения вывода входной строки из
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
54
Гл. 3. Синтаксический анализ
S
A1
...
Ai
...
Am
a1
...
aj
...
ak
Рис. 3.1. Дерево разбора для строки α = a1 a2 . . . ak
нетерминала S сводится к решению m задач, по количеству символов
в теле продукции для S: о выводимости первых нескольких символов
из A1 , некоторого количества следующих символов из A2 и так далее.
Решение этих задач сопровождается поиском подходящего разбиения
входной строки.
Входными параметрами для метода Ангера являются контекстносвободная грамматика и входная строка. Ограничимся сначала рассмотрением грамматик без циклов и ε-продукций на примере грамматики, изображенной на рис. 3.2 и входной строки (i + i) × i. Начальная
задача построения вывода может быть представлена как
S
(i + i) × i
Для тела каждой S-продукции мы должны построить все возможные разбиения выводимой цепочки. Построение всех возможных
разбиений можно решить с помощью рекурсивного алгоритма. Так,
если дана продукция S → A1 A2 . . . Am , т.е. существует m классов
разбиения, и цепочка α = t1 t2 . . . tk , то будем действовать с использованием следующего алгоритма:
1. Если m = 1, то помещаем все символы строки α в этот единственный класс разбиения и завершаем работу.
2. Помещаем символ t1 в 1-й класс разбиения и рекурсивно строим
все разбиения строки t2 t3 . . . tk для m − 1 класса. После этого помещаем два символа, t1 и t2 , в 1-й класс разбиения и рекурсивно
строим все разбиения строки t3 t4 . . . tk на m−1 класс и так далее.
S
T
F
→
→
→
S+T |T
T ×F |F
(S) | i
Рис. 3.2. Пример грамматики, описывающей арифметические операции с операндом i.
3.3. Синтаксический анализ с использованием магазинных автоматов 71
Моделирование работы МП-автомата с использованием стратегии
поиска в глубину имеет следующий недостаток: для хранения таблицы конфигураций может потребоваться значительный объем памяти.
Поэтому можно использовать стратегию поиска в глубину, которая не
обладает таким недостатком.
Алгоритм 19. Моделирование работы МП-автомата с использованием стратегии поиска в глубину
Вход: МП-автомат M = (Q, Σ, Γ, δ, q0 , Z0 , F ), а также входная
строка α = a1 a2 . . . an
Выход: вывод строки α из начального символа грамматики G
1. Началом работы алгоритма является таблица, которая соответствует начальной конфигурации МП-автомата (q, α, S):
a1 a2 . . . a n ♯
S♯
2. До тех пор пока правая часть строки таблицы конфигураций
начинается с нетерминала, скажем A, то выбираем первый
по порядку переход МП-автомата из текущей конфигурации
(q, ai+1 . . . an , Aγ) ⊢ (q, ai+1 . . . an , β1 γ):
a 1 a 2 . . . ai
τ
ai+1 . . . an ♯
Aγ♯
−→
a 1 a 2 . . . ai
τ A1
ai+1 . . . an ♯
β1 γ♯
3. В противном случае, если правая часть строки таблицы конфигураций начинается с терминала, то производим его сравнение с
текущим нетерминалом на входе. Если они совпадают, то перекидываем его из правой части таблицы в левую:
a 1 a 2 . . . ai
τ
ai+1 . . . an ♯
ai+1 γ♯
−→
a1 a2 . . . ai ai+1
τ ai+1
ai+2 . . . an ♯
γ♯
Если в результате в правой части остаются только символы ≪♯≫,
то алгоритм успешно завершается, иначе переходим к шагу 2. В
противном случае, если нетерминалы не совпадают, переходим к
шагу 4, который моделирует возврат.
4. До тех пор пока последним символом в левой части таблицы
является терминал, производится возврат по терминалу:
a 1 a 2 . . . ai
τ ai
ai+1 . . . an ♯
γ♯
−→
a1 a2 . . . ai−1
τ
a i . . . an ♯
ai γ♯
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
70
Гл. 3. Синтаксический анализ
С первого взгляда может показаться, что приведенный алгоритм
работает для всех КС-грамматик. Действительно, для произвольной
КС-грамматики можно построить МП-автомат, который будет по пустому магазину распознавать в точности тот же самый язык, что задает
грамматика. Алгоритм же просто перебирает все возможные варианты
срабатывания этого автомата. Однако можно привести простой пример
грамматики, для которой не будет работать этот алгоритм. Такая
грамматика имеет одно-единственное правило:
S → Sa | a
Действительно, для такой грамматики алгоритм зациклится на
шаге 2, причем количество строк в таблице будет постоянно расти.
Если обобщить это наблюдение, то алгоритм попадет в бесконечный цикл, когда существует последовательность A → . . . → Aα, где
каждая промежуточная сентенциальная форма начинается с нетерминала. Напомним, что нетерминал, который порождает сентенциальную
форму, начинающуюся с него же, называется леворекурсивным. Левая
рекурсия может выражаться непосредственно с помощью некоторой
продукции грамматики, например, S → Sb. Другим примером может
служить левая рекурсия, возникающая ≪транзитом≫ через одно или
несколько правил грамматики: S → Ab, A → Sa. Более того, левая рекурсия может быть скрыта с помощью ε-порождающих нетерминалов.
Например, в следующей грамматике нетерминалы S, B и C являются
леворекурсивными:
S
B
B
C
A
→
→
→
→
→
ABa
Cc
ABb
Sc
ε
Тем не менее для произвольной грамматики, не имеющей циклов
и ε-продукций, можно предложить модификацию алгоритма, которая
позволит строить вывод даже для грамматик с левой рекурсией. Так,
если правая часть некоторой строки содержит количество символов,
большее, чем оставшаяся часть входа, то такую строку можно удалить.
Действительно, в этом случае вывод построить невозможно, так как
каждый нетерминальный символ порождает по крайней мере один
терминал. Однако при использовании этого приема необходимо знать
длину входной строки перед началом работы алгоритма, следовательно,
метод работает непрямо.
Другим подходом является преобразование леворекурсивной грамматики к эквивалентной, но уже без леворекурсивных нетерминалов.
Это можно сделать с помощью алгоритма 7, приведенного в п. 1.3.6.
3.2. Универсальные методы синтаксического анализа
55
3. В том случае, если количество классов больше, чем количество
символов строки, то разбиение невозможно построить, так как
наличие пустого класса разбиения означало бы что из соответствующего символа выводится пустая строка.
Первой для S является продукция S → S + T , что дает нам 15
возможных разбиений исходной строки, показанных на рис. 3.3. Мы не
S
S
+
T
(
i
+i) × i
(
i+
i) × i
(
i+i
)×i
(
i + i)
×i
(
i + i)× i
(i
+
i) × i
(i
+i
)×i
(i
+i)
×i
(i
+i)×
i
(i+
i
)×i
(i+
i)
×i
(i+
i)×
i
(i + i
)
×i
(i + i
)×
i
(i + i) ×
i
Рис. 3.3. Все разбиения для продукции S → S + T .
будем рассматривать все получившиеся разбиения, несмотря на то что
неоптимизированный вариант алгоритма требует этого. Исключим из
рассмотрения те варианты, которые заведомо не приведут к успеху —
такими вариантами являются все, где терминалу ≪+≫ из правой части
продукции соответствуют отличные от него символы. Таким образом,
единственным кандидатом для дальнейшего рассмотрения является
разбиение
S
S
(i
+
+
T
i) × i
Итак, исходная задача разделяется на подзадачи, первая из которых
состоит в том, чтобы убедиться в возможности, а если это так, то и
построить, порождение нетерминалом S подстроки (i. Первая альтернатива, S → S + T , которой мы пользовались до этого, не подходит,
так как подстрока (i состоит из двух символов и, следовательно,
ее невозможно разбить на три непустых части. Значит, необходимо
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
56
Гл. 3. Синтаксический анализ
выбрать следующую продукцию для S, которой является S → T ,
и убедиться в том, что помощью нее выводится данная подстрока.
Аналогично рассуждая, следующей продукцией, которую мы можем
использовать, является T → F , и процесс вывода рассматриваемой
подстроки может быть записан как
S
T
F
(i
2. Каждую строку таблицы, правая часть которой начинается с
нетерминального символа
a 1 a 2 . . . ai
...
τ
...
ai+1 . . . an ♯
...
Aγ♯
...
a 1 a 2 . . . ai
...
τ A1
...
τ Ak
...
ai+1 . . . an ♯
...
β1 γ♯
...
βk γ♯
...
заменяем на k строк:
Однако вывести подстроку (i из нетерминала F невозможно, следовательно, исходное разбиение не подходило с самого начала и
необходимо рассмотреть следующее по порядку. Другие разбиения,
показанные на рис. 3.3, были также отвергнуты. Таким образом, можно
сделать заключение, что продукция S → S + T не является начальной
для вывода входной строки (i + i) × i.
Значит, нам необходимо рассмотреть следующую продукцию для
нетерминала S. Это продукция S → T . Она имеет в правой части
только один символ, следовательно, мы имеем единственное разбиение
входной строки:
S
T
(i + i) × i
Первая альтернатива для нетерминала T , продукция T → T × F ,
порождает 15 различных разбиений, из которых только одно может
привести нас к успеху:
S
T
T
(i + i)
3.3. Синтаксический анализ с использованием магазинных автоматов 69
×
×
F
i
Продолжая поиск в соответствии с описанными принципами, мы придем к следующему выводу исходной строки в данной грамматике (этот вывод будет единственным):
S → T → T × F → F × F → (E) × F →
→ (E + T ) × F → (T + T ) × F → (F + T ) × F → (i + T ) × F →
→ (i + F ) × F → (i + i) × F → (i + i) × i
Рассмотренный пример демонстрирует несколько отличительных
черт метода Ангера: даже небольшие примеры требуют значительного
объема вычислений, однако даже простые проверки могут существенно
оптимизировать алгоритм. Так, сопоставление терминалов, принадле-
где каждой новой строке соответствует один и только один переход МП-автомата (q, ai+1 . . . an , γ) ⊢ (q, ai+1 . . . an , βi γ), а k — это
число вариантов перехода.
3. Выполняем шаг 2 до тех пор, пока существует хоть одна строка
таблицы, правая часть которой начинается с нетерминала, в
противном случае переходим к шагу 4.
4. Удаляем те строки из таблицы, у которых первый символ в правой
части не совпадает с очередным входным символом.
5. В том случае, если таблица пуста, а оставшаяся часть входа
нет, тогда строка α не принадлежит языку, распознаваемому
автоматом M . Алгоритм останавливается.
6. Перемещаем символ ai+1 из правого столбца в левый:
a 1 a 2 . . . ai
...
τ
...
ai+1 . . . an ♯
...
ai+1 γ♯
...
−→
a1 a2 . . . ai ai+1
...
τ ai+1
...
ai+2 . . . an ♯
...
γ♯
...
7. Если оставшаяся часть входа пуста, то алгоритм завершает свою
работу. Иначе переходим к шагу 2.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
68
Гл. 3. Синтаксический анализ
Пусть для каждого нетерминала A пронумеровано множество продукций, т.е. если A → β1 | β2 | . . . βk , то через Ai обозначим
продукцию A → βi . Текущий вывод — это строка символов, которая
формируется по индукции:
1. Если МП-автомат, соответствующий грамматике G, находится в
начальной конфигурации (q, α, S), то текущий вывод — это пустая
строка.
2. Если текущий вывод представлен в виде некоторой строки τ ,
тогда:
(a) Если автомат осуществляет переход вида
(q, ak . . . an , Aγ) ⊢ (q, ak . . . an , βi γ),
т.е. моделируется использование продукции A → βi , то
текущий вывод — это строка τ Ai .
(b) Если автомат осуществляет переход вида
(q, ak . . . an , ak γ) ⊢ (q, ak+1 . . . an , γ),
т.е. моделируется сравнение нетерминального символа на
вершине стека с очередным символом входной строки, то
текущий вывод — это строка τ ak .
Текущий вывод будет нами использоваться для восстановления вывода
строки α после того, как будет найдена допускающая конфигурация
автомата. При описании алгоритма будем также полагать, что входная
строка ограничена справа символом ≪♯≫, указывающим на ее конец.
На практике таким символом можно считать символ окончания файла.
Алгоритм 18. Моделирование работы МП-автомата с использованием стратегии поиска в ширину
Вход: МП-автомат M = (Q, Σ, Γ, δ, q0 , Z0 , F ), а также входная
строка α = a1 a2 . . . an
Выход: вывод строки α из начального символа грамматики G
1. Алгоритм начинает работу с таблицы, которая соответствует начальной конфигурации МП-автомата (q, α, S):
a1 a2 . . . a n ♯
S♯
3.2. Универсальные методы синтаксического анализа
S
L
D
→
→
→
57
LSD | ε
ε
d
Рис. 3.4. Грамматика, порождающая строки из символов d.
жащих телу рассматриваемой продукции, с текущим разбиением помогает отбросить разбиения, которые заведомо не приведут к успеху.
Ангер в [29] рассматривает несколько таких критериев. Например,
можно рассчитать минимальную длину выводимой из каждого нетерминала строки. Тогда все разбиения, где для некоторого нетерминала
предлагаются подстроки длины меньше минимальной, могут быть сразу
же ≪отбракованы≫.
3.2.2. Метод Ангера для произвольных КС-грамматик
Рассмотрим модификации, которые необходимо внести в метод
Ангера, чтобы можно было сконструировать парсер для грамматик с
ε-правилами и циклами. Рассмотрим грамматику, изображенную на
рис. 3.4. Язык, порождаемый этой грамматикой, состоит из строк,
содержащих произвольное количество символов d, а также пустую
строку.
∗
Попытаемся проверить, что S ⇒ d. Начальная задача формулируется как
S
d
Рассмотрим первую S-продукцию, S → LSD, и построим для нее
возможные разбиения:
L
ε
ε
d
S
S
ε
d
ε
D
d
ε
ε
Видно, что кроме символов входной строки в разбиение включается
еще пустая строка ε. Рассмотрим первое разбиение из предложен∗
∗
∗
ных трех. Необходимо убедиться, что L ⇒ ε, S ⇒ ε и D ⇒ d.
Для нетерминала L существует единственная продукция, для которой разбиение тривиально и состоит из одного варианта — пустой
∗
строки. Таким образом, действительно, L ⇒ ε. Далее необходимо
∗
убедиться, что S ⇒ ε. Рассмотрим первую S-продукцию, S → LSD,
и построим единственное возможное разбиение пустой строки ε:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
58
Гл. 3. Синтаксический анализ
L
ε
S
S
ε
D
ε
Очевидно, что это разбиение не является корректным, так как ε не является выводимой строкой из нетерминала D. Однако до этой проверки
мы никогда не дойдем, так как перед этим необходимо последовательно
∗
∗
проверить, что L ⇒ ε и S ⇒ ε. Первая задача выполнится успешно,
однако вторая снова приведет нас к исходной задаче, которой является
∗
S ⇒ ε. Очевидно, что алгоритм зациклится — мы будем снова и снова
разбивать пустую строку и проверять, можно ли ее вывести с помощью
продукции S → LSD.
В более общем случае, если грамматика имеет ε-правила, то может
возникнуть ситуация, когда A → . . . → αAβ, где A — это нетерминальный символ грамматики. Если α и β порождают пустую строку, то
при использовании в выводе последовательности продукций, ведущей к
сентенциальной форме αAβ, алгоритм может зациклиться. В этом случае возможно построить бесконечно много выводов, в которых участвует сентенциальная форма αAβ. Тем не менее интерес представляет
единственный вывод, в котором отсутствует цикл. То есть мы должны
останавливать процесс построения вывода, если обнаруживается, что
алгоритм попадает в бесконечный цикл.
Это можно сделать следующим образом. На каждом шаге алгоритма решается некоторая задача о выводе некоторой подстроки из
нетерминального символа грамматики. В нашем примере на первом
∗
шаге решалась задача S ⇒ d, которая на следующем шаге сводилась
∗
∗
∗
к трем другим задачам — L ⇒ ε, S ⇒ ε и D ⇒ d. Таким образом,
всего нам необходимо решить четыре задачи. Для того чтобы исключить циклы, необходимо перед исследованием некоторого разбиения
выяснять, к списку каких задач оно сводит общую проблему, и если
хоть одна задача из этого списка уже исследуется, не рассматривать
∗
это разбиение. Так, при исследовании факта, что S ⇒ ε, мы свели это
∗
∗
∗
∗
к задачам L ⇒ ε, S ⇒ ε и D ⇒ ε. Однако задача S ⇒ ε и так уже
находится в стадии проверки, следовательно, необходимо отказаться от
такого разбиения, а так как оно единственное, то и от проверки того,
что c помощью продукции S → LSD можно вывести строку ε.
Запоминание ответов — положительных либо отрицательных — решения отдельных задач может также существенно ускорить алгоритм
Ангера. Так, при построении вывода некоторой строки можно запом∗
нить, что выполняется L ⇒ ε, и использовать это знание во всех
3.3. Синтаксический анализ с использованием магазинных автоматов 67
Автомат M будет допускать по пустому магазину тот же самый
язык, что и грамматика. Отличительной особенностью МП-автоматов,
сконструированных для КС-грамматик, является недетерминизм. Это
свойство МП-автоматов не является приемлемым с практической точки
зрения, так как на практике мы имеем дело с детерминированными алгоритмами, т.е. такими, у которых каждый следующий шаг
однозначно определяется на основе предыдущего. Для МП-автомата
необходима некоторая внешняя сила, которая бы его ≪направляла≫ по
той ветке вычислений, которая ведет к пустому магазину. Таким образом, в чистом виде построенные МП-автоматы не предназначены для
практического использования. Тем не менее можно предложить два
детерминированных способа моделирования работы этих устройств,
которые можно использовать на практике.
3.3.3. Методы детерминированного моделирования работы
МП-автомата
Все возможные конфигурации, достижимые от начальной, а также
переходы между ними можно представить в виде дерева с корнем
в начальной конфигурации. Это отчетливо видно на рис. 3.8, где
демонстрируется работа МП-автомата. Для того чтобы доказать выводимость данной цепочки, необходимо найти конфигурацию автомата,
где оставшаяся часть входа и магазин одновременно являются пустыми.
Следовательно, задача поиска вывода сводится к задаче обхода дерева,
начиная от его корня, и поиска вершины, удовлетворяющей этому
критерию. Известно, что существует две стратегии реализации поиска
вершин в деревьях, удовлетворяющих некоторому критерию: поиск в
ширину и поиск в глубину.
Рассмотрим сначала алгоритм нахождения вывода с использованием стратегии поиска в ширину. Если МП-автомат моделирует распознавание строки α = a1 a2 . . . an , то после распознавания
первых k символов, из-за недетерминированного характера работы
автомата, возможен переход в некоторое множество конфигураций
{(q, ak+1 . . . an , γi ) | (q, α, S) ⊢ . . . ⊢ (q, ak+1 . . . an , γi )}. Перепишем это
множество конфигураций в виде таблицы:
a1 a2 . . . a k
текущий вывод1
текущий вывод2
...
ak+1 . . . an
γ1
γ2
...
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
66
Гл. 3. Синтаксический анализ
S
A
B
C
D
→
→
→
→
→
AB | DC
a | aA
bc | bBc
c | cC
ab | aDb
Рис. 3.9. Неоднозначная грамматика, которая порождает язык am bn cn ∪ ap bp cq .
Алгоритм 17. Построение МП-автомата, распознающего тот же
язык, что и заданная КС-грамматика
Вход: КС-грамматика G = (N , T , P , S)
Выход: МП-автомат M = (Q, Σ, Γ, δ, q0 , Z0 , F ), допускающий по
пустому магазину и распознающий язык L(G)
Тогда автомат M = ({q}, T , N ∪ T , δ, q, S, {q}), где функция δ
строится согласно следующим правилам:
1. {(q, u)} ∈ δ(q, ε, A) ⇔ A → u, где u ∈ (N ∪ T )∗ .
2. {(q, ε)} ∈ δ(q, a, a) для всех a ∈ T .
Автомат M содержит одно состояние, которое является начальным
и финальным. Следовательно, основной объем вычислений состоит из
манипуляций символами на вершине стека. При этом прогноз того,
какую продукцию выбрать, осуществляется с помощью правил, построенных согласно п. 1, а проверка соответствия очередного входного
символа происходит с использованием правил из п. 2.
Рассмотрим неоднозначную грамматику, которая порождает язык
am bn cn ∪ ap bp cq (рис. 3.9). Тогда для нее можно построить МП-автомат
M = ({q}, {a, b, c}, {S, A, B, C, D} ∪ {a, b, c}, δ, q, S, {q}), где
• δ(q, ε, S) = {(q, AB), (q, DC)};
• δ(q, ε, A) = {(q, a), (q, aA)};
• δ(q, ε, B) = {(q, bc), (q, bBc)};
• δ(q, ε, C) = {(q, c), (q, cC)};
• δ(q, ε, D) = {(q, ab), (q, aDb)};
• δ(q, a, a) = {(q, ε)};
• δ(q, b, b) = {(q, ε)};
• δ(q, c, c) = {(q, ε)}.
3.2. Универсальные методы синтаксического анализа
59
остальных шагах алгоритма. Без использования оптимизации алгоритм
Ангера имеет экспоненциальную трудоемкость. Шейл в [27] показывает, что такая оптимизация может существенно сократить сложность алгоритма Ангера — до полиномиальной. Другой возможностью
оптимизации является вычисление всех ε-порождающих символов и
использование этой информации при работе алгоритма.
3.2.3. Метод Кока—Янгера—Касами
Данный метод синтаксического анализа был предложен Дж. Коком,
Д. Янгером и Т. Касами, которые независимо предложили различные
варианты этого алгоритма. Этот метод работает непрямо и реализует
стратегию восходящего синтаксического анализа. Входными данными
для алгоритма являются контекстно-свободная грамматика G и строка,
для которой необходимо построить вывод в данной грамматике. Будем
рассматривать грамматики, которые находятся в нормальной форме
Хомского. Напомним, что грамматика в нормальной форме Хомского
может содержать два вида правил: A → BC и A → a, где A, B, C — это
нетерминальные символы грамматики, а a представляет терминальный
символ. Это не ограничивает общности рассуждений, так как любая
контекстно-свободная грамматика может быть эффективно приведена
к этой форме (см. п. 1.3.4).
Алгоритм Кока—Янгера—Касами последовательно рассматривает
все варианты выводимости для любых подстрок длины 1, 2, . . . n входной строки α = t1 t2 . . . tn . Это делается путем построения набора
множеств Ri,l . Во множество Ri,l помещаются те нетерминалы, из
которых можно вывести подстроку si,l = ti ti+1 . . . ti+l−1 . Эта подстрока
начинается с i-й позиции в строке α и имеет длину l. Отметим, что
так как строка α состоит из n символов, то подстрока этой строки,
начинающаяся с i-го символа, не может иметь длину больше n + 1 − i.
Это означает, что для любой подстроки si,l выполняется неравенство
i + l 6 n + 1. Таким образом искомый набор множеств может быть
организован в виде треугольной таблицы, показанной на рис. 3.5.
Множества Ri,1 конструируются просто: необходимо рассмотреть
все продукции вида A → a и поместить в множество Ri,1 те нетерминалы A, из которых выводится i-й символ исходной строки, т.е. ti = a.
Далее для каждого значения i рассматриваются все подстроки длины
2, 3 и так далее. Допустим для некоторого i рассматривается подстрока
длины l. Следовательно, необходимо вычислить нетерминалы, из которых она порождается, и поместить их во множество Ri,l .
Элементы этого множества вычисляются с помощью набора ячеек
таблицы, закрашенных серым цветом на рис. 3.5. Все нетерминалы,
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
60
3.3. Синтаксический анализ с использованием магазинных автоматов 65
Гл. 3. Синтаксический анализ
(q0 , 0110, Z0 )
R1,n
R1,n−1
R2,n−1
...
...
...
...
...
...
...
...
R1,l
...
...
R1,1
...
...
Ri,l
...
V. . .
Ri,1
...
...
...
... W ...
...
...
...
...
...
...
Ri+l−1,1
...
...
(q0 , 110, 0Z0 )
(q1 , 0110, Z0 )
(q0 , 10, 10Z0 )
(q1 , 110, 0Z0 )
(q0 , 0, 110Z0 )
(q1 , 10, 10Z0 )
(q0 , ε, 0110Z0 )
(q1 , 0, 110Z0 )
(q2 , 0110, Z0 )
Rn,1
Рис. 3.5. Вид таблицы распознавания для метода Кока—Янгера—Касами.
(q1 , 0, 0Z0 )
принадлежащие множеству Ri,1 , порождают подстроки, которые начинаются с i-й позиции и имеют длину 1. Следовательно, представляют интерес те нетерминалы, которые могут порождать подстроки,
начинающиеся с i + 1-й позиции и имеют длину l − 1. Они являются
элементами множества Ri+1,l−1 . Теперь надо найти все продукции вида
A → bc, где b ∈ Ri,1 , c ∈ Ri+1,l−1 , и поместить найденные нетерминалы A в Ri,l . Далее необходимо аналогичным образом рассматривать элементы Ri,2 , Ri,3 , . . . , Ri,l−1 (они располагаются по стрелке,
обозначенной как V на рис. 3.5) и соответствующие им элементы
Ri+2,l−2 , Ri+3,l−3 , . . . , Ri+l−1,1 (они располагаются по стрелке W на
рис. 3.5). В итоге если нетерминал S принадлежит множеству R1,n ,
то строка α выводима в грамматике G.
Необходимо заметить, что множество Ri,l не может быть полностью
сформировано до тех пор, пока не построены множества, составляющие
треугольник, где это множество является вершиной. Существуют два
способа организовать порядок вычислений множеств, которые схематично показаны на рис. 3.6. Первый вариант подходит, когда имеется
возможность держать распознаваемую строку в памяти и работать
непрямо, второй вариант может работать при последовательном чтении
символов строки. Алгоритм имеет трудоемкость, равную O(n3 ), где n —
длина входной строки.
Далее автомат имеет возможность делать ошибочные предположения.
Вся последовательность конфигураций, достижимых из начальной, показана на рис. 3.8.
Необходимо также заметить, что существуют два способа определения языка, который допускает МП-автомат. Традиционно можно считать, что некоторая цепочка допускается, если после ее прочтения автомат перешел в допускающее состояние. Другой способ заключается в
допускании тех цепочек, которые приводят МП-автомат из начальной
конфигурации к опустошению магазина. Эти два метода эквивалентны в том смысле, что для любого МП-автомата, допускающего по
заключительному состоянию, найдется МП-автомат, допускающий по
пустому магазину, который распознает тот же самый язык, и наоборот
(доказательство можно увидеть в [5]). Однако если выбрать некоторый
конкретный МП-автомат, то он будет допускать различные языки по
пустому магазину и по заключительному состоянию.
Рис. 3.6. Способы заполнения таблицы распознавания.
3.3.2. Построение эквивалентного МП-автомата для заданной
КС-грамматики
Для КС-грамматики можно построить МП-автомат, допускающий
по пустому магазину, который будет распознавать тот же самый язык.
При этом автомат будет имитировать построение всех возможных
левых выводов этой грамматики.
(q1 , ε, 0110Z0 )
(q1 , ε, Z0 )
(q2 , ε, Z0 )
Рис. 3.8. Конфигурации МП-автомата из примера для входа 0110.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
64
Гл. 3. Синтаксический анализ
1. δ(q0 , 0, Z0 ) = {(q0 , 0Z0 )} и δ(q0 , 1, Z0 ) = {(q0 , 1Z0 )}. Эти правила
устанавливают, что если автомат находится в начальном состоянии и на вход был подан символ 0 или 1, то он помещается в
магазин. Символ Z0 остается на дне магазина.
2. δ(q0 , 0, 0) = {(q0 , 00)}, δ(q0 , 0, 1) = {(q0 , 01)}, и по аналогии
положим, что δ(q0 , 1, 0) = {(q0 , 10)}, и δ(q0 , 1, 1) = {(q0 , 11)}. Эти
четыре похожих правила позволяют читать входные символы и
помещать их в магазин над предыдущим магазинным символом.
3. δ(q0 , ε, Z0 ) = {(q1 , Z0 )}, δ(q0 , ε, 1) = {(q1 , 1)}, δ(q0 , ε, 0) = {(q1 , 0)}.
Эти правила позволяют автомату спонтанно переходить из состояния q0 в состояние q1 без изменения символа на вершине
магазина.
4. δ(q1 , 0, 0) = {(q1 , ε)} и δ(q1 , 1, 1) = {(q1 , ε)}. В состоянии q1
осуществляется проверка входных символов с теми, которые находятся на вершине магазина. При совпадении последние выталкиваются.
5. δ(q1 , ε, Z0 ) = {(q2 , Z0 )}. Если в состоянии q1 на вершине обнаружен маркер дна магазина, это значит, что успешно завершен процесс перебрасывания входных символов в магазин (распознавание
цепочки w), их сравнения с оставшейся частью входной цепочки и
выталкивания из магазина (распознавание цепочки wR ). Автомат
переходит в состояние q2 и допускает.
В отличие от конечных автоматов, для которых на каждом этапе
распознавания входной цепочки известно состояние, для МП-автоматов
кроме состояния имеется еще содержимое магазина. Магазин может
содержать значительное количество символов и является важной частью конфигурации. Это дает нам основание записывать каждый этап
распознавания входной строки с помощью тройки (q, w, γ), где q — состояние, w — оставшаяся часть входа, а γ — содержимое магазина, где
вершина изображается слева, а дно справа. Такая тройка называется
конфигурацией МП-автомата. Магазинный автомат при распознавании строчки переходит от конфигурации к конфигурации следующим
образом:
(q, aw, Xβ) ⊢ (p, w, αβ) ⇔ (p, α) ∈ δ(q, a, X)
Рассмотрим теперь работу МП-автомата P , допускающего язык
wwR для входа 0110. Начальной является конфигурация (q0 , 0110, Z0 ).
3.3. Синтаксический анализ с использованием магазинных автоматов 61
3.3. Синтаксический анализ с использованием
магазинных автоматов
В этом разделе мы рассмотрим методы синтаксического анализа,
основная идея которых состоит в попытке предсказать очередную
продукцию вывода строки при ее последовательном чтении.
Рассмотрим грамматику, изображенную на рис. 3.7. Она порождает
строки, которые содержат равное количество символов a и b. Попробуем построить вывод строки aabb в этой грамматике.
Вывод начинается с нетерминального символа S, который является начальным символом данной грамматики. При построении вывода
нетерминал S должен быть заменен при помощи одной из продукций
для него. В нашей грамматике мы имеем две возможности для этого:
использовать продукцию S → aB либо продукцию S → bA. Выводимая
строка начинается с символа a, поэтому мы не можем использовать
вторую продукцию. Таким образом, мы делаем догадку, что вся строка
выводится из сентенциальной формы aB. Запишем это следующим
образом:
a
a
abb
B
Верхняя строка показывает цепочку, для которой мы строим вывод,
в нижней строке записывается сентенциальная форма, из которой, по
нашему прогнозу, выводится данная цепочка. Теперь задача свелась к
тому, чтобы подтвердить прогноз, который утверждает, что из нетерминала B выводится цепочка abb, которая является подстрокой исходной
цепочки. Выбор может быть сделан из трех возможностей: B → b,
B → bS и B → aBB. Первые две не подходят, так как цепочка abb
начинается с символа a, следовательно, мы выбираем третий вариант:
a
a
a
a
bb
BB
На этом шаге необходимо сделать прогноз, как вывести из сентенциальной формы BB цепочку bb. Снова мы имеем выбор из трех
возможностей, которым соответствуют продукции для нетерминала B,
расположенного слева в сентенциальной форме. Вариант B → aBB не
подходит, так как цепочка начинается с символа b, следовательно, нам
S
A
B
→
→
→
aB | bA
a | aS | bAA
b | bS | aBB
Рис. 3.7. Грамматика, порождающая строки с равным количеством символов a
и b.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
62
Гл. 3. Синтаксический анализ
необходимо сделать выбор между продукциями B → b и B → bS. Можно последовательно их перебрать и увидеть, что продукция B → bS
не подходит, так как из S будет обязательно выведен терминальный
символ a. Следовательно, выберем продукцию B → b и получим:
aa
aa
b
b
b
B
Аналогично рассуждая, снова заменим нетерминал B на b со помощью продукции B → b, и входная цепочка закончится. Если последовательно выписать продукции, которые мы применяли, то получим
следующий вывод:
S → aB → aaBB → aabB → aabb
Этот пример показывает основные характеристики методов синтаксического анализа, которые будут рассмотрены в этом разделе:
• для каждой предложенной сентенциальной формы, мы рассматриваем символ, расположенный слева;
• если рассматриваемый символ является терминальным, то его
необходимо сравнить с текущим символом входной цепочки, и в
случае несовпадения отвергнуть рассматриваемую сентенциальную форму;
• если символ является нетерминальным, то мы должны спрогнозировать продукцию для данного символа, котороя поможет нам
построить вывод;
• всегда первым рассматривается левый нетерминал, следовательно, строится левосторонний вывод. Построение идет нисходящим
способом.
Оказывается, что похожим образом работают анализаторы, в основе
которых лежит формальная модель, которая называется магазинным
автоматом.
3.3.1. Магазинные автоматы
В п. 2.3 мы рассматривали конечные автоматы как устройства,
распознающие множество регулярных языков. Контекстно-свободные
языки не распознаются автоматами этого типа, однако если расширить
модель недетерминированного конечного автомата с ε-переходами при
помощи магазина, то класс получившихся устройств будет допускать
в точности множество КС-языков (доказательство этого факта можно
найти в [5]). Магазин представляет собой стек, в который по принципу
3.3. Синтаксический анализ с использованием магазинных автоматов 63
последний пришел-первый ушел≫ могут помещаться или удаляться
символы, принадлежащие некоторому алфавиту. Магазин может содержать бесконечное количество символов, таким образом, в отличие
от конечного автомата магазинный автомат может ≪помнить≫ бесконечное количество информации. Тем не менее из-за отсутствия произвольного доступа к символам в магазине существуют языки, не
распознаваемые ни одним магазинным автоматом. Например, таким
является язык {an bn cn | n > 1}, т.е. множество цепочек, состоящее
из одинакового количества символов a, b и c. Формально автомат с
магазинной памятью (МП-автомат) определяется следующим образом.
≪
Определение 8. Автомат с магазинной памятью (МП-автомат) —
это семерка символов (Q, Σ, Γ, δ, q0 , Z0 , F ), где
• Q является конечным множеством состояний;
• Σ — конечное множество входных символов;
• Γ представляет собой конечный магазинный алфавит и является множеством символов, которые можно помещать в
магазин;
• δ : Q × Σ ∪ {ε} × Γ → Q × Γ∗ представляет функцию переходов
автомата;
• q0 — начальное состояние автомата, q0 ∈ Q;
• Z0 представляет начальный магазинный символ (≪маркер
дна≫), Z0 ∈ Γ;
• F — множество финальных, или допускающих, состояний,
F ⊆ Q.
МП-автомат, допускающий язык {wwR | w ∈ (0 + 1)∗ } (под wR
здесь понимается цепочка w, записанная в обратном порядке), можно
представить следующим образом:
P = ({q0 , q1 , q2 }, {0, 1}, {0, 1, Z0 }, δ, q0 , Z0 , {q2 })
Функция δ сопоставляет тройке (q, a, X), где q — это текущее состояние автомата, a — входной символ либо ε, а X — это магазинный
символ, пару (p, γ), где p — новое состояние, а γ — цепочка магазинных
символов, замещающая X на вершине магазина. Для нашего примера
она определяется так:
Документ
Категория
Без категории
Просмотров
13
Размер файла
835 Кб
Теги
соколова, 914, технология, трансляции
1/--страниц
Пожаловаться на содержимое документа