Здесь я попытался показать на практике, что собой представляют некоторые важные концепции из области создания компиляторов. Есть вероятность, что подобные 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 транслятора. Но упоминание "транспилятора" может вызвать раздражение у специалистов по компиляторам, будьте осторожны!
Поэкспериментируйте с кодом. Жду отзывов!