Skip to content

Latest commit

 

History

History
157 lines (116 loc) · 8.4 KB

tutorial.md

File metadata and controls

157 lines (116 loc) · 8.4 KB
Raw

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

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

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

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

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;
}

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