Путь от Кода до Бинарного Файла

Средний

4 мин

4.3K

Туториал

Recovery Mode

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

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

P.S. Вторая часть про лексический анализ – https://habr.com/ru/articles/890344/.

Этапы

1. Lexing

На этом этапе исходный код в виде строки разделяется на отдельные части, то есть токены. Этот этап – самый простой во всём процессе компиляции.

Вход
let a = 10 + 2 if a > 8 then debug "A больше 8" else debug "А либо меньше, либо равно 8" end
Выход
[ Let, Identifier("a"), Equal, Integer(10), Plus, Integer(2), If, Identifier("a"), Greater, Integer(8), Then, Debug, String("A больше 8"), Else, Debug, String("А либо меньше, либо равно 8"), End, ]

2. Parsing

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

[ Let { identifier: "a", value: Binary(Add, Integer(10), Integer(2)), }, If { condition: Binary(Greater, Identifier("a"), Integer(8)), then: [ Debug(String("A больше 8")), ], else_: [ Debug(String("А либо меньше, либо равно 8")), ], }, ]

3. Промежуточное представление (IR)

AST преобразуется в низкоуровневые инструкции, которые не зависят от конкретной архитектуры. Это удобно, так как упрощает поддержку большого количества архитектур и процессоров.

В компиляторах Rust и Clang в качестве промежуточного представления используется LLVM IR, так как его экосистема берёт на себя многие оптимизации, и компилирование в ассемблерный код для разных платформ как X86, ARM и так далее.

Граф потока управления (CFG)

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

Блоки, не содержащие условий
{ 0: [ Let { identifier: "a", value: Binary(Add, Integer(10), Integer(2)), }, ], 1: [ Debug(String("A больше 8")), ], 2: [ Debug(String("А либо меньше, либо равно 8")), ], 3: Empty, }
Блок Empty – это пустой блок, который не содержит в себе инструкций, и служит только для удобства построения CFG.
И условные переходы между блоками
{
0: Branch { # переход с условием
condition: Binary(Greater, Identifier("a"), Integer(8)),
true_: 1,
false_: 2,
},
1: Direct(3), # прямой переход без условия
2: Direct(3),
}

Трёхадресный код (3AC)

Состоит из низкоуровневых инструкций максимально приближенных к нативному ассембли-коду.

Первый блок
[ Label(0), LoadInteger { to: 0, value: 10 }, LoadInteger { to: 1, value: 2 }, Add { to: 2, left: 0, right: 1 }, Set { identifier: "a", from: 2 }, Get { to: 3, from: "a" }, LoadInteger { to: 4, value: 8 }, Greater { to: 5, left: 3, right: 4 }, JumpIf { condition: 5, label: 1 }, Jump(2),
Второй
Label(1), LoadString { to: 6, value: "A больше 8" }, Debug { value: 6 }, Get { to: 7, from: "a" }, LoadInteger { to: 8, value: 8 }, Greater { to: 9, left: 7, right: 8 }, JumpIf { condition: 9, label: 3 }, Jump(2),
Третий
Label(2), LoadString { to: 10, value: "А либо меньше, либо равно 8" }, Debug { value: 10 },
И последний, пустой блок
Label(3), ]
Или в виде псевдо-кода
@0: #0 = 10 #1 = 2 #2 = add #0 #1 $a = #2 #3 = $a #4 = 8 #5 = gt #3 #4 jump @1 if #5 jump @2 @1: #6 = "A больше 8" debug #6 #7 = $a #8 = 8 #9 = gt #7 #8 jump @3 if #9 jump @2 @2: #10 = "А либо меньше, либо равно 8" debug #10 @3:

4. Ассембли

Далее, каждая 3AC инструкция конвертируется в одну или несколько ассемблерных инструкций, которые уже напрямую выполняются на процессоре без какой-либо прослойки.

section .data str_0: db "A больше 8", 0 str_1: db "А либо меньше, либо равно 8", 0
Строки будут записаны вместе с файлом как его часть, то есть они не будут аллоцированны динамически во время выполнения.
section .bss a: resq 1
Мы будем хранить переменную в секции .bss, так как в нашей программе одна зона видимости. В настоящих компиляторах переменные обычно хранятся на стеке, или вовсе в регистрах в зависимости от степени оптимизации.
section .text global start start:
Делаем _start глобально видимым для того, чтобы линкер смог собрать бинарный файл.
L0: mov rax, 10 mov rbx, 2 mov rcx, rax add rcx, rbx mov [a], rcx
a = rcx = rax + rbx = 10 + 2 = 12.
mov rax, [a] mov rbx, 8 cmp rax, rbx mov rcx, 0 setg cl
rcx = rax > rbx = a > 8 = 1 то есть true.
cmp rcx, 1 je L1 jmp L2
Если rcx = 1, то есть true, то переходим в L1, иначе – в L2.
L1: mov rax, str_0 call debug
debug – это какая-то функция, которая печатает строки в консоль. В целях соблюдения компактности, я не стал её включать в код. Регистр rax – первый аргумент.
mov rax, [a] mov rbx, 8 cmp rax, rbx setg rcx cmp rcx, 1 je L3 jmp L2 L2: mov rax, str_1 call debug
L2 – начало блока else.
L3: mov rax, 60 mov rdi, 0 syscall
Выходим из программы, производя системный вызов (syscall). В rax находится номер вызова – 60, то есть выход (SYS_exit). А в rdi лежит статус завершения программы, в данном случае 0, то есть успешное завершение.

Полезное

Заключение

Надеюсь вам понравилась эта статья! Она написана на основе моего хобби-компилятора, поэтому если у вас есть желание внести свою лепту в проект – отправляйте пул-реквест в репозиторий!

Хабы: