Каждый, кто интересовался разработкой компиляторов, несомненно, слышал о знаменитой "Книге Дракона" - "Dragon Book", классическом труде Ахо и Ульмана "Принципы разработки компиляторов". Бурное развитие технологий компиляции привело к рождению нового дракона - книги "Компиляторы: принципы, технологии, инструментарий" Альфреда Ахо, Рави Сети и Джеффри Ульмана. Новая книга начинается с изложения принципов создания компиляторов, проиллюстрированного разработкой простейшего однопроходного компилятора Оставшаяся часть книги посвящена развитию базовых идей и более прогрессивным и современным технологиям, включая такие вопросы, как синтаксический анализ, проверка типов, генерация и оптимизация кода. Строгость изложения материала смягчается большим количеством практических примеров. Написание компиляторов охватывает языки программирования, архитектуру вычислительных систем, теорию языков, алгоритмы и технологию создания программного обеспечения. Помочь в освоении этих технологий и инструментария и призвана данная книга. Несмотря на учебную ориентацию, книга будет полезна всем, кто работает над созданием компиляторов или просто интересуется данной темой.
The file will be sent to selected email address. It may takes up to 1-5 minutes before you received it.
The file will be sent to your Kindle account. It may takes up to 1-5 minutes before you received it.
Please note you"ve to add our email [email protected]
to approved e-mail addresses. Read more .
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you"ve read. Whether you"ve loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
Компиляторы Принципы, технологии, инструменты Альфрел Ахо Рави Сети Джеффри Ульман
Compilers Principles, Techniques, and Tools ALFRED V. AHO AT&T Bell Laboratories Murray Hill, New Jersey RAVI SETHI AT&T Bell Laboratories Murray Hill, New Jersey JEFFREY D. ULLMAN Stanford University Stanford, California A TT ADDISON-WESLEY PUBLISHING COMPANY Reading, Massachusetts Menlo Park, California Don Mills, Ontario Wokingham, England Amsterdam Sydney Singapore Tokyo Mexico City Bogota Santiago San Juan
Компиляторы Принципы, технологии, инструменты АЛЬФРЕД АХО AT&T Bell Laboratories Мюррей Хилл, штат Нью-Джерси РАВИ СЕТИ AT&T Bell Laboratories Мюррей Хилл, штат Нью-Джерси ДЖЕФФРИ УЛЬМАН Станфордский университет Станфорд, штат Калифорния Москва Санкт-Петербург. Киев 2003
ББК 32.973.26-018.2.75 А95 УДК 681.3.07 Издательский дом "Вильяме" Перевод с английского канд.техн.наук И.В. Красикова Под редакцией канд.техн.наук И.В. Красикова и канд.физ.-мат.наукЛ.?. Ставровского Под обшей редакцией канд.техн.наук И.В. Красикова По общим вопросам обращайтесь в Издательский дом "Вильяме" по адресу: [email protected], http://www.williamspublishing.com Лхо, Альфред, В., Сети, Рави, Ульман, Джеффри, Д. А95 Компиляторы: принципы, технологии и инструменты.: Пер. с англ. - М.: Изда- Издательский дом "Вильяме", 2003. - 768 с. : ил. - Парал. тит. англ. ISBN 5-8459-0189-8 (рус.) Каждый, кто интересовался разработкой компиляторов, несомненно, слышал о знамени- знаменитой "Книге Дракона" - "Dragon Book", классическом труде Ахо и Ульмана "Принципы раз- разработки компиляторов". Бурное развитие технологий компиляции привело к рождению но- нового дракона - книги "Компиляторы: принципы, технологии, инструментарий" Альфреда Ахо, Рави Сети и Джеффри Ульмана. Новая книга начинается с изложения принципов создания компиляторов, проиллюстриро- проиллюстрированного разработкой простейшего однопроходного компилятора Оставшаяся часть книги по- посвящена развитию базовых идей и более прогрессивным и современным технологиям, включая такие вопросы, как синтаксический анализ, проверка типов, генерация и оптимизация кода Строгость изложения материала смягчается большим количеством практических при- примеров. Написание компиляторов охватывает языки программирования, архитектуру вы- вычислительных систем, теорию языков, алгоритмы и технологию создания программного обеспечения. Помочь в освоении этих технологий и инструментария и призвана данная книга. Несмотря на учебную ориентацию, книга будет полезна всем, кто работает над соз- созданием компиляторов или просто интересуется данной темой. ББК 32.973.26-018.2.75 Все названия программных продуктов являются зарегистрированными торговыми марками соответст- соответствующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ии было форме и какими бы то ии было средствами, будь то электронные или механические, включая фотокопи- фотокопирование и запись на магнитный носитель, если иа это нет письменного разрешения издательства Addison- Wesley Publishing Company, Inc. Authorized translation from the English language edition published by Addison-WesSey Publishing Company, Inc., Copyright © 1985 ¦ All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Russian language edition published by Williams Publishing House according to the Agreement with R&I Enterprises International, Copyright © 2001 Издательство выражает признательность Дмитрию Владленовичу Виленскому за информационную по- помощь и поддержку. ISBN5-8459-0189-8(pyc.) © Издательский дом "Вильяме", 2001 ISBN0-201 -10088-6(англ.) © Addison-Wesley Publishing Company, Inc., 1985
Оглавление ГЛАВА 1. Введение в компиляцию 22 ГЛАВА 2. Простой однопроходный компилятор 44 ГЛАВА 3. Лексический анализ 97 ГЛАВА 4. Синтаксический анализ 167 ГЛАВА 5. Синтаксически управляемая трансляция 279 ГЛАВА 6. Проверка типов 336 ГЛАВА 7. Среды времени исполнения 376 ГЛАВА 8. Генерация промежуточного кода 443 ГЛАВА 9. Генерация кода 487 ГЛАВА 10. Оптимизация кода 553 ГЛАВА 11. Создание компилятора 679 ГЛАВА 12. Некоторые компиляторы 688 ПРИЛОЖЕНИЕ А. Программный проект 698 ПРИЛОЖЕНИЕ Б. Спецификации языков программирования 704 БИБЛИОГРАФИЯ 742
Содержание От редактора 18 Предисловие 19 Использование данной книги 19 Упражнения 20 Благодарности 21 ГЛАВА 1. Введение в компиляцию 22 1.1. Компиляторы 22 Модель анализа-синтеза компиляции 23 Контекст компилятора 25 1.2. Анализ исходной программы 25 Лексический анализ 26 Синтаксический анализ 26 Семантический анализ ^ 28 Анализ в программах форматирования текста 29 1.3. Фазы компилятора „ 30 Управление таблицей символов 30 Обнаружение ошибок и сообщение о них 31 Фазы анализа 33 Генерация промежуточного кода 34 Оптимизация кода 34 Генерация кода 35 1.4. Родственники компилятора 35 Препроцессоры 35 Ассемблеры 37 Двухпроходный ассемблер 37 Загрузчики и редакторы связей 38 1.5. Группировка фаз 39 Предварительная и заключительная стадии 39 Проходы 40 Уменьшение количества проходов 40 1.6. Инструментарий для создания компиляторов 41 Библиографические примечания 43 ГЛАВА 2. Простой однопроходный компилятор 44 2.1. Обзор 44 2.2. Определение синтаксиса 45 Деревья разбора 47 Неоднозначность 48 Ассоциативность операторов 49 Приоритет операторов 50 6 СОДЕРЖАНИЕ
2.3. Синтаксически управляемая трансляция 51 Постфиксная запись 51 Синтаксически управляемые определения 52 Синтезируемые атрибуты 52 Рекурсивный обход дерева 55 Схемы трансляции 55 Вывод результатов трансляции 56 2.4. Разбор 58 Нисходящий анализ 58 Предиктивный анализ 61 Использование е-продукций 63 Создание предиктивного анализатора 63 Левая рекурсия 64 2.5. Транслятор для простых выражений 65 Абстрактный и конкретный синтаксис 65 Адаптация схемы трансляции 67 Процедуры для нетерминалов expr, term и rest 67 Оптимизация транслятора 69 Полная программа 70 2.6. Лексический анализ 71 Удаление пробелов и комментариев 71 Константы 72 Распознавание идентификаторов и ключевых слов 72 Интерфейс к лексическому анализатору 73 Лексический анализатор 74 2.7. Использование таблиц символов 76 Интерфейс таблицы символов 76 Обработка зарезервированных ключевых слов 77 Реализация таблицы символов 77 2.8. Абстрактная стековая машина 79 Арифметические инструкции 79 1-значения и г-значения 80 Работа со стеком 80 Трансляция выражений 80 Управление выполнением 81 Трансляция инструкций 82 Вывод результатов трансляции 82 2.9. Сборка транслятора 84 Описание транслятора 84 Модуль лексического анализа lexer. с 85 Модуль синтаксического анализатора parser. с 86 Модуль вывода emitter. с 87 Модули работы с таблицей символов symbol. с и init. с 87 Модуль обработки ошибок error. с 87 Создание компилятора 87 Листинг 88 Упражнения 92 СОДЕРЖАНИЕ 7
Программные упражнения 95 Библиографические примечания 96 ГЛАВА 3. Лексический анализ 97 3.1. Роль лексических анализаторов 97 Задачи лексического анализа 98 Токены, шаблоны, лексемы 99 Атрибуты токенов 100 Лексические ошибки 101 3.2. Буферизация ввода 102 Пары буферов 102 Ограничители 104 3.3. Определение токенов 105 Строки и языки 105 Операции над языками 106 Регулярные выражения 107 Регулярные определения 109 Сокращения 110 Нерегулярные множества ПО 3.4. Распознавание токенов 111 Диаграммы переходов 112 Реализация диаграммы переходов 116 3.5. Язык спецификации лексических анализаторов 119 Спецификации Lex 119 Прогностический оператор 123 3.6. Конечные автоматы 125 Недетерминированные конечные автоматы 125 Детерминированный конечный автомат 127 Преобразование НКА в ДКА 12 8 3.7. От регулярного выражения к НКА 132 Построение НКА по регулярному выражению 132 Двустековое моделирование НКА 136 Скорость работы 13 7 3.8. Построение генератора лексических анализаторов 139 Поиск по шаблону на основе НКА 140 ДКА для лексического анализа 142 Реализация прогностического оператора 143 3.9. Оптимизация поиска соответствия шаблону на базе ДКА 144 Важные состояния в НКА 144 От регулярного выражения к ДКА 145 Минимизация количества состояний ДКА 150 Минимизация состояний в лексических анализаторах 153 Методы сжатия таблиц 153 Упражнения 155 Программные упражнения 165 Библиографические примечания 165 СОДЕРЖАНИЕ
ГЛАВА 4. Синтаксический анализ 167 4.1. Роль синтаксического анализатора 167 Обработка синтаксических ошибок 168 Стратегии восстановления после ошибок 172 4.2. Контекстно-свободные грамматики 173 Соглашения по обозначениям 174 Порождение 175 Деревья разбора и приведения 177 Неоднозначность 179 4.3. Разработка грамматики 179 Регулярные выражения и контекстно-свободные грамматики 180 Проверка языка, порожденного грамматикой 181 Устранение неоднозначности 181 Устранение левой рекурсии 183 Левая факторизация 185 Построение не-контекстно-свободных грамматик 186 4.4. Нисходящий анализ 188 Анализ методом рекурсивного спуска 188 Предиктив"ные анализаторы 189 Диаграммы переходов предиктивных синтаксических анализаторов 190 Нерекурсивный предиктивный анализ 192 FIRST и FOLLOW 195 Построение таблиц предиктивного анализа 197 LL(1)-грамматики 197 Восстановление после ошибок в предиктивном анализе 199 4.5. Восходящий синтаксический анализ 201 Основы 202 Обрезка основ 204 Стековая реализация ПС-анализа 205 Активные префиксы 207 Конфликты в процессе ПС-анализа 207 4.6. Синтаксический анализ приоритета операторов 209 Использование отношений приоритетов операторов 211 Нахождение отношений приоритетов операторов 213 Обработка унарных операторов 214 Функции приоритета 214 Восстановление после ошибок при синтаксическом анализе приоритета операторов 216 4.7. LR-анализаторы 220 Алгоритм LR-анализа 221 LR-грамматики 225 Построение таблиц SLR-анализа 226 Построение канонических таблиц LR-анализа 234 Построение таблиц LARL-анализа 240 Эффективное построение таблиц LALR-анализа 244 4.8. Использование неоднозначных грамматик 250 Использование приоритетов и ассоциативности для разрешения конфликтов 251 СОДЕРЖАНИЕ 9
Неоднозначность "кочующего" else * , 253 Неоднозначности особых продукций частных случаев 255 Восстановление после ошибок при LR-анализе 257 4.9. Генераторы синтаксических анализаторов 259 Генератор синтаксических анализаторов Yacc 260 Использование Yacc с неоднозначной грамматикой 263 Создание лексического анализатора в Yacc с помощью Lex 265 Восстановление после ошибок в Yacc 266 Упражнения 268 Библиографические примечания 277 ГЛАВА 5. Синтаксически управляемая трансляция 279 5.1. Синтаксически управляемые определения 280 Вид синтаксически управляемого определения 280 Синтезируемые атрибуты 281 Наследуемые атрибуты 282 Графы зависимости 283 Порядок выполнения 285 5.2. Построение синтаксических деревьев 286 Синтаксические деревья щ, 286 Построение синтаксических деревьев для выражений 287 Синтаксически управляемое определение для построения синтаксических деревьев 288 Направленные ациклические графы выражений 289 5.3. Восходящее выполнение S-атрибутных определений 292 Синтезируемые атрибуты в стеке синтаксического анализатора 292 5.4. L-атрибутные определения 295 L-атрибутные определения 295 Схемы трансляции 296 5.5. Нисходящая трансляция 299 Устранение левой рекурсии из схемы трансляции 299 Разработка предиктивного транслятора 303 5.6. Восходящее вычисление наследуемых атрибутов 305 Удаление внедренных действий из схемы трансляции 305 Наследование атрибутов в стеке синтаксического анализатора 306 Моделирование вычисления наследуемых атрибутов 308 Замена наследуемых атрибутов синтезируемыми 312 Сложное синтаксически управляемое определение 312 5.7. Рекурсивные вычислители 312 Обход слева направо 313 Другие обходы 314 5.8. Память для значений атрибутов во время компиляции 315 Назначение памяти атрибутам во время компиляции 317 Устранение копий 318 5.9. Назначение памяти в процессе создания компилятора 319 Вычисление времени жизни по грамматике 319 Неперекрывающиеся времена жизни 323 10 СОДЕРЖАНИЕ
5.10. Анализ синтаксически управляемых определений 324 Рекурсивное вычисление атрибутов 325 Строго нецикличные синтаксически управляемые определения 327 Проверка цикличности 328 Упражнения « 330 Библиографические примечания 334 ГЛАВА 6. Проверка типов 336 6.1. Системы типов 337 Выражения типов 338 Системы типов 339 Статическая и динамическая проверка типов 340 Восстановление после ошибки 340 6.2. Спецификация простой программы проверки типов 341 Простой язык 341 Проверка типов выражений 342 Проверка типов инструкций 343 Проверка типов функций 343 6.3. Эквивалентность выражений типа J 344 Структурная эквивалентность выражений типа 344 Имена выражений типа 347 Циклы в представлениях типов 349 6.4. Преобразования типов 350 Неявное преобразование типов 350 6.5. Перегрузка функций и операторов 352 Множество возможных типов подвыражения 352 Сужение множества возможных типов 354 6.6. Полиморфные функции 355 Почему используются полиморфные функции 355 Переменные типа 356 Язык с полиморфными функциями 358 Подстановки, примеры и унификация 360 Проверка полиморфных функций 361 6.7. Алгоритм унификации 365 Упражнения 369 Библиографические примечания 374 ГЛАВА 7. Среды времени исполнения 376 7.1. Вопросы исходного языка 376 Процедуры 376 Деревья активации 377 Стеки управления 379 Область видимости объявления 380 Организация памяти и связывание имен 382 7.2. Организация памяти 382 Классификация памяти времени выполнения 382 Записи активаций 384 СОДЕРЖАНИЕ 11
Размещение локальных данных в процессе компиляции 385 7.3. Стратегии выделения памяти 386 Статическое распределение памяти 387 Стековое распределение памяти 389 Висячие ссылки 394 Распределение памяти в куче 395 7.4. Доступ к нелокальным именам 396 Блоки 396 Лексическая область видимости без вложенных процедур 398 Лексическая область видимости при наличии вложенных процедур 400 Дисплеи 403 Динамическая область видимости 406 7.5. Передача параметров 407 Передача по значению 408 Передача по ссылке 409 Копирование-восстановление 410 Передача по имени 411 7.6. Таблицы символов 412 Записи таблицы символов 413 Символы имени ^ 414 Информация о выделенной памяти 415 Использование списков для представления таблицы символов 415 Хеш-таблицы 416 Представление информации об области видимости 420 7.7. Возможности языков по динамическому выделению памяти 422 Мусор 424 Висячие ссылки 424 7.8. Технологии динамического распределения памяти 425 Явное выделение блоков фиксированного размера 425 Явное выделение блоков переменного размера 426 Неявное освобождение 426 7.9. Распределение памяти в Fortran 428 Данные в областях COMMON 429 Простой алгоритм эквивалентности 430 Алгоритм эквивалентности для языка программирования Fortran 433 Отображение областей данных 435 Упражнения 436 Библиографические примечания 442 ГЛАВА 8. Генерация промежуточного кода 443 8.1. Языки промежуточных представлений 443 Графическое представление 444 Трехадресный код 445 Типы трехадресных инструкций 446 Синтаксически управляемая трансляция в трехадресный код 447 Реализация трехадресных инструкций 449 Сравнение представлений: использование косвенного обращения 451 12 СОДЕРЖАНИЕ
8.2. Объявления 452 Объявления в процедуре 452 Отслеживание информации об области видимости 453 Имена полей в записях 455 8.3. Инструкции присвоения 456 Имена в таблице символов 456 Повторное использование временных имен 458 Адресация элементов массива 459 Схема трансляции для адресации элементов массива 461 Преобразования типов в присвоениях 463 Доступ к полям записей 465 8.4. Логические выражения 465 Методы трансляции логических выражений 466 Числовое представление 466 Сокращенные вычисления 467 Инструкции потока управления 468 Трансляция логических выражений с помощью потока управления 470 Смешанные логические выражения 471 8.5. Инструкции case 473 Синтаксически управляемая трансляция инструкции case 474 8.6. Технология обратных поправок 476 Логические выражения 476 Инструкции потока управления 479 Схема реализации трансляции 479 Метки и безусловные переходы 481 8.7. Вызовы процедур 481 Вызывающие последовательности 481 Простой пример 482 Упражнения 483 Библиографические примечания 485 ГЛАВА 9. Генерация кода 487 9.1. Вопросы создания генератора кода 487 Вход генератора кода 487 Целевые программы 488 Управление памятью 489 Выбор инструкций 489 Распределение регистров 490 Выбор порядка вычислений 491 Подходы к генерации кода 491 9.2. Целевая машина 492 Стоимость инструкции 493 9.3. Управление памятью во время исполнения 494 Статическое распределение 495 Стековое распределение 497 Адресация имен во время исполнения 499 9.4. Базовые блоки и графы потоков 500 СОДЕРЖАНИЕ 13
Базовые блоки 500 Преобразования в базовых блоках 502 Преобразования, сохраняющие структуру 502 Алгебраические преобразования 503 Графы потоков 503 Представление базовых блоков 504 Циклы 505 9.5. Информация о последующем использовании 505 Вычисление последующих использований 505 Память для временных имен 506 9.6. Простой генератор кода 507 Дескрипторы регистров и адресов 508 Алгоритм генерации кода 508 Функция getreg 509 Генерация кода для других типов инструкций 511 Условные инструкции 512 9.7. Распределение и назначение регистров 512 Глобальное распределение регистров 513 Счетчики использований 513 Назначение регистров для внешних циклов 516 Распределение регистров путем раскраски графа 516 9.8. Представление базовых блоков в виде дага 517 Построение дага 518 Применение дагов 520 Массивы, указатели и вызовы процедур 522 9.9. Локальная оптимизация 524 Излишние загрузки и сохранения 524 Недостижимый код 525 Оптимизация потока управления 526 Алгебраические упрощения 527 Снижение стоимости 527 Использование машинных идиом 527 9.10. Генерация кода на основе дагов 527 Переупорядочение 528 Эвристическое упорядочение дагов 529 Оптимальное упорядочение для деревьев 530 Алгоритм назначения меток 531 Генерация кода на основе помеченного дерева 532 Многорегистровые операции 535 Алгебраические свойства 535 Общие подвыражения 536 9.11. Алгоритм динамического программирования для генерации кода 537 Класс регистровых машин 538 Принцип динамического программирования 538 Последовательное вычисление 538 Алгоритм динамического программирования 539 9.12. Генераторы генераторов кода 541 14 СОДЕРЖАНИЕ
Генерация кода путем преобразования дерева Проверка соответствия шаблону путем синтаксического анализа Программы семантической проверки Упражнения Библиографические примечания ГЛАВА 10. Оптимизация кода 10.1. Введение Критерии для преобразований, улучшающих код Повышение производительности Организация оптимизирующего компилятора 10.2. Основные источники оптимизации Преобразования, сохраняющие функции Общие подвыражения Распространение копий Удаление бесполезного кода Оптимизации циклов Перемещение кода Переменные индукции и снижение стоимости 10.3. Оптимизация базовых блоков Использование алгебраических тождеств 10.4. Циклы в графах потока Доминаторы Естественные циклы Внутренние циклы Предзаголовки Приводимые графы потоков 10.5. Введение в глобальный анализ потоков данных Точки и пути Достигающие определения Анализ потока данных структурированной программы Консервативная оценка информации потока данных Вычисление in и out Работа с циклами Представление множеств Локальные достигающие определения Цепочки определений использований Порядок вычислений Общий поток управления 10.6. Итеративное решение уравнений потока данных Итеративный алгоритм для достигающих определений Доступные выражения Анализ активных переменных Цепочки использований определений 10.7. Преобразования, улучшающие код Устранение глобальных общих подвыражений Распространение копирований СОДЕРЖАНИЕ
Поиск вычислений, инвариантных относительно цикла 601 Выполнение перемещения кода 602 Альтернативные стратегии перемещения кода 604 Поддержание информации о потоке данных после перемещения кода 605 Устранение переменных индукции 605 Переменные индукции и выражения, инвариантные относительно цикла 610 10.8. Работа с альтернативными именами 610 Простой язык указателей 611 Воздействие присвоений указателей 611 Использование информации об указателях 614 Анализ межпроцедурного потока данных 615 Модель кода с вызовами процедур 616 Вычисление псевдонимов 617 Анализ потока данных при наличии вызовов процедур 618 Использование информации об изменениях 621 10.9. Анализ потока данных структурированных графов потока 622 Поиск вглубь 622 Дуги представления графа потока вглубь 625 Глубина графа потока 626 Интервалы 626 Разбиение на интервалы 627 Графы интервалов 628 Разделение узлов 629 ГгГ2-анализ 629 Области 630 Поиск доминаторов 631 10.10. Эффективные алгоритмы потоков данных 633 Упорядочение вглубь в итеративных алгоритмах 633 Анализ потока данных, основанный на структуре 635 Некоторые ускорения структурного алгоритма 639 Обработка неприводимых графов потока 639 10.11. Средства для анализа потока данных 640 Схема анализа потока данных 641 Аксиомы схем анализа потока данных 643 Монотонность и дистрибутивность 644 Решения типа "слияние всех путей" в задачах о потоках данных 648 Консервативные решения задач о потоках 649 Итеративный алгоритм для обобщенных схем 650 Инструмент анализа потока данных 650 Свойства алгоритма 10.18 651 Сходимость алгоритма 10.18 652 Исправление инициализации 653 10.12. Оценка типов 653 Работа с бесконечными множествами типов 654 Простая система типов 656 Прямая схема 657 Обратная схема 658 16 СОДЕРЖАНИЕ
10.13. Символьная отладка оптимизированного кода 661 Отслеживание значений переменных в базовых блоках 662 Влияние глобальной оптимизации 667 Устранение переменных индукции 667 Устранение глобальных общих подвыражений 667 Перемещение кода 668 Упражнения 669 Библиографические примечания 675 ГЛАВА 11. Создание компилятора 679 11.1. Планирование компилятора 679 Вопросы исходного языка 679 Вопросы целевого языка 680 Критерии производительности 680 11.2. Подходы к разработке компилятора 680 Раскрутка 681 11.3. Среда разработки компилятора 684 11.4. Тестирование и сопровождение 686 ГЛАВА 12. Некоторые компиляторы 688 12.1. Препроцессор математических формул EQN 688 12.2. Компиляторы Pascal 689 12.3. Компиляторы С 690 12.4. Компиляторы Fortran H 691 Оптимизация кода в Fortran H 693 Алгебраическая оптимизация 693 Оптимизация регистров 694 12.5. Компилятор Bliss/11 694 12.6. Оптимизирующий компилятор Modula-2 696 ПРИЛОЖЕНИЕ А. Программный проект 698 АЛ. Введение 698 А.2. Структура программы 698 А.З. Синтаксис подмножества Pascal 699 А.4. Лексические соглашения 701 А.5. Предлагаемые упражнения 701 А.6. Эволюция интерпретатора 703 А.7. Расширения 703 ПРИЛОЖЕНИЕ Б. Спецификации языков программирования 704 Б. 1. Язык программирования C++ 704 Б.2. Язык программирования С# 721 БИБЛИОГРАФИЯ 742 Предметный указатель 764 СОДЕРЖАНИЕ 17
От редактора Перед вами перевод известной книги знаменитых авторов, перу которых принадлежит ряд бестселлеров в области компьютерных наук, причем диапазон их плодотворной ра- работы чрезвычайно широк- от фундаментальных научных статей до великолепных учебников для студентов. Именно таким учебником и является данная книга, которая доступна широкому кругу программистов и представляет собой завершенное изложение технологий построения компиляторов. Многие работы этих авторов переведены на русский язык и неизменно пользуются повышенным спросом у серьезного читателя. Достаточно вспомнить такие книги, как Построение и анализ вычислительных алгоритмов , Структуры данных и алго- алгоритмы или Теория синтаксического анализа, перевода и компиляции . Предлагаемая книга выгодно отличается от большинства своих предшественниц тем, что здесь охвачен весь процесс создания компилятора - от лексического анализа до ге- генерации и оптимизации целевого кода. Использование абстрактных математических по- понятий доводится в ней до конкретных алгоритмов, пригодных для непосредственной реализации. Технологии, изложенные в этой книге, уже нашли свое применение не толь- только в компиляции, но и в системах подготовки текстов, управления базами данных, гене- генерации схем электронных устройств и других областях. Оригинал этой книги опубликован в 1988 году. С тех пор были созданы новые пара- парадигмы программирования, десятки новых языков и компиляторов для них. Однако осме- осмелимся утверждать, что в их реализации не было ничего принципиально нового по срав- сравнению с тем, что изложено в этой книге. Данное издание может служить практическим руководством по технологиям создания компиляторов. Описанные в ней технологии бы- были созданы в основном еще в 60-е-80-е годы и существенно уже не изменятся. Книга по праву может считаться классической, потому что она не устарела и не устареет, пока лю- люди будут создавать языки и системы программирования.
Предисловие Данное издание является развитием книги Альфреда Ахо и Джеффри Ульмана Principles of Computer Design. Подобно своей предшественнице, она задумана как начальный учеб- учебный курс по проектированию компиляторов. Основное внимание уделяется решению общих проблем, возникающих при создании трансляторов языков программирования, независимо от исходного языка или целевой машины. Вероятно, лишь немногие из вас будут заниматься построением или поддержкой компиляторов для основных языков программирования, однако идеи и технологии, опи- описанные в ней, можно с успехом применять при разработке другого программного обес- обеспечения. Например, технологии поиска соответствия строк шаблонам, используемые при построении лексических анализаторов, применяются и в текстовых редакторах, и в сис- системах выборки информации, и в распознавании образов. Контекстно-свободные грамма- грамматики и синтаксически управляемые определения используются для создания многих не- небольших языков, например типографских систем для подготовки макетов книг. Техноло- Технологии оптимизации кода применяются для проверки корректности программ и создания "структурированных" программ из неструктурированных. Использование данной книги В книге глубоко раскрыты основные аспекты создания компиляторов. Глава 1 описы- описывает базовую структуру компилятора и представляет собой фундамент для остального материала книги. В главе 2 рассматривается транслятор, переводящий инфиксные выражения в пост- постфиксные. Он построен с использованием базовых технологий, описываемых в этой кни- книге. В следующих главах развивается изложенный здесь материал. Глава 3 посвящена лексическому анализу, регулярным выражениям, конечным авто- автоматам и инструментарию для создания сканеров входного потока. Материал этой главы может быть широко использован при разработке текстовых редакторов. Глава 4 пополняет наши знания о технологиях синтаксического анализа. Здесь рас- рассматриваются как методы рекурсивного спуска, применяемые при ручной реализации трансляторов, так и более сложные и универсальные LR-технологии, используемые в ге- генераторах синтаксических анализаторов. Глава 5 знакомит нас с принципиальными идеями синтаксически управляемой транс- трансляции. Материал этой главы используется в оставшейся части книги как для описания, так и реализации трансляторов. В главе 6 выдвигаются основные идеи выполнения статической семантической про- проверки и детально рассматриваются вопросы проверки типов. В главе 7 обсуждаются вопросы организации памяти для поддержки сред времени исполнения программ. Глава 8 начинается с обсуждения языков промежуточного представления программ, а затем показывает нам, каким образом основные конструкции языка программирования могут транслироваться в промежуточный код. Глава 9 посвящена генерации целевого кода, включая вопросы генерации кода "на лету" и оптимальные методы генерации кода для выражений. Здесь также рассмотрены локальная оптимизация и генераторы генераторов кода. ПРЕДИСЛОВИЕ 19
Глава 10 представляет исчерпывающую информацию об оптимизации кода. В ней де- детально изложены методы анализа потока данных, а также основные методы глобальной оптимизации. В главе 11 обсуждается ряд практических вопросов, возникающих при реализации компиляторов, в частности важность вопросов разработки программного обеспечения и тестирования. В главе 12 проведено исследование компиляторов, построенных с использованием представленных в книге технологий. Приложение А описывает простой язык- "подмножество" Pascal, который может использоваться в качестве основы для реальных проектов. На основе этой книги авторы преподавали как вводный, так и основной курсы для студентов и аспирантов AT&T Bell Laboratories, Колумбийского, Принстонского и Стан- фор дского университетов. Вводный курс, посвященный компиляторам, может основываться на материале сле- следующих разделов книги. Введение Глава 1 и разделы 2.1-2.5 Лексический анализ 2.6,3.1-3.4 Таблицы символов 2.7, 7.6 Синтаксический анализ 2.4, 4.1-4.4 Синтаксически управляемая трансляция 2.5, 5.1-5.5 Проверка типов 6.1, 6.2 Организация времени исполнения 7.1-7.3 Генерация промежуточного кода 8.1-8.3 Генерация кода 9.1-9.4 Оптимизация кода 10.1,10.2 Информация, необходимая для программного проекта, подобного приведенному в приложении А, имеется в главе 2. Курс, посвященный инструментарию построения компиляторов, может включать об- обсуждение генераторов лексических анализаторов из раздела 3.5, генераторов синтакси- синтаксических анализаторов из разделов 4.8 и 4.9, генераторов генераторов кода из раздела 9.12, а также материал о технологиях построения компиляторов из главы 11. Основной курс может делать упор на алгоритмы, используемые в генераторах лекси- лексических и синтаксических анализаторов (главы 3 и 4); материал об эквивалентности ти- типов, перегрузке, полиморфизме и унификации (глава 6), организации памяти времени исполнения (глава 7); методы генерации кода на основе шаблонов из главы 9; и материал об оптимизации кода из главы 10. Упражнения Как и ранее, сложность упражнений указана звездочками. Упражнения без звездочек проверяют понимание определений, упражнения с одной звездочкой относятся к более сложному курсу, а "двухзвездные" служат "пищей" для серьезных размышлений. 20 ПРЕДИСЛОВИЕ
Благодарности На различных этапах написания этой книги мы получили множество неоценимых комментариев и советов от большого числа специалистов. В связи с этим мы выражаем свою признательность Биллу Эппельбу (Bill Appelbe), Нельсону Бибу (Nelson Beebe), Джону Бентли (Jon Bentley), Луи Богесу (Lois Bogess), Родни Фэрроу (Rodney Farrow), Стью Фельдман (Stu Feldman), Чарльзу Фишеру (Charles Fischer), Крису Фрэзеру (Chris Fraser), Арту Життельману (Art Gittelman), Эрику Гроссе (Eric Grosse), Дэйву Хансону (Dave Hanson), Фрицу Хенглайну (Fritz Henglein), Роберту Генри (Robert Henry), Жерару Хольцману (Gerard Holzmann), Стиву Джонсону (Steve Johnson), Брайену Кернигану (Brian Kernighan), Кену Кубота (Ken Kubota), Дэниэлу Леману (Daniel Lehmann), Дэйву Мак-Квину (Dave MacQueen), Дианне Маки (Dianne Maki), Алану Мартину (Alan Martin), Дугу Мак-Илрою (Doug Mcllroy), Чарльзу Мак-Лафлину (Charles McLaughlin), Джону Митчеллу (John Mitchell), Эллиоту Органику (Elliot Organick), Роберту Пейджу (Robert Paige), Филу Пфайфферу (Phil Pfeiffer), Робу Пайку (Rob Pike), Кари-Йоко Ряйхя (Kari- Jouko Raiha), Дэнису Ритчи (Dennis Ritchie), Срираму Санкару (Sriram Sankar), Полу Сто- Стокеру (Paul Stoecker), Бьерну Страуструпу (Bjarne Stroustrup), Тому Шимански (Tom Szy- manski), Киму Трейси (Kim Tracy), Петеру Вайнбергеру (Peter Weinberger), Дженнифер Видом (Jennifer Widom) и Рейнгарду Вильгельму (Reinhard Wilhelm). Оригинал этой книги создан с использованием великолепного программного обес- обеспечения, доступного в UNIX. Команда типографского набора выглядела следующим образом. pic files | tbl | eqn | troff -ms Pic- это язык Брайена Кернигана (Brian Kernighan) для набора рисунков; мы особо признательны Брайену за успешное удовлетворение наших обширных потребностей в иллюстрациях, tbl - это язык Майка Леска (Mike Lesk), предназначенный для макети- макетирования таблиц; eqn - язык Брайена Кернигана (Brian Kernighan) и Лоринды Черри (Lorinda Cherry) для печати математических формул; troff - программа Джо Оссана (Joe Ossana) для форматирования текста при фотонаборе (в нашем случае - для Мег- genthaler Linotron 202/N). Пакет макросов ms разработан Майком Леском (Mike Lesk). И наконец, с текстом мы работали с помощью make Стью Фельдман (Stu Feldman); пере- перекрестные ссылки в тексте обрабатывались посредством awk, созданного Альфредом Ахо (Alfred Aho), Брайеном Керниганом (Brian Kernighan) и Петером Вайнбергером (Peter Weinberger), и sed Ли Мак-Мэхона (Lee McMahon). Авторы должны отдельно поблагодарить Патрицию Соломон (Patricia Solomon) за помощь в подготовке книги для фотокомпозиции. Во время работы над книгой поддерж- поддержку Джеффри Ульману (Jeffrey Ullman) оказало Эйнштейновское общество Академии ис- искусств и науки Израиля. И наконец, авторы признательны AT&T Bell Laboratories за под- поддержку во время подготовки рукописи. A.V.A., R.S., J.D.U. ПРЕДИСЛОВИЕ 21
ГЛАВА 1 Введение в компиляцию Принципы и технологии написания компиляторов столь распространены, что идеи, опи- описанные в этой книге, используются в самых разных областях информационных техноло- технологий. Написание компиляторов охватывает языки программирования, архитектуру вычис- вычислительных систем, теорию языков, алгоритмы и технологию создания программного обеспечения. К счастью, при создании трансляторов для широкого круга языков и машин достаточно лишь нескольких основных технологий написания компиляторов. В этой гла- главе мы приступим к рассмотрению компонентов компиляторов, среды, в которой они ра- работают, и программного инструментария, упрощающего их создание. 1.1. Компиляторы Компилятор - это программа, которая считывает текст программы, написанной на одном языке - исходном, и транслирует (переводит) его в эквивалентный текст на дру- другом языке- целевом (рис. 1.1). Одним из важных моментов трансляции является сооб- сообщение пользователю о наличии ошибок в исходной программе. Исходная программа" Компилятор > Целевая программа Сообщения об ошибках Рис. 1.1. Компилятор На первый взгляд, разнообразие компиляторов потрясает. Используются тысячи ис- исходных языков, от традиционных, таких как Fortran и Pascal, до специализированных, возникающих во всех областях компьютерных приложений. Целевые языки не менее разнообразны - это могут быть другие языки программирования, различные машинные языки - от языков микропроцессоров до суперкомпьютеров. Иногда компиляторы клас- классифицируют как однопроходные, многопроходные, исполняющие (load-and-go), отлажи- отлаживающие, оптимизирующие - в зависимости от предназначения и принципов и техноло- технологий их создания. Несмотря на кажущуюся сложность и разнообразие, основные задачи, выполняемые различными компиляторами, по сути, одни и те же. Понимая эти задачи, мы можем создавать компиляторы для различных исходных языков и целевых машин с использованием одних и тех же базовых технологий. Знания об организации и написании компиляторов существенно возросли со времен первых компиляторов, появившихся в начале 1950-х гг. Сегодня сложно определить, ко- когда именно появился на свет первый компилятор, поскольку в те годы проводилось мно-
жество экспериментов и разработок различными независимыми группами. В основном целью этих разработок было преобразование в машинный код арифметических формул. В 50-х годах о компиляторах ходила слава как о программах, крайне сложных в написании (например, первый компилятор Fortran потребовал 18 человеко-лет работы ). С тех пор разработаны разнообразные систематические технологии решения многих задач, возникаю- возникающих при компиляции. Кроме того, разработаны хорошие языки реализации, программные среды и программный инструментарий. Благодаря этому "солидный" компилятор может быть реализован даже в качестве курсовой работы по проектированию компиляторов. Модель анализа-синтеза компиляции Компиляция состоит из двух частей: анализа и синтеза. Анализ - это разбиение ис- исходной программы на составные части и создание ее промежуточного представления. Синтез - конструирование требуемой целевой программы из промежуточного пред- представления. В разделе 1.2 мы неформально рассмотрим анализ, а способ синтеза целевого кода в стандартных компиляторах будет представлен в разделе 1.3. В процессе анализа определяются и записываются в иерархическую древовидную структуру операции, заданные исходной программой. Часто используется специальный вид дерева, называемого синтаксическим (или деревом синтаксического разбора), в ко- котором каждый узел представляет операцию, а его дочерние узлы - аргументы операции. Пример синтаксического дерева инструкции присвоения показан на рис. 1.2. position + initial * rate 60 Рис. 1.2. Синтаксическое дерево для оператора posi tion: =ini tial+rate*60 Многие программные инструменты, работающие с исходными программами, сначала выполняют определенный вид анализа. Рассмотрим примеры таких инструментов. 1. Структурные редакторы. Эти программы получают в качестве входа последова- последовательность команд для построения исходной программы. Такой редактор не только выполняет обычные для текстового редактора функции по созданию и модификации текста, но и анализирует текст программы, помещая в исходную программу соответ- соответствующую иерархическую структуру. Тем самым он выполняет дополнительные за- задачи, облегчающие подготовку программы. Например, редактор может проверять корректность введенного текста, автоматически добавлять структурные элементы (так, если пользователь введет while, редактор добавит соответствующее ему клю- ключевое слово do и предложит ввести условное выражение между ними) или перехо- переходить от ключевого слова begin или левой скобки к соответствующему end или правой скобке. Более того, выход такого редактора зачастую подобен выходу после фазы анализа компиляции. 2. Программы форматированного вывода на печать. С помощью этих инструментов программа анализируется и распечатывается таким образом, чтобы ее структура бы- была максимально ясной. Например, комментарии могут быть выделены специальным шрифтом, а операторы - выведены с отступами, указывающими уровень вложенно- вложенности в иерархической структуре операторов. 1.1. КОМПИЛЯТОРЫ 23
3. Статические проверяющие программы. Данные инструменты считывают програм- программы, анализируют их и пытаются найти потенциальные ошибки без запуска програм- программы. Такой анализ зачастую очень похож на анализ в оптимизирующих компилято- компиляторах, обсуждаемых в главе 10, "Оптимизация кода". Например, статическая прове- проверяющая программа может определить невыполнение какой-то части исходной программы или использование некоторой переменной до ее объявления. Точно так же могут быть обнаружены логические ошибки, например попытки использования действительной переменной в качестве указателя (с применением технологии про- проверки типов, обсуждаемой в главе 6, "Проверка типов"). 4. Интерпретаторы. Вместо создания целевой программы в результате трансляции интерпретатор выполняет операции, указанные в исходной программе. Например, для оператора присвоения он может построить дерево, подобное приведенному на рис. 1.2, а затем выполнить операции, проходя по его узлам. Корень дерева указыва- указывает на выполнение присвоения, так что интерпретатор вызовет подпрограмму для вы- вычисления выражения, определяемого правым поддеревом, а затем сохранит его зна- значение в переменной position. Правое поддерево указывает подпрограмме, что она должна вычислить сумму двух выражений. Рекурсивный вызов подпрограммы при- приводит к вычислению значения rate*60, которое затем суммируется со значением переменной initial. Интерпретаторы часто используются для командных языков, поскольку каждый их оператор представляет собой вызов сложной программы, такой как редактор или ком- компилятор. Точно так же и некоторые языки "очень высокого уровня", типа APL, обычно интерпретируются, поскольку имеется множество атрибутов данных, таких как размер или тип массива, которые не могут быть определены в процессе компиляции. Традиционно мы говорим о компиляторе как о программе, которая транслирует ис- исходный язык типа Fortran в ассемблер или машинный язык. Однако имеются и другие применения технологии компиляции. Так, анализирующая часть в каждом из приведен- приведенных ниже примеров подобна анализатору обычного компилятора. 1. Форматирование текста. Программа форматирования текста получает на вход по- поток символов, большинство из которых представляет выводимый текст, но многие из символов означают абзацы, рисунки или математические структуры, например верх- верхние или нижние индексы. Мы вернемся к использованию анализа при форматирова- форматировании текста в следующем разделе. 2. "Кремниевые" компиляторы (Silicon compilers). Такой компилятор имеет исходный язык, схожий с обычным языком программирования. Однако переменные языка представляют не положения в памяти, а логические сигналы @ или 1) или группы сигналов в коммутируемых линиях. На выходе такого компилятора получается схе- схема устройства на соответствующем языке. (Детальнее об этих компиляторах см. в , или .) 3. Интерпретаторы запросов. Данные интерпретаторы транслируют предикаты, со- содержащие операторы отношений и логические операторы, в команды поиска в базе данных записей, удовлетворяющих данному предикату (см. и I. " В настоящее время наличие языка структурированных запросов SQL снимает вопрос о том, явля- является ли интерпретация запросов задачей, всего лишь схожей с компиляцией. - Прим. перев. 24 ГЛАВА!. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ
Контекст компилятора При создании целевой программы, кроме компилятора, может потребоваться и ряд других программ. Исходная программа может быть разделена на модули, хранимые в отдельных файлах. Задача сбора исходной программы иногда поручается отдельной про- программе - препроцессору, который может также раскрывать в тексте исходной програм- программы сокращения, называемые макросами. На рис. 1.3 показана типичная "компиляция". Целевая программа, создаваемая ком- компилятором, может потребовать дополнительной обработки перед запуском. Компилятор, представленный на рис. 1.3, создает ассемблерный код, который переводится ассембле- ассемблером в машинный код, а затем связывается ("линкуется") совместно с некоторыми биб- библиотечными программами в реально запускаемый на машине код. В следующих двух разделах мы рассмотрим компоненты компилятора; остальные программы, представленные на рис. 1.3, будут рассмотрены в разделе 1.4. Скелетная исходная программа 1 Препроцессор т Исходная программа 1 Компилятор т Целевая ассемблерная программа 1 Ассемблер т Перемещаемый машинный код Загрузчик/редактор связей - Библиотека, объектные файлы Абсолютный машинный код Рис. 1.3. Система обработки языка 1.2. Анализ исходной программы В этом разделе будет рассмотрен процесс анализа и проиллюстрировано его исполь- использование в некоторых языках форматирования текста. Детальнее об этом будет говорить- говориться в главах 2-4 и 6. При компиляции анализ состоит из трех фаз. 1.2. АНАЛИЗ ИСХОДНОЙ ПРОГРАММЫ 25
1. Линейный анализ, при котором поток символов исходной программы считывается слева направо и группируется в токены (token), представляющие собой последова- последовательности символов с определенным совокупным значением. 2. Иерархический анализ, при котором символы или токены иерархически группиру- группируются во вложенные конструкции с совокупным значением. 3. Семантический анализ, позволяющий проверить, насколько корректно совместное размещение компонентов программы. Лексический анализ В компиляторах линейный анализ называется лексическим, или сканированием. На- Например, при лексическом анализе символы в инструкции присвоения position:= initial + rate * 60 будут сгруппированы в следующие токены. 1. Идентификатор position. 2. Символ присвоения: =. 3. Идентификатор initial. 4. Знак сложения. 5. Идентификатор rate. 6. Знак умножения. 7. Число 60. Пробелы, разделяющие символы этих токенов, при лексическом анализе обычно от- отбрасываются. Синтаксический анализ Иерархический анализ называется разбором (parsing), или синтаксическим анализом, который включает группирование токенов исходной программы в грамматические фра- фразы, используемые компилятором для синтеза вывода. Обычно грамматические фразы ис- исходной программы представляются в виде дерева, пример которого показан на рис. 1.4. В выражении initial+rate*60 фраза rate*60 является логической единицей, поскольку обычные соглашения о приоритете арифметических операций гласят, что ум- умножение выполняется до сложения. Поскольку после выражения initial+rate следу- следует знак умножения *, само по себе оно не группируется в единую фразу на рис. 1.4. Иерархическая структура программы обычно выражается рекурсивными правилами. Например, при определении выражений можно придерживаться следующих правил. 1. Любой идентификатор {identifier) есть выражение {expression). 2. Любое число {number) есть выражение {expression). 3. Если expression и expression являются выражениями, то выражениями являются и expression + expression^ expression * expression {expression). 26 ГЛАВА 1. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ
Инструкция присвоения Идентификатор position Выражение I Идентификатор initial Выражение Идентификатор rate Рис. J .4. Дерево разбора для выражения posit ion: =initial+rate* 60 Правила A) и B) являются базовыми (нерекурсивными), в то время как C) определя- определяет выражения с помощью операторов, применяемых к другим выражениям. Согласно правилу A), initial и rate представляют собой выражения; правило B) гласит, что 60 также является выражением. Таким образом, из C) можно сначала сделать вывод, что rate*60 -выражение, а затем -что выражением является и initial+rate*60. Точно так же многие языки программирования рекурсивно определяют инструкции языка правилами типа приведенных далее. 1. Если identifier\ является идентификатором, a expression - выражением, то identifier^ := expression есть инструкция. 2. Если expressioni - выражение, a statement - инструкция, то while (expressioni) do statemenh if (expression\) then statemenh являются инструкциями2. Разделение анализа на лексический и синтаксический достаточно произвольно. Обычно оно используется для упрощения анализа в целом. Одним из факторов, опреде- определяющих данное разделение, является использование рекурсии в правилах анализа. Лек- Лексические конструкции не требуют рекурсии, в то время как синтаксические редко обхо- обходятся без нее. Контекстно-свободные грамматики представляют собой формализацию 2 Здесь следует обратить внимание на перевод термина statement. Дословно statement означает вы- высказывание, утверждение, однако в применении к компьютерной тематике это не совсем удачно. Обычно при переводе используется термин оператор, но в данной книге, посвященной формальным языкам, этот термин имеет собственное значение. Поэтому при переводе термина statement за редкими исключениями было использовано понятие инструкция - как наиболее близкое по смыслу, так и уже используемое при описании языка, например, в книге Б. Страуструп. Язык программирования C++, 3-е изд. - СПб.; М.: "НевскийДиалект"- "ИздательствоБИНОМ", 1999. - Прим. перев. 1.2. АНАЛИЗ ИСХОДНОЙ ПРОГРАММЫ 27
рекурсивных правил, используемых при синтаксическом анализе. Данные грамматики рассматриваются в главе 2 и подробно изучаются в главе 4. Например, рекурсия не нужна при распознавании идентификаторов, которые обычно представляют собой строки букв и цифр, начинающиеся с буквы. Распознать идентифи- идентификатор можно с помощью простого последовательного сканирования входящего потока до тех пор, пока в нем не встретится символ, не являющийся символом идентификатора. После этого сканированные символы группируются в токен, представляющий идентифи- идентификатор. Сгруппированные символы записываются в так называемую таблицу символов, удаляются из входного потока, и начинается сканирование следующего токена. Однако такое линейное сканирование недостаточно для анализа выражений или ин- инструкций. Например, мы не можем проверить соответствие скобок в выражениях или ключевых слов begin и end в инструкциях без наложения некоторой иерархической или вложенной структуры на вводимые данные. position + position + initial * initial * rate 60 rate inttoreal I 60 a) 6) Рис. 1.5. Семантический анализ добавляет преобразование из целого числа в действительное Дерево разбора, показанное на рис. 1.4, описывает синтаксическую структуру посту- поступающей информации. Более общее внутреннее представление этой синтаксической струк- структуры представлено на рис. 1.5а. Синтаксическое дерево- это "сжатое" дерево разбора, в котором операторы размещены во внутренних узлах, а операнды оператора представлены дочерними ветвями узла, представляющего этот оператор. Построение подобных деревьев (рис. 1.5а) обсуждается в разделе 5.2. В главе 2, "Простой однопроходный компилятор", мы приступим к рассмотрению синтаксически управляемой трансляции (syntax-directed translation), а в главе 5, "Синтаксически управляемая трансляция", изучим ее подробнее. При синтаксически управляемой трансляции для построения вывода компилятор использу- использует иерархическую структуру вводимой информации. Семантический анализ В процессе семантического анализа проверяется наличие семантических ошибок в исходной программе и накапливается информация о типах для следующей стадии - ге- генерации кода. При семантическом анализе используются иерархические структуры, по- полученные во время синтаксического анализа для идентификации операторов и операндов выражений и инструкций. Важным аспектом семантического анализа является проверка типов, когда компиля- компилятор проверяет, что каждый оператор имеет операнды допустимого спецификациями язы- языка типа. Например, определение многих языков программирования требует, чтобы при использовании действительного числа в качестве индекса массива генерировалось сооб- сообщение об ошибке. В то же время спецификация языка может позволить определенное насильственное преобразование типов, например, когда бинарный арифметический опе- оператор применяется к операндам целого и действительного типов. В этом случае компи- компилятору может потребоваться преобразование целого числа в действительное. Проверка типов и семантический анализ обсуждаются в главе 6, "Проверка типов". 28 ГЛАВА 1. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ
Пример 1.1 Битовое представление целого числа в компьютере, вообще говоря, отличается от би- битового представления действительного числа, даже если эти числа имеют одно и то же значение. Предположим, что все идентификаторы на рис. 1.5 объявлены как имеющие действительный тип, а 60 трактуется как целое число. При проверке типов на рис. 1.5а будет обнаружено, что оператор * применяется к действительному числу rate и целому 60. Обычно при этом осуществляется преобразование целого числа в действительное; на рис. 1.56 для этого создается дополнительный узел для оператора inttoreal, который не- неявно преобразует целое число в действительное. Однако, поскольку операнд оператора inttoreal представляет собой константу, компилятор может вместо этого сам заменить целую константу на эквивалентную действительную. ? Анализ в программах форматирования текста В программах форматирования текста удобно рассматривать входную информацию как иерархию блоков (boxes). Эти блоки являются прямоугольными областями битовых образов, представляющих светлые и темные пиксели на выводящем устройстве. Так, например, система Tj$i () работает именно таким образом. Каждый символ, который не является частью команды, представляет собой блок, содержащий битовый образ этого символа в определенном шрифте требуемого размера. Последовательные символы, не отделенные "разделителями" (пробелами или символами новой строки), группируются в слова, состоящие из последовательностей горизонтальных блоков, как схематически показано на рис. 1.6. Группирование символов в слова (или команды) представляет собой линейный, или лексический аспект анализа программы форматиро- форматирования текста. Ш ШшШ Рис. 1.6. Группировка символов и слов в блоки В Tgi блоки могут быть построены из меньших блоков в различных горизонтальных и вертикальных сочетаниях. Например, \hbox{ <список блоков> } группирует список блоков, собранных по горизонтали. По вертикали блоки группируют- группируются с помощью команды \vbox. Таким образом, следующая конструкция в T^JC \hbox{\vbox{! 1} \vbox{@ 2}} представляет набор блоков, показанный на рис. 1.7. Определение иерархического рас- расположения блоков, заданного входным потоком, является частью синтаксического анализа в ш ш Рис. 1.7. Иерархия блоков в 1.2. АНАЛИЗ ИСХОДНОЙ ПРОГРАММЫ 29
Еще одним примером могут послужить математические препроцессоры EQN () и T^i, создающие математические выражения из операторов типа sub и sup для нижних и верхних индексов. Если EQN встречает входной текст вида BOX sub box он изменяет размеры блока box и присоединяет к блоку BOX справа внизу, как показано на рис. 1.8. Оператор sup приведет к блоку такого же размера, но размещенному справа вверху. Рис. 1.8. Построение нижнего индекса в математическом тексте Такие операторы могут использоваться рекурсивно, т.е. EQN-текст a sub { .1 sup 2} дает в результате а., . Группировка операторов sub и sup в токены представляет собой часть лексического анализа текста EQN. Однако для определения размера и размещения блоков требуется синтаксическая структура текста. 1.3. фазы компилятора Концептуально компилятор работает пофазно, причем в процессе каждой фазы про- происходит преобразование исходной программы из одного представления в другое. Типич- Типичное разбиение компилятора на фазы показано на рис. 1.9. На практике некоторые фазы могут быть сгруппированы вместе, как упоминается в разделе 1.5, и промежуточные представления программы внутри таких групп могут явно не строиться. Первые три фазы, формирующие анализирующую часть компилятора, были рассмот- рассмотрены в предыдущем разделе. Управление таблицей символов и обработка ошибок пока-, заны во взаимодействии с шестью фазами: лексическим анализом, синтаксическим ана- анализом, семантическим анализом, генерацией промежуточного кода, оптимизацией кода и генерацией кода. Неформально диспетчер таблицы символов и обработчик ошибок так- также могут считаться "фазами" компилятора. Управление таблицей символов Одной из важных функций компилятора является запись используемых в исходной программе идентификаторов и сбор информации о различных атрибутах каждого иден- идентификатора. Эти атрибуты предоставляют сведения об отведенной идентификатору па- памяти, его типе, области видимости (где в программе он может применяться). При ис- использовании имен процедур атрибуты говорят о количестве и типе их аргументов, мето- методе передачи каждого аргумента (например, по ссылке) и типе возвращаемого значения, если таковое имеется. Таблица символов представляет собой структуру данных, содержащую записи о каж- каждом идентификаторе с полями для его атрибутов. Данная структура позволяет быстро найти информацию о любом идентификаторе и внести необходимые изменения. Табли- Таблицы символов подробнее рассматриваются в главах 2, "Простой однопроходный компилятор", и 7, "Среды времени исполнения". 30 ГЛАВА 1. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ
Исходная программа 1 Генератор промежуточного кода Целевая программа Рис. 1.9. Фазы компилятора Если лексическим анализатором в исходной программе обнаружен идентификатор, он записывается в таблицу символов. Однако атрибуты идентификатора обычно не могут быть определены в процессе лексического анализа. Например, в объявлении переменных на языке Pascal var position, initial, rate: real; когда лексический анализатор находит идентификаторы position, initial и rate, их тип real еще неизвестен. В процессе остальных фаз информация об идентификаторах вносится в таблицу сим- символов и используется различными способами. Например, при семантическом анализе и генерации промежуточного кода необходимо знать типы идентификаторов, чтобы гаран- гарантировать их корректное использование в исходной программе и сгенерировать правиль- правильные операции по работе с ними. Обычно генератор кода вносит в таблицу символов и использует детальную информацию о памяти, назначенной идентификаторам. Обнаружение ошибок и сообщение о них В каждой фазе компиляции могут встретиться ошибки. Однако после их обнаружения необходимы определенные действия, чтобы продолжить компиляцию и выявить другие ошибки в исходной программе. Компилятор, который останавливается при обнаружении первой же ошибки, не настолько полезен в работе, каким мог бы быть. В процессе синтаксического и семантического анализа обычно обрабатывается боль- большая часть ошибок, обнаруживаемых компилятором. При лексическом анализе выявля- выявляются ошибки, при которых символы из входного потока не формируют ни один из токе- нов языка. Ошибки, при которых поток токенов нарушает структурные правила 1.3. ФАЗЫ КОМПИЛЯТОРА 31
(синтаксис) языка, определяются в фазе синтаксического анализа. В процессе семантиче- семантического анализа компилятор пытается обнаружить конструкции, корректные с точки зре- зрения синтаксиса, но не имеющие смысла с точки зрения выполняемых операций, напри- например попытка сложения двух идентификаторов, один из которых - имя массива, а вто- второй - имя процедуры. Обработка ошибок в каждой фазе компиляции будет рассмотрена детальнее в разделах книги, посвященных каждой из фаз в отдельности. position:= initial + rate 60 1 Лексический анализатор id, : 60 2 1 Синтаксический анализатор "1 + id," \ 1 60 Семантический анализатор Таблица символов id/4 1 2 3 4 position initial rate id," \ id, inttoreal I ¦ 60 Генератор промежуточного кода tempi temp2 temp3 idi:= temp3 I = inttorealF0) = id3 * tempi = id2 * temp2 Оптимизатор кода \ tempi: = id3 60 id1: = id2 + tempi 1 Генератор кода MOVF id3, R2 MOVF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R2, id1 Рис. 1.10. Трансляция инструкции 32 ГЛАВА 1. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ
Фазы анализа В процессе трансляции изменяется внутреннее представление исходной программы. Для иллюстрации рассмотрим инструкцию. position:= initial + rate * 60 0-1) На рис. 1.10 показано внутреннее представление инструкции после каждой фазы. При лексическом анализе символы исходной программы считываются и группируют- группируются в поток токенов, в котором каждый токен представляет логически связанную последо- последовательность символов- идентификатор, ключевое слово (if, while и т.п.), символ пунктуации или многосимвольный оператор типа:=. Последовательность символов, формирующая токен, называется лексемой токена. Некоторые токены дополняются "лексическим значением". Например, когда найден идентификатор rate, лексический анализатор не только генерирует токен, скажем id, но и вносит лексему rate в таблицу символов, если ее там нет. Лексическое значение, свя- связанное с этим появлением токена id, указывает на запись rate в таблице символов. В этом разделе мы будем использовать обозначения idb id2 и id3 для position, initial и rate, чтобы подчеркнуть отличие внутреннего представления идентифика- идентификатора от последовательности символов, формирующих его. Инструкция A.1) после лекси- лексического анализа выглядит так: id, := id2 + id3 * 60 С1-2) Нужно также создать токены для многосимвольного оператора:= и числа 60, но об этом - в главе 2, "Простой однопроходный компилятор". Детальнее лексический анализ рассматривается в главе 3, "Лексический анализ". Вторая и третья фазы, синтаксический и семантический анализ, также были рас- рассмотрены в разделе 1.2. При синтаксическом анализе на поток токенов налагается ие- иерархическая структура, которую можно изобразить с помощью синтаксического дере- дерева, приведенного на рис. 1.11а. Типичная структура данных для такого дерева показа- показана на рис. 1.116. Ее внутренний узел представляет собой запись с полем для оператора и двумя полями с указателями на дочерние записи. Лист представляет собой запись с двумя или более полями (для идентификации токена в листе и записи информации о токене). Дополнительная информация о языковых конструкциях может содержаться в дополнительных полях записей для узлов. Синтаксический и семантический анализ будут детальнее рассматриваться в главах 4, "Синтаксический анализ", и 6, "Проверка типов", соответственно. " "On ld3 60 а) б) Рис. 1.11. Структура данных (б) для дерева (а) 1.3. ФАЗЫ КОМПИЛЯТОРА 33
Генерация промежуточного кода После синтаксического и семантического анализа некоторые компиляторы генериру- генерируют явное промежуточное представление исходной программы, которое можно рассмат- рассматривать как программу для абстрактной машины. Это представление должно легко созда- создаваться и транслироваться в целевую программу. Промежуточное представление может иметь ряд форм. В главе 8, "Генерация промежуточного кода", мы рассмотрим промежуточную форму, называемую "трехадресным кодом". Этот код похож на язык ассемблера для машины, в которой каж- каждая ячейка памяти может работать в качестве регистра. Трехадресный код состоит из по- последовательности инструкций, каждая из которых имеет не более трех операндов. Ис- Исходная программа A.1) в трехадресном коде может выглядеть так: tempi:= inttorealF0) temp2:= id3 * tempi temp3:= id2 + temp2 A.3) idl:= temp3 Данная промежуточная форма имеет ряд специфических свойств. Во-первых, каждая трехадресная инструкция помимо присвоения имеет не более одного оператора. Поэтому при генерации этих инструкций компилятор должен определить порядок выполнения операций; так, в исходной программе A.1) умножение предшествует сложению. Во- вторых, компилятор должен сгенерировать временное имя для хранения результатов, вычисляемых каждой инструкцией. В-третьих, некоторые трехадресные инструкции имеют меньше трех операндов (например, первая и последняя инструкции в A.3)). В главе 8, "Генерация промежуточного кода", будут рассмотрены основные проме- промежуточные представления, используемые в компиляторах. Вообще говоря, эти представ- представления должны не только вычислять выражения, но и управлять потоком инструкций и вызовов процедур. В главах 5, "Синтаксически управляемая трансляция", и 8, "Генерация промежуточного кода", представлены алгоритмы генерации промежуточного кода для типичных конструкций языков программирования. Оптимизация кода При оптимизации кода производятся попытки улучшить промежуточный код, чтобы получить более эффективный машинный код. Некоторые оптимизации тривиальны. На- Например, естественный алгоритм генерирует промежуточный код A.3), используя инст- инструкцию для каждого оператора в дереве, созданном в результате семантического анали- анализа, хотя те же вычисления можно выполнить с помощью двух инструкций: tempi:= id3 * 60.0 idl:= id2 + tempi A.4) Оптимизирующее преобразование может быть выполнено в процессе генерации кода. Во-первых, компилятор может принять решение о преобразовании целого числа 60 в действительное еще во время компиляции, устраняя необходимость в операции inttoreal. Во-вторых, переменная temp3 используется лишь для передачи своего значения в idl, поэтому вполне корректно использовать idl вместо temp3 и удалить последнюю инструкцию из A.3), получая код A.4). Степень оптимизации кода у различных компиляторов значительно отличается. В не- некоторых компиляторах, называемых "оптимизирующими", большая часть времени рабо- 34 ГЛАВА 1. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ
ты уходит именно на оптимизацию. Однако существуют простые приемы оптимизации, которые существенно уменьшают время работы целевой программы, не сильно замедляя работу компилятора. Многие из этих приемов рассматриваются в главе 9, "Генерация кода", а в главе 10, "Оптимизация кода" вы познакомитесь с технологиями, используе- используемыми более мощными оптимизирующими компиляторами. Генерация кода Последняя фаза компиляции состоит в генерации целевого кода, обычно перемещае- перемещаемого (relocatable) машинного кода или ассемблерного кода. Для каждой переменной про- программы определяется ее положение в памяти. После этого каждая промежуточная инст- инструкция транслируется в последовательность машинных инструкций, выполняющих ту же самую работу. Ключевой аспект этой фазы заключается в назначении переменных реги- регистрам. Например, используя регистры 1 и 2 при трансляции кода A.4), получим следующий код: MOVF id3, R2 MULF #60.0, R2 MOVF id2, Rl A.5) ADDF R2, Rl MOVF Rl, idl Первый и второй операнды каждой инструкции определяют источник и приемник. F говорит о том, что в инструкции используются числа с плавающей точкой. Этот код пе- перемещает содержимое адреса3 id3 в регистр 2, затем умножает его на действительную константу 60.0. Символ # означает, что 60.0 представляет собой константу. Третья инструкция переносит значение id2 в регистр 1, а затем к нему добавляется вычислен- вычисленное ранее значение из регистра 2. И наконец, значение из регистра 1 переносится в ячей- ячейку памяти с адресом idl. Тем самым код реализует присвоение, показанное на рис. 1.10. О генерации кода вы прочтете в главе 9, "Генерация кода". 1.4. Родственники компилятора Как видно из рис. 1.3, входная информация для компилятора может порождаться од- одним или несколькими препроцессорами; кроме того, после компиляции может потребо- потребоваться дополнительная обработка для получения выполняемого машинного кода. В этом разделе мы рассмотрим типичное окружение, в котором работает компилятор. Препроцессоры Препроцессоры создают входной поток информации для компилятора. С их помощью можно выполнить следующие функции. 1. Обработка макросов. Пользователь может определить макросы - краткие записи длинных конструкций. 3 Следует упомянуть о важности вопроса выделения памяти для размещения идентификаторов исход- исходной программы. Как мы увидим в главе 7, "Среды времени исполнения", распределение памяти в процессе работы зависит от компилируемого языка. Принятие решения о выделении памяти происходит либо в про- процессе создания промежуточного кода, либо при генерации целевого кода. 1.4. РОДСТВЕННИКИ КОМПИЛЯТОРА 35
2. Включение файлов. В текст программы можно включить заголовочные файлы. Например, при обработке файла препроцессор С заменяет выражение #include
Для любого программиста понимание принципа работы используемых им инструментов - залог успеха. Особенно сильно в изучении программирования способно помочь знание того, как устроен и пишется компилятор, пусть даже совсем простой. Мы собрали подборку лучших книг по принципам работы компиляторов и их написанию, которые научат вас грамотному проектированию и низкоуровневому программированию этих мощнейших инструментов.
Всеобъемлющая книга о самых насущных проблемах проектирования и написания компиляторов под современные процессоры. Написанная как для студентов, так и уже состоявшихся разработчиков, она расскажет вам о множестве способов оптимизации кода и наиболее эффективных из них, а также расскажет о создании компилятора для современных актуальных языков.
Курсы по компиляторам в учебных заведениях далеко не всегда хорошо освещают эту тему. Книга «Создаем оптимизированный компилятор» призвана восполнить этот пробел. Здесь описывается принцип построения оптимизатора, генедатора кода, планировщика и распределения регистров на современных RISC процессорах. Выделяет книгу подход к вопросам с практической точки зрения: теория добавляется там, где интуитивное понимание невозможно.
Данная книга - официальное руководство от Free Software Foundation по «изнанке» компиляторов GNU. В нем содержатся следующие материалы: как поучаствовать в разработке компилятора GCC, разбор необходимых характеристик для хоста и целевой машины, поддерживаемых GCC, а также описание древовидной структуры исходного кода GCC и системы сборки. Сами авторы этой книги преподносят ее как справочник, в котором можно найти множество информации по внутренней структуре GCC.
Книга полна материала, охватывающего последние разработки технологии компиляции. Здесь описаны важные темы, без которых не обойтись в процессе построения современного компилятора, а именно принцип работы императивных и объектно-ориентированных языков, планирование инструкций и распределение регистров.
Данная книга является одной из серии книг, различающихся по используемым языкам программирования. В каждой из них изложены все этапы создания современного компилятора: лексический анализ, синтаксический анализ, абстрактные синтаксические и семантические действия, анализ потоков данных, распределение регистров. Также описывается покрытие текущих методов генерации кода и функциональные и объектно-ориентированные языки.
Вторая книга из серии «Modern Compiler Implementation», содержащая в себе примеры кода на языке Си. Рассматриваются те же темы, что и в предыдущей книге.
Третья книга из серии «Modern Compiler Implementation», проиллюстрированная частями кода, написанного на языке Java.
Цель книги «Introduction to Compiler Design» - обучить читателя создавать компиляторы для простых языков программирования. Хоть материал руководства и не охватывает методы оптимизации компилируемого кода, зато в книге даются некоторые наработки, которые используются в реальных компиляторах и помогут лучше разобраться в самой их концепции. В руководстве освещаются все этапы, необходимые для компиляции кода, написанного на языке высокого уровня, в машинный язык: разделение кода на лексические составляющие, его разбор, создание промежуточного кода, генерация машинного кода и использование регистров. Примеры кода представлены на псевдоязыке.
Широко известная книга, своего рода классика жанра, рекомендуемая многими профессорами и разработчиками. Не так давно она была переиздана, и теперь каждая глава содержит только самые актуальные сведения по разработке компиляторов. Авторы помнят, что некоторые читатели могут использовать эту книгу как полное пособие, и поэтому обращают внимание на широчайший круг проблем, с которыми можно столкнуться в процессе разработки программного обеспечения.
Фокусируясь на фундаментальных техниках, общих для всех языковых парадигм, эта книга расскажет вам все, что необходимо для создания современного компилятора. Тема рассмотрена с позиции всех наиболее популярных парадигм программирования – императивной, объектно-ориентированной, функциональной и некоторых других. Акцент сделан на техниках автоматизации, в том числе на инструментах для автоматизации проектирования компилятора.
Цель данной книги - познакомить читателя с основами компиляторов. Основное внимание в ней уделяется императивным и функциональным языкам программирования: подмножествам языков C++ и Haskell, на которых часто пишут компиляторы. Материал, представленный в руководстве, переносим на разные языки программирования. В книге используется инструмент BNF Converter , с помощью которого в автоматическом режиме генерируется большая часть кода компилятора.
По мнению автора, каждый программист должен знать, как работают компиляторы и интерпретаторы, чтобы легче понимать, как работают другие языки, и, возможно, создавать новые. В последней главе рассказывается о различных концепциях языков: от минималистичных полных по Тьюрингу языков до полноценного взаимодействия человека и компьютера на естественном языке.
Книга создана для того, чтобы помочь каждому исследователю и программисту обновить свои знания, усовершенствовать навыки и подготовиться к созданию прогрессивных качественных продуктов. 14 глав этого справочника посвящены таким вопросам, как сборка мусора, уменьшение времени выполнения компиляции и оптимизация процесса. Особое внимание уделено работе со встраиваемыми устройствами, а также способам отладки кода с ошибками. Книга обеспечит вам глубокое понимание принципа распределения регистров, программной конвейеризации, планировании инструкций и системы типизации.
Данная книга разработана вики-сообществом, поэтому постоянно дорабатывается. Ее основная цель - дать читателю понять, что написать самому компилятор вполне реально. Помимо компиляторов, в книге рассматривается создание интерпретаторов кода. Материал содержит минимум теоретической информации. Хорошо подходит для новичков, не знающих ничего о написании компиляторов и интерпретаторов.
Книга станет бесценной находкой для всех, кто начинает изучение семантики и логики языков программирования. Эта информация позволит вывести и систематизировать правила, которыми можно описать любой из существующих языков программирования. В книге использованы данные прогрессивных исследований, в том числе по такой животрепещущей теме, как параллелизм. Последняя глава посвящена параллельным языкам программирования, в том числе методам определения и проверки недетерминированных и параллельных программ.
Эта книга не о компиляторах и их проектировании, но она незаменима для всех, кто имеет дело с низкоуровневым программированием (а без него в создании компилятора не обойтись). Здесь вы найдете информацию о CRC, научитесь таким трюкам, как целочисленное деление, в том числе с помощью сдвигов, вычисление остатка без подсчета частного, новые алгоритмы сжатия и расширения, деление с плавающей точкой, алгоритм LRU, а также оцените галерею графиков дискретных функций.
Если вы знаете еще пару-тройку интересных книг, которые наглядно и понятным языком поясняют устройство и написание компиляторов, то поделитесь вашим мнением в комментариях. Лучшие книги добавим в эту подборку.
Каждый программист должен знать, как работает его код, как он взаимодействует с «железом», и множество тонкостей разработки программного обеспечения. И желательно знать как работают компиляторы.
Компиляторы – неотъемлемая часть базовых знаний любого кодера. Поэтому мы составили подборку книг, которая поможет вам увеличить свои знания по этой важной теме.
Книга описывает проект Оберон – полную программную среду для современной рабочей станции. Суть проекта в том, чтобы создать проект, который будет спроектирован и реализован с нуля, а затем описан, объяснён и понят, как единое целое. Также пособие содержит подробнейшее описание компилятора языка Оберон и его графической подсистемы.
В этой книге будет подробно рассмотрена разработка компилятора для высокоуровневого языка программирования. Также в ней будут освещены все этапы его реализации. Вам будет представлен исходный код на нескольких языках программирования. Кроме того, пособие содержит теорию по формальным языкам и грамматикам, а благодаря обилию примеров весь материал будет легче запоминать. Работа предназначена для студентов технических вузов и всех тех, кто интересуется искусством программирования.
Книга содержит основные принципы разработки компиляторов, лексический и синтаксический анализ, генерацию кода, а также их детальное рассмотрение. Издание широко освещает вопросы оптимизации кода, его строгое изложение уравновешивается множеством практических примеров. Для того чтобы создать компилятор, необходимы знания языков программирования, архитектуры вычислительных систем, теории языков и пр. Устранить пробелы вам поможет эта книга.
Книга содержит информацию о фундаментальных техниках, которые являются общими для всех языковых парадигм. С их помощью вы сможете создать современный компилятор. Большое внимание уделяется техникам автоматизации, в том числе автоматизации проектирования компилятора.
Y.N.Srikant, Priti Shankar «The Compiler Design Handbook: Optimizations and Machine Code Generation»/»Справочник о проектировании компиляторов: оптимизация и машинная генерация кода»
Издание поможет каждому читателю обновить свои знания, развить навыки, научиться создавать качественные продукты разработки. Книга посвящена сборке мусора, уменьшению времени компиляции и оптимизации процесса. Акцент сделан на работу со встраиваемыми девайсами и способам отладки кода.
Пособие расскажет о большом выборе способов оптимизации кода и том, как выбрать наиболее эффективный. Оно также содержит информацию о проблемах проектирования и написания современных компиляторов.
Перед вами перевод известной книги знаменитых авторов, перу которых принадлежит ряд бестселлеров в области компьютерных наук, причем диапазон их плодотворной работы чрезвычайно широк - от фундаментальных научных статей до великолепных учебников для студентов. Именно таким учебником и является данная книга, которая доступна широкому кругу программистов и представляет собой завершенное изложение технологий построения компиляторов.
Многие работы этих авторов переведены на русский язык и неизменно пользуются повышенным спросом у серьезного читателя. Достаточно вспомнить такие книги, как Построение и анализ вычислительных алгоритмов , Структуры данных и алгоритмы или Теория синтаксического анализа, перевода и компиляции .
Предлагаемая книга выгодно отличается от большинства своих предшественниц тем, что здесь охвачен весь процесс создания компилятора - от лексического анализа до генерации и оптимизации целевого кода. Использование абстрактных математических понятий доводится в ней до конкретных алгоритмов, пригодных для непосредственной реализации. Технологии, изложенные в этой книге, уже нашли свое применение не только в компиляции, но и в системах подготовки текстов, управления базами данных, генерации схем электронных устройств и других областях.
Оригинал этой книги опубликован в 1988 году. С тех пор были созданы новые парадигмы программирования, десятки новых языков и компиляторов для них. Однако осмелимся утверждать, что в их реализации не было ничего принципиально нового по сравнению с тем, что изложено в этой книге. Данное издание может служить практическим руководством по технологиям создания компиляторов. Описанные в ней технологии были созданы в основном еще в 60-е–80-е годы и существенно уже не изменятся. Книга по праву может считаться классической, потому что она не устарела и не устареет, пока люди будут создавать языки и системы программирования.
Предисловие
Данное издание является развитием книги Альфреда Ахо и Джеффри Ульмана Principles of Computer Design . Подобно своей предшественнице, она задумана как начальный учебный курс по проектированию компиляторов. Основное внимание уделяется решению общих проблем, возникающих при создании трансляторов языков программирования, независимо от исходного языка или целевой машины.
Вероятно, лишь немногие из вас будут заниматься построением или поддержкой компиляторов для основных языков программирования, однако идеи и технологии, описанные в ней, можно с успехом применять при разработке другого программного обеспечения. Например, технологии поиска соответствия строк шаблонам, используемые при построении лексических анализаторов, применяются и в текстовых редакторах, и в системах выборки информации, и в распознавании образов. Контекстно-свободные грамматики и синтаксически управляемые определения используются для создания многих небольших языков, например типографских систем для подготовки макетов книг. Технологии оптимизации кода применяются для проверки корректности программ и создания "структурированных" программ из неструктурированных.
Использование данной книги
В книге глубоко раскрыты основные аспекты создания компиляторов. Глава 1 описывает базовую структуру компилятора и представляет собой фундамент для остального материала книги.
В главе 2 рассматривается транслятор, переводящий инфиксные выражения в постфиксные. Он построен с использованием базовых технологий, описываемых в этой книге. В следующих главах развивается изложенный здесь материал.
Глава 3 посвящена лексическому анализу, регулярным выражениям, конечным автоматам и инструментарию для создания сканеров входного потока. Материал этой главы может быть широко использован при разработке текстовых редакторов.
Глава 4 пополняет наши знания о технологиях синтаксического анализа. Здесь рассматриваются как методы рекурсивного спуска, применяемые при ручной реализации трансляторов, так и более сложные и универсальные LR-технологии, используемые в генераторах синтаксических анализаторов.
Глава 5 знакомит нас с принципиальными идеями синтаксически управляемой трансляции. Материал этой главы используется в оставшейся части книги как для описания, так и реализации трансляторов.
В главе 6 выдвигаются основные идеи выполнения статической семантической проверки и детально рассматриваются вопросы проверки типов.
В главе 7 обсуждаются вопросы организации памяти для поддержки сред времени исполнения программ.
Глава 8 начинается с обсуждения языков промежуточного представления программ, а затем показывает нам, каким образом основные конструкции языка программирования могут транслироваться в промежуточный код.
Глава 9 посвящена генерации целевого кода, включая вопросы генерации кода "на лету" и оптимальные методы генерации кода для выражений. Здесь также рассмотрены локальная оптимизация и генераторы генераторов кода.
Глава 10 представляет исчерпывающую информацию об оптимизации кода. В ней детально изложены методы анализа потока данных, а также основные методы глобальной оптимизации.
В главе 11 обсуждается ряд практических вопросов, возникающих при реализации компиляторов, в частности важность вопросов разработки программного обеспечения и тестирования.
В главе 12 проведено исследование компиляторов, построенных с использованием представленных в книге технологий.
Приложение А описывает простой язык - "подмножество" Pascal, который может использоваться в качестве основы для реальных проектов.
Вводный курс, посвященный компиляторам, может основываться на материале следующих разделов книги.
Информация, необходимая для программного проекта, подобного приведенному в приложении А, имеется в главе 2.
Курс, посвященный инструментарию построения компиляторов, может включать обсуждение генераторов лексических анализаторов из раздела 3.5, генераторов синтаксических анализаторов из разделов 4.8 и 4.9, генераторов генераторов кода из раздела 9.12, а также материал о технологиях построения компиляторов из главы 11.
Основной курс может делать упор на алгоритмы, используемые в генераторах лексических и синтаксических анализаторов (главы 3 и 4); материал об эквивалентности типов, перегрузке, полиморфизме и унификации (глава 6), организации памяти времени исполнения (глава 7); методы генерации кода на основе шаблонов из главы 9; и материал об оптимизации кода из главы 10.
Упражнения
Как и ранее, сложность упражнений указана звездочками. Упражнения без звездочек проверяют понимание определений, упражнения с одной звездочкой относятся к более сложному курсу, а "двухзвездные" служат "пищей" для серьезных размышлений.
Благодарности
На различных этапах написания этой книги мы получили множество неоценимых комментариев и советов от большого числа специалистов. В связи с этим мы выражаем свою признательность Биллу Эппельбу (Bill Appelbe), Нельсону Бибу (Nelson Beebe), Джону Бентли (Jon Bentley), Луи Богесу (Lois Bogess), Родни Фэрроу (Rodney Farrow), Стью Фельдман (Stu Feldman), Чарльзу Фишеру (Charles Fischer), Крису Фрэзеру (Chris Fraser), Арту Життельману (Art Gittelman), Эрику Гроссе (Eric Grosse), Дэйву Хансону (Dave Hanson), Фрицу Хенглайну (Fritz Henglein), Роберту Генри (Robert Henry), Жерару Хольцману (Gerard Holzmann), Стиву Джонсону (Steve Johnson), Брайену Кернигану (Brian Kernighan), Кену Кубота (Ken Kubota), Дэниэлу Леману (Daniel Lehmann), Дэйву Мак-Квину (Dave MacQueen), Дианне Маки (Dianne Maki), Алану Мартину (Alan Martin), Дугу Мак-Илрою (Doug McIlroy), Чарльзу Мак-Лафлину (Charles McLaughlin), Джону Митчеллу (John Mitchell), Эллиоту Органику (Elliot Organick), Роберту Пейджу (Robert Paige), Филу Пфайфферу (Phil Pfeiffer), Робу Пайку (Rob Pike), Кари-Йоко Ряйхя (Kari-Jouko Rдihд), Дэнису Ритчи (Dennis Ritchie), Срираму Санкару (Sriram Sankar), Полу Стокеру (Paul Stoecker), Бьерну Страуструпу (Bjarne Stroustrup), Тому Шимански (Tom Szymanski), Киму Трейси (Kim Tracy), Петеру Вайнбергеру (Peter Weinberger), Дженнифер Видом (Jennifer Widom) и Рейнгарду Вильгельму (Reinhard Wilhelm).
Оригинал этой книги создан с использованием великолепного программного обеспечения, доступного в UNIX. Команда типографского набора выглядела следующим образом.
pic files | tbl | eqn | troff -ms
Pic - это язык Брайена Кернигана (Brian Kernighan) для набора рисунков; мы особо признательны Брайену за успешное удовлетворение наших обширных потребностей в иллюстрациях. tbl - это язык Майка Леска (Mike Lesk), предназначенный для макетирования таблиц; eqn - язык Брайена Кернигана (Brian Kernighan) и Лоринды Черри (Lorinda Cherry) для печати математических формул; troff - программа Джо Оссана (Joe Ossana) для форматирования текста при фотонаборе (в нашем случае - для Mergenthaler Linotron 202/N). Пакет макросов ms разработан Майком Леском (Mike Lesk). И наконец, с текстом мы работали с помощью make Стью Фельдман (Stu Feldman); перекрестные ссылки в тексте обрабатывались посредством awk , созданного Альфредом Ахо (Alfred Aho), Брайеном Керниганом (Brian Kernighan) и Петером Вайнбергером (Peter Weinberger), и sed Ли Мак-Мэхона (Lee McMahon).
Авторы должны отдельно поблагодарить Патрицию Соломон (Patricia Solomon) за помощь в подготовке книги для фотокомпозиции. Во время работы над книгой поддержку Джеффри Ульману (Jeffrey Ullman) оказало Эйнштейновское общество Академии искусств и науки Израиля. И наконец, авторы признательны AT&T Bell Laboratories за поддержку во время подготовки рукописи.
| Компиляторы: принципы, технологии и инструменты |
|
|
Обложка книги |
|
|
Альфред Ахо, Рави Сети, Джеффри Ульман |
|
| Язык оригинала: | |
| Переводчик: |
И. В. Красиков |
| Издательство: |
«Вильямс» |
| Страниц: | |
| ISBN : | |
Компиляторы: принципы, технологии и инструменты - классический учебник по теории построения компиляторов под авторством Альфреда В. Ахо, Рави Сети и Джеффри Д. Ульмана, известный также как «Книга дракона» (так как на обложке изображены дракон и рыцарь). Иногда его называют «книгой красного дракона», в отличие от «книги зелёного дракона» - первого издания с зелёным драконом на обложке .
Новое английское издание книги, исправленное и дополненное, вышло в августе 2006 года.
Русское издание
: Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8
Английское издание
: Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986. ISBN 0-201-10088-6
Второе издание
| Компиляторы: принципы, технологии и инструментарий |
|
| Principles, Techniques, and Tools | |
|
|
|
|
Альфред Ахо, Моника С. Лам, Рави Сети, Джеффри Ульман |
|
| Язык оригинала: | |
| Переводчик: |
И. В. Красиков |
| Издательство: |
«Вильямс» |
| Страниц: | |
| ISBN : | |
Второе издание книги, вышедшее в 2007 году, значительно дополнено и обновлено. Добавлено несколько новых глав, в том числе имеется пример законченной начальной стадии компилятора на языке Java . Значительно расширенно описание методов оптимизации кода.
Продолжая традицию предшественников, на обложке второго издания книги изображены рыцарь и дракон. Это издание неофициально известно как пурпурный дракон . Четвёртым соавтором стала Моника Лам (Monica S. Lam).
Примечания
Ссылки
- Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман Компиляторы: принципы, технологии и инструментарий, 2 издание = Compilers: Principles, Techniques, and Tools. - 2 изд. - М .: Вильямс, 2008. - ISBN 978-5-8459-1349-4
Wikimedia Foundation . 2010 .
Смотреть что такое "Компиляторы: принципы, технологии и инструменты" в других словарях:
Компиляторы: принципы, технологии и инструменты Компиляторы: принципы, технологии и инструменты классический учебник по теории построения компиляторов под авторством Альфреда В. Ахо, Рави Сети и Джеффри Д. Ульмана, известный также как «Книга… … Википедия
Обложка книги с рыцарем и драконом Компиляторы: принципы, технологии и инструменты классический учебник по теории построения компиляторов под авторством Альфреда В. Ахо, Рави Сети и Джеффри Д. Ульмана, известный также как «Книга дракона» (так как … Википедия - (кратко орграф) (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами … Википедия
- (англ. bootstrapping) метод создания компилятора некоторого языка программирования, позволяющий использовать для написания компилятора сам этот язык (не прибегая к программированию на языке низкого уровня). Раскрутка также используется … Википедия
В Википедии есть статьи о других людях с такой фамилией, см. Ахо. Альфред Ахо Alfred Vaino Aho Дата рождения: 9 августа 1941(1941 08 09) (71 год) Место рождения: Тимминс … Википедия
В теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все… … Википедия
В теории компиляторов, мёртвым кодом (так же бесполезным кодом, англ. dead code) называют код, который может быть исполнен, но результаты его вычислений в дальнейшем в программе не используются. Другими словами это код, определяющий … Википедия
