Компиляторы: принципы, технологии и инструменты

Альфред В. Ахо, Рави Сети, Джеффри Д. Ульман

 

Каждый, кто интересовался разработкой компиляторов, несомненно, слышал о знаменитой "Книге Дракона" - "Dragon Book", классическим трудом Ахо и Ульмана "Принципы разработки компиляторов". Бурное развитие технологий компиляции привело к рождению нового дракона - книги "Компиляторы: принципы, технологии, инструментарий" Альфреда Ахо, Рави Сети и Джеффри Ульмана.Новая книга начинается с изложения принципов создания компиляторов, проиллюстрированного разработкой прос тейшего однопроходного компилятора. Оставшаяся часть книги посвящена развитию базовых идей и более прогрессивным и современным технологиям, включая такие вопросы, как синтаксический анализ, проверку типов, генерацию и оптимизацию кода.Строгость изложения материала смягчается большим количеством практических примеров. Принципы и технологии написания компиляторов столь распространены, что идеи, которые вы найдете в этой книге, часто используются в области информационных технологий. Написание компиляторов ох ватывает языки программирования, архитектуру вычислительных систем, теорию языков, алгоритмы и технологию создания программного обеспечения. Помочь в освоении этих технологий и инструментария и призвана данная книга. Однако, несмотря на свою учебную ориентацию, книга будет полезна всем, кому приходится работать над созданием компиляторов или кто просто интересуется данной темой, - от начинающих программистов до профессионалов.

От редактора

Перед вами перевод известной книги знаменитых авторов, перу которых принадлежит ряд бестселлеров в области компьютерных наук, причем диапазон их плодотворной работы чрезвычайно широк - от фундаментальных научных статей до великолепных учебников для студентов. Именно таким учебником и является данная книга, которая доступна широкому кругу программистов и представляет собой завершенное изложение технологий построения компиляторов.

Многие работы этих авторов переведены на русский язык и неизменно пользуются повышенным спросом у серьезного читателя. Достаточно вспомнить такие книги, как Построение и анализ вычислительных алгоритмов [7], Структуры данных и алгоритмы [8] или Теория синтаксического анализа, перевода и компиляции [18√19].

Предлагаемая книга выгодно отличается от большинства своих предшественниц тем, что здесь охвачен весь процесс создания компилятора - от лексического анализа до генерации и оптимизации целевого кода. Использование абстрактных математических понятий доводится в ней до конкретных алгоритмов, пригодных для непосредственной реализации. Технологии, изложенные в этой книге, уже нашли свое применение не только в компиляции, но и в системах подготовки текстов, управления базами данных, генерации схем электронны х устройств и других областях.

Оригинал этой книги опубликован в 1988 году. С тех пор были созданы новые парадигмы программирования, десятки новых языков и компиляторов для них. Однако осмелимся утверждать, что в их реализации не было ничего принципиально нового по сравнению с тем, что изложено в этой книге. Данное издание может служить практическим руководством по технологиям создания компиляторов. Описанные в ней технологии были созданы в основном еще в 60-е√80-е годы и существенно уже не изменятся. Книга по праву может считаться классической, потому что она не устарела и не устареет, пока люди будут создавать языки и системы программирования.

Предисловие

Данное издание является развитием книги Альфреда Ахо и Джеффри Ульмана Principles of Computer Design. Подобно своей предшественнице, она задумана как начальный учебный курс по проектированию компиляторов. Основное внимание уделяется решению общих проблем, возникающих при создании трансляторов языков программирования, независимо от исходного языка или целевой машины.

Вероятно, лишь немногие из вас будут заниматься построением или поддержкой компиляторов для основных языков программирования, однако идеи и технологии, описанные в ней, можно с успехом применять при разработке другого программного обеспечения. Например, технологии поиска соответствия строк шаблонам, используемые при построении лексических анализаторов, применяются и в текстовых редакторах, и в системах выборки информации, и в распознавании образов. Контекстно-свободные грамматики и синтаксически управл яемые определения используются для создания многих небольших языков, например типографских систем для подготовки макетов книг. Технологии оптимизации кода применяются для проверки корректности программ и создания "структурированных" программ из неструктурированных.

Использование данной книги

В книге глубоко раскрыты основные аспекты создания компиляторов. Глава 1 описывает базовую структуру компилятора и представляет собой фундамент для остального материала книги.

В главе 2 рассматривается транслятор, переводящий инфиксные выражения в постфиксные. Он построен с использованием базовых технологий, описываемых в этой книге. В следующих главах развивается изложенный здесь материал.

Глава 3 посвящена лексическому анализу, регулярным выражениям, конечным автоматам и инструментарию для создания сканеров входного потока. Материал этой главы может быть широко использован при разработке текстовых редакторов.

Глава 4 пополняет наши знания о технологиях синтаксического анализа. Здесь рассматриваются как методы рекурсивного спуска, применяемые при ручной реализации трансляторов, так и более сложные и универсальные LR-технологии, используемые в генераторах синтаксических анализаторов.

Глава 5 знакомит нас с принципиальными идеями синтаксически управляемой трансляции. Материал этой главы используется в оставшейся части книги как для описания, так и реализации трансляторов.

В главе 6 выдвигаются основные идеи выполнения статической семантической проверки и детально рассматриваются вопросы проверки типов.

В главе 7 обсуждаются вопросы организации памяти для поддержки сред времени исполнения программ.

Глава 8 начинается с обсуждения языков промежуточного представления программ, а затем показывает нам, каким образом основные конструкции языка программирования могут транслироваться в промежуточный код.

Глава 9 посвящена генерации целевого кода, включая вопросы генерации кода "на лету" и оптимальные методы генерации кода для выражений. Здесь также рассмотрены локальная оптимизация и генераторы генераторов кода.

Глава 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.

Упражнения

Как и ранее, сложность упражнений указана звездочками. Упражнения без звездочек проверяют понимание определений, упражнения с одной звездочкой относятся к более сложному курсу, а "двухзвездные" служат "пищей" для серьезных размышлений.

Благодарности

На различных этапах написания этой книги мы получили множество неоценимых комментариев и советов от большого числа специалистов. В связи с этим мы выражаем свою признательность Биллу Эппельбу (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 P feiffer), Робу Пайку (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 за поддержку во время подготовки рукописи.

A.V.A., R.S., J.D.U.

Вернуться к начальной странице