А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947)
Текст из файла
е ° $) Э ' $ Л ' ее в ° в Л ББК 32.973.26-0! 8.2.75 К63 УДК 681.3.07 Издательский дом "Вильямс" Зав. редакцией С.Н. Тригуб Перевод с английского и редакция канд. техн. наук И.В. Красикова По общим вопросам обращайтесь в Издательский дом "Вильямс" по адресу: !0(о®ьу!1йагпзрпЫ!8Ыпй.сош, Ьнр://чссгтнлн!1йашзрпЫ!8Ь|пй.сош 115419, Москва, а/я 783; 03150, Киев, а/я 152 Ахо, Альфред В., Лам, Моника С., Сети, Рави, Ульман, Джеффри Д. К63 Компиляторы: принципы, технологии и инструментарий, 2-е изд.: Пер.
с англ. — М.: 000 нИ.Д, Вильямс", 2008. — 1184 с.: ип. — Парал. тит. англ. 18ВХ 978-5-8459-1349-4 (рус.) Эта книга, как и предыдущее издание„начинается с изложения основных принципов разработки компиляторов, включая детальное рассмотрение лексического и синтаксического анализа и генерации кода. Особенностью данного издания является широкое освещение вопросов оптимизации кода, в том числе для работы в многопроцессорных системах.
Строгость изложения материала смягчается большим юличеством практических примеров. Написание компиляторов охватывает такие области знаний, как языки программирования, архитектура вычислительных систем, теория языков, алгоритмы и технология создания программного обеспечения. Помочь в освоении этих технологий и соответствующего инструментария и призвана данная книга. Несмотря на ее учебную ориентацию — в первую очередь, она предназначена для студентов и преподавателей соответствующих специальностей — книга будет полезна всем, кто работает над созданием юмпиляторов или просю интересуется данной темой.
ББК 32.973.26-018.2.75 © Издательский дом "Вильямс", 2008 © Реагзоп Ебнсайоп, 1пс., 2007 18ВН 978-5-8459-! 349-4 (рус.) 18ВН 0-321-48081-! (внгл.] Все названия программных продукюв являются зарегисгрированными торговыми маркамн соответствующих фирм. Никакая часть настоящего издания нн в каких лелях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средспмми, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на зто нег письменного разрешения издательства Абб!воп-'йгев1еу РнЫ!зйюй Союрвпу, 1пс.
Аойопхсб папз1абоп пою йе Еп81НЬ 1апйоайе айюп роЫ!зЬеб Ьу Абб!зоп-туев!еу РпЫпЬюй Соптрапу,!пс, Сорупйм © 2007 Ай пйЬи гюегчед. Но рап о( йн рпЫ(салоп юау Ье гергобпсеб, зпиеб !п а ге!печа( яузгею, ог папюнпеб, ю апу бзпп ог Ьу апу пгеапз, е(ее!гоп(с, пгесЬапгса1, РЬоьюору(пя, мсогб!пй, ог ойегиме, пгйою бге рпог жппеп репи!зыоп о( йе роЫ!зьег. Князгап 1апйгмйе еййоп рнЫмьеб Ьу Угййаюя РнЫВЫав Ноеве ассопйпй Го йе Аягееюепз и!й йм! Епгегрпзез Ьггепыг!опа1, Сорупййг © 2008 Оглавление 24 29 75 155 251 383 525 617 705 841 911 1061 Приложение А. Завершенный пример начальной стадии Приложение Б.
Поиск линейно независимых решений 1133 компилятора 1163 Предметный указатель 1167 Предисловие Глава 1. Введение в компиляцию Глава 2. Простой синтаксически управляемый транслятор Глава 3. Лексический анализ Глава 4. Синтаксический анализ Глава 5. Синтаксически управляемая трансляция Глава 6. Генерация промежуточного кода Глава 7.
Среды времени выполнения Глава 8. Генерация кода Глава 9. Машинно-независимые оптимизации Глава 10. Параллелизм на уровне команд Глава 11. Оптимизация параллелизма и локальности Глава 12. Межпроцедурный анализ Содержание Предисловие 24 Глава 1.1 1. Введение в компиляцию !.2 1.3 !.4 45 46 48 48 50 52 54 1.5 55 Компиляторы 1.1.! Упражнения к разделу !.1 Структура компилятора 1.2.1 Лексический анализ 1.2.2 Синтаксический анализ 1.2.3 Семантический анализ 1.2.4 Генерация промежуточного кода 1.2.5 Оптимизация кода 1.2.6 Генерация кода 1.2.7 Управление таблицей символов 1.2.8 Объединение фаз в проходы !.2.9 Инструментарий для создания компиляторов Эволюция языков программирования 1.3.! Переход к языкам высокого уровня 1.3.2 Влияние на компиляторы 1.3.3 Упражнения к разделу 1.3 "Компилятороведение" 1.4.1 Моделирование при проектировании и реализации компилятора 1.4.2 Изучение оптимизации кода Применения технологий компиляторов 1.5.1 Реализация высокоуровневых языков программирования !.5.2 Оптимизация для архитектуры компьютера 1.5.3 Разработка новых архитектур компьютеров 1.5.4 Трансляции программ !.5.5 Инструментарий для повышения производительности программного обеспечения 29 29 32 32 33 35 37 38 39 39 40 41 41 42 42 44 45 45 Содержание 57 58 58 61 65 65 68 70 70 72 73 1.6 1.7 1.8 Глава 2 2.! 2.2 ятор 2.3 ределения 2.4 2.5 Азы языков программирования !.6.1 Понятия статического и динамического 1.6.2 Среды и состояния 1.6.3 Статическая область видимости и блочная структура 1.6.4 Явное управление доступом 1.6.5 Динамическая область видимости 1.6.6 Механизмы передачи параметров 1.6.7 Псевдонимы !.6.8 Упражнения к разделу !.6 Резюме к главе 1 Список литературы к главе 1 Простой синтаксически управляемый трансл Введение Определение синтаксиса 2.2.1 Определения грамматик 2.2.2 Выведение 2.2.3 Деревья разбора 2.2.4 Неоднозначности 2.2.5 Ассоциативность операторов 2.2.6 Приоритет операторов 2.2.7 Упражнения к разделу 2.2 Синтаксически управляемая трансляция 2.3.! Постфиксная запись 2.3.2 Синтезированные атрибуты 2.3.3 Простые синтаксически управляемые оп 2.3.4 Обходы дерева 2.3.5 Схемы трансляции 2.3.6 Упражнения к разделу 2.3 Разбор 2.4.1 Нисходящий анализ 2.4.2 Предиктивный анализ 2.4.3 Использование пустых продукций 2.4.4 Разработка предиктивного анализатора 2,4.5 Левая рекурсия 2.4.6 Упражнения к разделу 2.4 Транслятор простых выражений 2.5.1 Абстрактный и конкретный синтаксис 2.5.2 Адаптация схемы трансляции 2.5.3 Процедуры для нетерминалов 2.5.4 Упрощение транслятора 75 76 78 79 8! 82 84 85 86 89 90 91 92 94 95 97 99 100 101 104 106 106 107 109 109 110 111 113 114 Содержание 2.6 2.8 2.9 3.
Лексический анализ Глава 3.1 3.2 3.3 3.4 181 183 2.5.5 Завершенная программа Лексический анализ 2.6.1 Удаление пробельных символов и комментариев 2.6.2 Опережающее чтение 2.6.3 Константы 2.6.4 Распознавание ключевых слов и идентификаторов 2.6.5 Лексический анализатор 2.6.6 Упражнения к разделу 2.6 Таблицы символов 2.7.1 Таблица символов для области видимости 2.7.2 Использование таблиц символов Генерация промежуточного кода 2.8.1 Два вида промежуточных представлений 2.8.2 Построение синтаксических деревьев 2.8.3 Статические проверки 2.8.4 Трехадресный код 2.8.5 Упражнения к разделу 2.8 Резюме к главе 2 Роль лексического анализатора 3.!.1 Лексический и синтаксический анализ 3.1.2 Токены, шаблоны и лексемы 3.1.3 Атрибуты токенов 3.1.4 Лексические ошибки 3.1.5 Упражнения к разделу 3.1 Буферизация ввода 3.2.1 Пары буферов 3.2.2 Ограничители Спецификация токенов 3.3.1 Строки и языки 3.3.2 Операции над языками 3.3.3 Регулярные выражения 3.3.4 Регулярные определения 3.3.5 Расширения регулярных выражений 3.3.6 Упражнения к разделу 3.3 Распознавание токенов 3.4.1 Диаграммы переходов 3.4.2 Распознавание зарезервированных слов и идентификаторов 3.4.3 Завершение примера 115 118 119 120 !г! 12! 123 128 128 129 !33 136 136 137 142 144 151 152 155 155 157 157 159 160 161 162 162 163 165 165 166 168 170 172 173 !77 179 Содержание 3.5 3.6 3.7 3.8 3.9 235 237 242 242 244 3.4.4 Архитектура лексического анализатора на основе диаграммы переходов 3.4.5 Упражнения к разделу 3.4 Генератор лексических анализаторов 1 ех 3.5.1 Использование 1 ех 3.5.2 Структура программ Ьех 3.5.3 Разрешение конфликтов в Ьех 3.5.4 Прогностический оператор 3.5.5 Упражнения к разделу 3.5 Конечные автоматы 3.6.1 Недетерминированные конечные автоматы 3.6.2 Таблицы переходов 3.6.3 Принятие входной строки автоматом 3.6.4 Детерминированный конечный автомат 3.6.5 Упражнения к разделу 3.6 От регулярных выражений к автоматам 3.7.! Преобразование НКА в ДКА 3.7.2 Моделирование НКА 3.7.3 Эффективность моделирования НКА 3.7.4 Построение НКА из регулярного выражения 3.7.5 Эффективность алгоритма обработки строк 3.7.6 Упражнения к разделу 3.7 Разработка генератора лексических анализаторов 3.8.! Структура генерируемого анализатора 3.8.2 Распознавание шаблонов на основе НКА 3.8.3 ДКА для лексических анализаторов 3.8.4 Реализация прогностического оператора 3.8.5 Упражнения к разделу 3.8 Оптимизация распознавателей на основе ДКА 3.9.! Важные состояния НКА 3.9.2 Функции, вычисляемые на синтаксическом дереве 3.9.3 Вычисление пи!1аЫе, бгзгроз и 1аз!роз 3.9.4 Вычисление !о!!обаров 3.9.5 Преобразование регулярного выражения непосредственно в ДКА 3.9.6 Минимизация количества состояний ДКА 3.9.7 Минимизация состояний в лексических анализаторах 3.9.8 Компромисс между скоростью и используемой памятью при моделировании ДКА 3.9.9 Упражнения к разделу 3.9 184 187 191 191 192 196 197 198 199 200 201 201 203 204 205 206 210 210 213 218 221 221 221 223 225 226 228 229 229 231 232 234 10 Содержание 3.10 3.1 1 Резюме к главе 3 Список литературы к главе 3 245 247 Глава 4.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
