|
|
|
|
|
|
|
В.А.Серебряков, М.П.Галочкин, Д.Р.Гончар, М.Г.Фуругян
«Теория и реализация языков программирования», учебное пособие для ВУЗов
по специальности прикладная физика и
математика (М.: МЗ-Пресс, |
|
|
|
|
Содержание
Предисловие 1. Введение 1.1. Место
компилятора в программном обеспечении 1.2. Структура
компилятора |
Страницы по 1-му изданию 7 8 8 9 |
|
|
|
2. Языки и их представление 2.1. Алфавиты, цепочки и языки 2.2. Представление языков 2.3. Грамматики 2.3.1. Формальное определение грамматики 2.3.2. Типы грамматик и их свойства 2.4. Машины Тьюринга 2.4.1. Неразрешимость проблемы останова 2.4.2. Класс рекурсивных множеств 2.5. Связь машин Тьюринга и грамматик типа 0 2.6. Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками |
13 13 15 17 17 19 20 22 23 24 27 |
|
|
|
3. Лексический анализ 3.1. Регулярные множества и выражения 3.2. Конечные автоматы 3.3. Алгоритмы построения конечных автоматов 3.3.1. Построение недетерминированного конечного автомата
по регулярному выражению 3.3.2. Построение детерминированного конечного автомата
по недетерминированному 3.3.3. Построение детерминированного конечного автомата
по регулярному выражению 3.3.4. Построение детерминированного конечного автомата
с минимальным числом состояний 3.4. Связь регулярных множеств, конечных автоматов и регулярных грамматик 3.5. Программирование лексического анализа 3.6. Конструктор лексических анализаторов LEX |
32 34 36 40 40 42 43 47 49 53 57 |
|
|
|
4. Синтаксический анализ 4.1. Контекстно-свободные грамматики и автоматы с магазинной
памятью 4.2. Преобразования КС-грамматик 4.2.1. Алгоритм Кока-Янгера-Касами 4.3. Предсказывающий разбор сверху-вниз 4.3.1. Алгоритм разбора сверху-вниз 4.3.2. Функции FIRST и FOLLOW 4.3.3. Конструирование таблицы предсказывающего
анализатора 4.3.4. LL(1)-грамматики 4.3.5. Удаление левой рекурсии 4.3.6. Левая факторизация 4.3.7. Рекурсивный спуск 4.3.8. Восстановление анализа после синтаксических
ошибок 4.4. Разбор снизу-вверх типа сдвиг-свёртка 4.4.1. Основа 4.4.2. LR(1)- анализаторы 4.4.3. Конструирование LR(1)-таблицы 4.4.4. LR (1)-грамматики 4.4.5. Восстановление анализа после синтаксических
ошибок 4.4.6. Варианты LR-анализаторов |
62 62 69 70 71 71 74 77 78 79 80 81 83 83 83 85 89 92 95 95 |
|
|
|
5. Элементы теории перевода 5.1. Преобразователи с магазинной памятью 5.2. Синтаксически управляемый перевод 5.2.1. Схемы синтаксически управляемого перевода 5.2.2. Обобщенные схемы синтаксически управляемого
перевода 5.3. Атрибутные грамматики 5.3.1. Определение атрибутных грамматик 5.3.2. Классы атрибутных грамматик и их
реализация 5.3.3. Язык описания атрибутных грамматик |
97 97 99 99 101 103 104 108 111 |
|
|
|
6. Проверка контекстных условий 6.1. Описание областей видимости и блочной структуры 6.2. Занесение в среду и поиск объектов |
115 115 117 |
|
|
|
7. Организация таблиц символов 7.1. Таблицы идентификаторов 7.2. Таблицы расстановки 7.3. Таблицы расстановки со списками 7.4. Функции расстановки 7.5. Таблицы на деревьях 7.6. Реализация блочной структуры 7.7. Сравнение методов реализации таблиц |
124 124 125 128 129 131 135 136 |
|
|
|
8. Промежуточное представление
программы 8.1. Представление в виде ориентированного графа 8.2. Трёхадресный код 8.3. Линеаризованные представления 8.4. Виртуальная машина Java 8.4.1. Организация памяти 8.4.2. Набор команд виртуальной машины 8.5. Организация информации в генераторе кода 8.6. Уровень промежуточного представления |
137 137 139 142 144 145 145 147 148 |
|
|
|
9. Генерация кода 9.1. Модель машины 9.2. Динамическая организация памяти 9.2.1. Организация магазина со статической
цепочкой 9.2.2. Организация магазина с дисплеем 9.3. Назначение адресов 9.4. Трансляция переменных 9.5. Трансляция целых выражений 9.6. Трансляция арифметических выражений 9.7. Трансляция логических выражений 9.8. Выделение общих подвыражений 9.9. Трансляция объектно-ориентированных свойств языков
программирования 9.9.1. Виртуальные базовые классы 9.9.2. Множественное наследование 9.9.3. Единичное наследование и виртуальные функции 9.9.4. Множественное наследование и виртуальные функции 9.9.5. Виртуальные базовые классы с виртуальными
функциями 9.10. Генерация оптимального кода методами синтаксического анализа 9.10.1. Сопоставление образцов 9.10.2. Синтаксический анализ для Т-грамматик 9.10.3. Выбор дерева вывода наименьшей стоимости 9.10.4. Атрибутная схема для алгоритма
сопоставления образцов |
149 150 152 154 158 159 160 163 164 172 180 184 184 185 186 187 189 191 191 195 200 202 |
|
|
|
10. Системы автоматизации построения
трансляторов 10.1. Система СУПЕР 10.2. Система YACC |
207 207 209 |
|
|
|
А. Семантика контекстно-свободных
языков А.1. Введение А.2. Формальные свойства А.3. Проверка на зацикленность А.4. Простой язык программирования А.5. Обсуждение |
212 212 218 223 228 238 |
|
|
|
B. Атрибутные грамматики В.1. Введение В.2. Определение атрибутных грамматик В.3. Атрибутированное дерево разбора В.4. Незацикленные атрибутные
грамматики В.5. Вычислительные последовательности и корректность. Определение
визита В.6. Чистые многовизитные грамматики В.7. Абсолютно незацикленные
атрибутные грамматики В.8. Простые многовизитные атрибутные
грамматики В.9. Одновизитные атрибутные
грамматики В.10. Многопроходные грамматики |
245 245 246 247 248 250 251 253 257 259 260 |
|
|
|
C. Задачи по разделам книги С.2. Языки и их представление С.2.1. Алфавиты, цепочки и языки С.2.2. Представление языков С.2.3. Грамматики С.3. Лексический анализ С.3.1. Регулярные множества и выражения С.3.2. Конечные автоматы С.3.3. Алгоритмы построения конечных автоматов С.3.4. Регулярные множества и их представления С.3.5. Алгебраические свойства регулярных
множеств. Лемма
о разрастании С.4. Синтаксический анализ С.4.1. КС-грамматики и МП-автоматы С.4.2. Алгебраические свойства КС-языков. Лемма
о разрастании С.4.3. Преобразования КС-грамматик С.4.4. Предсказывающий разбор сверху-вниз С.4.5. Разбор снизу-вверх типа сдвиг-свёртка С.5. Элементы теории перевода С.5.3. Атрибутные грамматики С.9. Генерация кода С.9.1. Трансляция арифметических выражений С.9.2. Трансляция логических выражений С.9.3. Генерация оптимального кода методами синтаксического
анализа Литература |
268 268 268 268 269 274 274 276 277 277 277 278 278 281 282 285 287 290 290 291 291 292 292 293 |
|
|
|
|
|
|