Как написать свой компилятор

Как написать свой компилятор

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

Техническое задание

1. Ознакомиться со спецификацией (англ. language reference) одного из реальных языков, который будет взят за основу своего языка:
   • Python: docs.python.org/3/reference
   • Javascript: ecma-international.org/publications/standards/Ecma-262.htm
   • Golang: golang.org/ref/spec
   • ANSI C: softeng.polito.it/tongji/AP/C-reference-language.pdf, en.cppreference.com/w/c
2. Составить 5-10 небольших программ на языке, взятом за основу, использующих как можно более ограниченное процедурное подмножество языка
3. Спроектировать компилятор
   • Составить список возможностей, которые формируют минимальный возможный язык. Учесть обязательные требования: поддержу выражений с арифметическими, логическими и сравнительными операторами; переменных и присваивания; подпрограмм (функций) с параметрами и возвращаемым значением
   • Составить список поддерживаемых типов данных. Учесть обязательные требования: поддержку чисел с плавающей точкой, строк, а также массивов либо пользовательских структур
4. Составить дорожную карту (roadmap) проекта в виде таблицы, которая бы ответила на вопросы
   • сколько итераций и каковы их сроки сдачи (deadline)?
   • что получает пользователь в конце каждой итерации?
   • как это выглядит?
   • какие задачи надо выполнить в итерации, чтобы пользователь смог получить обещанное?
5. Реализовать компилятор, содержащий в себе драйвер, фронтенд и бекенд.
   • Фронтенд должен выполнять лексическую, синтаксическую и семантическую стадию анализа, на выходе создавать AST.
   • Можно использовать LLVM и его промежуточный язык LLVM-IR как набор готовых компонентов для бекенда, в этом случае бекенд должен выполнять преобразование AST в промежуточный код, оптимизатор промежуточного кода и генератор машинного кода из промежуточног
   • Можно разработывать бекенд без промежуточного кода, в этом случае используется ассемблер целевой платформы, и придётся реализовать оптимизатор ассемблерного кода
   • Драйвер должен уметь превращать объектный файл, созданный в бекенде, в исполняемый файл путём вызова компоновщика или иным способом.

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

Кроме этих компонентов предстоит написать библиотеку времени выполнения языка (runtime library) и набор функциональных тестов.

Процесс написания компилятора

Компилятор можно разработать по методологии “водопад” либо по гибким методологиям.

В методологии “водопад” процесс разработки выглядит как последовательное движение по ТЗ, описанному выше. Перед каждым этапом нужно тщательно проектировать, изучать критически готовые примеры и теоретические материалы. Если пренебречь проектированием, проект наверняка пойдёт в неправильную сторону и не будет сдан в сроки.

В методологии agile вы за один короткий спринт реализуете минимальный рабочий прототип, а затем слоями накладываете новую функциональность. Проектирование, изучение теории и готовых примеров выполняется перед каждым спринтом. Если пренебречь проектированием, спринт наверняка будет потрачен впустую, что задержит сдачу проекта.

Для тех, кто предпочитает agile, есть примерный план послойного наращивания функционала:

1. Компилятор уровня калькулятора с поддержкой + , — , * , / , учётом неявного приоритета и с основными компонентами компилятора: парсером на основе рекурсивного спуска, AST и бекендом, использующим для вычисления стек. Пользователь может использовать компилятор как калькулятор.
2. Компилятор с инструкциями (одна на строку) и переменными, на этом спринте можно улучшить грамматику, реализацию парсера, добавить лексер, улучшить генератор кода. Пользователь может использовать компилятор как калькулятор с переменными.
3. Компилятор структурного языка (с циклами и ветвлениями), на этом спринте потребуется улучшить грамматику и парсер, а в бекенде разобраться с генерацией программы с корректным графом потока выполнения (control flow graph)
4. …

Командная работа

Проект компиляторов можно выполнять вдвоём. Зоны ответственности можно разделить, например, так

1. Первый — реализует Frontend компилятора, определяет структуру AST и грамматику языка
2. Второй — реализует Backend и драйвер компилятора, интегрирует Backend и Frontend
3. Тестовый набор программ пишется сообща

Как сделать язык разнообразнее

Разные языки используют разные подходы к таким привычным вещам, как выражения, ветвления и циклы, подпрограммы и та далее. Ниже показаны некоторые типовые решения из разных языков программирования:

Name already in use

Compiler-Development / docs / tutorial.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

1 contributor

Users who have contributed to this file

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Кратчайшее введение в создание компилятора

Давайте сделаем компилятор арифметических выражений. Такой, который переведет исходный текст в обратной польской форме записи (ее еще называют RPN или ПОЛИЗ) в промежуточный код стековой машины. Но у нас не будет интерпретатора стекового кода, как вы, возможно, могли подумать. Далее мы сразу переведем результат в представление на языке Си. То есть у нас получится компилятор RPN в Си.

Кстати говоря, писать компилятор мы будем на Python. Но пусть это не останавливает тех, кто предпочитает какой-то иной язык программирования. Вот вам полезное упражнение: переведите приведенный код на ваш любимый язык. Или воспользуйтесь уже готовым переводом:

Начнем с синтаксического анализа

Что мы здесь сделали? Функция scan получает от пользователя строку в обратной польской форме записи («2 2 +»). А на выходе мы получаем промежуточное представление. Вот такое, например:

Итак, мы уже получили компилятор. Но уж очень он несерьезный. Вспомним, что изначально речь шла о коде на Си.

Займемся трансляцией в Си

Что здесь происходит? Давайте посмотрим на вывод данной функции (на том же примере с «2 2 +»).

Да, это уже похоже на код на Си. Массив st играет роль стека, а sp — его указатель. Обычно с этими вещами работают виртуальные стековые машины. Вот только самой машины — интерпретатора у нас-то и нет. Есть компилятор. Что нам осталось? Надо добавить необходимое обрамление для программы на Си.

Наш первый компилятор в готовом виде

Остается скомпилировать вывод данной программы компилятором Си.

Вы все еще готовы продолжать? Тогда давайте обсудим, что у нас получилось. Есть один сомнительный момент — наш компилятор транслирует константные выражения, а ведь их можно вычислить просто на этапе компиляции. Нет смысла переводить их в код. Но давайте пока считать, что какие-то аргументы могут попасть в стек извне. Например, из аргументов командной строки. Остановимся на том, что практический смысл нашей разработке можно придать и позднее. Сейчас же важно получить общее представление о построении простейших компиляторов, верно?

Компилятор с использованием формы SSA

Вам нравится заголовок? SSA — это звучит очень солидно для любого компиляторщика. А мы уже сейчас будем использовать эту самую SSA. Что это такое? Давайте двигаться по порядку.

Мы генерируем в данный момент код на Си, безо всяких виртуальных машин. Но зачем нам тогда рудимент в виде операций со стеком? Давайте заменим эти операции работой с обычными переменными из Си. Причем, мы не будем экономить переменные — для каждого выражения заведем новое имя. Пусть компилятор Си сам со всем этим разбирается. Получается, что у нас каждой переменной значение присваивается лишь однажды. А это, кстати говоря, и есть форма SSA.

Вот наш новый компилятор.

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

Вот окончательный результат:

Похоже, пришла пора расширять возможности нашего входного языка, как вы считаете? И двигаться, на мой взгляд, здесь можно в направлении стековых языков, таких как Forth, Postscript, Joy или Factor. Конечно же, можно и пойти путем усложнения входного синтаксиса. Но все эти вопросы давайте оставим для следующих заметок. Успехов в построении компиляторов!

Пишем примитивный и никому не нужный компилятор

Я считаю, что каждый программист должен написать свой компилятор.

Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.

В посте мы рассмотрим, как можно написать свой компилятор 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):

Пишем свой собственный компилятор или заново изобретаем SASS

Профессия разработчика прекрасна не только тем что ей можно обучиться самому проходя онлайн-курсы или читая книги. Но и получить небольшой опыт самостоятельно: написать свой аналог (или доработку) существующей библиотеки или продукта “just for fun” и залит его на github.

Лично я убежден, что каждый разработчик должен потратить личное время чтобы написать свою CMS, интерпретатор/компилятор или свою js-библиотеку для создания интерактивных интерфейсов ��. Это очень хорошая самостоятельная практика языка и доведения проекта до конца.

Свою CMS я писал дважды, так что пришло время написать компилятор.

Зачем нужно писать компилятор/интерпретатор?

Каждый из этих инструментов решает свою специфичную задачу.

Компилятор выполняет задачу преобразования одного языка в другой без потери смысла. Это необходимо когда среда, в которой пишется код и то где он будет выполняться — разная.

Более конкретный пример: Современные браузеры понимают только язык javascript, но это не повод писать на нем клиентскую часть. Есть много языков которые компилируются в него.

Интерпретатор выполняет задачу обработки и мгновенного выполнения исходной программы или запроса, без компиляции его в другой язык. Есть много интерпретируемых языков программирования, таких как Ruby, Python, Javascript и др.

Более конкретный, рабочий пример: Отдел маркетинга каждый день посылает запрос IT-отделу на выгрузку данных из БД в csv-файлы. При этом форматы метрик, по которым надо сделать выгрузку, могут часто меняться. Чтобы не продолжать нагружать программистов каждодневным переписыванием кода, можно реализовать интерпретатор, который будет представлять собой ограниченную версию SQL и будет более понятен типичному сотруднику. Благодаря этому отдел маркетинга получает возможность делать выгрузки самостоятельно и быстро.

Пишем свой компилятор

Перед тем как начать писать, нужно было определиться с функционалом.

При выборе функционала компилятора стояли следующие требования:

• Он не должен быть слишком простой, чтобы его было скучно делать
• Он не должен быть сложным, чтобы тратить на него все свободное время

Идеи о создании компилятора языка программирования отошли на второй план. Был выбор между написанием аналога препроцессинга SASS или шаблонизатора HAML/SLIM. В итоге был выбран SASS.

Осталось определиться с функционалом. Я поставил цель реализовать следующие фичи:

• Использование многострочных комментариев
• Использование переменных
• Использование миксинов
• Вложенность селекторов

Но и появился ряд ограничений:

• Переменные и миксины не могут быть вложенные
• Миксины не имеют входящих аргументов

Структура приложения

Само приложение представляет собой механизм компиляции (machine) и CLI (консольный интерфейс).

Консольный интерфейс — это стандартный bin-файл. А механизм компиляции состоит из трех частей:

• Парсер — здесь логика преобразования текста в абстрактное синтаксическое дерево (AST).
• Трансформатор — здесь логика преобразования вложенного синтаксического дерева в не вложенную структуру.
• Компилятор — здесь логика компиляции (отрисовки) синтаксического дерева в файл.

Парсер

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

Иными словами: нужен инструмент который способен преобразовать сплошной текст в набор коротких, последовательный и вложенных процедур. Относительно которых можно легко описать правила взаимодействия машины с ними. Парсер выполняет задачу: “преобразуй этот текст в набор инструкций которыми будет удобно манипулировать машине”.

Более подробно про его работу:

И так, у нас есть файлик с css, который надо преобразовать.

Парсер проходит по тексту, удаляет комментарии, разбивает текст на минимальные логические части. В данном случае, для разделения текста на минимальные логические части, достаточно разбить текст относительно символов ‘;’, ‘<‘, ‘>’. В итоге, текст преобразовывается в массив строк.

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

После этого парсер преобразует предыдущий массив в абстрактное синтаксическое дерево (AST). У нас появилась вложенная структура, которой легко манипулировать для дальнейшей обработки.