Основы компиляции: инкрементный подход

Автор Джереми Сик

Компиляторы традиционно считаются одной из самых трудных для понимания и изучения тем. Обычно в книгах каждая глава посвящена отдельному проходу компилятора. Но такая структура не позволяет раскрыть, как языковые средства влияют на решения, принимаемые при проектировании компилятора.
Вместо этого в «Основах компиляции» выбран инкрементный подход: компилятор совершенствуется последовательно, и читатель может написать весь код самостоятельно. Книга помогает создать собственный компилятор для небольшого, но достаточно мощного языка программирования, постепенно, шаг за шагом вводя все более сложные языковые средства.
Джереми Сик объясняет важнейшие концепции, алгоритмы и структуры данных, лежащие в основе современных компиляторов, и закладывает основу для изучения более сложных тем. Это краткое, но доступное руководство уже давно используют студенты и профессионалы.

• Язык: Русский
• Издатель: Питер
• Дата выпуска: 29 янв. 2024 г.
• ISBN: 9785446121168

Предварительный просмотр книги

Предисловие

Всем разработчикам знаком тот магический момент, когда при нажатии кнопки run программа начинает выполняться. Программа, написанная на языке высокого уровня, каким-то образом выполняется на компьютере, способном работать только с битами. В этой книге раскрываются секреты волшебства, благодаря которым подобное становится возможным. Начиная с новаторской работы Бэкуса (Backus) и его коллег в 1950-х годах, компьютерные теоретики разработали методы построения компиляторов — программ, автоматически преобразующих код, написанный на языках высокого уровня, в машинный код.

В этой книге мы займемся построением собственного компилятора для небольшого, но мощного языка. Попутно мы разберем важнейшие концепции, алгоритмы и структуры данных, лежащие в основе компиляторов. Вы сможете лучше понять, какая связь существует между программами и аппаратной частью компьютера. Это необходимо, чтобы рассуждать о том, что происходит на стыке аппаратного и программного обеспечения: о времени выполнения, программных ошибках и уязвимостях в области безопасности. Читателям, которые намерены связать с построением компиляторов свою карьеру, книга облегчит переход к таким нетривиальным темам, как JIT-компиляция, анализ программ и оптимизация кода. Читателям, интересующимся проектированием и реализацией языков программирования, мы продемонстрируем связь между решениями, принимаемыми при создании языка, и их влиянием на компилятор и сгенерированный код.

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

Самый очевидный способ описать работу компилятора — посвятить каждую главу отдельному проходу. К сожалению, при таком подходе остается нераскрытым вопрос, как языковые средства влияют на решения, принимаемые в ходе проектирования компилятора. Поэтому в книге выбран инкрементный подход: в каждой главе строится полный компилятор, начиная с маленького входного языка, поддерживающего только арифметические операции и переменные. По мере продвижения по главам мы будем добавлять новые возможности и расширять компилятор по мере необходимости.

Наш выбор языковых средств продиктован стремлением продемонстрировать фундаментальные концепции и алгоритмы, используемые в компиляторах.

• Мы начнем с целочисленной арифметики и локальных переменных в главах 1 и 2, где будут представлены фундаментальные средства построения компиляторов: абстрактные синтаксические деревья и рекурсивные функции.

• В главе 3 метод раскраски графа применяется для распределения переменных между машинными регистрами.

• В главе 4 добавляются условные выражения, для преобразования которых в условные команды goto будет применен элегантный рекурсивный алгоритм.

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

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

• В главе 7 добавляются функции как первоклассные значения без лексической области видимости, по аналогии с функциями языка программирования C (Kernighan and Ritchie, 1988)¹. Читатель познакомится со стеком вызовов процедур и соглашениями о вызовах и их влиянием на выделение регистров и сборку мусора. Вы также узнаете, как генерировать эффективные хвостовые вызовы.

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

• В главе 9 добавляется динамическая типизация. До ее появления в языках использовалась статическая типизация. Мы расширим язык со статической типизацией типом Any, который становится признаком применения динамической типизации при компиляции.

• В главе 10 тип Any, представленный в главе 9, используется для реализации языка с постепенной типизацией, в котором в разных частях программы может использоваться статическая или динамическая типизация. Читатель реализует поддержку времени выполнения для заместителей, позволяющих безопасно перемещать значения между разными областями.

• В главе 11 добавляются обобщения с автоматической упаковкой, использующие тип Any и преобразования типов, реализованные в главах 9 и 10.

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

С 2009 года черновики этой книги используются в 16-недельном курсе построения компиляторов для студентов старших курсов в Университете Колорадо и Университете штата Индиана. Слушатели этого курса уже владеют основами программирования, структур данных, алгоритмов и дискретной математики. В начале обучения студенты разбиваются на группы от 2 до 4 человек. Группы изучают главы, соответствующие их интересам, начиная с главы 2, по одной примерно за две недели, соблюдая при этом зависимости между главами, показанные на илл. 0.1. Глава 7 (функции) зависит от главы 6 (кортежи) только в реализации эффективных хвостовых вызовов. Последние две недели курса отводятся под курсовой проект, в котором студенты проектируют и реализуют расширение компилятора по своему выбору. Для поддержки таких проектов могут использоваться заключительные главы книги. Во многие главы включены задания повышенной сложности.

Илл. 0.1. Диаграмма зависимостей между главами

Для университетских учебных курсов, строящихся по триместровой системе (около 10 недель), мы рекомендуем завершить курс на главе 6 или 7 и предоставлять студентам часть вспомогательного кода для каждого прохода компилятора. Курс можно адаптировать так, чтобы уделить особое внимание функциональным языкам; для этого целесообразно пропустить главу 5 (циклы) и включить главу 8 (лямбда-выражения). Чтобы адаптировать курс для языков с динамической типизацией, включите в него главу 9.

Книга используется на курсах построения компиляторов в Политехническом университете штата Калифорния, Университете Портленда, Технологическом институте Роуз-Хульман, Университете Фрайбурга, Массачусетском университете Лоуэлла и Вермонтском университете.

Мы используем язык Racket как для реализации компилятора, так и для входного языка, так что от читателя потребуется хорошее знание Racket или Scheme. Существует много отличных ресурсов для изучения Scheme и Racket (Dybvig, 1987a; Abelson and Sussman, 1996; Friedman and Felleisen, 1996; Felleisen et al., 2001; Felleisen et al., 2013; Flatt, Findler, and PLT, 2014). Вспомогательный код книги доступен в репозитории GitHub по следующему адресу:

https://github.com/IUCompilerCourse/

Компилятор генерирует код на языке ассемблера x86 (Intel, 2015), поэтому полезно, но не обязательно изучить работу вычислительных систем (Bryant and O’Hallaron, 2010). В книге представлены части языка ассемблера x86-64, необходимые для компилятора. Мы используем соглашения о вызовах System V (Bryant and O’Hallaron, 2005; Matz et al., 2013), так что генерируемый код на языке ассемблера будет работать с системой исполнения (написанной на C), если он откомпилирован компилятором GNU C (gcc) в ОС Linux и MacOS на оборудовании Intel. В ОС Windows gcc использует соглашения о вызовах Microsoft x64 (Microsoft, 2018, 2020), поэтому сгенерированный код на языке ассемблера не будет работать с системой исполнения в Windows. Одно из возможных решений — использовать виртуальную машину с Linux в качестве гостевой ОС.

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

Практика разработки компиляторов в Университете штата Индиана восходит к исследованиям и курсам Дэниела Фридмана (Daniel Friedman) по языкам программирования в 1970-х и 1980-х годах. Один из его студентов, Кент Дибвиг (Kent Dybvig), реализовал Chez Scheme (Dybvig, 2006) — эффективный компилятор Scheme коммерческого уровня. В 1990-е и 2000-е годы Дибвиг вел курс проектирования компиляторов и продолжал разработку Chez Scheme. Учебный курс постепенно развивался, в него включались новые обучающие приемы, а также элементы реально существующих компиляторов. Одно из предложений Фридмана заключалось в том, чтобы разбить компилятор на множество мелких проходов. Другое предложение, названное «игра», — тестировать код, сгенерированный при каждом проходе, с применением интерпретаторов.

Дибвиг с помощью своих студентов Дипанвиты Саркар (Dipanwita Sarkar) и Эндрю Кипа (Andrew Keep) разработал инфраструктуру для поддержки этого метода и доработал курс так, чтобы использовать микропроходы (Sarkar, Waddell, and Dybvig, 2004; Keep, 2012). Многие решения в области проектирования компиляторов, представленные в книге, были вдохновлены описаниями Дибвига и Кипа (2010). В середине 2000-х годов студент Дибвига Абдулазиз Гулум (Abdulaziz Ghuloum) заметил, что при строго направленной структуре курса студентам было труднее понять обоснование выбора тех или иных проектировочных решений. Гулум предложил инкрементный подход (Ghuloum, 2006), который был взят за основу в этой книге.

Я благодарен многим студентам, ассистентам кафедры на курсе проектирования компиляторов в Университете штата Индиана, в том числе Карлу Факторе (Carl Factora), Райану Скотту (Ryan Scott), Кэмерону Сордсу (Cameron Swords) и Крису Уэйлзу (Chris Wailes). Спасибо Андре Кюленшмидту (Andre Kuhlenschmidt) за работу над сборщиком мусора и интерпретатором x86, Майклу Воллмеру (Michael Vollmer) за работу над эффективными хвостовыми вызовами и Майклу Витусеку (Michael Vitousek) за помощь с внедрением инкрементного курса проектирования компиляторов в Университете штата Индиана.

Спасибо профессорам Бор-Ю Чану (Bor-Yuh Chang), Джону Клементсу (John Clements), Джею Маккарти (Jay McCarthy), Джозефу Ниру (Joseph Near), Райа­ну Ньютону (Ryan Newton), Нейту Нистрому (Nate Nystrom), Питеру Тиманну (Peter Thiemann), Эндрю Толмачу (Andrew Tolmach) и Майклу Волловски (Michael Wollowski) за учебные курсы, в основу которых были положены черновики этой книги, и за обратную связь. Спасибо Национальному научному фонду за гранты, обеспечившие поддержку этой работы: номера грантов 1518844, 1763922 и 1814460.

Я благодарен Рональду Гарсиа (Ronald Garcia) за то, что он помог мне выжить на курсе Дибвига по проектированию компиляторов в начале 2000-х — и особенно за то, что он нашел ошибку, из-за которой у нашего сборщика мусора сносило крышу!

Джереми Дж. Сик. Блумингтон, штат Индиана

---

¹ Керниган Б., Ритчи Д. «Язык программирования С».

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

В этой главе будут рассмотрены основные средства, необходимые для реализации компилятора. Программы обычно вводятся в компьютер в виде текста, то есть последовательности символов. Представление программы в виде текста называется конкретным синтаксисом (concrete syntax). Конкретный синтаксис используется для записи и анализа программ. Внутри компилятора используются абстрактные синтаксические деревья (AST, abstract syntax tree), которые формируют представления программ, позволяющие компилятору выполнять необходимые операции. Процесс преобразования конкретного синтаксиса в абстрактный называется парсингом, а программный код, в котором он реализуется, — парсером. Теория и реализация парсинга программ в книге не рассматривается. Читателям, интересующимся данной процедурой на достаточно серьезном уровне, стоит обратиться к книге (Aho et al., 2006)². Парсер включается в исходный код для преобразования конкретного синтаксиса в абстрактный.

В зависимости от языка программирования, на котором написан компилятор, существует много разных способов представления абстрактных синтаксических деревьев внутри компилятора. Для представления AST в книге будет использоваться конструкция struct языка Racket (раздел 1.1). Грамматики будут использоваться для определения абстрактного синтаксиса языков программирования (раздел 1.2), а поиск по шаблону — для поиска отдельных узлов AST (раздел 1.3). Рекурсивные функции будут использоваться для построения и разложения AST (раздел 1.4). В этой главе приводится краткое вводное описание этих компонентов.

1.1. Абстрактные синтаксические деревья

Компиляторы используют абстрактные синтаксические деревья для представления программ, поскольку, обрабатывая фрагмент программы, они должны знать в том числе, какой языковой конструкции он соответствует, какие элементы содержит. Рассмотрим программу в левой части схемы и диаграмму AST справа (1.1). Программа выполняет операцию сложения, состоящую из двух элементов: операции чтения и операции изменения знака. Операция изменения знака включает еще один элемент – целочисленную константу 8. Используя дерево для представления программы, можно легко переходить от фрагмента программы к его составным элементам.

         (1.1)

Для описания AST будет использоваться стандартная терминология: каждый прямоугольник на схеме выше называется узлом (node). Линии со стрелками соединяют узлы с их потомками, которые также являются узлами (дочерними). Узел верхнего уровня называется корневым. У каждого узла, кроме корневого, имеется родитель (то есть узел, по отношению к которому этот узел является дочерним). Если у узла нет дочерних узлов, такой узел называется листовым; в противном случае он называется внутренним узлом.

Для каждой разновидности узлов мы определим структуру (struct) Racket. Для этой главы достаточно всего двух разновидностей узлов: для целочисленных констант (литералов) и для примитивных операций. Ниже приведено определение struct для целочисленных констант³.

(struct Int (value))

Целочисленный узел содержит только целое значение. Мы будем использовать соглашение, в соответствии с которым имена структур (такие, как Int) записываются с прописной буквы. Чтобы создать узел AST для целого числа 8, используется запись (Int 8).

(define eight (Int 8))

Значение, созданное обозначением (Int 8), называется экземпляром структуры Int.

Определение структуры для примитивных операций выглядит так:

(struct Prim (op args))

Узел примитивной операции включает обозначение оператора op и список дочерних аргументов args. Например, при создании AST для изменения знака числа 8 используется следующая конструкция:

(define neg-eight (Prim '- (list eight)))

У примитивных операций может быть нуль и более дочерних узлов. У оператора read их нуль:

(define rd (Prim 'read '()))

Оператор сложения имеет два дочерних узла:

(define ast1_1 (Prim '+ (list rd neg-eight)))

В отношении структуры Prim было принято проектировочное решение. Вместо того чтобы использовать одну структуру для нескольких разных операций (read, + и -), можно было определить отдельную структуру для каждой операции:

(struct Read ())

(struct Add (left right))

(struct Neg (value))

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

Чтобы откомпилировать такую программу, как (1.1), необходимо знать, что с корневым узлом связана операция сложения, и иметь возможность обратиться к двум его дочерним узлам. Для подобных запросов в Racket существует механизм поиска по шаблону, который более подробно рассматривается в разделе 1.3.

Конкретный синтаксис программы часто приводится даже в том случае, когда на самом деле имеется в виду AST, потому что конкретный синтаксис более компактный. Мы рекомендуем всегда рассматривать программы как абстрактные синтаксические деревья.

1.2. Грамматики

Язык программирования можно рассматривать как множество программ. Это множество бесконечно (то есть всегда можно создать программу большего ­размера), так что язык невозможно описать простым перечислением всех его программ. Вместо этого записывается набор правил построения программ — контекстно-свободная грамматика. Грамматики часто используются для определения конкретного синтаксиса языка, но они также могут использоваться для описания абстрактного синтаксиса. Правила записываются как разновидность формы Бэкуса — Наура (BNF) (Backus et al., 1960; Knuth, 1964). Для примера можно описать маленький язык LInt, состоящий из целых чисел и арифметических операций.

Первое правило грамматики для абстрактного синтаксиса LInt гласит, что экземпляр структуры Int является выражением:

exp ::= (Int int)       (1.2)

У каждого правила есть левая и правая сторона. Если имеется узел AST, соответствующий правой стороне, это означает, что его можно классифицировать в соответствии с левой стороной. Символы, записанные моноширинным шрифтом (например, Int), называются терминальными; они должны буквально входить в программу, чтобы правило было применимо. В наших грамматиках не упоминаются пропуски (то есть такие символы-ограничители, как пробелы, табуляции и новые строки.) Пропуски могут вставляться между символами для устранения неоднозначности и улучшения удобочитаемости. Имя, определяемое правилами грамматики (такое, как exp), является нетерминальным. Имя int тоже является нетерминальным, но вместо того чтобы определять его правилом грамматики, мы определяем его следующим описанием. int представляет собой последовательность десятичных цифр (от 0 до 9), которая может начинаться с необязательного знака «–» (минус, для отрицательных чисел) и позволяет представлять целые числа в диапазоне от –2⁶² до 2⁶² – 1. Такое определение открывает возможность представления целых чисел в 63-разрядном виде, что немного упрощает вычисления. Таким образом, эти числа соответствуют типу данных Racket fixnum на 64-разрядных машинах.

Второе правило грамматики — операция read, которая получает целое число от пользователя программы.

exp ::= (Prim ’read ())      (1.3)

Третье правило классифицирует изменение знака узла exp как exp.

exp ::= (Prim ’- (exp))       (1.4)

Эти правила можно применить для классификации AST, принадлежащих языку LInt. Например, по правилу (1.2) (Int 8) является exp (выражением), и тогда по правилу (1.4) следующее AST тоже является exp.

        (1.5)

Следующие два правила грамматики предназначены для сложения и вычитания выражений:

exp ::= (Prim ’+ (exp exp))         (1.6)

exp ::= (Prim ’- (exp exp))        (1.7)

Теперь можно проверить, что AST (1.1) является exp в LInt. Мы знаем, что (Prim 'read ()) является exp согласно правилу (1.3), и мы уже классифицировали (Prim '- ((Int 8))) как exp, поэтому применение правила (1.6) доказывает, что

(Prim ’+ ((Prim ’read ()) (Prim ’- ((Int 8)))))

также является exp в языке LInt.

Если имеется AST, к которому эти правила неприменимы, то AST не принадлежит LInt. Например, программа (* (read) 8) не