Задача этого проекта - написать компилятор для моего языка программирования. Он будет состоять из 3 основных этапов - front-end (парсит программу пользователя в дерево команд), middle-end (упрощает это дерево) и back-end (создаёт исполняемый файл).
Язык не содержит в себе что-то очень необычное. Просто некоторые стандартные обозначения здесь заменены на слова из хип-хоп сленга:
- aka - =
- choppa - if
- smoke - while
- lesss_go - {
- stop_that_shit - }
- freestyle - print
- houmi - def
- glock - return
- megera - input
Front-end состоит из 2 этапов - лексического и синтаксического анализа.
На первом этапе код пользователя парсится в массив структур - токенов. Они содержат информацию о типе, значении объекта.
Далее эти токены преобразуются в дерево (используется алгоритм рекурсивного спуска).
По итогу получается AST дерево. В нём содержатся команды, переменные, функции и прочее.
На этом этапе нужно упростить дерево команд.
Оптимизируется следующее: все операции с числами, умножение и деление на 1, сложение с 0 и его вычитание, деление 0 и умножение на 0, возведение в 0 и в 1 степень.
Далее задача создать исполняемый файл из дерева команд. У меня реализовано 3 варианта: ассемблер для моего виртуального процессора, elf файл (вместе с nasm) и файл в формате LLVM IR. 2 и 3 варианты подробно описаны здесь и здесь. Обязательно прочитайте!
Напишем программу, в которой будем 10000 раз считать факториал 8 (рекурсивно), и сравним скорость ее выполнения. Будем сравнивать скорость генерируемого мной elf-файла, генерируемого gcc elf-файла (из генерируемого мной ассемблера), генерируемого llvm elf-файла (из генерируемого мной LLVM IR формата) и программы, запущенной на виртуальном процессоре.
Время будем измерять через rdtsc.
| Исполнение | Кол-во тиков | Абсолютное ускорение | Относительное ускорение |
|---|---|---|---|
| мой процессор | 79722571967 | 1 | 1.00 |
| elf из llvm | 7429222 | 10731 | 10730.94 |
| elf из asm | 7354701 | 10840 | 1.01 |
| мой elf | 6815915 | 11697 | 1.08 |