Здесь я попытался показать на практике, что собой представляют некоторые важные концепции из области создания компиляторов. Есть вероятность, что подобные 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 транслятора. Но упоминание "транспилятора" может вызвать раздражение у специалистов по компиляторам, будьте осторожны!
Поэкспериментируйте с кодом. Жду отзывов!
Комментарии (17)
a-tk
13.12.2018 19:38Очередная статья для начинания деланья компиляторов, но почему все они так недалеко заходят? Как только начинаются менее тривиальные вещи, чем семантический анализ, и всё, цикл оборвался.
Задумано ли что-то серьёзное из этой статьи или автор честно ограничится введением?true-grue Автор
13.12.2018 20:00Я думаю, не стоит даже упоминать том, что создавать компиляторы — дело непростое. За 15 минут вас никто не сможет научить это делать. Тут у нас, скорее, ситуация в духе знаменитой заметки Teach Yourself Programming in Ten Years П. Норвига. Поэтому специалисты по компиляторам и ценятся так высоко, правильно?
Есть и еще один момент. Компиляторы это чрезвычайно широкая область. В большинстве случаев ее и не нужно досконально изучать. Необходимо определить свою нишу. Например, в последнее время очень популярна тема создания собственных DSL, в том числе и на основе source-to-source подхода. Еще один популярный аспект — создание компилятора с порождением целевого кода для LLVM или подобного готового backend'а. Здесь надо понимать, хотя бы, что такое SSA. Теперь давайте вернемся к моей 15-минутной заметке. А ведь тут уже изложены на простых примерах как source-to-source-подход, так и SSA.
Я и сам немного подустал от многочисленных легковесных введений в компиляторостроение. Но мне захотелось попробовать свои силы: как много я смогу доходчиво рассказать в пределах условных 15 минут. Мне показалось, что можно разработать цикл 15-минутных историй по разным моментам, связанным с данной тематикой. И эти истории помогут читателям с разбором серьезных материалов. О них — ниже.
Итак, вы хотите серьезного подхода. Тогда добро пожаловать на вики-страничку.a-tk
13.12.2018 21:06Речь не про 15 минут, а про разочарование от ожидания внятного продолжения.
Поскольку продолжения не анонсировано, то и разочарования не будет.true-grue Автор
13.12.2018 21:16Продолжение будет, определенно. Идея была в том, чтобы публиковать отдельные фрагменты «руководства» (назовем это так) на хабре, получая обратную связь. Но теперь я для себя выяснил, что разумнее будет написать здесь, спустя время, уже о выходе полного и окончательного результата :)
MaxVetrov
13.12.2018 21:19Не забывайте о том, что полного окончательного результата вы не достигнете никогда ,)
true-grue Автор
13.12.2018 21:22Это понятно. Но я говорю о результате в духе «книга ушла в печать» :)
x86128
14.12.2018 07:38Продолжайте. Очень интересно получилось про SSA. Интересно, что будет дальше. Преобразования над SSA?
MaxVetrov
14.12.2018 18:21Можно примерно в таком стиле ruslanspivak.com/lsbasi-part1
Нашел вики
А код непосредственно файлом .py есть?
foldr
14.12.2018 11:43+1Если будет хотя бы сравнение, как можно сделать то, что Вас написано, с помощью готовых лексеров/парсеров (в питоне есть ply, sly), и что писать парсеры самостоятельно — не лучшая идея, было бы замечательно. Ведь компиляторы — действительно сложная штука! И если надо по-быстрому набросать свой DSL, кто-то может пойти на хабр, найти подобный туториал и нафигачить все с нуля. Гораздо ценнее было бы почитать, что делать с ast после парсинга. Таких статей, как мне показалось, значительно меньше
P.s. навеяно болью переписывания самописного парсера (предыдущим коллегой) на plytrue-grue Автор
14.12.2018 12:27Обратите внимание, что моя заметка, по большому счету, именно о backend. Как раз по той причине, что статей на эту тему «значительно меньше».
Лексический/синтаксический анализ вы можете найти в любом учебнике. Это самая формализованная, проверенная часть компилятора. Тем не менее, действительно, полезно еще раз обратить внимание на это, что кроме lex/yacc существуют более удобные, современные средства: PEG, комбинаторы. Вот пример игрушечного компилятора, который сделан с помощью моей библиотеки raddsl: github.com/true-grue/PigletC
dcc0
14.12.2018 01:40«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 перекладывается в С почти без усилий.
klirichek
14.12.2018 08:41+1По-моему если писать подобное 15-минутное введение — то было бы весьма неплохо сделать прототип с помощью широко известных в узких кругах инструментов, вроде lex/bison.
А то банальный парсер грамматики пробуют писать все, и даже до конечного автомата дело доходит — но вот в реальной жизни в подавляющем большинстве случаев удобнее использовать готовый парсер, чем городить свой. Особенно с точки зрения поддержки синтаксиса в будущем и его расширяемости (добавить правило из пяти строчек в бизоновский исходник всё же проще, чем перелопатить тысячу строк готового ДКА).
Да, такие "вводные" уже есть, но что-то кроме dragon book я их особо то и не видел.
Лучше, если простых примеров будет больше!true-grue Автор
14.12.2018 12:30Я выше уже написал по поводу lex/yacc/bison. Обратите внимание, что в современных «промышленных» компиляторах (clang, gcc и проч.) такого рода инструментарий не используется. А используется там традиционный подход на основе рекурсивного спуска.
Среди современных генераторов парсеров, удобных для начинающих, я бы выделил, например, Ohm: nextjournal.com/dubroy/ohm-parsing-made-easy
MaxVetrov
Целая куча терминов для одного и того же, транспайлер, транскомпилятор, транспилер, транспилятор.
Почему?true-grue Автор
Собственно, Вы сами ответили уже на свой вопрос. Зачем «целая куча терминов для одного и того же»? «Транспилятор» это тот же транслятор. Ведь ничего же нового нет в такого рода трансляции. Вот здесь имеется любопытная дискуссия на тему: news.ycombinator.com/item?id=15154994
MaxVetrov
Да уж.) А вы как думаете если код транслируется в ассемблерный код(не машинный), то является ли транслятор компилятором?
true-grue Автор
Конечно же является. Вот определения из двух известных учебников:
«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).