Как написать простейший компилятор
Лучший способ понять как работает компилятор — написать свой собственный. В этом поможет этот краткий, но исчерпывающий гайд.
Введение
Стандартный компилятор осуществляет следующие шаги:
В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз. Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).
После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.
Запомните основные моменты
Компилятор должен быть:
Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.
Читайте книги!
Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.
Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.
Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.
Хорошо определите свой язык
Вы можете использовать любую нотацию, но будьте уверены, что имеете полное и последовательное описание языка. Оно включает в себя как синтаксис, так и семантику.
Используйте свой любимый язык
Это совершенно нормально — писать компилятор на Pyhton, Ruby или любом другом языке, который вам нравится. Используйте простые алгоритмы, принцип которых вы хорошо понимаете. Первый ваш компилятор вовсе не обязан быть быстрым, или эффективным, или обладать кучей фич. Все, что от него требуется — работать достаточно правильно и легко поддаваться переработкам.
Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.
Приготовьтесь к написанию множества тестов
Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.
Регулярно прогоняйте все тесты. Чините некорректные тесты. Будет очень обидно остаться у разбитого корыта с плохо определенным языком, который не способен принять валидный код.
Сделайте хороший парсер
Парсеров существует огромное количество, выбирайте любой. Можно написать свой собственный, но это сработает только в том случае, если синтаксис вашего языка примитивен до маразма.
Парсер должен выявлять синтаксически ошибки и сообщать о них. Пишите много тестов, как позитивных, так и негативных. Переиспользуйте написанный код для определения языка.
На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».
Напишите семантический валидатор
Вполне вероятно, что ваш язык допускает синтаксически правильные конструкции, не имеющие смысла в некоторых контекстах. Примером может служить повторное объявление одной и той же переменной или пропуск параметра неправильного типа. Валидатор призван выявлять ошибки такого рода.
Также зона его ответственности охватывает разрешение зависимостей с другими модулями, написанными на вашем языке, загрузкой этих модулей и использовании их в процессе валидации. Например, именно на этом этапе проверяется соответствие количества параметров, поступающих на вход функции из подключаемого модуля.
Еще раз, пишите и запускайте много тестов. Тривиальные случаи также обязательны к рассмотрению, как и сложные.
Генерируйте код
Воспользуйтесь простейшими техниками, которые вы знаете. Чаще всего допустимо непосредственно переводить языковую конструкцию (например, условны й оператор) в слабо параметризированный шаблон кода.
Забудьте об эффективности и сосредоточьтесь только на правильности.
Настройте платформо-независимую низкоуровневую виртуальную машину
Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.
Забудьте об оптимизации
Оптимизация — это сложно. И почти всегда она бывает преждевременной. Генерируйте неэффективный, но рабочий код. Реализуйте весь язык прежде чем приступите к оптимизации.
Конечно, некоторая простая оптимизация вполне уместна на начальном этапе. Но старайтесь избегать излишних хитростей, пока ваш компилятор не будет достаточно стабилен.
Введение
Здравствуй, уважаемый хабраюзер.Я хотел бы тебе представить материал о практическом создании компилятора, который будет транслировать код, написанный на языке Cool, в код виртуальной машины CIL (Common Intermediate Language) под платформу .NET.Данный материал я решил разбить на две части из-за лени все сразу это описывать
В первой части будет описан процесс написания грамматики с учетом приоритетов операторов в среде ANTLR, а также генерации лексера и парсера под язык C#. Также в ней будут рассмотрены подводные камни, которые встретились у меня на пути. Таким образом я постараюсь хоть кому-нибудь сэкономить время (может быть для себя в будущем).
Во второй же части будет описан процесс построения семантического анализатора кода, генерации кода и самопальной никому не нужной оптимизации кода. Также будет описано, как сделать красивый интерфейс с блекджеком и шлюхами с подсветкой синтаксиса и сворачиванием блоков, как в современных IDE. В конце второй части я, конечно же, выложу все исходники моего солюшена и расскажу о дальнейшей улучшении архитектуры и кода, во всяком случае как это представляется мне.
Предупреждение: перед разработкой данного компилятора я практически не изучал никакой тематической литературы. Всё обошлось чтением нескольких интересующих меня статей, просмотром видеоуроков по ANTLR на официально сайте и разговорами с «шарящими» одногруппниками. Так что разработанное ПО является УГ далеко не идеальным.
Описание языка Cool
Здесь у классов A и B наиболее близким общим предком является класс D.
Оператор case подобен оператору if, примененному несколько раз.
В конструкции while всегда возвращается void (если конечно цикл не зацикливается).
Такая конструкция < ;… ; >возвращает объект выражения exprn, т.е. последнего выражения.
Функции здесь могут вызываться не только у класса и его предка (виртуальные функции), но и вообще у любых предков данного класса. Это можно осуществить, использовав оператор ‘@’. В качестве примера рассмотрим иерархию классов на рисунке 1. Пусть класс E имеет функцию func(), все остальные потомки переопределяют ее по своему. Тогда, если мы имеет экземпляр объекта A и хотим вызывать функцию func из класса D, нужно использовать следующий синтаксис:
Ключевое слово SELF_TYPE используется как синоним класса, в котором описывается определенная функция. Идентификатор self же является указатель на текущий класс (т.е. this в других языка).
Локальных переменные вводятся в языке Cool с помощью оператора let и они могут использоваться только в рамках данного блока let.
void — аналог null, признак того, что объект не создан.
Думаю все остальные операторы в пояснениях не нуждаются, а если не понятно, то вы можете изучить мануал по данному диалекту языка Cool по ссылке, указанной в конце статьи.
Написание грамматики языка Cool в ANTLRWorks
Итак, исходная грамматика задана в следующей форме:
Здесь используется StringBuilder для того, чтобы обработка строк была эффективной.В принципе, для оптимизации лексера допустимы и другие вкрапления такого кода, но не для всех правил.Для того, чтобы в C# коде лексера и парсера указать пространства имен (например System.Text для StringBuilder), используются следующие конструкции (здесь также отключаются некоторые «ненужные» предупреждения):
После того, как мы составили грамматику в ANTLRWorks, нужно сгенерировать C# код лексера и парсера (спасибо, кэп).
Использование сгенерированного лексера в C# коде
Получение списка всех токенов в сгенерированном C# коде выглядит не очень тривиально (хоть это и не всегда нужно):
CoolTokens.Dictionary должен генерироваться следующим образом:fileName — Путь к файлу CoolCompiler.tokens
Использование сгенерированного парсера в C# коде
Заключение
Напоследок я бы хотел задать один вопрос хабрасообществу, ответ на который мне найти не удалось:
Для C# лексера у меня всегда генерируется такой код для исключения NoViableAltException, причем этот throw невозможно никак перехватить:
Как мне написать файл грамматики, чтобы в этой строчке не просто стояло throw, а вызывалось например мое исключение или вообще лексер продолжал работу? А то приходится при каждой генерации C# кода исправлять эту строчку.Примечание: манипуляции с @rulecatch в ANTLR ни к чему не привели.
Было бы приятно, если кто-нибудь разобрался с этой проблемой и написал ответ в комментариях.
Как быть* компилятором — создание компилятора на JavaScript
Привет, Хабр! Представляю вашему вниманию перевод статьи «How to be* a compiler — make a compiler with JavaScript» автора Mariko Kosaka.
*Все верно! Быть компилятором — это здорово!
Дело было одним замечательным воскресеным днем в Бушвике, Бруклин. В моем местном книжном магазине я наткнулась на книгу Джона Маэда “Design by Numbers”. Это была пошаговая инструкция по изучению DBN — языка программирования, созданного в конце 90-х в MIT Media Lab для визуального представления концепций компьютерного программирования.
Приведенные на первом рисунке три строки кода рисуют черную линию на белой бумаге (пример взят отсюда). Для отрисовки более сложных фигур, таких как, например, квадрат, требуется нарисовать просто больше линий (второй рисунок).
Я сразу подумала, что в 2016 году, это могло бы стать интересным проектом — создавать SVG из DBN без установки Java для выполнения исходного DBN кода.
Я решила, что для этого мне нужно написать компилятор из DBN в SVG, таким образом мой квест написания компилятора начался. Создание компилятора звучит как довольно сложный научный процесс, но я даже никогда не писала обход графа на интервью… Смогу ли я написать компилятор?
Попробуем сначала сами стать компилятором
Компилятор — это механизм, который берет кусок кода и преобразует его во что-то другое. Давайте скомпилируем простой DBN код в физический рисунок.
Возьмем три DBN команды: Paper задает цвет бумаги, Pen задает цвет кисти и Line рисует линию. Цвет 100 равнозначен 100%-ному черному цвету, что есть rgb(0%, 0%, 0%) в CSS. Изображения созданные в DBN всегда находятся в градации серого. В DBN бумага всегда 100×100, ширина линии всегда 1, а сама линия задается (x, y) координатами, отсчет ведется от нижнего левого угла изображения.
Давайте остановимся на этом и попробуем сами побыть компилятором. Возьмите бумагу, ручку и попробуйте скомпилировать следующий код в рисунок.
Вы нарисовали горизонтальную линию от левого края листа до правого, и она находится в центре по вертикали? Поздравляю! Вы только что стали компилятором.
Как же работает компилятор?
Давайте разберемся, что происходило в нашей голове, пока мы были компилятором.
1. Лексический анализ (Tokenization)
Первое, что мы сделали, разбили исходный код на слова по пробелам. В процессе мы условно определили примитивные типы для каждого токена, такие как “слово” или “число”.
2. Синтаксический анализ (Parsing)
Как только мы разбили фрагмент текста на токены, мы прошли по каждому из них и попытались найти взаимосвязь между ними.
В данном случае мы сгруппировали вместе набор чисел и относящееся к ним слово. Сделав это, мы стали различать определенные структуры кода.
3. Трансформация (Transformation)
После синтаксического анализа, мы трансформировали полученные структуры во что-то более подходящее под конечный результат. В нашем случае мы собираемся нарисовать изображение, значит нам нужно преобразовать наши структуры в пошаговую инструкцию, понятную человеку.
4. Генерация кода (Code Generation)
На этом этапе мы просто следуем инструкциям, которые мы сделали на предыдущем шаге подготовки к рисованию.
Именно этим занимается компилятор!
Давайте напишем компилятор
Теперь, когда мы знаем, как работает компилятор, давайте напишем еще один, но уже с использованием JavaScript. Этот компилятор будет брать DBN код и преобразовывать его в SVG.
1. Lexer function
Точно так же, как мы можем разделить предложение “У меня есть ручка” на слова [У, меня, есть, ручка], лексический анализатор может разбить представленный в виде строки код на определенные осмысленные части (токены). В DBN все токены разделены пробелами и классифицируются как “слово” или “число”.
2. Parser function
Парсер проходит по каждому токену, собирает синтаксическую информацию и строит так называемое абстрактное синтаксическое дерево (Abstract Syntax Tree). Вы можете рассматривать AST как карту нашего кода — способ увидеть как он структурирован.
В нашем коде два синтаксических типа “NumberLiteral” и “CallExpression”. NumberLiteral означает, что значение — это число. Это число используется в качестве аргумента для CallExpression.
3. Transformer function
Абстрактное синтаксическое дерево (AST), что мы создали на предыдущем шаге, хорошо описывает, что происходит в коде, но мы все еще не можем создать из этого SVG.
Например, команда “Paper” понятна только коду, написанному на DBN. В SVG для представления бумаги мы бы хотели использовать элемент, поэтому нам нужна функция, которая сконвертировала бы наше AST в другое AST, более подходящее для SVG.
4. Generator function
На последнем шаге компилятора вызывается функция, которая строит SVG код на основе нового AST, которое мы создали на предыдущем шаге.
5. Соберем все вышесказанное вместе
Давайте назовем наш компилятор “sbn compiler”. Создадим sbn объект с нашими лексером, парсером, трансформатором и генератором. Добавим “compile” метод, который будет вызывать цепочку из 4 этих методов.
Теперь мы можем передать строку кода методу компиляции и получить SVG.
Я сделала интерактивное демо, в котором можно посмотреть результат работы компилятора на каждом их шагов. Код для sbn компилятора можно скачать на github. На данный момент я работаю над расширением функционала компилятора. Если вы хотите увидеть только базовый компилятор, собственно тот, что создавался в этой статье, вы можете найти его здесь.
Должен ли компилятор использовать рекурсию, обход и т.д.?
Да, все эти техники безусловно прекрасно подходят для создания компилятора, но это совершенно не значит, что вы сразу должны применить их в своем компиляторе.
Я начала писать свой компилятор, используя лишь небольшой набор команд DBN. Постепенно я стала усложнять функциональность, и сейчас собираюсь добавить в компилятор использование переменных, блоков и циклов. Это конечно хорошо иметь все эти конструкции, но не обязательно применять их с самого начала.
Писать компиляторы это здорово
Что вы можете делать, если вы умеете писать компилятор? Быть может, вам захочется написать свою новую версию JavaScript на испанском… Как насчет EspañolScript?
Уже есть те, кто написали свой язык, используя Emoji (Emojicode) или цветные изображения (Piet). Возможности безграничны!
Обучение в процессе создания компилятора
Создавать компилятор было весело, и я многому научилась, касаемо разработки ПО. Перечислю всего несколько вещей, которым я научилась в процессе написания компилятора.
1. Вполне нормально чего-то не знать
Как и нашему лексическому анализатору, вам не нужно все знать с самого начала. Если вы не совсем понимаете часть какого-то кода или технологии, это нормально перенести работу с этим на следующий шаг. Не стоит нервничать, рано или поздно вы разберетесь в этом!
2. Уделите внимание тексту ваших сообщений об ошибках
Роль парсера — четко следовать инструкциям и проверять, написано ли все так, как сказано в правилах. Да, ошибки случаются часто. Когда это происходит, попробуйте отправлять информативное, дружеское сообщение об ошибке. Легко сказать — “Так оно не работает” (“ILLEGAL Token” или “undefined is not a function” в JavaScript), но вместо этого попробуйте предоставить пользователю как можно больше полезной информации.
Это также относится к командной коммуникации. Когда кто-то застрял со своим таском, вместо того, чтобы сказать ”Да это не работает”, можно начать говорить “Я бы поискал информацию в google по таким ключевым словам как…” или “Я рекомендую почитать такую-то документацию”. Вам не нужно брать на себя работу другого человека, но вы определенно можете помочь ему сделать его работу лучше и быстрее всего лишь подкинув ему свежую идею.
Язык программирования Elm использует этот подход в выводе сообщений об ошибках, где пользователю предлагаются варианты решения его проблемы (“Maybe you want to try this?”).
3. Контекст наше все
И наконец, точно так же, как наш трансформатор превратил один тип AST в другой, более подходящий для конечного результата, все в программировании зависит от контекста.
Нет ни одного совершенно идеального решения. Не делайте что-то, только потому, что сейчас это модно, или потому, что вы уже делали это раньше, подумайте сначала о контексте задачи. Вещи, которые работают для одного пользователя, могут быть совершенно ужасны для другого.
Поэтому цените работу “трансформаторов”, вы вполне возможно знаете такого в своей команде, человека, который хорошо завершает, начатую кем-то работу, или делает рефакторинг. Он по сути не создает новый код, но ведь результат его работы чертовски важен для конечного качественного продукта.
Надеюсь, вам понравилась эта статья и что я убедила вас, как это здорово писать компиляторы и самому быть компилятором!
Это перевод статьи Mariko Kosaka, которая является частью ее выступления на JSConf Colombia 2016 в Медельине, Колумбия. Если вы хотите узнать больше об этом, вы можете найти слайды здесь и оригинал статьи здесь.
Кратчайшее введение в создание компилятора
Здесь я попытался показать на практике, что собой представляют некоторые важные концепции из области создания компиляторов. Есть вероятность, что подобные 15-минутные завершенные истории могут оказаться неплохим способом погружения в сложные темы. Только хорошо бы не пассивно читать то, что представлено ниже, а еще и проверять код в работе.
Если первый опыт окажется успешным, то в будущем вас могут ожидать и другие 15-минутные «зарисовки» по тематике компиляторов.
О чем пойдет речь
Давайте сделаем компилятор арифметических выражений. Такой, который переведет исходный текст в обратной польской форме записи (ее еще называют RPN или ПОЛИЗ) в промежуточный код, работающий со стеком. Но мы обойдемся здесь без интерпретаторов. Далее мы сразу переведем результат в представление на языке Си. То есть у нас получится компилятор из RPN в Си.
Кстати говоря, писать компилятор мы будем на Python. Но пусть это не останавливает тех, кто предпочитает какой-то иной язык программирования. Вот вам полезное упражнение: переведите приведенный код на ваш любимый язык. Или воспользуйтесь уже готовым переводом:
Начнем с синтаксического анализа
Что мы здесь сделали? Функция scan получает от пользователя строку в обратной польской форме записи («2 2 +»).
А на выходе мы получаем ее промежуточное представление. Вот такое, например:
Вот так, мы уже получили компилятор. Но уж очень он несерьезный. Вспомним, что изначально речь шла о коде на Си.
Займемся трансляцией в Си
Что здесь происходит? Давайте посмотрим на вывод данной функции (на том же примере с «2 2 +»).
Да, это уже похоже на код на Си. Массив st играет роль стека, а sp — его указатель. Обычно с этими вещами работают виртуальные стековые машины.
Вот только самой машины — интерпретатора у нас-то и нет. Есть компилятор. Что нам осталось? Надо добавить необходимое обрамление для программы на Си.
Наш первый компилятор в готовом виде
Остается скомпилировать вывод данной программы компилятором Си.
Вы все еще готовы продолжать? Тогда давайте обсудим, что у нас получилось. Есть один сомнительный момент — наш компилятор транслирует константные выражения, а ведь их можно вычислить просто на этапе компиляции. Нет смысла переводить их в код. Но давайте пока считать, что какие-то аргументы могут попасть в стек извне. Остановимся на том, что практический смысл нашей разработке можно придать и позднее. Сейчас же важно получить общее представление о построении простейших компиляторов, верно?
Компилятор с использованием формы SSA
Вам нравится заголовок? SSA — это звучит очень солидно для любого компиляторщика. А мы уже сейчас будем использовать эту самую SSA. Что же это такое? Давайте двигаться по порядку.
Мы генерируем в данный момент код на Си, безо всяких виртуальных машин. Но зачем нам тогда рудимент в виде операций со стеком? Давайте заменим эти операции работой с обычными переменными из Си. Причем, мы не будем экономить переменные — для каждого выражения заведем новое имя. Пусть компилятор Си сам со всем этим разбирается. Получается, что у нас каждой переменной значение присваивается лишь однажды. А это, кстати говоря, и есть форма SSA.
Вот наш новый компилятор.
Обратите внимание — стека в коде на Си уже нет, а работа с ним имитируется в процессе трансляции. На стеке, который используется в процессе компиляции, содержатся не значения, а имена переменных.
Вот окончательный результат:
Итоги
Похоже, время нашего совместного занятия истекло. Мы занимались тем, что переводили программу с одного языка на другой. Это называется source-to-source трансляцией. Или же — просто трансляцией, которую можно считать синонимом компиляции, но обычно компилятор переводит программу из высокоуровневого представления в низкоуровневое. Существует еще модное словечко «транспилятор» для обозначения source-to-source транслятора. Но упоминание «транспилятора» может вызвать раздражение у специалистов по компиляторам, будьте осторожны!
Пишем примитивный и никому не нужный компилятор
Я считаю, что каждый программист должен написать свой компилятор.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.
Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.
Да, компилятор совершенно нагло основан на Tiny-С.
Грамматика
Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
Уметь он будет очень мало:
— единственный тип данных — int
— все переменные — глобальные. Всего есть 26 переменных (a-z)
— из математических операций поддерживаются только «+» и «-»
— единственный оператор сравнения — это »
Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.
Программа — это один оператор (statement).
Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»).
Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
Выражения — это либо сумма, либо присваивание переменной значения.
Здесь сумма — это последовательность сложений-вычитаний термов.
Терм — это число, переменная или выражение в скобках.
Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.
Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.
Лексический анализатор
На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.
Итак, наш лексический анализатор должен узнавать следующие токены:
Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.
Для описания узлов введем класс Node. Вот код класса парсера и класса Node:
Этот парсер работает рекурсивно, начиная с метода parse().
Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.
Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.
При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.
Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.
Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.
На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.
Машинный код
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:
Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:
Код виртуальной машины очень простой. Он весь описывается в методе run:
Осталось написать собственно компилятор — генератор кода.
Компилятор
Венец нашего творения. Вот его исходный код:
Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.
Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.
Тестируем
Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):
Ответы машина выдавала вроде бы правильные.