Распознавание вложенности скобок и q-грамматика
Теперь у нас достаточно знаний для построения простой грамматики, порождающей вложенные скобки. Данная q-грамматика содержит следующие правила:
S → (B)B
B → B)B
B → e
Правила выбора выглядят следующим образом:
ВЫБОР(1) = ВЫБОР (S → (B)B ) = {(}
ВЫБОР(2) = ВЫБОР (B → B)B ) = {(}
ВЫБОР(3) = ВЫБОР (B → e) = СЛЕД (B) = {), ┤}
Они лишний раз подтверждают, что мы построили q-грамматику. Следует специально отметить, что, начиная с q-грамматики, далее постоянно приходиться доказывать принадлежность грамматики заданному классу, чтобы затем использовать необходимые процедуры построения автомата. Таблица переходов данного автомата будет выглядеть следующим образом:
| Магазинные символы | Входные символы | ||
| ( | ) | ┤ | |
| S | ↕ B)B,→ | Отвергнуть | Отвергнуть |
| B | ↕ B)B,→ | ↑ | ↑ |
| ) | Отвергнуть | ↑,→ | Отвергнуть |
| Ñ | Отвергнуть | Отвергнуть | Допустить |
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под общей ред. А. Матросова. – СПб.: Питер, 2002. – 688 с.: ил.
2. Серебряников В.А. Теория и реализация языков программирования. – М.: МЗ-Пресс, 2003.
3. Альфред В. Ахо, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий. – М.: Вильямс, 2001.
4. Системное программирование. Основы построения трансляторов. Учебное пособие. – М.: КОРОНА-принт, 2001.
5. Кауфман В. Ш. Языки программирования. Концепции и принципы. - М.: Радио и связь, 1993. - 432 с.
6. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.
7. Маккиман У. Генератор Компиляторов. - М.: Статистика, 1980.
8. Рейоурд-Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988.
9. Фостер Дж. Автоматический синтаксический анализ. - М.: Мир, 1975.
10. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.
11. Шишмарев А.И., Заморин А.П. Англо-русско-немецко-французский толковый словарь по вычислительной технике. М.: Издательство «Русский язык», 1978.
12. Браун П. Макропроцессоры и мобильность программного обеспечения. - М.: Мир, 1977.
13. Легалов А.И. Процедурно-параметрическая парадигма программирования. Возможна ли альтернатива объектно-ориентированному стилю? - Красноярск: 2000. Деп. рук. № 622-В00 Деп. в ВИНИТИ 13.03.2000. - 43 с.
14. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - М.: Мир, 1978.
15. Грис Д. Наука программирования. М.: Мир, 1984.
16. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.
17. Легалов А.И. Основы разработки трансляторов. Конспект лекций.
18. Вайнгартен Ф. Трансляция языков программирования. - М.: Мир, 1977.
СОДЕРЖАНИЕ
ЛЕКЦИЯ № 1 ВВЕДЕНИЕ.. 3
1.1 Предмет дисциплины, ее цели и задачи.. 3
1.2 Структура, содержание дисциплины.. 4
1.3 Связь с другими дисциплинами учебного плана направления. 4
1.4 Перечень основных и дополнительных источников. 5
1.4.1 Основная литература. 5
1.4.2 Дополнительная литература. 6
ЛЕКЦИЯ № 2 ОБЩИЕ СВЕДЕНИЯ О ТРАНСЛЯТОРАХ.. 7
2.1 Основные понятия и определения. 7
2.2 Общие особенности языков программирования и трансляторов 11
2.3 Обобщенная структура транслятора.. 18
2.4 Варианты взаимодействия блоков транслятора.. 22
2.4.1 Многопроходная организация взаимодействия блоков транслятора 23
2.4.2 Однопроходная организация взаимодействия блоков транслятора 25
2.4.3 Комбинированные взаимодействия блоков транслятора. 28
ЛЕКЦИЯ № 3 ТЕОРИЯ ЯЗЫКОВ И ФОРМАЛЬНЫХ ГРАММАТИК.. 33
3.1 Способы определения языков. 33
3.2 Формальные грамматики.. 33
3.3 Грамматики с ограничениями на правила.. 36
ЛЕКЦИЯ № 4 СПОСОБЫ ЗАПИСИ СИНТАКСИСА ЯЗЫКА. РАСПОЗНАВАТЕЛИ 38
4.1 Метаязык Хомского.. 38
4.2 Метаязык Хомского-Щутценберже. 39
4.3 Бэкуса-Наура формы (БНФ) 40
4.4 Расширенные Бэкуса-Наура формы (РБНФ) 40
4.5 Диаграммы Вирта.. 42
4.6 Распознаватели.. 44
ЛЕКЦИЯ № 5 ДЕМОНСТРАЦИОННЫЙ ЯЗЫК ПРОГРАММИРОВАНИЯ DPL 47
5.1 Синтаксис и семантика DPL.. 47
5.1.1 Элементарные конструкции. 48
5.1.2 Составные конструкции. Организация программы.. 50
5.1.3 Краткое описание семантики языка. 52
5.2 Примеры программ на DPL.. 53
5.2.1 Алгоритм Евклида (нахождение наибольшего общего делителя) 53
5.2.2 Одновременное нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) 54
5.2.3 Суммирование n элементов из входного потока. 54
5.2.4 Сортировка элементов вектора. 54
5.3 Описание пользовательского синтаксиса с использованием диаграмм Вирта 55
5.3.1 Элементарные конструкции. 56
5.3.2 Составные конструкции. 59
ЛЕКЦИЯ № 6 ОРГАНИЗАЦИЯ ЛЕКСИЧЕСКОГО АНАЛИЗА.. 63
6.1 Назначение и необходимость фазы лексического анализа.. 63
6.2 Транслитератор. 64
6.3 Грамматики и распознаватели для лексического анализа.. 65
6.3.1 Связь между диаграммой Вирта и конечным автоматом.. 65
6.3.2 Связь между диаграммами Вирта и праволинейными грамматиками. Преобразование правой рекурсии в итерацию 67
6.3.3 Связь между диаграммами Вирта и грамматиками с левой рекурсией. Преобразование левой рекурсии в итерацию 70
6.4 Методы лексического анализа.. 72
6.4.1 Организация непрямого лексического анализатора. 72
6.4.2 Организация прямого лексического анализатора. 77
ЛЕКЦИЯ № 7 ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР ДЕМОНСТРАЦИОННОГО ЯЗЫКА ПРОГРАММИРОВАНИЯ 80
7.1 Транслитератор DPL.. 80
7.1.1 Общая организация транслитератора. 80
7.1.2 Программная реализация транслитератора. 81
7.2 Непрямой лексический анализатор DPL.. 83
7.2.1 Диаграммы Вирта для отдельных автоматов непрямого лексического анализатора 86
7.2.1 Программная реализация отдельных автоматов. 92
7.2.3 Общая структура непрямого лексического анализатора. 92
7.3 Прямой лексический анализатор DPL.. 97
ЛЕКЦИЯ № 8 ОБЩИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО РАЗБОРА 104
8.1 Назначение синтаксического разбора.. 104
8.2 Классификация методов синтаксического разбора.. 105
8.3 Методы разбора.. 106
8.4 Последовательность разбора.. 115
8.5 Использование просмотра вперед.. 116
8.6 Использование возвратов. 116
8.7 Выводы.. 117
ЛЕКЦИЯ № 9 ИСПОЛЬЗОВАНИЕ АВТОМАТОВ С МАГАЗИННОЙ ПАМЯТЬЮ ДЛЯ НИСХОДЯЩЕГО РАЗБОРА СЛЕВА НАПРАВО.. 118
9.1 Организация автомата с магазинной памятью... 119
9.1.1 Операции автомата. 120
9.1.2 Распознаватель скобочных выражений. 120
9.2 Общая связь между грамматиками.. 123
и автоматами с магазинной памятью... 123
9.3 Связь между S-грамматикой и автоматом с магазинной памятью 124
9.3.1 Обобщенный алгоритм построения нисходящего АМП.. 125
для S - грамматики. 125
9.3.2 S-грамматика и распознавание вложенности скобок. 128
9.4 Построение автомата с магазинной памятью по q-грамматике 129
9.4.1 Построение нисходящего автомата. 132
9.4.2 Примеры построения АМП по q-грамматике. 133
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 136