А.Ахо, Дж. Ульман «Теория синтаксического анализа, перевода и компиляции», т.1. (М.: Мир, 1978 г.) ОГЛАВЛЕНИЕ
ОТ РЕДАКТОРА ПЕРЕВОДА ПРЕДИСЛОВИЕ 0. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ 0.1. Основные понятия теории множеств 0.1.1. Множества 0.1.2. Операции над множествами 0.1.3. Отношения 0.1.4. Замыкание отношений 0.1.5. Отношения порядка 0.1.6. Отображения Упражнения 0.2. Множества цепочек 0.2.1. Цепочки 0.2.2. Языки 0.2.3. Операции над языками Упражнения 0.3. Некоторые понятия математической логики 0.3.1. Доказательства 0.3.2. Доказательство индукцией 0.3.3. Логические связки Упражнения Замечания по литературе 0.4. Алгоритмы (частичные и всюду определённые) 0.4.1. Частичные алгоритмы 0.4.2. Алгоритмы 0.4.3. Рекурсивные функции 0.4.4. Задание алгоритмов 0.4.5. Проблемы 0.4.6. Проблема соответствий Поста Упражнения Замечания по литературе 0.5. Некоторые понятия теории графов 0.5.1. Ориентированные графы 0.5.2. Ориентированные ациклические графы 0.5.3. Деревья 0.5.4. Упорядоченные графы 0.5.5. Индукция по ациклическому графу 0.5.6. Вложение частичного порядка в линейный 0.5.7. Представления деревьев 0.5.8. Пути в графе Упражнения Замечания по литературе	7 11 11 11 14 16 18 20 21 23 26 27 28 29 30 31 31 32 33 35 38 38 38 40 41 42 43 47 48 51 52 52 54 55 56 58 59 61 62 66 68
1. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ 1.1. Языки программирования 1.1.1. Задание языков программирования 1.1.2. Синтаксис и семантика 1.1.3. Замечания по литературе 1.2. Обзор процесса компиляции 1.2.1. Основные части компилятора 1.2.2. Лексический анализ 1.2.3. Работа с таблицами 1.2.4. Синтаксический анализ 1.2.5. Генерация кода 1.2.6. Оптимизация кода 1.2.7. Анализ и исправление ошибок 1.2.8. Резюме Упражнения Замечания по литературе 1.3. Другие приложения алгоритмов разбора и перевода 1.3.1. Естественные языки 1.3.2. Структурное описание образов Замечания по литературе	69 69 69 71 74 75 75 76 79 80 82 88 90 91 92 95 96 97 98 102
2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 2.1. Способы определения языков 2.1.1. Мотивировка 2.1.2. Грамматики 2.1.3. Грамматики с ограничениями на правила 2.1.4. Распознаватели Упражнения Замечания по литературе 2.2. Регулярные множества, их распознавание и порождение 2.2.1. Регулярные множества и регулярные выражения 2.2.2. Регулярные множества и праволинейные грамматики 2.2.3. Конечные автоматы 2.2.4. Резюме Упражнения Замечания по литературе 2.3. Свойства регулярных множеств 2.3.1. Минимизация конечных автоматов 2.3.2. Лемма о разрастании для регулярных множеств 2.3.3. Свойства замкнутости регулярных множеств 2.3.4. Разрешимые проблемы, связанные с регулярными множествами Упражнения Замечания по литературе 2.4. Контекстно-свободные языки 2.4.1. Деревья выводов 2.4.2. Преобразования КС-грамматик 2.4.3. Нормальная форма Хомского 2.4.4. Нормальная форма Грейбах 2.4.5. Другой метод преобразования к нормальной форме Грейбах Упражнения Замечания по литературе 2.5. Автоматы с магазинной памятью 2.5.1. Основное определение 2.5.2. Варианты МП-автоматов 2.5.3. Эквивалентность МП-автоматов и КС-грамматик 2.5.4. Детерминированные МП-автоматы Упражнения Замечания по литературе 2.6. Свойства контекстно-свободных языков 2.6.1. Лемма Огдена 2.6.2. Свойства замкнутости класса КС-языков 2.6.3. Результаты о разрешимости 2.6.4. Свойства детерминированных КС-языков 2.6.5. Неоднозначность Упражнения Замечания по литературе	103 103 104 105 111 112 116 123 124 124 131 134 153 143 147 147 147 151 152 154 156 162 163 163 168 176 178 184 188 192 192 193 198 203 211 217 220 220 220 227 227 230 231 236 241
3. ТЕОРИЯ ПЕРЕВОДА 3.1. Формализмы, используемые для определения перевода 3.1.1. Перевод и семантика 3.1.2. Схемы синтаксически управляемого перевода 3.1.3. Конечные преобразователи 3.1.4. Преобразователи с магазинной памятью Упражнения Замечания по литературе 3.2. Свойства синтаксически управляемых переводов 3.2.1. Характеризующие языки 3.2.2. Свойства простых СУ-переводов 3.2.2. Иерархия СУ-переводов Упражнения Замечания по литературе 3.3. Лексический анализ 3.3.1. Язык расширенных регулярных выражений 3.3.2. Непрямой лексический анализ 3.3.3. Прямой лексический анализ 3.3.4. Программное моделирование конечных преобразователей Упражнения Замечания по литературе 3.4. Синтаксический анализ 3.4.1. Определение разбора 3.4.2. Нисходящий разбор 3.4.3. Восходящий разбор 3.4.4. Сравнение нисходящего разбора с восходящим 3.4.5. Грамматическое покрытие Упражнения Замечания по литературе	242 242 242 246 254 258 264 268 268 269 273 274 281 283 283 284 286 290 293 294 295 296 296 297 301 304 309 315
4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.1. Синтаксический анализ с возвратами 4.1.1. Моделирование МП-преобразователя 4.1.2. Неформальное описание нисходящего разбора 4.1.3. Алгоритм нисходящего разбора 4.1.4. Временная и емкостная сложность нисходящего анализатора 4.1.5. Восходящий разбор Упражнения Замечания по литературе 4.2. Табличные методы синтаксического анализа 4.2.1. Алгоритм Кока—Янгера — Касами 4.2.2. Алгоритм Эрли Упражнения Замечания по литературе	316 317 317 321 325 333 338 344 351 352 352 358 369 372
5. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ 5.1. LL(k)-грамматики 5.1.1. Определение LL(k)-грамматики 5.1.2. Предсказывающие алгоритмы разбора 5.1.3. Следствия определения LL(k)-грамматики 5.1.4. Разбор для LL(1)-грамматик 5.1.5. Разбор для LL(k)-грамматик Проверка LL(k)-условия Упражнения Замечания по литературе Дополнение. О методах разбора „по текущему символу" В. И. Агафонов 5.2. Детерминированный восходящий синтаксический анализ 5.2.1. Разбор с помощью детерминированного алгоритма типа „перенос-свёртка" 5.2.2. LR (k)-грамматики 5.2.3. Следствия определения LR(k)-грамматики 5.2.4. Проверка LR (k)-условия 5.2.5. Детерминированные правые анализаторы для LR(k)-грамматик 5.2.6. Реализация LL(k)- и LR(k)-анализаторов Упражнения Замечания по литературе 5.3. Грамматики предшествования 5.3.1. Формальное определение алгоритма типа „перенос-свёртка" 5.3.2. Грамматики простого предшествования 5.3.3. Грамматики расширенного предшествования 5.3.4. Грамматики слабого предшествования Упражнения Замечания по литературе 5.4. Другие классы грамматик, анализируемых методом „перенос - свёртка" 5.4.1. Грамматики ограниченного правого контекста 5.4.2. Грамматики смешанной стратегии предшествования 5.4.3. Грамматики операторного предшествования 5.4.4. Язык Флойда — Эванса Резюме Упражнения Замечания по литературе	373 374 374 378 382 387 388 396 400 408 408 420 420 423 432 442 443 448 448 452 452 452 455 463 469 477 480 481 481 488 492 497 502 505 510
6. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ 6.1. Нисходящий разбор с ограниченными возвратами 6.1.1. Язык нисходящего разбора с ограниченными возвратами 6.1.2. ЯНРОВ и детерминированные КС-языки 6.1.3. Обобщённый ЯНРОВ 6.1.4. Временная сложность ОЯНРОВ-языков Реализация ОЯНРОВ-программ Упражнения Замечания по литературе 6.2. Восходящий разбор с ограниченными возвратами 6.2.1. Неканонический разбор 6.2.2. Анализаторы с двумя магазинами 6.2.3. Отношения предшествования Колмерауэра 6.2.4. Проверка условий предшествования Колмерауэра Упражнения Замечания по литературе	511 511 512 522 525 530 533 539 542 542 542 544 547 549 556 558
Приложение П.1. Синтаксис расширяемого языка П.2. Синтаксис операторов языка Снобол 4 П.3. Синтаксис ПЛ 360 П.4. Схема синтаксически управляемого перевода для языка PAL Список литературы Указатель обозначений Указатель лемм, теорем и алгоритмов Именной указатель Предметный указатель	559 559 562 565 569 575 590 591 593 596