Опыт написания компилятора вручную25.01.2025 12:45

cd2be966d76c53d4b7062f9caed46818.png

Компилятор и главный репозиторий: GitHub

Здесь я напишу о своём личном проекте — компиляторе к C-подобному языку. Я не являюсь профессиональным разработчиком, изучал эту тему почти самостоятельно и не читал никакие книги по написанию компиляторов (но читал по операционным системам).

Документацию к языку и к его стандартной библиотеке Altlib можно найти в репозитории. Реализация (надеюсь) полностью рабочая (по крайней мере, есть немаленький набор тестов).

Есть вспомогательный репозиторий для упрощения установки компилятора и IDE к нему: GitHub

В процессе чтения статьи вы увидите, что я сильно вдохновлялся языком Zig.

Обзор языка

Alias является языком системного программирования, имеет стандартные черты языка C и по выразительности синтаксиса находится между C и Zig. Язык не является «стабильным» и не следует к какой-либо определённой заведомо выбранной точке. Я пишу то, что приходит мне в голову (предварительно подумав, конечно, не вступит ли это в противоречие с чем либо).

Основные характеристики языка, которым я уделяю большое внимание:

  1. Соизмеримая скорость (наверное, программа на этом языке не должна быть более, чем в пять (так как я не делаю оптимизации) раз медленнее аналогичной на C)

  2. Возможность компоноваться с C (не совсем полная — о нюансах ниже) и Asm

  3. Удобство и привычность использования, соизмеримый современным языкам набор инструментов (например, автоматические тесты)

Первый пример

Начнём с простой программы. Учтите — язык полностью самостоятельный, не имеет никакой runtime среды, а вся его библиотека написана на нём же или Asm-е. Поэтому язык будет непростым для понимания. Здесь я опущу необходимые includes.

func ^._start() -> #V {
    def allocator #TestAllocator
    eval allocator&.init(1024)
    defer eval allocator&.deinit()

    def vec #Vector
    eval vec&.init(allocator&)
    eval vec&.push(1)
    eval puti_(vec&.get(0))

    eval posix_exit(0)
}

Пойдём по тем местам, которые бросаются в глаза и не являются очевидными:

  1. Символ ^. Этот символ отменяет mangling названия функции. Mangling используется для полиморфизма. Мы же хотим, чтобы entry function называлась именно _start, ведь именно эту метку ожидает ld по умолчанию. (В C компоновщик генерирует свою функцию _start, в которой настраивает runtime.)

  2. #TestAllocator — это некий тип, объявленный в подключенном файле (не обязательно структура).

  3. Для типа «указатель на #TestAllocator» объявлен метод init. Чтобы получить из локальной переменной указатель на неё, мы добавляем &.

  4. defer выполняет statement в конце блока.

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

  6. Вернуться из функции _start нельзя (так работают процессы). Необходимо выполнить системный вызов exit.

Типы

Перед анализом следующих примеров посмотрим, как здесь выглядят типы.

  1. #I — это целое число размером 8 байт.

  2. #1I — это указатель на целое число.

  3. #2I — это указатель на указатель на целое число.

  4. #C — это целое число размером 1 байт.

  5. #V — это void размером 0 байт.

  6. #S{x: #I, y: #I} — это инстанс (instance, объект структуры), который имеет два поля x и y, которые являются целыми числами.

  7. #F(#I) -> #I — это указатель на функцию, которая принимает одно целое число и возвращает целое число (partial application и closures отсутствуют).

Допускается любая вложенность типов. Константы пока отсутствуют.

Функции

Иногда я буду вставлять примеры из документации языка. Данный пример является тестом, который проверяется автоматически (и если тест проваливается, компилятор считается сломанным).

test demo_higher_order_functions {
    def twice := \(f #F(#I) -> #I, x #I) -> #I {
        return f(f(x))
    }
    return test_equal(twice(\(x #I) -> #I x * x, 2), 16)
}

  1. twice — это лямбда-функция. Она принимает в качестве первого аргумента тип #F(#I) -> #I, то есть, указатель на функцию, которая принимает целое число и возвращает целое число. Посмотрев на тело это функции видим, что она дважды применяет функцию к своему второму аргументу и возвращает результат.

  2. Во второй лямбде, которую мы подаём в первую, мы видим, что тело лямбды может быть не блоком, а лишь expression-ом. В данном случае она возвращает квадрат аргумента.

Методы

func #I.add_one(x #I) -> #I {
    return x + 1
}

func #I.add(x #I, y #I) -> #I {
    return x + y
}

test demo_methods {
    def a := 3
    def b := a.add_one()
    def c := 5.add_one()
    def d := b.add(c)
    return test_equal(d, 10)
}

Здесь всё довольно очевидно: мы можем объявить метод для любого типа (и первый аргумент этого метода обязан быть равен этому типу).

Но есть важный момент: в языке отсутствуют closures, а значит в этом примере мы не сможем сделать так: def d := b.add, ведь это значило бы взятие значения b.

Контроль потока

Здесь есть несколько интересных моментов.

  1. Блок является expression-ом и всегда что-то возвращает (это может быть void).

  2. В языке Zig выполняют возвращение из блока с помощью break-а. В то же время им же возвращают из цикла. Приоритет у цикла, поэтому блок всегда необходимо помечать меткой (почти всегда это blk).

  3. Я захотел их разделить. В Alias-е break возвращает только из цикла, в то время как return возвращает не из функции, а из блока (что непривычно). Метки здесь присутствуют и для break, и для return.

  4. If и while являются expression-ами и всегда возвращают. Если они возвращают не void, они обязаны иметь else (else у цикла может некоторых удивить).

Посмотрим на реализацию strnlen теперь из документации к стандартной библиотеке: 

func ^.strnlen_(a #1C, n #I) -> #I {
    def i := 0
    return while (i < n) {
        eval if (a[i] = '\0') { break i }
        i := i + 1
    } else n
}

  1. return здесь возвращает результат вычисления цикла. Если цикл завершится break-ом, возвратиться значение у break-а. Иначе возвратиться результат вычисления else.

  2. Мы не можем написать if, так как он не является statement-ом. Нам необходимо написать eval expression, который вычислит expression и забудет результат.

  3. Мы не можем написать break без фигурных скобок, так как break является statement-ом, а if должен в качестве ветвей иметь именно expression-ы. Фигурные скобки объявляют блок, который возвращает void, а поэтому if тоже возвращает void.

Сложный пример с указателями

Рассмотрим метод push для Vector-а (Vector не полиморфен и может хранить только целые числа). Здесь есть ещё несколько неочевидных мест.

func ^#1Vector.push(this #1Vector, x #I) -> #V {
    eval if (this->size = this->reserved) {
        def buffer #1I := this->allocator.alloc(this->reserved * 2 * $#I)
        eval puti_(this->data as #I)
        eval _memcpy(buffer, this->data, this->size * $#I)
        this->data& <- buffer
        this->reserved& <- this->reserved * 2
    }
    this->data[this->size]& <- x
    this->size& <- this->size + 1
}

  1. $#I возвращает размер типа #I.

  2. as выполняет смену типа. Это reinterpret_cast.

  3. a->b возвращает поле b в инстансе a.

  4. a->b& возвращает указатель на поле b в инстансе a.

  5. a <- b копирует значение b по указателю a (что в C делает *a = b).

  6. a[b] возвращает значение по адресу a + b * sizeof(*a).

  7. a[b]& возвращает значение a + b * sizeof(*a).

Обзор реализации

  1. Реализация написана только на C.

  2. Не используется C stdlib и какой-либо код за пределами проекта. Для системных вызовов и некоторых функций написана реализация на Asm. Написана «своя stdlib», которая используется компилятором.

  3. Написана stdlib на Alias-е под названием altlib. Все программы на Alias-е используют её (то есть, код на Alias-е не требует код на C (но требует на Asm-е)).

  4. Фронтенд написан вручную. Генерация кода для архитектуры x86_64 (пока только на неё) написана вручную. Никаких оптимизаций не выполняется. Intermediate representation отсутствует (но является одной из ближайших целей).

Далее я рассмотрю каждый модуль компилятора подробнее.

Настройки

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

Ничего сложного здесь нет.

Лексер

Лексер выполняет здесь сразу две задачи.

  1. Стандартная — получить строку и вернуть список токенов.

  2. Сформировать подсветку токенов для языкового сервера (конечно, здесь есть language server)

Здесь тоже нет ничего сложного.

Синтаксер

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

Я дам подсказки, как написать синтаксер с минимальной болью.

  1. Все конструкции разделяются на statement-ы и expression-ы.

  2. Блок — это последовательность statement-ов.

  3. Определить statement обычно можно по первому в нём токену.

  4. Primary — это expression без операторов на верхнем уровне (например, a.new(5, b + 7) — primary, а a + 4 — нет).

  5. Будем дробить expression-ы на primaries с помощью простого алгоритма со стеком операторов и стеком primaries. (Я не знаю, как этот алгоритм называется. Обычно его упоминают с обратной польской записью, но она скорее не используется здесь, а помогает догадаться об алгоритме.)

Мой код для синтаксера выглядит примерно так: 

считать_блок() {
  считать '{'
  А = []
  пока дальше не '}':
    A.положить(считать_statement())
  считать '}'
  вернуть А
}

считать_statement() {
  если дальше и считать 'def':
    Def def
    def->тип = считать_тип()
    def->значение = считать_expression()
    вернуть def
  иначе ...
}

считать_expression() {
  А = [] // стек операторов
  Б = [] // стек primaries
  пока истина:
    если дальше и считать '(':
      А.положить('(')
    иначе если дальше и считать ')':
      пока А.конец() не '(':
        Node node = подвесить_за_операцию(А[-1], Б[-1], Б[-2])
        А.удалить()
        Б.удалить()
        Б.удалить()
        Б.положить(node)
      A.удалить()
    иначе если дальше_оператора():
      ...
    иначе:
      Б.положить(считать_primary())
}

Генератор кода

В противоположность синтаксера, здесь нужно хорошо знать прикладной Asm, но писать код уметь особо не нужно. Если мы не пытаемся оптимизировать, нам достаточно знать об x86_64 следующее.

  1. Регистры общего назначения, регистр eflags

  2. Арифметические инструкции: mov, add, sub, mul, div

  3. Инструкции прыжков: jmp, jl, je, call, ret

  4. Инструкции для стека: push, pop

  5. Как устроен stack frame и как вызываются функции

Теперь о том, как написать какую-то генерацию. Пусть мы обрабатываем expression. Будем класть результат expression-а на стек. Как написать бинарную операцию?

  1. Выполним генерацию первого аргумента. Он положится на стек.

  2. Добавим фиктивную локальную переменную. (Но ведь в C переменные в функции кладутся на стек снизу. Однако я посчитал это неоправданно неудобным и кладу переменные сверху вниз в блоке, а не в функции.)

  3. Выполним генерацию второго аргумента. Он положится на стек после фиктивной переменной.

  4. Уберём фиктивную переменную, достанем операнды из стека в регистры, выполним операцию и положим результат на стек.

Когда я выполняю генерацию, в каждый момент времени я храню некий контекст:

  1. Локальные переменные и их позиции в stack frame

  2. Функции и методы

  3. Метки в блоках и циклах и их позиции в stack frame (кстати, реализация goto statement весьма сложна)

Отмечу генерацию вложенных инстансов. Пусть у нас есть инстанс с двумя инстансами. В Alias-е инстансы являются packed, как в Asm-е

Стек растёт вправо. Символами | отделены блоки размером 8 байт (natural alignment)
Адрес начала инстанса должен делиться на natural alignment.
...|--------|--------|--------|--------|

Скомпилируем первый вложенный инстанс.
...|-----+++|++++++++|--------|--------|

Создадим фиктивную переменную. Скомпилируем второй вложенный инстанс.
...|-----+++|++++++++|------++|++++++++|

"Спрессуем" все инстансы.
...|---+++++|++++++++|++++++++|--------|

Важно то, что мы не пишем это сжатие, а пишем генерацию Asm-кода, который выполнит это сжатие.

Языковой сервер

Компилятор может быть запущен в режиме сервера. Я не воспользовался стандартным Language Server Protocol, потому что не смог понять его документацию (как и любую документацию от Microsoft) потому что хотел придумать свой самостоятельно.

Языковой сервер — это http сервер, имеющий два endpoint-а:

  1. Для подсветки синтаксиса

  2. Для проверки кода на ошибки

Проверка кода не проста, так как нет общего способа организации проекта. Кроме того для проверки компилятор запускает себя же, для чего ему нужно знать, где он.

Была реализована примитивная IDE на Qt, которая поддерживает данный языковой сервер.

Intermediate Representation

До сих пор отсутствовал, так как я не представлял, что и как следует абстрагировать в языках ассемблера. Однако теперь у меня это представление есть, поэтому intermediate representation появится.

Стандартная библиотека

Должна быть полностью самостоятельной.

  1. Как мы выводим текст в stdout без использования функций? С помощью системного вызова write, который принимает дескриптор (изначально для stdout это 1, но можно с этим поиграться), указатель на строку и длину строки.

  2. Как мы запускаем процесс? С помощью системных вызовов fork и execve. Обратите внимание, что системного вызова execvp нет — необходимо написать поиск по переменной PATH самостоятельно.

  3. Как мы выделяем память? С помощью системного вызова mmap. После выделения памяти на нём следует построить кучу, как структуру данных.

(Кстати, что вы думаете о слове heap? Я под ним понимаю и сегмент процесса, и структуру данных для выделения памяти, построенную над отрезком памяти, и структуру данных корневое дерево, которое поддерживает отношение порядка между вершинами и их потомками. Второе часто называют аллокатором, но тогда и с этим словом возникают проблемы, ведь у нас получаются аллокаторы, требующие аллокаторы (как, например, arena allocator как-то должен получить свои буферы)).

Дополнение

Предложение: автопроталкивание аллокаторов

Здесь я напишу об одной видимой мне проблеме в Zig. В этом языке (и Alias-е) мы избегаем использования внешних аллокаторов в библиотеке, и часто требуем передавать их в функции. При этом обычно для «поддерева» программы у нас есть один аллокатор, который мы используем, а затем удаляем. Идея: пусть функция автоматически передаёт вызываевым функциям свой аллокатор, если обе функции его требуют (что мы будем помечать специальным синтаксисом).

Выглядеть это может примерно так.

func foo@(a: int, b: int) {
  boo(a + b);
}

func boo@(a: int) {
  @.alloc(a);
}

func doo(a: int) {
  @ := heap.page_allocator;
  foo(a, a * a);
  @ := heap.FixedBufferAllocator;
  doo(a);
}

Принимаются предложения

Мне интересно мнение о том,

  1. каких инструментов не хватает в компиляторе,

  2. что в языке сделано неудачно,

что сильно снижает комфорт использования компилятора и раздражает.

Я выделил список вещей, которые ухудшают мне опыт пользования языком:

  1. Отсутствие формата «проекта». Организация даже тривиального проекта весьма сложна (посмотрите на Makefile в примере GitHub).

  2. Отсутствие пакетного менеджера.

  3. Отсутствие поддержки Language Server Protocol, что требует пользоваться именно своей IDE (которая, по сути, является блокнотом с вкладками и подсветкой синтаксиса и ошибок). Свой протокол имеет недостатки в проектировании.

  4. Генерация кода только под одну архитектуру. Для поддержки большего числа архитектур желательно иметь intermediate representation.

  5. Отсутствие возможности передавать в функции инстансы и отсутствие float-ов. Поддержка этого требует дополнительного изучения Application Binary Interface-а.

  6. Отсутствие большого количество синтаксических конструкций: удобного movement-а <- как в C, циклов.

  7. Отсутствие closures (я пока не представляю, как их писать).

  8. Отсутствие вывода типов.

  9. Отсутствие comptime (но они будут) и полиморфизма вообще (макросов нет и не будет).

© Habrahabr.ru