Как написать свой компилятор
Перейти к содержимому

Как написать свой компилятор

  • автор:

Как создать простой компилятор для простого языка (например, brainfuck)?

В общем хочу написать компилятор brainfuck или своего собственного языка (простого). Как это сделать?
P.S.
Интерпретатор (для brainfuck) я осилил сам, как сделать компилятор я даже не догадываюсь.
Желательно найти литературу.

Отслеживать
49.3k 17 17 золотых знаков 57 57 серебряных знаков 101 101 бронзовый знак
задан 16 сен 2011 в 14:07
1,823 5 5 золотых знаков 28 28 серебряных знаков 40 40 бронзовых знаков

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

для brainfuck я когда то сам писал компилятор. Лучше для начала написать траслятор, который переведет код в с/с++/java/любой другой любимый язык. Это очень просто. Вот пример траслятора в Java. После того, как получится написать такое, никто не мешает написать похожее для ассеблера (для fasm или masm). Последней ступенькой будет генерирование сразу исполнимого файла. О том, что нужно знать ассемблер, я думаю вопросов нет.

Отслеживать
ответ дан 16 сен 2011 в 14:12
112k 6 6 золотых знаков 94 94 серебряных знака 161 161 бронзовый знак

Есть такая книжка, Marc-André Cournoyer, «How To Create Your Own Freaking Awesome Programming Language» (по ссылке — продается, но ищущий название и слово «pdf» всегда найдет и где взять менее цивлизованно, ЕВПОЧЯ). Показывают основы на пальцах, этакая «Драконья Книга для самых маленьких». Начинают с лексера и парсера, затем интерпретатор, и затем — компилятор под LLVM и, на всякий случай, собственную игрушечную виртуальную машину. Все, правда, на Ruby, но общие идеи от языка не зависят. Так что если есть интерес — можете поискать и посмотреть, рекомендую.

Отслеживать
ответ дан 16 сен 2011 в 14:21
9,253 1 1 золотой знак 20 20 серебряных знаков 37 37 бронзовых знаков
Отслеживать
ответ дан 16 сен 2011 в 14:09
25.9k 1 1 золотой знак 38 38 серебряных знаков 71 71 бронзовый знак
тут используется pascal-я его плохо понимаю(тем-более на линукс его нет)
17 сен 2011 в 8:41
На линукс есть паскаль(free pascal compiler), но лучше не нужно.
10 дек 2011 в 21:57
вот именно
11 дек 2011 в 10:34

  • c++
  • компилятор
  • brainfuck
    Важное на Мете
Похожие

Подписаться на ленту

Лента вопроса

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.4.30.8420

Как создать свой простой компилятор

За время пребывания на стажировке в Штутгарте я узнал и научился применять системы для написания парсеров и интерпретаторов. Разумеется, написать любую программу можно и на императивном языке программирования, в том числе и интерпретатор. Но как только начнется процесс разработки, сразу станет очевидным, что приходится писать слишком много однообразного кода. Разобравшись с поставленной задачей я узнал, что эта проблема была решена, были созданы специальные программы, позволяющие декларативно описывать язык, а затем транслировать это описание в эффективный код на императивных языках программирования. Опытом применения таких средств я и хочу поделиться в индивидуальном разделе.

Я не буду рассматривать сложные концепции, но эта статья претендует быть хорошим началом для изучения темы компиляторов и интерпретаторов. После изучения изложенного материала у Вас больше не будет желания писать сколь-нибудь сложный парсер на императивных языках программирована (таких как С++ или Java), и более-того, Вы сможете писать парсеры не только для языков программирования, но и для других данных, например для своего собственного формата конфигурационного файла (если вам такой вдруг понадобится).

И так, что же такое современный компилятор? Рассмотрим его сначала как черный ящик. На входе компилятору поступает файл с некоторыми (обычно текстовыми) данными – описание программы на исходном языке компилятора. На выходе компилятор выдает файл с другими данными – описание той же программы, но уже на другом языке – зачастую в машинном коде, или на языке ассемблера. То есть, компилятор можно рассматривать как переводчик программ с одного машинного языка на другой. Тут возникает проблема масштабируемости. Сейчас существует множество языков и множество целевых платформ (не забываем так же про виртуальные процессоры, такие как JVM, CLR, Parrot и т.д.). Когда создается новый язык программирования, Появляется необходимость использовать его на разных архитектурах, а как следствие приходится писать множество компиляторов. Эту проблему достаточно быстро осознали, и перешли к 3х этапной модели компиляции программ [1].

  1. Парсер, генератор дерева синтаксического разбора
  2. Оптимизатор промежуточного представления кода
  3. Генератор кода из промежуточного представления в целевую платформу

Такая архитектура позволила уменьшить объем работы, связанный с созданием новых языков программирования, позволала переносить программы на новые платформы(кто бы мог подумать, есть способы конвертации С++ кода в JavaScript!), а так же упростила разработку и отладку компилятора в целом.

LLVM как библиотека для разработки компиляторов

Ярким примером такой системы компиляторов является Low Level Virtual Machine (LLVM). На рисунке наглядно показано, как с помощью LLVM реализуется компиляция различных языков.

Как можно заметить на рисунке, проект LLVM реализует оптимизатор и генератор кода, поэтому, при использовании LLVM требуется реализовывать только парсер. В рамках этой статьи я не буду рассказывать о архитектуре виртуального процессора LLVM и системе команд, но для примера привожу программу на LLVM, что бы именть понятие, как язык вообще выглядит.

%char = type i8 %int = type i32 @msg = internal constant [13 x %char] c»Hello World!\00″ declare %int @puts(%char*) define %int @main()

Лексический и грамматический анализ исходного кода

И так, перейдем непосредственно к написанию парсера. Какой бы не были язык программирования, сразу в голову приходят однотипные действия. Нужно как-то вычленять лексемы, искать выражения, области видимости и т.д. Много работы было проведено в исследовании парсеров, и в итоге на данный момент была сформирована следующая концепция: сначала исходный текст разбивается на лексемы лексическим анализатором. Лексемами могут являться ключевые слова слова, имена переменных, пробелы, числа, специальные символы. Ниже приведен пример некого выражения на JSON- подобдном языке и его разбор лексическим анализатором.

После лексического разбора, лексемы и исходный текст отдаются синтаксическому анализатору. Синтаксический анализатор собирает вместе лексемы, формируя более сложные выражения. А из них в свою очередь еще более сложные. В итоге вся программа представляется парсером как одно выражение, и оно называется деревом синтаксического разбора. Этим деревом легко манипулировать, например на его основе можно сделать простой интерпретатор или компилятор. Причем, единственное отличие компилятора от интерпретатора только в том, что компилятор записывает в выходной поток соответствующую команду, а интерпретатор эту команду непосредственно исполняет [2].

Написание парсеров и лексеров дело рутинное и сложное. Но прогресс не стоит на месте и появилось множество программ которые по описанию лексики и грамматики языка генерируют парсер и лексер на Вашем любимом языке программирования.

Так сложилось, что я предпочитаю С/С++, поэтому для примеров буду использовать flex для получения набора токенов и bison для построения дерева разбора.

Программа на языке LEX состоит из 3х частей, первая часть – это обычный код на С, заключенный в символы %< … >%. Второй блок, это список регулярных выражений, и соответствующий им код на С. Каждый раз, когда лексер будет встречать что-то во входном потоке, подходящее под регулярное выражение, он будет исполнять соответствующий ему код на С. 3я часть программы, это тоже код на С, в данном примере она не требуется и потому отсутствует. Пример простейшей программы с использованием генератора lex:

% < #include %> %% [0123456789]+ printf("NUMBER\n"); [a-zA-Z][a-zA-Z0-9]* printf("WORD\n"); %%

Откомпилировать и запустить программу можно так:

$ lex example.l $ cc lex.yy.c -o example -lfl $ ./example foo WORD bar WORD 123 NUMBER bar123 WORD 123bar NUMBER WORD

После чего вы получите программу, которая читает входной поток с клавиатуры, и при каждой встрече числа выводит слово «NUMBER», а каждый раз, когда встречает слово, выводит «WORD»

Грамматический анализ

Предположим, у нас есть двигатель, которым мы хотим управлять с помощью специального языка. Процесс работы с двигателем может выглядеть следующим образом:

power on Двигатель включен! power off Двигатель выключен! set speed 100 Задана новая скорость вращения!

Необходимо распознавать следующие токены: power, on/off (состояние STATE), set, speed и числа (NUMBER). Lex-анализатор выглядит следующим образом

% < #include #include "y.tab.h" %> %% [0-9]+ yylval=atoi(yytext, 10); return NUMBER; poer return TOKPOWER; on|off yylval=!strcmp(yytext,"on"); return STATE; set return TOKSET; speed return TOKSPEED; \n /* игнорируем символ конца строки */; [ \t]+ /* игнорируем пробелы и символы табуляции */; %%

В этом примере нужно отметить некоторые изменения, по сравнению с предыдущим примером. Во-первых, был подключен файл ‘y.tab.h’, во-вторых, на экран больше ничего не выводится, а лишь возвращаются имена токенов. Это изменение нужно потому, что поток токенов отдается на вход YACC, которому неважно, что выводится на экран. В файле y.tab.h как раз находятся определения этих токенов.

Теперь про сам файл y.tab.h. Он генерируется парсером BISON из файла грамматики, который мы сейчас напишем. Наш язык очень прост,такой же простой будет и его грамматика:

%token NUMBER TOKPOWER STATE TOKSET TOKSPEED commands: /* empty */ | commands command ; command: power_switch | set_speed ; power_switch: TOKPOWER STATE < if($2) // вместо $2 будет подставлено yylval из lex файла для токена STATE printf("\Двигатель включен!\n"); else printf("\tДвигатель выключен!\n"); >; set_speed: TOKSET TOKSPEED NUMBER < printf("\tЗадана новая скорость вращения - %d оборотов в минуту!\n", $3); >;

Первая часть грамматики означает, что имеются «команды» (commands), и эти команды состоят из отдельных «команд» (command). Как нетрудно заметить, это определение рекурсивно, ведь оно содержит в себе само себя. Благодаря рекурсии, программа способна постепенно сокращать набор команд одну за одной. Второе правило определяет, что из себя представляет команда. Предпологается лишь два типа команд — power_switch (вкл/выкл двигателя) и set_speed (установка скорости). Здесь используется знак ИЛИ — | . В целом правило означает: «command может быть power_switch или set_speed». Правило power_switch состоит из токена POWER (это просто слово «power»), после которого идет состояние (оно определено в Lex-файле как «on» или «off»). Немного более сложным является последнее правило set_speed, состоящее из токена SET (слово «set»), токена SPEED (слово «speed») и числа.

пример работы программы:

$ yacc -d example2.y $ lex example2.l $ cc lex.yy.c y.tab.c -o example2 $ ./example2 power on Двигатель включен! power off Двигатель выключен! set speed 100 Задана новая скорость вращения - 100 оборотов в минуту!

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

Создание собственного компилятора

В какой-то довольно близкий момент времени мне стало интересно устройство компиляторов в целом, а в частности трансляторов с языков высокого уровня в ассемблер. И оказалось, что статей на эту тему не так много, а с примерами и хоть сколько-нибудь детальным описанием я нашел вообще одну, выбор языков в которой был несколько странным.

Не говорю, что эта статья плоха, напротив, но основная проблема, на мой взгляд, была в том, что транслируется код в язык собственной виртуальной машины, а не в ассемблерный код. Поэтому я решил попробовать написать свою статью, для освещения этой проблемы.

Выбор языков программирования

В качестве языка самого компилятора я выбрал C++, потому что, по данным гугла, в основном для компиляторов используется он, либо чистый «Си». Транслировать же будем в старенький asm, предназначенный для DOS.

С выбором ассемблера стоит сделать оговорку, почему именно такое экзотическое решение для 2023 года. На деле все просто: его, на мой взгляд, поймет любой, кто работает с современными вариантами ассемблера, а также студенты, которые просто касались этого языка в вузе.

О чем будет и не будет идти речь в данной статье

Сразу сделаю оговорку: изображения в этой статье будут приведены из «Книги Дракона-2», но мое знакомство с ней было слишком мимолетным (достать картинки для статьи и пробежаться по диагонали по введению).

Вернемся к фазам компиляции программы. Для их описания можно привести вот такое изображение с примером каждой фазы:

В рамках данной статьи я, как и в статье, упомянутой в заголовке, я несколько упрощу схему, а именно будут пропущены шаги семантического анализа (в предложенной модели в нем нет смысла) генератора промежуточного кода и его оптимизатора. При этом в статье будет освещен вопрос построения лексического и синтаксического анализаторов, а также генерация ассемблерного кода.

Определение грамматики лексического анализатора

Лексический анализатор, можно сказать, одна из простейших частей компилятора. На его этапе текст программы преобразуется в набор токенов, без проверки на корректность их последовательности.

Для начала определимся, какие операции будут доступны в нашем компиляторе. В рамках данной статьи будет рассматриваться слегка усложненный калькулятор «с базара»:

  • Доступна базовая арифметика (+, -, *, / (целочисленное)). У арифметических действий нет приоритета друг над другом, но можно задать порядок действий с помощью скобок.
  • Для удобства некоторых вычислений добавлены условные операторы и операторы циклов if, if/else, while.
  • Вывод результатов вычислений в консоль осуществляется с помощью оператора print.
  • Для сравнения величин перегружен единственный оператор < (который возвращает 1, если сравнение верно, и 0 в противном случае).
  • Для повышения удобства пользователя, ему предоставлены 26 глобальных переменных, которые в тексте программы обозначаются строчными латинскими буквами.
  • Пользователю доступен один тип данных: unsigned short.
  • Пользователь может группировать операторы с помощью фигурных скобок.
  • В качестве результата операции присваивания переменной значения, возвращается новое значение переменной.
  • Пробелы, символы табуляции и переносы на новую строку не учитываются при анализе входного текста.

Грамматика языка получается следующей (модифицированная версия грамматики из статьи, указанной вначале данной):

 ::=  ::= "if"  | "if"  "else" | "while"  | "print" | " <" < > ">" | ";" | ";" ::= "(" ")" ::= | "  ::= | "+" | "*" | "-" | "/"  ::= | |  ::= "a" | "b" | . | "z" ::= , < > ::= "0" | "1" | . | "9" 

Вся программа состоит из одного оператора. Этот один оператор может быть либо набором таких же операторов, заключенных в фигурные скобки, либо условным/циклическим оператором (if, if/else, while), либо оператором вывода числа (print), либо просто выражением.

Условные и циклические операторы содержат в себе выражение-условие (записанное в круглых скобках. Если значение выражения равно 0, то компилятор интерпретирует его как false, в ином случае — как true) и тело (являющееся полноценным оператором).

Обычные выражения заканчиваются точкой с запятой.

Выражения, используемые в условиях и операторе print представляют собой арифметические выражения, состоящие из доступных нам арифметических операций присваиваний (которые, как было указано раньше, возвращают новое значение переменной).

Арифметическое выражение состоит из арифметических действий над термами, которые в свою очередь являются именем переменной, целым числом или выражением в круглых скобках.

Определив грамматику, мы сможем перейти к созданию лексического анализатора.

Лексический анализатор

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

//compiler.h enum class tokensTypes < NUM, VAR, IF, ELSE, WHILE, LBRA, RBRA, LPAR, RPAR, ADD, SUB, MUL, DIV, LESS, ASSIG, SEMICOL, ENDFILE, ERROR, PRINT >; //compiler.cpp std::map compiler::specialSymbols < std::pair, std::pair', tokensTypes::RBRA>, std::pair<'(', tokensTypes::LPAR>, std::pair<')', tokensTypes::RPAR>, std::pair, std::pair, std::pair, std::pair, std::pair, std::pair, std::pair, >; std::map compiler::specialWords < std::pair, std::pair, std::pair, std::pair, >;

А также определим метод, который по строке и текущей позиции курсора в ней будет определять следующий токен:

// compiler.h class token < public: tokensTypes type; unsigned short value; char variable; token(tokensTypes type, int value = 0, char variable = 'a'); >; // compiler.cpp compiler::token compiler::getNexttoken() < if (nowPos == textLen) // Если файл прочитан, возвращаем конец файла return token(compiler::tokensTypes::ENDFILE); std::string str = ""; // В эту строку будет записываться текущий токен char now = text[nowPos++]; // Пропускаем все незначимые символы while ((now == ' ' || now == '\r' || now == '\n' || now == '\t')&& nowPos < textLen) now = text[nowPos++]; // И снова проверяем на конец файла if (nowPos == textLen) return token(compiler::tokensTypes::ENDFILE); // Пока не подойшли к символу, который однозначно говорит о конце токена, считываем while (!(now == ' ' || now == '\r' || now == '\n' || now == '\t')) < // Если в строке нет символов, проверяем на причастностьк специальным символам или числам if (str.size() == 0) < if (specialSymbols.count(now)) return token(specialSymbols[now]); else if (isdigit(now)) < do < str += now; now = text[nowPos++]; >while (isdigit(now)); nowPos--; break; > else str += now; > else < if (specialSymbols.count(now)) // Если был встречен специальный символ < // Также заканчиваем парсинг токена nowPos--; break; >str += now; > if (specialWords.count(str)) //Проверяем на нахождение в списке зарезервированных слов return token(specialWords[str]); if (nowPos == textLen) break; now = text[nowPos++]; > // Если в токене единственная строчная буква, то интерпретируем как имя переменной if (str.size() == 1 && str[0] >= 'a' && str[0] return token(compiler::tokensTypes::NUM, value); >

В основном методе компиляции заполняем вектор токенов:

//compiler.cpp bool compiler::compile(std::string& result) < token token = getNexttoken(); while (token.type != tokensTypes::ENDFILE) < if (token.type == tokensTypes::ERROR) // Если токен не распознан < result = "Lexical error"; // Возвращаем лексическую ошибку return false; >tokens.push_back(token); token = getNexttoken(); > tokens.push_back(token); >

На этом лексический анализатор можно считать завершенным.

Синтаксический анализ

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

// compiler.h enum class nodeTypes < CONST, VAR, ADD, SUB, MUL, DIV, LESSTHEN, SET, IF, IFELSE, WHILE, EMPTY, SEQ, EXPR, PROG, PRINT >; class node < public: nodeTypes type; int value; node* op1; node* op2; node* op3; node(nodeTypes type, int value = 0, node* op1 = nullptr, node* op2 = nullptr, node* op3 = nullptr); ~node(); >;

С данными вводными определим методы, преобразующие последовательность токенов в синтаксическое дерево (кода много, поэтому скрыл под спойлер):

// compiler.cpp bool compiler::parser::parse(std::vector& tokens, compiler::node& result) < int count = 0; compiler::node* node = new compiler::node(nodeTypes::EMPTY); bool res = parser::statement(tokens, count, node); if (count != tokens.size() - 1 || !res) return false; result = *node; return true; >bool compiler::parser::statement(std::vector& tokens, int& count, compiler::node*& node) < delete node; node = new compiler::node(nodeTypes::EMPTY); bool parsed = true; switch (tokens[count].type) < case compiler::tokensTypes::IF: count++; node->type = nodeTypes::IF; parsed = compiler::parser::parenExpr(tokens, count, node->op1); if (!parsed) return false; parsed = compiler::parser::statement(tokens, count, node->op2); if (!parsed) return false; if (tokens[count].type == tokensTypes::ELSE) < count++; node->type = nodeTypes::IFELSE; bool parsed = compiler::parser::statement(tokens, count, node->op3); if (!parsed) return false; > break; case compiler::tokensTypes::WHILE: count++; node->type = nodeTypes::WHILE; parsed = compiler::parser::parenExpr(tokens, count, node->op1); if (!parsed) return false; parsed = compiler::parser::statement(tokens, count, node->op2); if (!parsed) return false; break; case compiler::tokensTypes::SEMICOL: count++; break; case compiler::tokensTypes::LBRA: count++; while (tokens[count].type != tokensTypes::RBRA && count < tokens.size()) < node = new compiler::node(nodeTypes::SEQ, 0, node); bool parsed = compiler::parser::statement(tokens, count, node->op2); if (!parsed) return false; > count++; break; case compiler::tokensTypes::PRINT: count++; node->type = nodeTypes::PRINT; parsed = compiler::parser::parenExpr(tokens, count, node->op1); if (!parsed) return false; break; if (!parsed) return false; default: node->type = nodeTypes::EXPR; parsed = compiler::parser::expr(tokens, count, node->op1); if (tokens[count++].type != tokensTypes::SEMICOL) return false; if (!parsed) return false; > return true; > bool compiler::parser::parenExpr(std::vector& tokens, int& count, compiler::node*& node) < delete node; if (tokens[count].type != tokensTypes::LPAR) return false; count++; bool res = expr(tokens, count, node); if (tokens[count].type != tokensTypes::RPAR) return false; count++; return true; >bool compiler::parser::expr(std::vector& tokens, int& count, compiler::node*& node) < delete node; if (tokens[count].type != compiler::tokensTypes::VAR) return test(tokens, count, node); bool res = test(tokens, count, node); if (!res) return false; if (node->type == nodeTypes::VAR && tokens[count].type == tokensTypes::ASSIG) < node = new compiler::node(nodeTypes::SET, 0, node); count++; res = expr(tokens, count, node->op2); > return res; > bool compiler::parser::test(std::vector& tokens, int& count, compiler::node*& node) < delete node; bool res = arExpr(tokens, count, node); if (!res) return false; if (tokens[count].type == tokensTypes::LESS) < count++; node = new compiler::node(nodeTypes::LESSTHEN, 0, node); res = arExpr(tokens, count, node->op2); > return res; > bool compiler::parser::arExpr(std::vector& tokens, int& count, compiler::node*& node) < delete node; bool res = term(tokens, count, node); if (!res) return false; tokensTypes now = tokens[count].type; while (now == tokensTypes::ADD || now == tokensTypes::SUB || now == tokensTypes::MUL || now == tokensTypes::DIV) < nodeTypes nT = nodeTypes::EMPTY; switch (now) < case compiler::tokensTypes::ADD: nT = nodeTypes::ADD; break; case compiler::tokensTypes::SUB: nT = nodeTypes::SUB; break; case compiler::tokensTypes::MUL: nT = nodeTypes::MUL; break; case compiler::tokensTypes::DIV: nT = nodeTypes::DIV; break; >node = new compiler::node(nT, 0, node); count++; bool res = term(tokens, count, node->op2); if (!res) return false; now = tokens[count].type; > return true; > bool compiler::parser::term(std::vector& tokens, int& count, compiler::node*& node) < delete node; bool parsed; switch(tokens[count].type) < case tokensTypes::VAR: node = new compiler::node(nodeTypes::VAR, tokens[count].variable - 'a'); count++; break; case tokensTypes::NUM: node = new compiler::node(nodeTypes::CONST, tokens[count].value); count++; break; default: bool res = parenExpr(tokens, count, node); if (!res) return false; break; >return true; >

Здесь каждое выражение распознается в соответствии с правилами грамматики, определенными выше. Стоит остановиться подробнее на том, как определяются дочерние узлы. Их можно разбить на несколько групп:

  • Узлы типа CONST, VAR: не содержат дочерних узлов, но содержат значение, определяющее значение числа или позицию элемента в массиве
  • Узлы типа ADD, SUB, MUL, DIV, LESSTHEN: содержат по два дочерних узла, где op1 — левый операнд, а op2 — правый.
  • Узлы типа SET: содержат по два дочерних узла: op1 — узел типа VAR с переменной, которой присваивается значение, op2 — узел, собирающий значение, которое нужно присвоить переменной.
  • Узлы типа IF и WHILE: также включают в себя по два дочерних узла: op1 — условие, истинность которого проверяется, op2 — выражение, которое выполняется в случае истинности.
  • Узлы типа IFELSE: содержат три дочерних узла. Первые два такие же, как у узлов IF или WHILE, третий — выражения, которые выполняются в случае, если выражение ложно.
  • Узлы типа SEQ: содержит два дочерних узла. op1 — предыдущее выполняемое действие, op2 — текущее действие. (Возможно, стоило сделать в «правильном» порядке: узел хранит следующее действие, но в таком виде реализация несколько проще)
  • Узлы типа EXPR и PROG: содержат единственный дочерний узел op1, определяющий выражение
  • Узлы типа PRINT: содержит единственный дочерний узел, описывающий выводимое значение

При построении дерева проверяется текущий токен и на его основании принимается решение о типе текущего узла, а также осуществляется проверка на корректность синтаксиса.

На этом синтаксический анализ окончен: в случае некорректно составленного кода, осталось добавить его в метод компиляции кода:

// compiler.cpp bool compiler::compile(std::string& result) < token token = getNexttoken(); while (token.type != tokensTypes::ENDFILE) < if (token.type == tokensTypes::ERROR) < result = "Lexical error"; return false; >tokens.push_back(token); token = getNexttoken(); > tokens.push_back(token); compiler::node tree = compiler::node(nodeTypes::EMPTY); if (!compiler::parser::parse(tokens, tree)) return false; >

Генерация кода

На основании дерева, нам необходимо построить ассемблерный код. Для начала выделим фрагменты, которые будут в любой программе: начало программы, макрос для вывода чисел в десятичном виде и выход из программы:

const std::string compiler::linker::programsStart = R"STR(ASSUME CS:CODE, DS:DATA DATA SEGMENT vars dw 26 dup (0) DATA ENDS; CODE SEGMENT PRINT MACRO local DIVCYC, PRINTNUM; push ax; push bx; push cx; push dx; mov bx, 10; mov cx, 0; DIVCYC: mov dx, 0; div bx; push dx; inc cx; cmp ax, 0; jne DIVCYC; PRINTNUM: pop dx; add dl, '0'; mov ah, 02h; int 21h; dec cx; cmp cx, 0; jne PRINTNUM; mov dl, 0dh; mov ah, 02h; int 21h; mov dl, 0ah; mov ah, 02h; int 21h; pop dx; pop cx; pop bx; pop ax; ENDM; begin: lea si, vars; )STR"; const std::string compiler::linker::programsEnd = R"STR( mov ah, 4Ch; int 21h; CODE ENDS; end begin)STR";

Из интересного в данном коде: выделение 26 слов (участков памяти по два байта) под переменные, а также вывод числа с помощью макроса PRINT (он выводит содержимое регистра AX, сохраняя состояние регистров в стеке перед выводом и восстанавливая его после, а также записывает в стек цифры числа, после чего выводит их одну за другой).

Следующим шагом будет определение используемых регистров для осуществления операций. В данном коде основным регистром, содержащим и обрабатывающим данные является регистр AX (в нем всегда находится левый операнд и результат операции), в качестве регистра, хранящего правый операнд, используется регистр BX.

При сборке ассемблерного кода вначале используется строка programsStart, затем к ней прибавляются операции кода, а завершается это строкой programsEnd.

Рассмотрим трансляцию каждого типа узлов дерева в ассемблерный код:

std::string compiler::linker::compileNode(compiler::node* block, int& labelCount) < std::string result = ""; int lCount1, lCount2, firstLabelNum, secondLabelNum, thirdLabelNum; switch (block->type) < case nodeTypes::PROG: result += compileNode(block->op1, labelCount); break; case nodeTypes::PRINT: result += compileNode(block->op1, labelCount); result += " PRINT;\n"; break; case nodeTypes::VAR: result += " mov ax, [si + " + std::to_string(block->value * 2) + "];\n"; break; case nodeTypes::CONST: result += " mov ax, " + std::to_string(block->value) + ";\n"; break; case nodeTypes::ADD: result += compileNode(block->op1, labelCount); result += " push ax;\n"; result += compileNode(block->op2, labelCount); result += " mov bx, ax;\n"; result += " pop ax;\n"; result += " add ax, bx;\n"; break; case nodeTypes::SUB: result += compileNode(block->op1, labelCount); result += " push ax;\n"; result += compileNode(block->op2, labelCount); result += " mov bx, ax;\n"; result += " pop ax;\n"; result += " sub ax, bx;\n"; break; case nodeTypes::MUL: result += compileNode(block->op1, labelCount); result += " push ax;\n"; result += compileNode(block->op2, labelCount); result += " mov bx, ax;\n"; result += " pop ax;\n"; result += " mul bx;\n"; break; case nodeTypes::DIV: result += compileNode(block->op1, labelCount); result += " push ax;\n"; result += compileNode(block->op2, labelCount); result += " mov bx, ax;\n"; result += " pop ax;\n"; result += " xor dx, dx;\n"; result += " div bx;\n"; break; case nodeTypes::SET: result += compileNode(block->op2, labelCount); result += " mov [si + " + std::to_string(block->op1->value * 2) + "], ax;\n"; break; case nodeTypes::EXPR: result += compileNode(block->op1, labelCount) + '\n'; break; case nodeTypes::LESSTHEN: result += compileNode(block->op1, labelCount); result += " push ax;\n"; result += compileNode(block->op2, labelCount); result += " mov bx, ax;\n"; result += " pop ax;\n"; result += " cmp ax, bx;\n"; result += " jae LBL" + std::to_string(labelCount++) + ";\n"; result += " mov ax, 1;\n"; result += " jmp LBL" + std::to_string(labelCount++) + ";\n"; result += " LBL" + std::to_string(labelCount - 2) + ":\n"; result += " mov ax, 0;\n"; result += " LBL" + std::to_string(labelCount - 1) + ": nop\n"; break; case nodeTypes::IF: result += compileNode(block->op1, labelCount); result += " cmp ax, 0;\n"; lCount1 = labelCount; result += " jne LBL" + std::to_string(labelCount++) + ";\n"; lCount2 = labelCount; result += " jmp LBL" + std::to_string(labelCount++) + ";\n"; result += " LBL" + std::to_string(lCount1) + ": nop\n"; result += compileNode(block->op2, labelCount); result += " LBL" + std::to_string(lCount2) + ": nop\n"; break; case nodeTypes::SEQ: result += compileNode(block->op1, labelCount); result += compileNode(block->op2, labelCount); break; case nodeTypes::IFELSE: result += compileNode(block->op1, labelCount); result += " cmp ax, 0;\n"; firstLabelNum = labelCount; result += " je LBL" + std::to_string(labelCount++) + ";\n"; result += compileNode(block->op2, labelCount); secondLabelNum = labelCount; result += " jmp LBL" + std::to_string(labelCount++) + ";\n"; result += " LBL" + std::to_string(firstLabelNum) + ": nop\n"; result += compileNode(block->op3, labelCount); result += " LBL" + std::to_string(secondLabelNum) + ": nop\n"; break; case nodeTypes::WHILE: secondLabelNum = labelCount; result += " jmp LBL" + std::to_string(labelCount++) + "; \n"; firstLabelNum = labelCount; result += " LBL" + std::to_string(labelCount++) + ": nop\n"; result += compileNode(block->op2, labelCount); result += " LBL" + std::to_string(secondLabelNum) + ": nop\n"; result += compileNode(block->op1, labelCount); result += " cmp ax, 0;\n"; thirdLabelNum = labelCount; result += " je LBL" + std::to_string(thirdLabelNum) + "\n"; result += " jmp LBL" + std::to_string(firstLabelNum) + "\n"; result += " LBL" + std::to_string(thirdLabelNum) + ": nop\n"; break; default: break; > return result; >

В данном коде стоит обратить внимание на следующее:

  1. Для операций, в которых необходимо участие двух операндов, вычисляется сначала левый, который находится в регистре AX, после чего он отправляется в стек, а затем на его месте формируется второй операнд. Перед осуществлением операции правый операнд перемещается в регистр BX, а левый — в AX, после чего результат остается в AX.
  2. Адреса ячеек в памяти частично вычисляются на этапе компиляции: умножение на сдвиг происходит в компиляторе, потому что этот сдвиг известен заранее.
  3. Оператор LESSTHEN оставляет в регистре AX 1 в случае истины и 0 в ином случае.
  4. Операторы IF, IFELSE и WHERE сравнивают дополнительно сравнивают число с 0 (см. пункт 3 и требования к языку).
  5. Вместо условных переходов на неизвестное расстояние используется отрицание условия для перехода через один оператор, а переход на неизвестное расстояние осуществляется с помощью оператора jmp (чтобы избежать ошибки «Relative jump out of range by xxxxh bytes».

И осталось все это добавить в метод компиляции:

// compiler.css std::string compiler::linker::compile() < std::string program = ""; program += programsStart; int a = 0; program += compileNode(tree, a); program += programsEnd; return program; >bool compiler::compile(std::string& result) < token token = getNexttoken(); while (token.type != tokensTypes::ENDFILE) < if (token.type == tokensTypes::ERROR) < result = "Lexical error"; return false; >tokens.push_back(token); token = getNexttoken(); > tokens.push_back(token); compiler::node tree = compiler::node(nodeTypes::EMPTY); if (!compiler::parser::parse(tokens, tree)) return false; compiler:linker linker = compiler::linker(&tree); result = linker.compile(); return true; >

Остается лишь проверить работоспособность данного компилятора.

Проверка работоспособности компилятора

Отставить легкие проверки! Только хардкор. Для проверки будут решены задачи поиска обратного числа в кольце простых чисел (привет, теорема Эйлера), а также алгоритм нахождения НОД двух чисел.

Для решения первой задачи используется следующий код на «нашем языке»:

#include #include "compiler.h" int main() < char* data = new char[166]; memcpy(data, "s = s / 2; b = b * b; b = b - (b / m * m);> print(c);>", 166); compiler comp = compiler(data, 166); std::string result; comp.compile(result); std::cout

Как можно заметить, строка с кодом программы написана без какого-либо форматирования, это сделано для проверки корректности распознавания кода даже в условиях слабого форматирования. Посмотрим на ассемблерный код, сгенерированный нашим компилятором:

ASSUME CS:CODE, DS:DATA DATA SEGMENT vars dw 26 dup (0) DATA ENDS; CODE SEGMENT PRINT MACRO local DIVCYC, PRINTNUM; push ax; push bx; push cx; push dx; mov bx, 10; mov cx, 0; DIVCYC: mov dx, 0; div bx; push dx; inc cx; cmp ax, 0; jne DIVCYC; PRINTNUM: pop dx; add dl, '0'; mov ah, 02h; int 21h; dec cx; cmp cx, 0; jne PRINTNUM; mov dl, 0dh; mov ah, 02h; int 21h; mov dl, 0ah; mov ah, 02h; int 21h; pop dx; pop cx; pop bx; pop ax; ENDM; begin: lea si, vars; mov ax, 6; mov [si + 0], ax; mov ax, 283; mov [si + 24], ax; mov ax, [si + 24]; push ax; mov ax, 2; mov bx, ax; pop ax; sub ax, bx; mov [si + 36], ax; mov ax, [si + 0]; mov [si + 2], ax; mov ax, 1; mov [si + 4], ax; jmp LBL0; LBL1: nop mov ax, 0; push ax; mov ax, [si + 36]; push ax; mov ax, [si + 36]; push ax; mov ax, 2; mov bx, ax; pop ax; xor dx, dx; div bx; push ax; mov ax, 2; mov bx, ax; pop ax; mul bx; mov bx, ax; pop ax; sub ax, bx; mov bx, ax; pop ax; cmp ax, bx; jae LBL2; mov ax, 1; jmp LBL3; LBL2: mov ax, 0; LBL3: nop cmp ax, 0; jne LBL4; jmp LBL5; LBL4: nop mov ax, [si + 4]; push ax; mov ax, [si + 2]; mov bx, ax; pop ax; mul bx; mov [si + 4], ax; mov ax, [si + 4]; push ax; mov ax, [si + 4]; push ax; mov ax, [si + 24]; mov bx, ax; pop ax; xor dx, dx; div bx; push ax; mov ax, [si + 24]; mov bx, ax; pop ax; mul bx; mov bx, ax; pop ax; sub ax, bx; mov [si + 4], ax; LBL5: nop mov ax, [si + 36]; push ax; mov ax, 2; mov bx, ax; pop ax; xor dx, dx; div bx; mov [si + 36], ax; mov ax, [si + 2]; push ax; mov ax, [si + 2]; mov bx, ax; pop ax; mul bx; mov [si + 2], ax; mov ax, [si + 2]; push ax; mov ax, [si + 2]; push ax; mov ax, [si + 24]; mov bx, ax; pop ax; xor dx, dx; div bx; push ax; mov ax, [si + 24]; mov bx, ax; pop ax; mul bx; mov bx, ax; pop ax; sub ax, bx; mov [si + 2], ax; LBL0: nop mov ax, 0; push ax; mov ax, [si + 36]; mov bx, ax; pop ax; cmp ax, bx; jae LBL6; mov ax, 1; jmp LBL7; LBL6: mov ax, 0; LBL7: nop cmp ax, 0; je LBL8 jmp LBL1 LBL8: nop mov ax, [si + 4]; PRINT; mov ah, 4Ch; int 21h; CODE ENDS; end begin

Получилось много и не очень красиво (а что ждать от взятия остатка через деление, умножение и вычитание?), сравним результаты работы программы и результата с первого попавшегося сайта:

Как видим, результаты сошлись. Перейдем к алгоритму Евклида. Код на «нашем» языке для него будет следующим:

#include #include "compiler.h" int main() < char* data = new char[85]; memcpy(data, "print(a);>", 85); compiler comp = compiler(data, 85); std::string result; comp.compile(result); std::cout

Получаем следующий ассемблерный код:

ASSUME CS:CODE, DS:DATA DATA SEGMENT vars dw 26 dup (0) DATA ENDS; CODE SEGMENT PRINT MACRO local DIVCYC, PRINTNUM; push ax; push bx; push cx; push dx; mov bx, 10; mov cx, 0; DIVCYC: mov dx, 0; div bx; push dx; inc cx; cmp ax, 0; jne DIVCYC; PRINTNUM: pop dx; add dl, '0'; mov ah, 02h; int 21h; dec cx; cmp cx, 0; jne PRINTNUM; mov dl, 0dh; mov ah, 02h; int 21h; mov dl, 0ah; mov ah, 02h; int 21h; pop dx; pop cx; pop bx; pop ax; ENDM; begin: lea si, vars; mov ax, 11004; mov [si + 0], ax; mov ax, 10087; mov [si + 2], ax; jmp LBL0; LBL1: nop mov ax, [si + 0]; push ax; mov ax, [si + 0]; push ax; mov ax, [si + 2]; mov bx, ax; pop ax; xor dx, dx; div bx; push ax; mov ax, [si + 2]; mov bx, ax; pop ax; mul bx; mov bx, ax; pop ax; sub ax, bx; mov [si + 4], ax; mov ax, [si + 2]; mov [si + 0], ax; mov ax, [si + 4]; mov [si + 2], ax; LBL0: nop mov ax, 0; push ax; mov ax, [si + 2]; mov bx, ax; pop ax; cmp ax, bx; jae LBL2; mov ax, 1; jmp LBL3; LBL2: mov ax, 0; LBL3: nop cmp ax, 0; je LBL4 jmp LBL1 LBL4: nop mov ax, [si + 0]; PRINT; mov ah, 4Ch; int 21h; CODE ENDS; end begin

Проверим результат работы кода:

Как видно, все сходится.

Ссылка на репозиторий

Полный исходный код программы доступен в репозитории.

Пишем примитивный и никому не нужный компилятор

Я считаю, что каждый программист должен написать свой компилятор.

Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.

В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.

Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.

Да, компилятор совершенно нагло основан на Tiny-С.

Грамматика

Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
Уметь он будет очень мало:

— единственный тип данных — int
— все переменные — глобальные. Всего есть 26 переменных (a-z)
— из математических операций поддерживаются только «+» и «-»
— единственный оператор сравнения — это » — из конструкций языка — условные операторы if, if/else, while, do/while

Все. Никаких массивов, функций, структур. Вот какая грамматика получается у нашего языка:

 ::=  ::= "if"  | "if"  "else" | "while"  | "do" "while" | " <" < > ">" | ";" | ";" ::= "(" ")" ::= | "  ::= | "+" | "-"  ::= | |  ::= "a" | "b" | . | "z" ::= , < > ::= "0" | "1" | . | "9"

Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.

Программа — это один оператор (statement).
Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»).
Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
Выражения — это либо сумма, либо присваивание переменной значения.
Здесь сумма — это последовательность сложений-вычитаний термов.
Терм — это число, переменная или выражение в скобках.
Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.

Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.

Лексический анализатор

На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.

Итак, наш лексический анализатор должен узнавать следующие токены:

— числа
— идентификаторы-переменные
— ключевые слова: if, else, while, do
— символы +, -, , (, ),;
— конец файла

Вот как выглядит его исходный код:

class Lexer: NUM, ID, IF, ELSE, WHILE, DO, LBRA, RBRA, LPAR, RPAR, PLUS, MINUS, LESS, \ EQUAL, SEMICOLON, EOF = range(16) # специальные символы языка SYMBOLS = < '': RBRA, '=': EQUAL, ';': SEMICOLON, '(': LPAR, ')': RPAR, '+': PLUS, '-': MINUS, ' # ключевые слова WORDS = < 'if': IF, 'else': ELSE, 'do': DO, 'while': WHILE ># текущий символ, считанный из исходника ch = ' ' # допустим, первый символ - это пробел def error(self, msg): print 'Lexer error: ', msg sys.exit(1) def getc(self): self.ch = sys.stdin.read(1) def next_tok(self): self.value = None self.sym = None while self.sym == None: if len(self.ch) == 0: self.sym = Lexer.EOF elif self.ch.isspace(): self.getc() elif self.ch in Lexer.SYMBOLS: self.sym = Lexer.SYMBOLS[self.ch] self.getc() elif self.ch.isdigit(): intval = 0 while self.ch.isdigit(): intval = intval * 10 + int(self.ch) self.getc() self.value = intval self.sym = Lexer.NUM elif self.ch.isalpha(): ident = '' while self.ch.isalpha(): ident = ident + self.ch.lower() self.getc() if ident in Lexer.WORDS: self.sym = Lexer.WORDS[ident] elif len(ident) == 1: self.sym = Lexer.ID self.value = ord(ident) - ord('a') else: self.error('Unknown identifier: ' + ident) else: self.error('Unexpected symbol: ' + self.ch) 

В методе next_tok() анализатор получает следующий токен. Тип токена можно получить из атрибута sym, а его значение (если это переменная или число) — из атрибута value.

Анализатор игнорирует пробелы, проверяет, является ли текущий символ специальным символом языка, если нет — проверяет, является ли он числом или идентификатором. Т.е. встретив цифру 1, анализатор продолжит вычитывать символы, пока не встретит не-числовой символ. Аналогично проверяются идентификаторы (там вместо чисел буквы).

Парсер

Это, наверное, самый сложный компонент нашего компилятора. Его задача, используя токены, полученные от лексического анализатора, сформировать своего рода дерево, в котором иерархия и связи отображают структуру кода. Например:

"if (a < 0) a = 5;" IF +-LESS | +-VAR(a) | +-NUM(0) +-SET +-VAR(a) +-NUM(5)

Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.

Для описания узлов введем класс Node. Вот код класса парсера и класса Node:

class Node: def __init__(self, kind, value = None, op1 = None, op2 = None, op3 = None): self.kind = kind self.value = value self.op1 = op1 self.op2 = op2 self.op3 = op3 class Parser: VAR, CONST, ADD, SUB, LT, SET, IF1, IF2, WHILE, DO, EMPTY, SEQ, EXPR, PROG = range(14) def __init__(self, lexer): self.lexer = lexer def error(self, msg): print 'Parser error:', msg sys.exit(1) def term(self): if self.lexer.sym == Lexer.ID: n = Node(Parser.VAR, self.lexer.value) self.lexer.next_tok() return n elif self.lexer.sym == Lexer.NUM: n = Node(Parser.CONST, self.lexer.value) self.lexer.next_tok() return n else: return self.paren_expr() def summa(self): n = self.term() while self.lexer.sym == Lexer.PLUS or self.lexer.sym == Lexer.MINUS: if self.lexer.sym == Lexer.PLUS: kind = Parser.ADD else: kind = Parser.SUB self.lexer.next_tok() n = Node(kind, op1 = n, op2 = self.term()) return n def test(self): n = self.summa() if self.lexer.sym == Lexer.LESS: self.lexer.next_tok() n = Node(Parser.LT, op1 = n, op2 = self.summa()) return n def expr(self): if self.lexer.sym != Lexer.ID: return self.test() n = self.test() if n.kind == Parser.VAR and self.lexer.sym == Lexer.EQUAL: self.lexer.next_tok() n = Node(Parser.SET, op1 = n, op2 = self.expr()) return n def paren_expr(self): if self.lexer.sym != Lexer.LPAR: self.error('"(" expected') self.lexer.next_tok() n = self.expr() if self.lexer.sym != Lexer.RPAR: self.error('")" expected') self.lexer.next_tok() return n def statement(self): if self.lexer.sym == Lexer.IF: n = Node(Parser.IF1) self.lexer.next_tok() n.op1 = self.paren_expr() n.op2 = self.statement() if self.lexer.sym == Lexer.ELSE: n.kind = Parser.IF2 self.lexer.next_tok() n.op3 = self.statement() elif self.lexer.sym == Lexer.WHILE: n = Node(Parser.WHILE) self.lexer.next_tok() n.op1 = self.paren_expr() n.op2 = self.statement(); elif self.lexer.sym == Lexer.DO: n = Node(Parser.DO) self.lexer.next_tok() n.op1 = self.statement() if self.lexer.sym != Lexer.WHILE: self.error('"while" expected') self.lexer.next_tok() n.op2 = self.paren_expr() if self.lexer.sym != Lexer.SEMICOLON: self.error('";" expected') elif self.lexer.sym == Lexer.SEMICOLON: n = Node(Parser.EMPTY) self.lexer.next_tok() elif self.lexer.sym == Lexer.LBRA: n = Node(Parser.EMPTY) self.lexer.next_tok() while self.lexer.sym != Lexer.RBRA: n = Node(Parser.SEQ, op1 = n, op2 = self.statement()) self.lexer.next_tok() else: n = Node(Parser.EXPR, op1 = self.expr()) if self.lexer.sym != Lexer.SEMICOLON: self.error('";" expected') self.lexer.next_tok() return n def parse(self): self.lexer.next_tok() node = Node(Parser.PROG, op1 = self.statement()) if (self.lexer.sym != Lexer.EOF): self.error("Invalid statement syntax") return node 

Этот парсер работает рекурсивно, начиная с метода parse().
Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.

Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.

При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.

Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.

Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.

На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.

Машинный код

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

FETCH x - положить на стек значение переменной x STORE x - сохранить в переменной x значение с вершины стека PUSH n - положить число n на вершину стека POP - удалить число с вершины стека ADD - сложить два числа на вершине стека SUB - вычесть два числа на вершине стека LT - сравнить два числа с вершины стека (a < b). Результат - 0 или 1 JZ a - если на вершине стека 0 - перейти к адресу a. JNZ a - если на вершине стека не 0 - перейти к адресу a. JMP a - перейти к адресу a HALT - завершить работу

Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:

PUSH 2 STORE 0 PUSH 5 STORE 1

Код виртуальной машины очень простой. Он весь описывается в методе run:

IFETCH, ISTORE, IPUSH, IPOP, IADD, ISUB, ILT, JZ, JNZ, JMP, HALT = range(11) class VirtualMachine: def run(self, program): var = [0 for i in xrange(26)] stack = [] pc = 0 while True: op = program[pc] if pc < len(program) - 1: arg = program[pc+1] if op == IFETCH: stack.append(var[arg]); pc += 2 elif op == ISTORE: var[arg] = stack.pop(); pc += 2 elif op == IPUSH: stack.append(arg); pc += 2 elif op == IPOP: stack.append(arg); stack.pop(); pc += 1 elif op == IADD: stack[-2] += stack[-1]; stack.pop(); pc += 1 elif op == ISUB: stack[-2] -= stack[-1]; stack.pop(); pc += 1 elif op == ILT: if stack[-2] < stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop(); pc += 1 elif op == JZ: if stack.pop() == 0: pc = arg else: pc += 2 elif op == JNZ: if stack.pop() != 0: pc = arg else: pc += 2 elif op == JMP: pc = arg; elif op == HALT: break print 'Execution finished.' for i in xrange(26): if var[i] != 0: print '%c = %d' % (chr(i+ord('a')), var[i]) 

Осталось написать собственно компилятор — генератор кода.

Компилятор

Венец нашего творения. Вот его исходный код:

class Compiler: program = [] pc = 0 def gen(self, command): self.program.append(command) self.pc = self.pc + 1 def compile(self, node): if node.kind == Parser.VAR: self.gen(IFETCH) self.gen(node.value) elif node.kind == Parser.CONST: self.gen(IPUSH) self.gen(node.value) elif node.kind == Parser.ADD: self.compile(node.op1) self.compile(node.op2) self.gen(IADD) elif node.kind == Parser.SUB: self.compile(node.op1) self.compile(node.op2) self.gen(ISUB) elif node.kind == Parser.LT: self.compile(node.op1) self.compile(node.op2) self.gen(ILT) elif node.kind == Parser.SET: self.compile(node.op2) self.gen(ISTORE) self.gen(node.op1.value) elif node.kind == Parser.IF1: self.compile(node.op1) self.gen(JZ); addr = self.pc; self.gen(0); self.compile(node.op2) self.program[addr] = self.pc elif node.kind == Parser.IF2: self.compile(node.op1) self.gen(JZ); addr1 = self.pc; self.gen(0) self.compile(node.op2) self.gen(JMP); addr2 = self.pc; self.gen(0) self.program[addr1] = self.pc self.compile(node.op3) self.program[addr2] = self.pc elif node.kind == Parser.WHILE: addr1 = self.pc self.compile(node.op1) self.gen(JZ); addr2 = self.pc; self.gen(0) self.compile(node.op2) self.gen(JMP); self.gen(addr1); self.program[addr2] = self.pc elif node.kind == Parser.DO: addr = self.pc self.compile(node.op1) self.compile(node.op2) self.gen(JNZ); self.gen(addr); elif node.kind == Parser.SEQ: self.compile(node.op1) self.compile(node.op2) elif node.kind == Parser.EXPR: self.compile(node.op1); self.gen(IPOP) elif node.kind == Parser.PROG: self.compile(node.op1); self.gen(HALT) return self.program 

Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.

Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.

Тестируем

Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):

echo " i = 3;" | ./cc.py echo " < a=3; b=5; >" | ./cc.py echo " < a = 1; b = 2; c = a + b; >" | ./cc.py echo " < a = 5; b = 2; c = a - b; >" | ./cc.py echo " < a = 5; b = 2; c = b < a; >" | ./cc.py echo " < a = 5; if (a < 10) a = 33; >" | ./cc.py echo " < a = 5; if (10 < a) a = 33; else < a = 1; b = 2; >>" | ./cc.py echo " < a = 10; do < a = a - 2;>while (3 < a); >" | ./cc.py echo " < a = 1; b = 5; while (a < b) < a = a + 3; >>" | ./cc.py 

Ответы машина выдавала вроде бы правильные.

Что дальше?

Применений у нашего компилятора нет. Зато получен опыт.
Я надеюсь, вам еще больше хочется написать свой компилятор. Тогда лучше начинать с языков с простым синтаксисом, напр. TinyBasic или PL/0.
Если вам хочется почитать исходники других компиляторов, то советую обратить внимание на работу Белларда (otcc), tinyc, tcc, smallC, lcc.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *