Построение компиляторов

Построение компиляторов

Москва, 2023

Никлаус Вирт

2-е издание, электронное

УДК 32.973.26-018.2
ББК 004.438
В52

В52
Вирт, Никлаус.
Построение компиляторов / Н. Вирт ; пер. с англ. Е. В. Борисова, 
Л. Н. Чернышова. — 2-е изд., эл. — 1 файл pdf : 193 с. — Москва : ДМК Пресс, 
2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 
4.5 ; экран 10". — Текст : электронный.

ISBN 978-5-89818-573-2

Книга известного специалиста в области информатики Никлауса Вирта написана 
по материалам его лекций по вводному курсу проектирования компиляторов. На 
примере простого языка Оберон-0 рассмотрены все элементы транслятора, включая 
оптимизацию и генерацию кода. Приведен полный текст компилятора на языке программирования 
Оберон.
Для программистов, преподавателей и студентов, изучающих системное программирование 
и методы трансляции.

УДК 32.973.26-018.2 
ББК 004.438

Электронное издание на основе печатного издания: Построение компиляторов / Н. Вирт ; 
пер. с англ. Е. В. Борисова, Л. Н. Чернышова. — Москва : ДМК Пресс, 2016. — 192 с. — ISBN 
978-5-97060-219-5. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами 
защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.


ISBN 978-5-89818-573-2
©  N.Wirth, 1985 (Oberon version: 
August 2004)
©  Перевод с английского 
Борисов Е. В., Чернышов Л. Н., 2014
©  Оформление, издание, 
ДМК Пресс, 2016

Краткое содержание

ОТ АВТОРОВ ПЕРЕВОДА ................................................... 10

ВВЕДЕНИЕ................................................................................ 12

ГЛАВА 1. ВВЕДЕНИЕ ........................................................... 15

ГЛАВА 2. ЯЗЫК И СИНТАКСИС ....................................... 19

ГЛАВА 3. РЕГУЛЯРНЫЕ ЯЗЫКИ ..................................... 27

ГЛАВА 4. АНАЛИЗ КОНТЕКСТНОСВОБОДНЫХ
ЯЗЫКОВ..................................................................................... 33

ГЛАВА 5. АТРИБУТНЫЕ ГРАММАТИКИ
И СЕМАНТИКИ ........................................................................ 45

ГЛАВА 6. ЯЗЫК ПРОГРАММИРОВАНИЯ
ОБЕРОН0................................................................................. 51

ГЛАВА 7. СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР
ДЛЯ ОБЕРОНА0 ................................................................... 55

ГЛАВА 8. УЧЕТ КОНТЕКСТА, ЗАДАННОГО
ОБЪЯВЛЕНИЯМИ .................................................................. 65

ГЛАВА 9. RISCАРХИТЕКТУРА КАК ЦЕЛЬ .................. 75

ГЛАВА 10. ВЫРАЖЕНИЯ И ПРИСВАИВАНИЯ ........... 81

ГЛАВА 11. УСЛОВНЫЕ И ЦИКЛИЧЕСКИЕ
ОПЕРАТОРЫ И ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ ............ 95

Содержание
4

ГЛАВА 12. ПРОЦЕДУРЫ И КОНЦЕПЦИЯ
ЛОКАЛИЗАЦИИ ................................................................... 109

ГЛАВА 13. ЭЛЕМЕНТАРНЫЕ ТИПЫ ДАННЫХ ......... 125

ГЛАВА 14. ОТКРЫТЫЕ МАССИВЫ,
УКАЗАТЕЛЬНЫЙ И ПРОЦЕДУРНЫЙ ТИПЫ .............. 131

ГЛАВА 15. МОДУЛИ И РАЗДЕЛЬНАЯ
КОМПИЛЯЦИЯ...................................................................... 141

ГЛАВА 16. ОПТИМИЗАЦИЯ И СТРУКТУРА
ПРЕ/ПОСТПРОЦЕССОРА ................................................. 153

ПРИЛОЖЕНИЕ A. СИНТАКСИС...................................... 164

ПРИЛОЖЕНИЕ B. НАБОР СИМВОЛОВ ASCII .......... 167

ПРИЛОЖЕНИЕ C. КОМПИЛЯТОР ОБЕРОН0 ......... 168

ЛИТЕРАТУРА ......................................................................... 191

Содержание

От авторов перевода .......................................................... 10
О книге ......................................................................................... 10
О переводе .................................................................................. 10

Введение .................................................................................. 12
Предисловие................................................................................ 12
Благодарности ............................................................................. 14

Глава 1. Введение ................................................................ 15

Глава 2. Язык и синтаксис ............................................... 19
2.1. Упражнения ........................................................................... 24

Глава 3. Регулярные языки ............................................. 27
3.1. Упражнение ........................................................................... 32

Глава 4. Анализ контекстносвободных языков...... 33
4.1. Метод рекурсивного спуска .................................................. 34
4.2. Табличноуправляемый нисходящий синтаксический
анализ .......................................................................................... 38
4.3. Восходящий синтаксический анализ ..................................... 40
4.4. Упражнения ........................................................................... 42

Глава 5. Атрибутные грамматики  и семантики .... 45
5.1. Правила типов ....................................................................... 46
5.2. Правила вычислений ............................................................. 47
5.3. Правила трансляции.............................................................. 48
5.4. Упражнение ........................................................................... 49

Глава 6. Язык программирования Оберон0 ......... 51
6.1. Упражнение ........................................................................... 54

Содержание
6

Глава 7. Синтаксический анализатор
для Оберона0 ....................................................................... 55
7.1. Лексический анализатор ....................................................... 56
7.2. Синтаксический анализатор.................................................. 57
7.3. Устранение синтаксических ошибок...................................... 59
7.4. Упражнения ........................................................................... 64

Глава 8. Учет контекста, заданного
объявлениями ........................................................................ 65
8.1. Объявления ........................................................................... 66
8.2. Записи о типах данных .......................................................... 68
8.3. Представление данных во время выполнения ....................... 69
8.4. Упражнения ........................................................................... 73

Глава 9. RISCархитектура как цель ........................... 75
9.1. Ресурсы и регистры............................................................... 76

Глава 10. Выражения и присваивания ...................... 81
10.1. Прямая генерация кода по принципу стека ......................... 82
10.2. Отсроченная генерация кода............................................... 84
10.3. Индексированные переменные и поля записей................... 89
10.4. Упражнения ......................................................................... 94

Глава 11. Условные и циклические операторы
и логические выражения .................................................. 95
11.1. Сравнения и переходы ........................................................ 96
11.2. Условные и циклические операторы .................................... 97
11.3. Логические операции ........................................................ 101
11.4. Присваивание логическим переменным ........................... 105
11.5. Упражнения ....................................................................... 106

Глава 12. Процедуры и концепция
локализации ......................................................................... 109
12.1. Организация памяти во время выполнения ....................... 110
12.2. Адресация переменных ..................................................... 112
12.3. Параметры ........................................................................ 114
12.4. Объявления и вызовы процедур ........................................ 116

Содержание
7

12.5. Стандартные процедуры ................................................... 121
12.6. Процедурыфункции ......................................................... 122
12.7. Упражнения ....................................................................... 123

Глава 13. Элементарные типы данных .................... 125
13.1. Типы REAL и LONGREAL ..................................................... 126
13.2. Совместимость между числовыми типами данных ............ 127
13.3. Тип данных SET.................................................................. 129
13.4. Упражнения ....................................................................... 130

Глава 14. Открытые массивы, указательный
и процедурный типы ......................................................... 131
14.1. Открытые массивы ............................................................ 132
14.2. Динамические структуры данных и указатели ................... 133
14.3. Процедурные типы ............................................................ 136
14.4. Упражнения ....................................................................... 138

Глава 15. Модули и раздельная компиляция ...... 141
15.1. Принцип скрытия информации.......................................... 142
15.2. Раздельная компиляция .................................................... 143
15.3. Реализация символьных файлов ....................................... 145
15.4. Адресация внешних объектов............................................ 149
15.5. Проверка конфигурационной совместимости ................... 150
15.6. Упражнения ....................................................................... 152

Глава 16. Оптимизация и структура
пре/постпроцессора ........................................................ 153
16.1. Общие соображения ......................................................... 154
16.2.  Простые оптимизации ...................................................... 155
16.3. Исключение повторных вычислений .................................. 156
16.4. Распределение регистров ................................................. 157
16.5. Структура пре/постпроцессорного компилятора .............. 158
16.6. Упражнения ....................................................................... 162

Приложение A. Синтаксис.............................................. 164
A.1. Оберон0 ............................................................................. 164
A.2. Оберон................................................................................. 164
A.3. Символьные файлы ............................................................. 166

Содержание
8

Приложение B. Набор символов ASCII .................... 167

Приложение C. Компилятор Оберон0.................... 168
C.1. Лексический анализатор..................................................... 169
C.2. Синтаксический анализатор ............................................... 172
C.3. Генератор кода ................................................................... 182

Литература ............................................................................ 191

От авторов перевода

О книге

Давно известно, что лучший способ постичь секреты мастерства – это наблюдать
за работой мастера. Эта небольшая, но насыщенная информацией книжка, по сути
дела, представляет собой отчет о такой работе. Ну а то, что ее автор – настоящий
мастер своего дела, сомнению не подлежит, потому что имя профессора Никлауса
Вирта ни в каких дополнительных рекомендациях не нуждается. Эта книга – своего рода мастеркласс, который дает своим ученикам всемирно известный маэстро. Она не является ни «тяжелой» теоретической монографией, ни сборником наставлений и поучений увенчанного лаврами мэтра. Эта книжка – практическое
пособие для всех тех любознательных людей, кто желает разобраться и понять,
что такое компилятор и как он устроен. По мнению автора, без этого ни один программист не может называть себя квалифицированным специалистом.
В отличие от многочисленных книг, которые исчерпывающе описывают и теорию, и разнообразные методы синтаксического анализа, перевода и компиляции,
эта книжка посвящена реализации одногоединственного компилятора современного языка программирования для конкретного компьютера. Но это нисколько не
умаляет ее достоинства. Если обычные книги после прочтения почти всегда оставляют читателя наедине с вопросом «А что же дальше? Где же результат?» или
с загадочными, полными опечаток текстами готовых программ, то эта небольшая
книжка расставляет практически все точки над i, проводя читателя от самого начала до самого конца процесса разработки компилятора, попутно предупреждая
его о неверных шагах и давая ему в руки богатый практический материал. Автор
придерживается принципа «Делай со мной. Делай, как я. Делай лучше меня».
Таким образом, книга Н. Вирта – безусловно, не только прекрасное дополнение к многочисленным и столь же прекрасным фундаментальным трудам по этой
теме, но может и должна использоваться в качестве практического пособия по
изучению компиляторов. Кроме того, простота и доступность преподнесения довольно сложного материала снимает с него покров таинственности и делает его
доступным практически каждому любителю программирования. Остается только
сожалеть о том, что эта книга не была своевременно переведена и издана у нас.
Для практического использования текст компилятора Оберон0, о котором
идет речь в книге, адаптирован к системе БлэкБокс (BlackBox Component Builder –
вариант системы Оберон). Оригинальные и адаптированные исходные тексты
компилятора можно найти на сайте www.oberoncore.ru.

О переводе

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

От авторов перевода
10

информацией. Поэтому наша основная задача при переводе состояла в том, чтобы
сохранить лаконичность и информационную насыщенность авторского текста и
при этом максимально точно довести его суть до читателя, не поддаваясь искушению сдобрить его отсебятиной.
Несмотря на царящие до сих пор «разброд и шатания» в терминологии по этой
теме, мы при переводе, следуя за автором, отдавали предпочтение наиболее устоявшимся, хотя и не всегда правильным и точным, терминам.
В связи с этим нельзя не упомянуть о терминах «frontend» и «backend». Они
уже давно употребляются в разнообразной англоязычной технической литературе, но тем не менее до сих пор не находят адекватных русскоязычных эквивалентов. Чаще всего их перевод зависит от контекста. Применительно к компиляторам
наиболее точными их русскими аналогами являются, пожалуй, «машиннонезависимая часть»  и «машиннозависимая часть» соответственно. Однако мы, теперь уже следуя авторской лаконичности,  предпочли им более абстрактные и менее точные, но более короткие термины – «препроцессор» и «постпроцессор»
соответственно.
Кроме того, список литературы пронумерован, и именные ссылки на него в
тексте заменены номерными. К списку литературы добавлено несколько более
поздних публикаций.
Авторы перевода выражают благодарность В. Н. Лукину за прочтение перевода и сделанные замечания.

Введение

Предисловие

Эта книга появилась из моих конспектов лекций по вводному курсу проектирования компиляторов в ETH (Федеральном технологическом институте) в Цюрихе.
Несколько раз меня просили объяснить необходимость этого курса, так как проектирование компиляторов рассматривается как некий эзотерический предмет,
применяемый только в нескольких узкоспециализированных программистских
фирмах. Поскольку в наши дни все, что не приносит немедленной выгоды, должно быть оправдано, я должен попробовать объяснить, почему я вообще считаю
этот предмет важным и уместным для студентов, изучающих информатику.
Основой любого академического образования является то, что передается не
только знание и, в случае инженерного образования, «ноухау», но и понимание
сути явления и способность проникнуть в его суть. В частности, в информатике
мало поверхностного знания системы, необходимо еще и понимание ее содержания. Каждый образованный программист должен знать возможности компьютера, понимать способы и методы представления и интерпретации программ.
Компилятор преобразует текст программы во внутренний код, это  мост, соединяющий программное обеспечение и аппаратные средства.
Однако комуто может показаться, что нет необходимости знать методы трансляции для понимания связи между исполняемой программой и кодом и еще менее
важно знать, как на самом деле пишется компилятор. Личный опыт преподавателя подсказывает мне, что глубокое понимание предмета лучше всего приходит
при всестороннем проникновении как в общую идею системы, так и в детали ее
реализации. В нашем случае таким проникновением будет написание реального
компилятора.
Конечно, мы должны сосредоточиться на основах. В конце концов, эта книга –
вводный курс, а не справочник для специалистов. Наше первое ограничение касается входного языка. Было бы неуместным рассматривать проектирование компиляторов для больших языков. Язык должен быть небольшим, но тем не менее
должен содержать все поистине фундаментальные элементы языков программирования. Для наших целей мы выбрали подмножество языка Оберон. Второе
ограничение касается целевого компьютера. Он должен иметь обычную структуру и простой набор команд. Наиболее важна практичность обучающих понятий.
Оберон – это общецелевой гибкий и мощный язык, а наш целевой компьютер идеальным образом отражает удачную RISCархитектуру. И наконец, третье ограничение состоит в отказе от изощренных методов оптимизации кода. При таких
условиях можно объяснить весь компилятор в деталях и даже создать его в ограниченные рамками курса сроки.
В главах 2 и 3 рассматриваются основы языка и синтаксиса. Глава 4 посвящена
синтаксическому анализу, то есть методу разбора предложений и программ. Мы

Теория и методы построения компиляторов. Введение
12

сосредоточили внимание на простом, но удивительно мощном методе рекурсивного спуска, который используется в нашем иллюстративном компиляторе. Мы
рассматриваем синтаксический анализ как средство для достижения цели, но не
как самоцель. Глава 5 готовит нас к переходу от синтаксического анализатора
к компилятору, а выбранный метод ставится в зависимость от атрибутов синтаксических конструкций.
После знакомства в главе 6 с языком Оберон0 в главе 7 приводится разработка его синтаксического анализатора методом рекурсивного спуска. Из практических соображений обсуждается также обработка синтаксических ошибок. В главе 8 мы объясняем, почему языки, содержащие объявления и, следовательно,
зависимость от контекста, могут тем не менее обрабатываться как контекстносвободные.
До этого момента не было необходимости в рассмотрении целевого компьютера и набора его команд. Но поскольку последующие главы посвящены теме генерации кода, то становится неизбежной спецификация целевого компьютера (глава 9). Это RISCархитектура с небольшим набором команд и набором регистров.
В связи с этим центральная тема разработки компилятора – генерация последовательностей команд – разнесена по трем главам: код для выражений и присваиваний (глава 10), код для условных операторов и операторов цикла (глава 11), код
для объявлений процедур и обращений к ним (глава 12). Вместе они покрывают
все конструкции языка Оберон0.
Последующие главы посвящены нескольким дополнительным важным конструкциям языков программирования общего назначения. Их трактовка поверхностна и не затрагивает деталей, но подкреплена несколькими упражнениями в конце
соответствующих глав. Рассматриваются следующие темы: элементарные типы
данных (глава 13), открытые массивы, динамические структуры данных и процедурные типы, называемые методами  в объектноориентированной терминологии
(глава 14).
Глава 15 касается модульного конструирования и принципов скрытия информации. Это приводит к теме разработки программного обеспечения в команде, основанной на определении интерфейсов и последующей независимой реализации
частей (модулей). Методика основана на раздельной компиляции модулей с полным контролем совместимости типов всех компонентов интерфейса. Такая методика имеет первостепенное значение для разработки программного обеспечения
в целом и для современных языков программирования в частности.
Наконец, глава 16 дает краткий обзор проблем оптимизации кода. Она необходима, с одной стороны, изза семантической пропасти между исходными языками
и архитектурами компьютеров, а с другой – изза нашего желания как можно полнее использовать все доступные ресурсы компьютеров.

Теория и методы построения компиляторов. Введение
13

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

Я выражаю мои искренние благодарности всем, кто способствовал своими предложениями и критикой этой книги, которая созрела за многие годы преподавания
курса проектирования компиляторов в ETH в Цюрихе. В частности, я обязан Ханспетеру Месенбоку и Михаэлю Францу, которые внимательно прочли рукопись и
подвергли ее критическому разбору. Кроме того, я благодарю Штефана Геринга,
Штефана Людвига и Джозефа Темпла за их ценные комментарии и сотрудничество в курсе обучения.
Никлаус Вирт
Декабрь 1995