Конструирование компиляторов. Основания и приложения
Покупка
Новинка
Тематика:
Программирование на Java
Издательство:
ДМК Пресс
Автор:
Мёссенбёк Ханспетер
Перевод:
Слинкин Алексей Александрович
Год издания: 2025
Кол-во страниц: 278
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
Профессиональное образование
ISBN: 978-5-93700-391-1
Артикул: 890830.01.99
В книге рассматриваются практические основы конструирования компиляторов — от лексического и синтаксического анализа до семантической обработки и генерирования кода. В качестве сквозного примера описан и реализован компилятор простого Java-подобного языка программирования (MicroJava). Навыки конструирования компиляторов найдут применение всюду, где есть структурированные входные данные, которые можно описать грамматикой, — от простых наборов команд до системных журналов и файлов конфигурации.
Издание ориентировано на студентов факультетов информатики и смежных дисциплин, а также на программистов-практиков, которые хотят применять базовые методы компиляции в повседневной работе.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Ханспетер Мёссенбёк Конструирование компиляторов
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. Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.