Обзор систем для перехода от исходного кода к исполняемой программе.
В какой-то момент каждая программа, которую мы используем, была скомпилирована компилятором. От настольных приложений до встроенного программного обеспечения в микроволновой печи. Все языки программирования, включая ассемблер, скомпилированы.
Компилятор - это программа, которая переводит текст или другие программы в новую программу.
Вывод компилятора может быть разным. Компиляторы могут изменять язык исходного кода (транспиляторы), создавать байт-код для интерпретации или машинный код для собственного исполнения. По своей сути компиляторы - это переводчики.
Структура компилятора
Сложные системы компилятора можно разделить на три этапа. Внешний интерфейс отвечает за понимание исходного кода. Он будет читать, проверять и преобразовывать свои входные данные в общее промежуточное представление (IR), которое будет использоваться на более поздних этапах. Второй шаг - оптимизатор. Оптимизатор использует серию проходов для изменения промежуточного представления. С каждой модификацией окончательное поведение программы останется прежним, но ее выполнение будет улучшаться. Последний шаг - задняя часть. Серверная часть принимает оптимизированное промежуточное представление и преобразует его в целевой вывод. Выходные данные могут быть байт-кодом для использования с интерпретатором или собственным исполняемым кодом для конкретной архитектуры машины.
Различие между шагами позволяет создавать универсальные компиляторы. Разделение обязанностей позволяет компиляторам GCC и LLVM поддерживать большое количество языков. Для каждого языка используется уникальный интерфейс для понимания и проверки правил языка ввода. Все внешние интерфейсы обрабатывают свой ввод для создания общего промежуточного представления. Это позволяет создать единственный оптимизатор - наиболее сложную часть компилятора. Для поддержки многих аппаратных архитектур (x86, x64, ARM, MIPS,…) написана уникальная серверная часть. Каждый бэкэнд принимает одно и то же промежуточное представление, а затем испускает программу для своей назначенной цели.
Внешний интерфейс
Внешний интерфейс компилятора отвечает за понимание языка. Он проверяет правильность введенного кода и выдает всю информацию, необходимую для последующих шагов. Передняя часть создаст таблицы промежуточных представлений и символов.
Внешний интерфейс компилятора может принимать несколько форм. Основными компонентами являются сканер, синтаксический анализатор, анализатор и преобразование промежуточного представления. На протяжении этих этапов используется серия таблиц символов для хранения и извлечения данных об обработанном коде. В таблицах символов хранятся сведения обо всех классах, функциях и глобальных данных.
Сканер
Сканер, который также может называться лексическим анализатором или лексическим анализатором, предназначен для разделения исходного кода на числа, операторы и слова. Например, учитывая следующее предложение Scanners identify words., сканер выдаст следующие лексемы:
Scanners _ // A single space identify _ // A single space words .
Для создания лексем сканер использует шаблоны. Шаблон - это допустимая последовательность символов, которая может быть объединена в лексему. Чаще всего шаблон можно представить с помощью регулярного выражения или фиксированной последовательности символов.
Каждая лексема представляет собой определенный образец кода. В зависимости от наблюдаемой закономерности некоторые лексемы будут объединены тегом. Пара лексема-тег называется токеном. В отличие от лексем, которые учитывают весь текст в исходном файле, токен будет создаваться только для символов, относящихся к синтаксическому анализатору. В приведенном выше примере пробел является разделителем. Как только сканер завершит работу, пробелы больше не актуальны. Токены, которые генерирует сканер, не ссылаются на пробелы:
< Scanners : WORD > < identify : WORD > < words : WORD > < . : OPERATOR >
Парсер
Парсер отвечает за знание основных правил языка. Он знает, что 2 + 2 допустимо, но 2 + × 2 недействительно. Парсер также обнаруживает классы и функции, которые он записывает в таблицу символов. Синтаксический анализатор не знает, действителен ли x + y. За определение допустимого соответствия типов отвечает семантический анализатор.
Парсер обработает токены, переданные ему сканером, чтобы сформировать абстрактное синтаксическое дерево (AST) для каждого выражения. В абстрактном синтаксическом дереве хранятся выражения, идентифицированные анализатором. В абстрактном синтаксическом дереве самый высокий узел называется корнем. При обработке дерева в первую очередь должны быть вычислены узлы, наиболее удаленные от корня.
Чтобы найти x, сначала умножаются целые числа 42 и 2. Затем 123 будет добавлено к результату умножения, прежде чем окончательно будет установлено равным x.
При создании абстрактного синтаксического дерева синтаксический анализатор несет ответственность за обеспечение приоритета операторов. Это означает, что все умножение и деление происходит перед сложением и вычитанием, что также должно происходить перед присваиванием. Если синтаксический анализатор строит узлы слева направо без принудительного приоритета операторов, x будет установлено значение 123.
В компиляторе C сканер и синтаксический анализатор могут быть объединены в один шаг, и нет необходимости в двухпроходном синтаксическом анализе. Это возможно, потому что C требует, чтобы все символы существовали до их использования. Вы не можете вызвать функцию в строке 2, которая объявлена в строке 256. C обходит это ограничение с помощью прямого объявления.
Разделив синтаксический анализатор на два этапа, нет необходимости в прямом объявлении. На первом проходе парсер будет искать объявления классов и функций. Каждое объявление будет зарегистрировано в таблице символов для последующего просмотра. На первом проходе также будет храниться список того, где были найдены объявления в потоке токенов, для использования на втором проходе. Второй проход будет обрабатывать тела функций, которые были пропущены первым. Он создаст абстрактные синтаксические деревья и проверит, что все вызовы функций и типы соответствуют допустимому символу. Однако он не будет пытаться проверить использование типов данных или выбрать правильную перегрузку функции.
Семантический анализ
Семантический анализатор проверяет абстрактные синтаксические деревья, созданные анализатором. Он будет выполнять вывод любого типа, выбор перегрузок функций и разрешение шаблона.
Промежуточное представление
Промежуточное представление - это упрощенный способ представления программы. Промежуточное представление должно быть точным. Это означает, что он должен давать тот же результат, что и исходный код. Обычно используемой формой промежуточного представления является статическая форма единого назначения (SSA). SSA создается путем преобразования каждого набора узлов в абстрактном синтаксическом дереве в одну операцию. Эта форма лучше всего представляет математические выражения, такие как рисунок 3. В форме SSA x = 123 + 42 × 2 можно записать как:
temp1 := 42 × 2 x := 123 + temp1
Это всего лишь одна из форм промежуточного представления. Промежуточное представление - это любая форма абстракции, используемая компилятором для хранения вашего кода в процессе его обработки. Это включает абстрактные синтаксические деревья для байт-кода в Java.
Оптимизация
Оптимизатор повышает эффективность программы. Это может включать предварительное вычисление статического содержимого, такого как 2 + 2. Он также может включать в себя устранение ветвей в цепочках if-else, когда можно статически доказать, что конкретный случай никогда не возникает. Возможны сотни оптимизаций. Чтобы получить представление о диапазоне тем, которые может охватывать оптимизация, см. Список опций оптимизации, предоставляемых GCC.
Ключевым моментом всех оптимизаций является то, что результат работы программы должен оставаться неизменным. Любая оптимизация, улучшающая окончательную программу, действительна, пока она соответствует предварительно оптимизированной версии. Скажем, есть оптимизация, которая может значительно сократить время, необходимое для выполнения программы. Однако вероятность того, что результат будет неверным, составляет 1 из 1 000 000. Как бы ни было сокращено время, оптимизацию проводить нельзя.
Оптимизация бывает разной. Оптимизация глазка пытается заменить сложные операции более простыми альтернативами. Оптимизация циклов направлена на повышение эффективности циклов. Анализ потока данных пытается выяснить время жизни данных. И их гораздо больше.
Back End
Серверная часть отвечает за преобразование промежуточного представления в целевой вывод. В зависимости от языка программирования серверная часть может создавать представление программы в виде байт-кода или собственный машинный код.
В компиляторе C ассемблер будет серверной частью. Наличие дополнительного шага байт-кода позволяет записывать один раз и запускать где угодно. Если бы байт-код не создавался, программу пришлось бы скомпилировать для каждой целевой архитектуры напрямую, включая предположения о возможностях машины, на которой будет выполняться код.
Мой компилятор отделит генерацию байт-кода от ассемблера. Компилятор создаст байт-код во время компиляции. Ассемблер будет включен в библиотеку времени выполнения, которая будет установлена на любой машине, желающей использовать программу, созданную с моим байт-кодом. Ассемблер завершит процесс компиляции, выпуская машинный код, специализированный для устройства, на котором будет работать программа.
Байт-код
Байт-код, также известный как переносимый код, представляет собой почти ассемблерную форму промежуточного представления. Он не зависит от машины и может использоваться ассемблером или интерпретатором во время выполнения. Основная мотивация использования байт-кода - это машинная независимость. Самый распространенный пример - байт-код Java.
Независимость от машины обеспечивает совместимость с большим количеством машин. Внутренние функции - это специальные поддерживаемые компилятором функции для доступа к инструкциям ЦП, которые не являются родными для языка программирования. Их использование позволяет создавать более быстрые программы, но не гарантируется наличие инструкций на всех машинах. Используя байт-код, можно использовать встроенные функции без необходимости проверять их поддержку или создавать откаты. Ассемблер определит, поддерживается ли встроенная функция. Затем он будет использовать его, когда доступен, или автоматически переключится на резервный. Никакой дополнительной работы для вас, никаких дополнительных проверок для поддержки и гарантированная совместимость со всеми системами.
Ассемблер
Задача ассемблера - воплотить вашу программу в жизнь. Ассемблер преобразует промежуточное представление в машинно-зависимые коды операций. Ассемблер - это язык программирования самого низкого уровня, доступный большинству разработчиков. Однако компьютеры на самом деле не работают на сборке. Они работают с серией числовых инструкций, называемых кодами операций. Сборка дает слово каждому коду операции, потому что думать шестнадцатеричными рядами - это не то, в чем многие (кто угодно ???) умеют.
Давайте посмотрим, как все это происходит. Рассмотрим следующую функцию:
После преобразования в сборку функция выглядит так:
Чтобы добраться до этого момента, ассемблер должен был выполнить три основные задачи. Сначала он выбрал инструкции, которые ему нужно было выполнить. В этом случае единственный выбор - add в строке 24. В то время как mov, pop, push и ret получают данные там, где они должны быть.
Следующая задача - планирование инструкций. Планирование инструкций, хотя и не имеет отношения к этому примеру, может помочь или навредить производительности программы. ЦП измеряют время циклами. Для выполнения каждой операции требуется 1 или более циклов. add обычно занимает 1 цикл, mul - 2. Не все работают быстро, div может занимать 20 циклов, а загрузка памяти может занимать сотни циклов. К счастью, процессоры могут выполнять последующие операции до завершения предыдущей. Если операция зависит от результата предыдущей операции, она не может быть выполнена до завершения первой. Планирование инструкций учитывает зависимость данных между операциями и время, необходимое для выполнения каждой операции. Он попытается разделить зависимые операции, максимизируя пропускную способность ЦП.
Последний шаг - выбор регистра. Регистр - это специализированная часть памяти, к которой ЦП может получить доступ при выполнении операции. В приведенном выше примере регистры представлены rbp, edi, esi, edx и eax. ЦП имеют ограниченное количество регистров. На машине x64 имеется только шестнадцать 64-битных регистров общего назначения и восемь 80-битных регистров с плавающей запятой. Это заставляет ассемблер сохранять регистры при выборе операций. В действительности выбор регистра происходит как во время планирования, так и во время выбора инструкций.
Эта статья является частью серии о компиляторах. Цель - создать новый язык программирования.
Обзор серии: Создание безопасного языка программирования
