Добро пожаловать во вторую статью из серии Создадим язык программирования (LBPL). Если вы не знакомы с серией, цель LBPL - помочь вам от 0 до 1 в реализации языка программирования.

В этой статье дается очень подробный обзор структуры компиляторов и интерпретаторов.

Что такое компилятор?

Простейшее определение компилятора - это программа, которая переводит код, написанный на языке программирования высокого уровня (например, JavaScript или Java), в код низкого уровня (например, Assembly), непосредственно исполняемый компьютером или другой программой, например виртуальной машиной.

Например, компилятор Java преобразует код Java в байт-код Java, выполняемый JVM (виртуальной машиной Java). Другими примерами являются V8, движок JavaScript от Google, который преобразует код JavaScript в машинный код, или GCC, который может преобразовывать код, написанный на языках программирования, таких как C, C ++, Objective-C, Go, в собственный машинный код.

Что в черном ящике?

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

Компилятор можно разделить на 2 части.

  • Первый, как правило, называется внешний интерфейс, сканирует отправленный исходный код на наличие синтаксических ошибок, проверяет (и при необходимости определяет) тип каждой объявленной переменной и гарантирует, что каждая переменная объявлена ​​перед использованием. Если есть какая-либо ошибка, он предоставляет пользователю информативные сообщения об ошибке. Он также поддерживает структуру данных, называемую таблицей символов, которая содержит информацию обо всех символах, найденных в исходном коде. Наконец, если ошибки не обнаружены, другая структура данных, промежуточное представление кода, создается из исходного кода и передается в качестве входных данных во вторую часть.
  • Вторая часть, серверная часть, использует промежуточное представление и таблицу символов, созданную внешней частью для генерации код низкого уровня.

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

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

Лексический анализ

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

лексему можно рассматривать как однозначно идентифицируемую строку символов в исходном языке программирования, например, ключевые слова, такие как if, while или func, идентификаторы , строки, числа, операторы или одиночные символы, например (, ), . или :.

токен - это объект, описывающий лексему. Наряду со значением лексемы (фактическая строка символов лексемы) он содержит такую ​​информацию, как ее тип (это ключевое слово? идентификатор ? оператор?…) и позицию (номер строки и / или столбца) в исходном коде, где он появляется.

Если компилятор обнаруживает строку символов, для которой он не может создать токен, он остановит свое выполнение, выдав ошибку; например, если он встречает неверно сформированную строку или число или недопустимый символ (например, не-ASCII-символ в Java).

Синтаксический анализ

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

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

Если на этом этапе ошибок не обнаружено, компилятор переходит к этапу семантического анализа.

Семантический анализ

Во время семантического анализа компилятор использует AST, сгенерированный во время синтаксического анализа, чтобы проверить, соответствует ли программа всем правилам исходного языка программирования. Семантический анализ включает

  • Вывод типа. Если язык программирования поддерживает вывод типа, компилятор попытается определить тип всех нетипизированных выражений в программе. Если тип успешно определен, компилятор аннотирует соответствующий узел в AST с информацией о предполагаемом типе.
  • Проверка типа. Здесь компилятор проверяет, что все значения, присваиваемые переменным, и все аргументы, участвующие в операции, имеют правильный тип. Например, компилятор следит за тем, чтобы ни одной переменной типа String не было присвоено значение Double или что значение типа Bool не было передано функции, принимающей параметр типа Double, или, опять же, что мы не пытаемся разделить String на Int, "Hello" / 2 (если это не разрешено определением языка).
  • Управление символами. Помимо выполнения вывода и проверки типов, компилятор поддерживает структуру данных, называемую таблицей символов, которая содержит информацию обо всех символах (или именах), встречающихся в программе. Компилятор использует таблицу символов для ответа на такие вопросы, как Объявлена ​​ли эта переменная перед использованием?, Есть ли две переменные с одинаковыми именами в одной области? Какого типа эта переменная? Доступна ли эта переменная в текущей области? и многие другие.

Результатом этапа семантического анализа является аннотированный AST и таблица символов.

Генерация промежуточного кода

После фазы семантического анализа компилятор использует аннотированный AST для генерации промежуточного и машинно-независимого низкоуровневого кода. Одним из таких промежуточных представлений является трехадресный код.

трехадресный код (3AC) в простейшей форме - это язык, на котором инструкция является присваиванием и имеет не более трех операндов.

Большинство инструкций в 3AC имеют форму a := b <operator> c или a := b.

На приведенном выше рисунке изображен код 3AC, сгенерированный из аннотированного AST, созданного во время компиляции функции.

func sum(n: Int): Int = {
    n * (n + 1) / 2
}

Генерация промежуточного кода завершает этап внешнего интерфейса компилятора.

Оптимизация

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

Например, очень простой оптимизацией кода 3AC в предыдущем примере будет удаление временного назначения t3 := t2 / 2 и прямое присвоение id1 значения t2 / 2.

Генерация кода

На этом последнем этапе компилятор переводит оптимизированный промежуточный код в машинно-зависимый код, Assembly или любой другой целевой низкоуровневый язык.

Компилятор против интерпретатора

Давайте закончим эту статью заметкой о разнице между компиляторами и интерпретаторами.

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

Интерпретатор обычно генерирует эффективное промежуточное представление и немедленно его оценивает. В зависимости от интерпретатора промежуточным представлением может быть AST, аннотированный AST или машинно-независимое низкоуровневое представление, такое как трехадресный код .

Что дальше?

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

Вы дошли до конца. 🎉

Хакерский полдень - это то, с чего хакеры начинают свои дни. Мы часть семьи @AMI. Сейчас мы принимаем заявки и рады обсудить рекламные и спонсорские возможности.

Если вам понравился этот рассказ, мы рекомендуем прочитать наши Последние технические истории и Современные технические истории. До следующего раза не воспринимайте реалии мира как должное!