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

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

Москва, 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». Они
уже давно употребляются в разнообразной англоязычной технической литературе, но тем не менее до сих пор не находят адекватных русскоязычных эквивалентов. Чаще всего их перевод зависит от контекста. Применительно к компиляторам
наиболее точными их русскими аналогами являются, пожалуй, «машиннонезависимая часть»  и «машиннозависимая часть» соответственно. Однако мы, теперь уже следуя авторской лаконичности,  предпочли им более абстрактные и менее точные, но более короткие термины – «препроцессор» и «постпроцессор»
соответственно.
Кроме того, список литературы пронумерован, и именные ссылки на него в
тексте заменены номерными. К списку литературы добавлено несколько более
поздних публикаций.
Авторы перевода выражают благодарность В. Н. Лукину за прочтение перевода и сделанные замечания.