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

  • Tutorial

Здесь я попытался показать на практике, что собой представляют некоторые важные концепции из области создания компиляторов. Есть вероятность, что подобные 15-минутные завершенные истории могут оказаться неплохим способом погружения в сложные темы. Только хорошо бы не пассивно читать то, что представлено ниже, а еще и проверять код в работе.


Если первый опыт окажется успешным, то в будущем вас могут ожидать и другие 15-минутные "зарисовки" по тематике компиляторов.


О чем пойдет речь


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


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


Реализация на F# (автор gsomix):
первая версия
SSA-версия


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


def scan(source):
  tokens = source.split()
  return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]

Что мы здесь сделали? Функция scan получает от пользователя строку в обратной польской форме записи ("2 2 +").


А на выходе мы получаем ее промежуточное представление. Вот такое, например:


[
  ('Push', 2),
  ('Push', 2),
  ('Op', '+')
]

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


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


def trans(ir):
  code = []
  for tag, val in ir:
    if tag == "Push":
      code.append("st[sp] = %d;" % val)
      code.append("sp += 1;")
    elif tag == "Op":
      code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val)
      code.append("sp -= 1;")
  return "\n".join(code)

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


st[sp] = 2;
sp += 1;
st[sp] = 2;
sp += 1;
st[sp - 2] = st[sp - 2] + st[sp - 1];
sp -= 1;

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


Вот только самой машины — интерпретатора у нас-то и нет. Есть компилятор. Что нам осталось? Надо добавить необходимое обрамление для программы на Си.


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


ST_SIZE = 100
C_CODE = r"""#include <stdio.h>
int main(int argc, char** argv) {
int st[%d], sp = 0;
%s
printf("%%d\n", st[sp - 1]);
return 0;
}"""

def scan(source):
  tokens = source.split()
  return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]

def trans(ir):
  code = []
  for tag, val in ir:
    if tag == "Push":
      code.append("st[sp] = %d;" % val)
      code.append("sp += 1;")
    elif tag == "Op":
      code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val)
      code.append("sp -= 1;")
  return "\n".join(code)

def rpn_to_c(source):
  return C_CODE % (ST_SIZE, trans(scan(source)))

print(rpn_to_c("2 2 +"))

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


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


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


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


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


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


C_CODE = r"""#include <stdio.h>
int main(int argc, char** argv) {
%s
printf("%%d\n", %s);
return 0;
}"""

def scan(source):
  tokens = source.split()
  return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]

def trans(ir):
  stack, code = [], []
  name_cnt = 0
  for tag, val in ir:
    if tag == "Push":
      code.append("int t%d = %d;" % (name_cnt, val))
      stack.append("t%d" % name_cnt)
      name_cnt += 1
    elif tag == "Op":
      a, b = stack.pop(), stack.pop()
      code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a))
      stack.append("t%d" % name_cnt)
      name_cnt += 1
  return "\n".join(code), stack.pop()

def rpn_to_c(source):
  return C_CODE % trans(scan(source))

print(rpn_to_c("2 2 +"))

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


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


#include <stdio.h>
int main(int argc, char** argv) {
int t0 = 2;
int t1 = 2;
int t2 = t0 + t1;
printf("%d\n", t2);
return 0;
}

Итоги


Похоже, время нашего совместного занятия истекло. Мы занимались тем, что переводили программу с одного языка на другой. Это называется source-to-source трансляцией. Или же — просто трансляцией, которую можно считать синонимом компиляции, но обычно компилятор переводит программу из высокоуровневого представления в низкоуровневое. Существует еще модное словечко "транспилятор" для обозначения source-to-source транслятора. Но упоминание "транспилятора" может вызвать раздражение у специалистов по компиляторам, будьте осторожны!


Поэкспериментируйте с кодом. Жду отзывов!

Поделиться публикацией

Комментарии 18

    0
    Целая куча терминов для одного и того же, транспайлер, транскомпилятор, транспилер, транспилятор.
    Но упоминание «транспилятора» может вызвать раздражение у специалистов по компиляторам, будьте осторожны!
    Почему?
      0
      Собственно, Вы сами ответили уже на свой вопрос. Зачем «целая куча терминов для одного и того же»? «Транспилятор» это тот же транслятор. Ведь ничего же нового нет в такого рода трансляции. Вот здесь имеется любопытная дискуссия на тему: news.ycombinator.com/item?id=15154994
        0
        Да уж.) А вы как думаете если код транслируется в ассемблерный код(не машинный), то является ли транслятор компилятором?
          0
          Конечно же является. Вот определения из двух известных учебников:

          «A compiler is a tool that translates software written in one language into
          another language». (K. Cooper. L Torczon. Engineering a Compiler)

          «Compilers are software systems that translate programs written in higher-level languages into equivalent programs in object code or machine language for execution on a computer». (Steven Muchnick. Advanced Compiler Design and Implementation).

      0
      Очередная статья для начинания деланья компиляторов, но почему все они так недалеко заходят? Как только начинаются менее тривиальные вещи, чем семантический анализ, и всё, цикл оборвался.
      Задумано ли что-то серьёзное из этой статьи или автор честно ограничится введением?
        0
        Я думаю, не стоит даже упоминать том, что создавать компиляторы — дело непростое. За 15 минут вас никто не сможет научить это делать. Тут у нас, скорее, ситуация в духе знаменитой заметки Teach Yourself Programming in Ten Years П. Норвига. Поэтому специалисты по компиляторам и ценятся так высоко, правильно?

        Есть и еще один момент. Компиляторы это чрезвычайно широкая область. В большинстве случаев ее и не нужно досконально изучать. Необходимо определить свою нишу. Например, в последнее время очень популярна тема создания собственных DSL, в том числе и на основе source-to-source подхода. Еще один популярный аспект — создание компилятора с порождением целевого кода для LLVM или подобного готового backend'а. Здесь надо понимать, хотя бы, что такое SSA. Теперь давайте вернемся к моей 15-минутной заметке. А ведь тут уже изложены на простых примерах как source-to-source-подход, так и SSA.

        Я и сам немного подустал от многочисленных легковесных введений в компиляторостроение. Но мне захотелось попробовать свои силы: как много я смогу доходчиво рассказать в пределах условных 15 минут. Мне показалось, что можно разработать цикл 15-минутных историй по разным моментам, связанным с данной тематикой. И эти истории помогут читателям с разбором серьезных материалов. О них — ниже.

        Итак, вы хотите серьезного подхода. Тогда добро пожаловать на вики-страничку.
          0
          Речь не про 15 минут, а про разочарование от ожидания внятного продолжения.
          Поскольку продолжения не анонсировано, то и разочарования не будет.
            0
            Продолжение будет, определенно. Идея была в том, чтобы публиковать отдельные фрагменты «руководства» (назовем это так) на хабре, получая обратную связь. Но теперь я для себя выяснил, что разумнее будет написать здесь, спустя время, уже о выходе полного и окончательного результата :)
              0
              Не забывайте о том, что полного окончательного результата вы не достигнете никогда ,)
                0
                Это понятно. Но я говорю о результате в духе «книга ушла в печать» :)
                  +1
                  Продолжайте. Очень интересно получилось про SSA. Интересно, что будет дальше. Преобразования над SSA?
                    0
                    Можно примерно в таком стиле ruslanspivak.com/lsbasi-part1

                    Нашел вики

                    А код непосредственно файлом .py есть?
              +1

              Если будет хотя бы сравнение, как можно сделать то, что Вас написано, с помощью готовых лексеров/парсеров (в питоне есть ply, sly), и что писать парсеры самостоятельно — не лучшая идея, было бы замечательно. Ведь компиляторы — действительно сложная штука! И если надо по-быстрому набросать свой DSL, кто-то может пойти на хабр, найти подобный туториал и нафигачить все с нуля. Гораздо ценнее было бы почитать, что делать с ast после парсинга. Таких статей, как мне показалось, значительно меньше
              P.s. навеяно болью переписывания самописного парсера (предыдущим коллегой) на ply

                0
                Обратите внимание, что моя заметка, по большому счету, именно о backend. Как раз по той причине, что статей на эту тему «значительно меньше».

                Лексический/синтаксический анализ вы можете найти в любом учебнике. Это самая формализованная, проверенная часть компилятора. Тем не менее, действительно, полезно еще раз обратить внимание на это, что кроме lex/yacc существуют более удобные, современные средства: PEG, комбинаторы. Вот пример игрушечного компилятора, который сделан с помощью моей библиотеки raddsl: github.com/true-grue/PigletC
            0
            «A compiler is a tool that translates software written in one language into
            another language». (K. Cooper. L Torczon. Engineering a Compiler)

            Т.е. достаточно sed, grep и awk и можно писать компилятор.

            Вот бы кто-нибудь компилятор из PHP (для основных конструкций работы с массивами и строками) в С сделал.
            А то мной было подмечно, что код из PHP перекладывается в С почти без усилий.
              +1

              По-моему если писать подобное 15-минутное введение — то было бы весьма неплохо сделать прототип с помощью широко известных в узких кругах инструментов, вроде lex/bison.
              А то банальный парсер грамматики пробуют писать все, и даже до конечного автомата дело доходит — но вот в реальной жизни в подавляющем большинстве случаев удобнее использовать готовый парсер, чем городить свой. Особенно с точки зрения поддержки синтаксиса в будущем и его расширяемости (добавить правило из пяти строчек в бизоновский исходник всё же проще, чем перелопатить тысячу строк готового ДКА).
              Да, такие "вводные" уже есть, но что-то кроме dragon book я их особо то и не видел.
              Лучше, если простых примеров будет больше!

                0
                Я выше уже написал по поводу lex/yacc/bison. Обратите внимание, что в современных «промышленных» компиляторах (clang, gcc и проч.) такого рода инструментарий не используется. А используется там традиционный подход на основе рекурсивного спуска.

                Среди современных генераторов парсеров, удобных для начинающих, я бы выделил, например, Ohm: nextjournal.com/dubroy/ohm-parsing-made-easy
                0

                Есть две хорошие книги с пошаговым написанием интерпретатора и компилятора на Go, рекомендую:


                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое