#common

Про компиляцию в общих чертах.

Представим выражение (строка кода):

pos = init + rate * 60

Что с ним произойдёт при компиляции?

👉 Лексический анализ — читаем поток символов и группируем их в лексемы (значащие последовательности). Для каждой лексемы получаем токен вроде <имя, значение>.

<id, 1> <=> <id, 2> <+> <id, 3> <*> <60>

id в данном случае указывает, что информацию о токене нужно искать в глобальной таблице символов (там инфа о всех встреченных объектах). Номер 1/2/3 — индекс объекта в этой таблице.

<60> можно представить в более общем виде как <number, 4>, но для простоты не будем.

Такой набор токенов и отправляется на следующий этап.

👉 Синтаксический анализ позволяет построить из токенов промежуточное древовидное представление, которое описывает грамматическую структуру потока токенов (обычно тут речь о синтаксическом дереве или ast). Получаем что-то такое:

=
/ \
<id, 1> +
/ \
<id, 2> *
/ \
<id, 3> 60

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

=
/ \
<id, 1> +
/ \
<id, 2> *
/ \
<id, 3> int_to_float
\
60

Или если у операндов некоторого оператора типы не совпадают, и язык запрещает неявные преобразования, уже на этом этапе можно кинуть ошибку.

👉 Генерация промежуточного кода.
В процессе трансляции исходного кода в целевой, компилятор может несколько раз генерировать различные промежуточные представления. В нашем примере можем получить что-то такое:

t1 = int_to_float(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

👉 Оптимизация кода.
Конечно, сгенерированный выше код кажется нам довольно неестественным. Его хочется упростить. Это и происходит на этапе оптимизации (пока это машинно-независимые процессы). Можем получить следующее:

t1 = id3 * 60.0
id1 = id2 + t1

Стоит понимать, что оптимизация (хотя это скорее трансформация) -- всегда эвристический процесс, который ничего не гарантирует и пытается улучшить какой-то основной/несколько критериев, возможно жертвуя другими. Часто, например, можно хотеть уменьшить количество инструкций. Хотя, если у вас какая-то встраеваемая система, вы можете хотеть использовать меньше памяти. Но никто не гарантирует, что не станет хуже.

Ещё такой процесс может проходить несколько раз, т.к. какие-то сделанные оптимизации открывают возможность для новых.

👉 Генерация кода из промежуточного кода получает код целевой платформы (например на асм). Тут могут происходить локальные оптимизации, исходя из того, что умеет конкретная архитектура.
Важной задачей также является грамотная работа с памятью (кого в какие регистры поместить, и т.п.).

Понятно, что это довольно упрощённая схема, т.к. в реальных компиляторах какие-то этапы могут отличаться, быть сильно более сложными или совсем отсутствовать. Может позже посмотрим на то, как это происходит с плюсовым кодом.

Если верхнеуровнево, то компиляторы для плюсов состоят из несколько крупных этапов:
1. Frontend: препроцессинг, лексический, синтаксические и семантический анализ, построение high level intermediate representation (hir).
2. Middleend + backend: оптимизации hir, оптимизации mir, оптимизации lir, кодогенерация.

Frontend для каждого языка свой. Middleend и backend работаю с ir, что позволяет переиспользовать их для разных языков.

Послушать про то, как работают компиляторы для C++, можно в плейлисте. Правда речь о toolchain, но от этого только интереснее : )

Ещё можно посмотреть пару лекций про LLVM IR. И почитать пару постов на похожую тему в @cxx95: раз, два.

P.S. пример из dragonbook.