От исходного языка к промежуточному представлению
Что такое компилятор?
Компилятор - это переводчик, который превращает программы на исходном языке в ту же программу на целевом языке. Обычно этот целевой язык является исполняемым, что означает, что он может запускаться на машине.
Переводчик? Это похоже на переводчика, не так ли? Что ж, интерпретатор дает вам результат выполнения программы. Компилятор не запускает исходную программу.
В этом посте я расскажу о внешнем интерфейсе компилятора (первые 5 или около того этапов компиляции). В современных реальных компиляторах эти этапы иногда комбинируются, но в целом все эти этапы должны выполняться примерно в таком порядке.
1. Лексический анализ
Строка символов ASCII - ›Строка лексических токенов
Этот этап посвящен преобразованию нашей программы в токены, которые представляют собой просто последовательность символов, соответствующую единице грамматики нашего языка. Например, это некоторые допустимые токены во многих популярных языках программирования:
- 15 (ИНТ), -0,6 (ПОПЛАВК), 6.022e23
- «Компиляторы рок» (STRING)
- foo, x (ИДЕНТИФИКАТОР)
- +, &&, ‹
- ; (ТОЧКА С ЗАПЯТОЙ)
- возврат (ВОЗВРАТ)
Как видите, помимо наших типичных примитивных типов String и Number, у нас также есть токены пунктуации, такие как return, if, void и т. Д., Которые нельзя использовать в качестве идентификаторов (имен переменных) - это зарезервированные слова (ключевые слова).
У нас также есть вещи, которые игнорируются во время этого процесса, и мы называем их нетокенами! Примеры включают:
- // Это однострочный комментарий
- / * Это многострочный комментарий * /
- #define ARRAY_SIZE 10 (директивы препроцессора)
- пробелы, табуляции, новые строки (будьте осторожны с этим, Python, например, чувствителен к пробелам)
В конце этапа лексирования
public static void main(String[] args) {
System.out.println("Hi Mom!");
}
может превратиться во что-то вроде этого:
PUBLIC STATIC VOID MAIN LPAREN STRING LBRACKET RBRACKET ID(args) RPAREN LBRACE ID(System) DOT ID(out) DOT ID(println) LPAREN STRING(Hi Mom!) RPAREN SEMICOLON RBRACE
2. Разбор
Строка лексических токенов - ›Абстрактное синтаксическое дерево (AST)
Целью данного этапа является проверка того, что структура этих токенов является законной и соответствует правилам грамматики языка (синтаксический анализ). Пока мы это делаем, поскольку список токенов на самом деле не очень полезен (и труден для чтения), мы собираемся превратить его в дерево.
Я не собираюсь вдаваться в подробности написания однозначной грамматики или самого левого и крайнего правого выводов. Чтобы узнать больше об этом, ознакомьтесь с разделом ресурсов внизу этой статьи.
Приведем пример.
i = 3 + (4 * 17)^2;
После лексирования у нас будет
ID(i) EQUALS INT(3) PLUS LPAREN INT(4) TIMES INT(17) RPAREN EXPONENT INT(2) SEMICOLON
И после разбора
EQUALS
/ \
ID(i) PLUS
/ \
INT(3) EXPONENT
/ \
TIMES INT(2)
/ \
INT(4) INT(17)
Обратите внимание, как приоритет BEDMAS фиксируется в этом дереве (умножение происходит до экспоненты, которая происходит до сложения). Скобки и точка с запятой удаляются.
Типы ошибок, которые могут быть обнаружены на этом этапе компиляции, - это ваши традиционные «синтаксические ошибки», такие как:
- Несоответствующие или отсутствующие круглые скобки в условиях if или циклах while
- Отсутствие точек с запятой после присвоения переменных, операторов и т. Д.
- Отсутствует инструкция return
Такие ошибки, как неспособность распознать, что выражения умножения связываются сильнее (должно быть выполнено в первую очередь), чем выражение сложения, указывают на проблему с вашей грамматикой.
3. Семантический анализ
Абстрактное синтаксическое дерево - ›Абстрактное синтаксическое дерево
Это этап проверки типов. Для этого мы обычно создаем и поддерживаем таблицы символов (также называемые средами), которые отслеживают привязки между переменными и их типами, а также методами и их возвращаемыми типами.
Мы должны пройти через абстрактное синтаксическое дерево и поместить в таблицу:
- Переменные и параметры с указанием их типа
- Методы с их типами возврата
- Классы со своими переменными и методами
Затем мы можем снова пройти через AST и убедиться, что все типы соответствуют тому, что мы ожидали. Необязательно делать это в два этапа, но может быть полезно подумать об этом как о сначала построении таблицы символов, а затем о проверке.
Как нам построить эту таблицу? Если вы думаете об использовании хеш-таблицы, вы правы - хеш-таблицы отлично подходят для нашего случая использования, потому что они позволяют нам быстро вставлять и искать объекты. Но если у нас есть методы и локальные переменные на нашем языке, одна главная таблица уже не сможет его сократить.
Существует два основных стиля реализации таблиц, которые выражают область действия: императивный и функциональный. Обязательные таблицы символов работают, отслеживая локальные привязки, когда вы помещаете их в таблицу, так что вы можете удалить их при выходе из области видимости (но всегда внося изменения в исходную таблицу). Функциональные таблицы символов работают, создавая новую таблицу всякий раз, когда вы входите в новую область видимости, которая содержит сумму старой таблицы и нового локального материала. К сожалению, создание новых хеш-таблиц, копирование значений и их уничтожение не очень эффективно. Вместо этого мы можем использовать древовидную структуру данных двоичного поиска (в том же духе, что и связанный список, но операции поиска более эффективны с деревом поиска).
Итак, на этом этапе мы сможем выявить следующие типы ошибок:
- Попытка перемножить две строки
- Объявление двух целочисленных переменных с одинаковым именем
- Попытка использовать переменную, которая не была определена
- Возврат int из метода, объявленного с типом возврата void
- Передача неправильного количества аргументов при вызове метода
- Передача неправильного типа аргументов при вызове метода
4. Перевод на промежуточное представление
Абстрактное синтаксическое дерево - ›Промежуточное представление (IR)
Итак, у нас есть эти красивые деревья, которые позволяют нам легко понять, что происходит в программе, но мы все еще очень далеки от нашей конечной цели - машинного кода. Теперь мы могли бы попытаться напрямую преобразовать AST в машинный код на этом этапе, но, к сожалению, машинный код содержит тонны архитектурно-зависимой информации, от которой наши AST все еще свободны. Это означает, что для каждого исходного языка нам потребуется отдельный компилятор для каждого машинного языка. Сколько комбинаций!
Промежуточное представление приближает нас к коду машинного уровня, при этом скрывая детали архитектуры целевой машины. На практике используется множество различных видов ИК-излучения, но все они должны быть:
- Удобно переводить с АСТ
- Удобно переводить в машинный код (для всех желаемых поддерживаемых целевых машин)
- Состоит из компонентов, описывающих очень простые вещи, такие как добавление, перемещение, переход, так что оптимизацию и переписывание можно легко реализовать на более поздних этапах.
Предположим, у нашего IR есть несколько таких конструкций, как:
/* Expressions: Instructions that return a value. */
/* Gets the value inside the register r. */
REG(r)
/* Applies binary operator to two expressions. */
BINOP(Binop, Expression, Expression)
/* Statements: Instructions that do not return a value but may have
side effects. */
/* Give a name to the current machine instruction address. */
LABEL(name)
/* Evaluate sourceExpression and move it into the destination.
The destination could be a register, or an address in memory. */
MOVE(destinationExpression, sourceExpression)
/* Conditional jump. If the RelOp applied to the expressions result
in true, go to the thenLabel. Else, go to the elseLabel. */
CJUMP(RelOp, Expression, Expression, thenLabel, elseLabel)
/* Constants. */
/* Types of binary operators. */
Binop ::= PLUS, MINUS, MULT
/* Types of relational operators. */
RelOp ::= EQUAL, LESSTHAN, GREATERTHAN
Тогда такая программа
sum = a + b + c; /* Return the absolute value of the sum. */ result = (sum > 0) ? sum : (sum * -1);
можно перевести на
MOVE(REG(sum), BINOP(PLUS, BINOP(PLUS, REG(a), REG(b)), REG(c))) CJUMP(GREATERTHAN, REG(sum), 0, trueBranch, falseBranch) LABEL(trueBranch) MOVE(REG(result), REG(sum)) JUMP(done) LABEL(falseBranch) MOVE(REG(result), BINOP(MULT, REG(sum), -1)) LABEL(done)
Этот конкретный способ вычисления условного выражения называется ленивым вычислением: мы не вычисляем sum * -1, если sum положительно. Как бы изменился IR, если бы мы хотели всегда оценивать обе ветви?
5. Канонизация
Промежуточное представление - ›Линеаризованное промежуточное представление (линеаризованное IR)
Чтобы выполнить оптимизацию, о которой я упоминал ранее, мы хотим иметь прямолинейный ИК-код, а не комплексный ИК-код с прыжками по всему месту, который мы могли бы иметь в начале этого этапа. В предыдущем примере все было не так уж плохо, но IR с большим количеством операторов, зависящих от порядка выполнения, затрудняет реорганизацию и переписывание позже.
Давайте посмотрим на более сложный IR. Но сначала нам нужно определить еще несколько конструкций:
/* Run the statement, then return the value of the expression. */ ESEQ(Statement, Expression) /* Run the first statement, then the second statement. */ SEQ(Statement, Statement)
Напомним, что выражения вычисляют и возвращают значение, а операторы - нет (хотя они могут иметь побочные эффекты, например, изменение значения переменной, выполнение операций ввода-вывода и т. Д.). Таким образом, ESEQ будет инструкцией выражения, а SEQ - инструкцией оператора.
Что мы можем сделать теперь, когда у нас есть эти новые дополнения? Ну как насчет:
// a = 1;
// b = 2;
// c = 3;
SEQ(MOVE(REG(a), 1),
SEQ(MOVE(REG(b), 2),
MOVE(REG(c), 3)))
// a = 1;
// b = a + 1;
// c = b + 1;
SEQ(MOVE(REG(a), 1),
SEQ(MOVE(REG(b), BINOP(PLUS, REG(a), 1)),
MOVE(REG(c), BINOP(PLUS, REG(b), 1))))
// a - (++a * b)
BINOP(MINUS, REG(a), ESEQ(MOVE(REG(a), BINOP(PLUS, REG(a), 1)),
BINOP(MULT, REG(a), REG(b))))
Что в этом плохого? Это потрясающе, мы можем писать более плотный ИК-код с помощью отдельных инструкций, которые делают много всего.
Проблема в том, что ESEQ и SEQ затрудняют нам переупорядочивание операторов, потому что разные порядки оценки могут давать разные результаты. В первом случае порядок исполнения значения не имеет. Это имеет значение во втором и третьем случаях - понимаете почему?
Мы должны переписать IR, чтобы убрать ESEQ внутри инструкции (потяните его вверх).
// a - (++a * b)
ESEQ(SEQ(MOVE(REG(temp), REG(a)), // save the value of a
MOVE(REG(a), BINOP(PLUS, REG(temp), 1))),
BINOP(MINUS, REG(temp), BINOP(MULT, REG(a), REG(b))))
Это всего лишь один пример упрощения IR. Есть и другие проблемы, с которыми нам нужно справиться, например, обработка возвращаемых значений, если у вас есть такое выражение, как
BINOP(PLUS, CALL(...), CALL(...))
и выражения вызова конкурируют за регистр возвращаемого значения. (Как это исправить ?!) Я не буду вдаваться в подробности, но ознакомьтесь с перечисленными ниже ресурсами, если вам интересно.
Теперь, когда у нас есть канонические деревья, мы сгруппируем их в базовые блоки, у которых нет внутренних меток или переходов. Наконец, мы упорядочим эти блоки так, чтобы за каждым CJUMP сразу следовала его ложная метка (этот шаг называется планирование трассировки). Мы хотим этого, потому что затем мы можем удалить ложную метку в переходе - если условие в CJUMP не выполняется, мы можем перейти непосредственно к следующей инструкции, и это именно то, что мы хотим выполнить.
Теперь наш IR готов к трансляции в машинный код, где мы будем делать захватывающие вещи, такие как выбор инструкций, анализ потока управления и распределение регистров!
Ресурсы:
Материалы из предложения CS143 в Стэнфорде в 2012 году, особенно по синтаксическому анализу
Аппель, Эндрю В. Современная реализация компилятора на Java, 2-е изд.
