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

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

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

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

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

Реализация на F# (автор gsomix ^[2]):
первая версия ^[3]
SSA-версия ^[4]

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

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("%%dn", 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 ^[5].

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

C_CODE = r"""#include <stdio.h>
int main(int argc, char** argv) {
%s
printf("%%dn", %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("%dn", t2);
return 0;
}

Итоги

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

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

Автор: Пётр Советов

Источник ^[6]