Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Конструирование компиляторов. Основания и приложения

Покупка
Новинка
Артикул: 890830.01.99
Доступ онлайн
1 599 ₽
В корзину
В книге рассматриваются практические основы конструирования компиляторов — от лексического и синтаксического анализа до семантической обработки и генерирования кода. В качестве сквозного примера описан и реализован компилятор простого Java-подобного языка программирования (MicroJava). Навыки конструирования компиляторов найдут применение всюду, где есть структурированные входные данные, которые можно описать грамматикой, — от простых наборов команд до системных журналов и файлов конфигурации. Издание ориентировано на студентов факультетов информатики и смежных дисциплин, а также на программистов-практиков, которые хотят применять базовые методы компиляции в повседневной работе.
53
126
181
221
Мёссенбёк, Х. Конструирование компиляторов. Основания и приложения : практическое руководство / Х. Мёссенбёк ; пер. с англ. А. А. Слинкина. – Москва : ДМК Пресс, 2025. - 278 с. – ISBN 978-5-93700-391-1. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2275239 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Ханспетер Мёссенбёк
Конструирование  
компиляторов


Hanspeter Mössenböck
Compiler  
Construction
Fundamentals and Applications


Ханспетер Мёссенбёк
Конструирование 
компиляторов
Основания и приложения
Москва, 2025


УДК	 004.4'422
ББК 32.972
М53
Мёссенбёк Х.
М53 	 Конструирование компиляторов / пер. с англ. А. А. Слинкина. – М.: ДМК 
Пресс, 2025. – 276 с.: ил. 
ISBN 978-5-93700-391-1
В книге рассматриваются практические основы конструирования компиляторов – от лексического и синтаксического анализа до семантической обработки 
и генерирования кода. В качестве сквозного примера описан и реализован компилятор простого Java-подобного языка программирования (MicroJava). Навыки 
конструирования компиляторов найдут применение всюду, где есть структурированные входные данные, которые можно описать грамматикой, – от простых 
наборов команд до системных журналов и файлов конфигурации.
Издание ориентировано на студентов факультетов информатики и смежных 
дисциплин, а также на программистов-практиков, которые хотят применять 
базовые методы компиляции в повседневной работе.
УДК  004.4'422
ББК  32.972
First published in the German language edition: “Compilerbau” by Hanspeter Mössenböck, 
© dpunkt.verlag 2024.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.
ISBN 978-3-031-84812-4 (англ.) 	
©  Springer Nature Switzerland AG 
2025 (English translation)
ISBN 978-5-93700-391-1 (рус.) 	
©  Перевод, оформление, издание, 
ДМК Пресс, 2025


Содержание
От издательства.......................................................................................................10
Вступительное слово Никлауса Вирта.............................................................11
Предисловие.............................................................................................................12
Глава 1. Общие сведения.....................................................................................14
1.1. Краткая история компиляторов........................................................................15
1.2. Динамическая структура компилятора............................................................18
1.2.1. Однопроходные и многопроходные компиляторы................................20
1.2.2. Компилятор и интерпретатор....................................................................22
1.3. Статическая структура компилятора................................................................23
1.4. Грамматики..........................................................................................................24
1.4.1. Нотация РБНФ для грамматик...................................................................24
1.4.2. Пример: грамматика арифметических выражений...............................25
1.4.3. Терминальные начальные символы нетерминальных символов.........27
1.4.4. Терминальные последующие символы нетерминальных символов...27
1.4.5. Еще о терминологии формальных языков...............................................28
1.4.6. Рекурсия.........................................................................................................30
1.4.7. Исключение левой рекурсии.......................................................................30
1.4.8. Классификация грамматик по Хомскому.................................................31
1.5. Синтаксические деревья.....................................................................................32
1.5.1. Неоднозначность..........................................................................................33
1.6. MicroJava................................................................................................................35
1.7. Упражнения...........................................................................................................36
Глава 2. Лексический анализ...............................................................................39
2.1. Регулярные грамматики и конечные автоматы.............................................40
2.1.1. Ограничения регулярных грамматик.......................................................42
2.1.2. Детерминированные конечные автоматы...............................................42
2.2. Сканер как детерминированный конечный автомат....................................44
2.3. Реализация ДКА...................................................................................................45
2.3.1. Реализация сканера.....................................................................................46
2.3.2. К вопросу об эффективности......................................................................50
2.4. Упражнения..........................................................................................................51
Глава 3. Синтаксический анализ........................................................................53
3.1. Контекстно-свободные грамматики и автоматы с магазинной памятью....53
3.1.1. Автоматы с магазинной памятью..............................................................54


6    Содержание
3.1.2. Ограничения контекстно-свободных грамматик...................................56
3.1.3. Контекстные условия...................................................................................57
3.1.4. Сравнение регулярных и контекстно-свободных грамматик...............58
3.2. Метод рекурсивного спуска...............................................................................59
3.2.1. Парсер как класс...........................................................................................60
3.2.2. Разбор терминальных символов................................................................60
3.2.3. Разбор нетерминальных символов...........................................................61
3.2.4. Разбор последовательностей......................................................................62
3.2.5. Разбор альтернатив......................................................................................63
3.2.6. Разбор факультативных элементов РБНФ................................................64
3.2.7. Разбор повторений РБНФ............................................................................64
3.2.8. Работа с большими множествами терминальных начальных  
символов..................................................................................................................65
3.2.9. Как избежать нескольких проверок...........................................................66
3.2.10. И снова о вычислении терминальных начальных символов..............67
3.2.11. Синтаксическое дерево, получающееся в результате разбора 
методом рекурсивного спуска..............................................................................69
3.3. Свойство LL(1)......................................................................................................70
3.3.1. Устранение LL(1)-конфликтов....................................................................70
3.3.2. Исключение левой рекурсии......................................................................72
3.3.3. Скрытые LL(1)-конфликты в РБНФ-конструкциях.................................72
3.3.4. Висячее else...................................................................................................74
3.3.5. Другие требования к грамматике..............................................................75
3.4. Обработка синтаксических ошибок..................................................................76
3.4.1. Обработка ошибок в режиме паники........................................................76
3.4.2. Обработка ошибок с общими якорями.....................................................77
3.4.3. Обработка ошибок со специальными якорями.......................................85
3.5. Упражнения..........................................................................................................88
Глава 4. Атрибутные грамматики......................................................................91
4.1. Компоненты атрибутных грамматик...............................................................92
4.1.1. Семантические действия............................................................................92
4.1.2. Выходные атрибуты.....................................................................................93
4.1.3. Входные атрибуты........................................................................................93
4.2. Примеры...............................................................................................................94
4.2.1. Обработка объявлений переменных.........................................................94
4.2.2. Вычисление константных выражений......................................................95
4.2.3. Статистика продаж.......................................................................................97
4.2.4. Язык описания изображений.....................................................................98
4.2.5. Преобразование из инфиксной в постфиксную нотацию...................100
4.3. Упражнения........................................................................................................101
Глава 5. Таблица символов................................................................................105
5.1. Записи объектов.................................................................................................106
5.1.1. Глобальные переменные...........................................................................108
5.1.2. Локальные переменные............................................................................109


Содержание    7
5.1.3. Вставка имен в таблицу символов...........................................................110
5.1.4. Предопределенные имена........................................................................110
5.2. Записи областей видимости............................................................................111
5.2.1. Вставка имен в текущую область видимости.........................................115
5.2.2. Поиск имен в областях видимости..........................................................115
5.3. Записи структур.................................................................................................116
5.4. Проверка типов..................................................................................................118
5.4.1. Эквивалентность по именам....................................................................119
5.4.2. Структурная эквивалентность..................................................................119
5.4.3. Варианты совместимости типов..............................................................120
5.5. Разрешение LL(1)-конфликтов с помощью таблицы символов.................122
5.6. Инициализация таблицы символов................................................................123
5.7. Упражнения.........................................................................................................124
Глава 6. Генерирование кода............................................................................126
6.1. ВМ MicroJava.......................................................................................................128
6.1.1. Области памяти..........................................................................................129
6.1.2. Система команд..........................................................................................132
6.2. Буфер кода..........................................................................................................143
6.3. Дескрипторы операндов...................................................................................143
6.4. Загрузка значений.............................................................................................147
6.4.1. Загрузка переменных................................................................................148
6.4.2. Загрузка констант.......................................................................................148
6.4.3. Загрузка полей объекта.............................................................................149
6.4.4. Загрузка элементов массива.....................................................................150
6.5. Выражения..........................................................................................................152
6.6. Присваивания.....................................................................................................155
6.6.1. Предложения инкремента и декремента...............................................157
6.7. Переходы и метки..............................................................................................158
6.7.1. Прямые и обратные переходы..................................................................159
6.7.2. Метки............................................................................................................160
6.7.3. Условия.........................................................................................................162
6.8. Управление потоком.........................................................................................164
6.8.1. Предложение while.....................................................................................164
6.8.2. Предложение if............................................................................................165
6.8.3. Предложение break.....................................................................................167
6.8.4. Закороченное вычисление составных булевых выражений................167
6.9. Методы................................................................................................................170
6.9.1. Вызов методов типа void...........................................................................170
6.9.2. Вызов функциональных методов............................................................171
6.9.3. Кадры стека.................................................................................................172
6.9.4. Объявления методов..................................................................................173
6.9.5. Формальные параметры...........................................................................174
6.9.6. Фактические параметры...........................................................................175
6.9.7. Предложение return....................................................................................176
6.10. Объектный файл..............................................................................................177
6.11. Упражнения......................................................................................................178


8    Содержание
Глава 7. Генератор компиляторов Coco/R.....................................................181
7.1. Спецификация сканера.....................................................................................185
7.1.1. Наборы литер..............................................................................................185
7.1.2. Терминальные символы............................................................................185
7.1.3. Прагмы.........................................................................................................186
7.1.4. Комментарии...............................................................................................187
7.1.5. Игнорируемые символы............................................................................187
7.1.6. Чувствительность к регистру....................................................................187
7.1.7. Интерфейс сгенерированного сканера....................................................188
7.2. Спецификация парсера.....................................................................................188
7.2.1. Продукции...................................................................................................189
7.2.2. Семантические действия...........................................................................189
7.2.3. Атрибуты......................................................................................................190
7.2.4. Трансляция в методы парсера..................................................................191
7.2.5. Символ ANY.................................................................................................191
7.2.6. Генерирование сканера и парсера...........................................................193
7.2.7. Интерфейс сгенерированного парсера....................................................194
7.3. Обработка ошибок.............................................................................................194
7.3.1. Сообщения о синтаксических ошибках..................................................194
7.3.2. Восстановление после синтаксических ошибок....................................195
7.3.3. Сообщения о семантических ошибках....................................................196
7.3.4. Класс Errors..................................................................................................196
7.4. LL(1)-конфликты................................................................................................197
7.4.1. Разрешение конфликтов путем заглядывания вперед  
на несколько символов........................................................................................198
7.4.2. Разрешение конфликтов с помощью семантической информации.....200
7.5. Примеры..............................................................................................................201
7.5.1. Чтение двоичного дерева..........................................................................201
7.5.2. Генератор анкет..........................................................................................203
7.5.3. Абстрактные синтаксические деревья....................................................208
7.6. Упражнения.........................................................................................................217
Глава 8. Восходящий синтаксический анализ............................................221
8.1. Как работает восходящий парсер....................................................................221
8.2. LR-грамматики...................................................................................................226
8.2.1. LR(0)-грамматики.......................................................................................227
8.2.2. LR(1)-грамматики.......................................................................................227
8.2.3. LALR(1)-грамматики..................................................................................227
8.2.4. Сильные стороны восходящего синтаксического анализа..................229
8.2.5. Сильные стороны восходящего синтаксического анализа..................229
8.3. Генерирование LR-таблиц................................................................................230
8.3.1. Ядро, замыкание и последующее состояние..........................................231
8.3.2. Алгоритм генерирования таблиц.............................................................233
8.3.3. LR(1)-конфликты........................................................................................237
8.4. Сжатие LR-таблиц..............................................................................................238
8.4.1. Объединение действий переноса и свертки..........................................238


Содержание    9
8.4.2. Объединение строк....................................................................................239
8.4.3. Пример.........................................................................................................240
8.5. Семантическая обработка................................................................................241
8.5.1. Семантические действия..........................................................................242
8.5.2. Атрибуты......................................................................................................242
8.5.3. Оценка..........................................................................................................244
8.6. Обработка ошибок в LR-грамматиках............................................................245
8.6.1. Алгоритм восстановления после ошибки...............................................246
8.6.2. Пример.........................................................................................................246
8.6.3. Направляющие символы для поиска пути эвакуации..........................248
8.6.4. Нахождение направляющих символов...................................................250
8.6.5. Оценка..........................................................................................................251
8.7. Упражнения.........................................................................................................252
Приложение А. Язык MicroJava........................................................................254
Приложение В. Компилятор MicroJava..........................................................260
Литература..............................................................................................................266
Предметный указатель.......................................................................................268


От издательства
Отзывы и пожелания
Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете 
об этой книге – что понравилось или, может быть, не понравилось. Отзывы 
важны для нас, чтобы выпускать книги, которые будут для вас максимально 
полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на 
страницу книги и оставив комментарий в разделе «Отзывы и рецензии». 
Также можно послать письмо главному редактору по адресу dmkpress@gmail.
com; при этом укажите название книги в теме письма. 
Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http://
dmkpress.com/authors/publish_book/ или напишите в  издательство по адресу 
dmkpress@gmail.com.
Список опечаток
Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое качество наших текстов, ошибки все равно случаются. Если вы найдете 
ошибку в одной из наших книг, мы будем очень благодарны, если вы сообщите о ней главному редактору по адресу dmkpress@gmail.com. Сделав это, 
вы избавите других читателей от недопонимания и поможете нам улучшить 
последующие издания этой книги. 
Нарушение авторских прав
Пиратство в интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав 
и лицензирования. Если вы столкнетесь в интернете с незаконной публикацией 
какой-либо из наших книг, пожалуйста, пришлите нам ссылку на интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу электронной почты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря 
которой мы можем предоставлять вам качественные материалы.


Доступ онлайн
1 599 ₽
В корзину