Пишем примитивный и никому не нужный компилятор
Я считаю, что каждый программист должен написать свой компилятор.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник. Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.
Да, компилятор совершенно нагло основан на Tiny-С.
Грамматика
Прежде чем начать, давайте определимся, что именно будет уметь наш язык. Уметь он будет очень мало:
— единственный тип данных — int — все переменные — глобальные. Всего есть 26 переменных (a-z) — из математических операций поддерживаются только "+" и "-" — единственный оператор сравнения — это "<" — из конструкций языка — условные операторы if, if/else, while, do/while
Все. Никаких массивов, функций, структур. Вот какая грамматика получается у нашего языка:
Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.
Программа — это один оператор (statement). Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»). Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор. Выражения — это либо сумма, либо присваивание переменной значения. Здесь сумма — это последовательность сложений-вычитаний термов. Терм — это число, переменная или выражение в скобках. Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.
Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.
Лексический анализатор
На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.
Итак, наш лексический анализатор должен узнавать следующие токены:
— числа — идентификаторы-переменные — ключевые слова: if, else, while, do — символы +, -, <, =, , (, ),; — конец файла
Вот как выглядит его исходный код:
В методе next_tok() анализатор получает следующий токен. Тип токена можно получить из атрибута sym, а его значение (если это переменная или число) — из атрибута value.
Анализатор игнорирует пробелы, проверяет, является ли текущий символ специальным символом языка, если нет — проверяет, является ли он числом или идентификатором. Т.е. встретив цифру 1, анализатор продолжит вычитывать символы, пока не встретит не-числовой символ. Аналогично проверяются идентификаторы (там вместо чисел буквы).
Парсер
Это, наверное, самый сложный компонент нашего компилятора. Его задача, используя токены, полученные от лексического анализатора, сформировать своего рода дерево, в котором иерархия и связи отображают структуру кода. Например:
Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.
Для описания узлов введем класс Node. Вот код класса парсера и класса Node:
Этот парсер работает рекурсивно, начиная с метода parse(). Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.
Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.
При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.
Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.
Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.
На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.
Машинный код
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:
Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:
Код виртуальной машины очень простой. Он весь описывается в методе run:
Осталось написать собственно компилятор — генератор кода.
Компилятор
Венец нашего творения. Вот его исходный код:
Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт). В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.
Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.
Тестируем
Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):