Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г., Теория и реализация языков программирования (2006 р.)
УДК 004.43
ББК 32.973.26-018.2
С 28
Серебряков в.А. и др.
С 28 Теория и реализация языков программирования: Учебное пособие./ В.А.Серебряков, М.П.Галочкин, Д.Р.Гончар,М.Г.Фуругян. - М.: МЗ Пресс, 2006. - 352 е.: ил.ISBN 5-94073-094-9
На основе лекций, прочитанных на ВМиК МГУ и ФУПМ МФТИ в 1991-2004 гг., излагаются основные разделы теории разработки компиляторов. Рассматриваются такие средства автоматизации процесса разработки трансляторов, как LEX, YACC, СУПЕР, методы генерации оптимального кода. Восполняется значительный (с 1991 г.)пробел в литературе на русском языке по данной теме.
Для студентов, аспирантов программистских специальностей и профессионалов - программистов и разработчиков компиляторов.
Оглавление
Предисловие 8
1. Введение 9
1.1. Место компилятора в программном обеспечении 9
1.2. Структура компилятора 11
2. Языки и их представление 15
2.1. Алфавиты, цепочки и языки 15
2.2. Представление языков 18
2.3. Грамматики 20
2.3.1. Формальное определение грамматики 20
2.3.2. Типы грамматик и их свойства 22
2.4. Машины Тьюринга 29
2.4.1. Неразрешимость проблемы останова 31
2.4.2. Класс рекурсивных множеств 33
2.5. Связь машин Тьюринга и грамматик типа О 35
2.6. Линейно-ограниченные автоматы и их связьс контекстно-зависимыми грамматиками 38
3. Лексический анализ 44
3.1. Регулярные множества и выражения 46
3.2. Конечные автоматы 50
3.3. Алгоритмы построения конечных автоматов 54
3.3.1. Построение недетерминированного конечного автомата по регулярному выражению 54
3.3.2. Построение детерминированного конечного автомата но недетерминированному 57
3.3.3. Построение детерминированного конечного автомата но регулярному выражению 59
3.3.4. Построение детерминированного конечного автомата с минимальным числом состояний 63
3.4. Связь регулярных множеств, конечных автоматов и регулярных грамматик 66
3.5. Программирование лексического анализа 70
3.6. Конструктор лексических анализаторов LEX 75
4. Синтаксический анализ 80
4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью 80
4.2. Преобразования КС-грамматик 89
4.2.1. Алгоритм Кока-Янгера-Касами 91
4.3. Предсказывающий разбор сверху-вниз 92
4.3.1. Алгоритм разбора сверху-вниз 92
4.3.2. Функции FIRST и FOLLOW 96
4.3.3. Конструирование таблицы предсказывающего анализатора 101
4.3.4. LL(l)-грамматики 102
4.4. LL(k:)-грамматики 104
4.5. Следствия определения LL(k)-грамматики 105
4.5.2. Левая факторизация 108
4.5.3. Рекурсивный спуск 109
4.5.4. Восстановление процесса анализа после синтаксических ошибок..110
4.6. Разбор снизу-вверх типа сдвиг-свёртка 111
4.6.1. Основа 111
4.6.2. LR(1)-анализаторы 113
4.6.3. Конструирование LR(1)-таблицы 118
4.6.4. LR(1)-грамматики 125
4.6.5. Восстановление процесса анализа после синтаксических ошибок..129
4.6.6. Варианты LR-анализаторов..130
5. Элементы теории перевода 132
5.1. Преобразователи с магазинной памятью 133
5.2. Синтаксически управляемый перевод 134
5.2.1. Схемы синтаксически управляемогоперевода 134
5.2.2. Обобщённые схемы синтаксически управляемого перевода 138
5.3. Атрибутные грамматики 141
5.3.1. Определение атрибутных грамматик 141
5.3.2. Классы атрибутных грамматик и их реализация 146
5.3.3. Язык описания атрибутных грамматик 149
6. Проверка контекстных условий 154
6.1. Описание областей видимости и блочнойструктуры 154
6.2. Занесение в среду и поиск объектов 156
7. Организация таблиц символов 165
7.1. Таблицы идентификаторов 166
7.2. Таблицы расстановки 168
7.3. Таблицы расстановки со списками..171
7.4. Функции расстановки 173
7.5. Таблицы на деревьях 174
7.6. Реализация блочной структуры 179
7.7. Сравнение методов реализации таблиц 180
8. Промежуточное представление программы 182
8.1. Представление в виде ориентированногографа 182
8.2. Трёхадресный код 183
8.4. Виртуальная машина Java 191
8.4.1. Организация памяти 191
8.4.2. Набор команд виртуальной машины 192
8.5. Организация информации в генераторе кода 195
8.6. Уровень промежуточного представления 196
9. Генерация кода 197
9.1. Модель машины 198
9.2. Динамическая организация памяти 202
9.2.1. Организация магазина со статической цепочкой 203
9.2.2. Организация магазина с дисплеем 208
9.3. Назначение адресов 209
9.4. Трансляция переменных 211
9.5. Трансляция целых выражений 215
9.6. Трансляция арифметических выражений 216
9.7. Трансляция логических выражений 226
9.9. Трансляция объектно-ориентированныхсвойств языков программирования 241
9.9.1. Виртуальные базовые классы 241
9.9.2. Множественное наследование 242
9.9.3. Единичное наследование и виртуальные функции 244
9.9.4. Множественное наследование и виртуальные функции 245
9.9.5. Виртуальные базовые классы с виртуальными функциями 247
9.10. Генерация оптимального кода методами синтаксического анализа 250
9.10.1. Сопоставление образцов 250
9.10.2. Синтаксический анализ для Т-грамматик 255
9.10.3. Выбор дерева вывода наименьшей стоимости 261
9.10.4. Атрибутная схема для алгоритма сопоставления образцов 264
10. Системы автоматизации построения трансляторов 269
10.1. Система СУПЕР 270
10.2. Система YACC 272
А. Семантика контекстно-свободных языков 276
А.1. Введение 277
А.2. Формальные свойства 282
А.З. Проверка на зацикленность 287
А.4. Простой язык программирования 292
А.5. Обсуждение 301
В. Атрибутные грамматики 307
В.1. Введение 307
В.2. Определение атрибутных грамматик 308
В.З. Атрибутированное дерево разбора 309
В.4. Незацикленные атрибутные грамматики 310
В.5. Вычислительные последовательности и корректность. Определение визита 311
В.6. Чистые многовизитные грамматики 313
В.7. Абсолютно незацикленные атрибутные грамматики 315
В.8. Простые многовизитные атрибутные грамматики 319
В.9. Одновизитные атрибутные грамматики 320
В.10.Многопроходные грамматики 321
С. Задачи по разделам книги 329
С.2. Языки и их представление 329
С.2.1. Алфавиты, цепочки и языки 329
С.2.2. Представление языков 329
С.2.3. Грамматики 330
С.З. Лексический анализ 335
С.3.1. Регулярные множества и выражения 335
С.3.2. Конечные автоматы 337
С.3.3. Алгоритмы построения конечных автоматов 338
С.3.4. Регулярные множества и их представления 338
С.3.5. Алгебраические свойства регулярных множеств. Лемма о разрастании 338
С.4. Синтаксический анализ 339
С.4.1. КС-грамматики и МП-автоматы 339
С.4.2. Алгебраические свойства КС-языков Лемма о разрастании 342
С.4.3. Преобразования КС-грамматик 343
С.4.4. Предсказывающий разбор сверху-вниз 345
С.4.5. Разбор снизу-вверх тина сдвиг-свертка 347
С.5. Элементы теории перевода 351
С.5.3. Атрибутные грамматики 351
С.9. Генерация кода 352
С.9.1. Трансляция арифметических выражений 352
С.9.2. Трансляция логических выражений 352
С.9.3. Генерация оптимального кода методами синтаксического анализа 352
Литература 353
(Для ознайомлення з повним текстом статті необхідно залогінитись)