Пишем простой интерпретатор на Haskell. Написать свой компилятор
В этой статье речь пойдет о довольно необычном проекте. Однажды меня посетило желание написать свой интерпретатор какого-нибудь скриптового языка и исполняющую машину для него. Просто для того, чтобы посмотреть, как оно внутри работает. Такая цель звучит не очень благородно и я отложил затею в долгий ящик, т.к. мне хотелось более полезной формулировки.
Как-то раз, один мой знакомый посетовал, что нужно написать скрипт автоматизации на WSH, но ни VBScript, ни Javascript он не знает. Тут «благородная» формулировка возникла сама собой… нужно помочь товарищу. В результате был написан компилятор и исполняющая машина, позволяющая исполнять скрипты для Windows Script Host, не прибегая к VBScript и JS. Под катом - краткая предыстория проекта и его внутреннее устройство и сам язык программирования.
Краткая предыстория
Господа, я раскрою вам страшную тайну. Я знаю, что признаться в таком грехе - очень стыдно, но тем не менее, признаюсь. Я - один-эсник. Да-да-да, я пишу большие и малые решения с помощью желтого фреймворка и совесть меня не мучает))).Помимо 1С я знаю и другие языки, но я молодой, могу себе позволить. Мой знакомый, которого я упомянул во введении - наоборот - военный отставник, хороший инженер-электронщик, переучился в программисты, когда вышел на гражданку. Для грамотного технаря такая переквалификация - несложное дело, платят в сфере 1С неплохо, а хорошим спецам - так и вовсе хорошо. Однако, с возрастом все труднее становится гнаться за новыми технологиями, все сложнее следить за стремительно меняющимся миром IT. Когда состоялся упомянутый разговор, он сказал что-то вроде: «Да это долго, новый язык учить, вот если бы такой скрипт на 1С можно было написать, но чтоб в консоли выполнялся…» Тогда-то я и вспомнил свою старую идею с написанием интерпретатора, которая теперь из чисто исследовательской получала вполне прикладную направленность - выполнение скриптов, работающих с инфраструктурой WSH, но на языке 1С.
Немного о языке программирования
Про язык 1С говорят, что это Visual Basic, переведенный промтом. Это действительно так. По духу язык очень близок к VB - в нем нестрогая типизация, нет ООП, лямбда-выражений и замыканий. В нем «словесный», а не «сишный» синтаксис. Кроме того, поскольку все ключевые слова имеют английские аналоги, то код 1С, написанный в английских терминах отличить с первого взгляда от VB почти невозможно. Разве что символ комментария - две косые черты, а не апостроф, как в бейсике.Язык различает процедуры и функции, имеет классические циклы «For» и «While», а также итераторный цикл «For Each … In». Обращение к свойствам и методам объектов выполняется «через точку», обращение к массивам - в квадратных скобках. Каждый оператор завершается точкой с запятой.
Что такое «стековая машина» и как она работает
Насколько мне известно, стековые машины являются наиболее распространенными. Например, виртуальные машины.NET CLR и JVM являются стековыми. На хабре даже есть отдельная про это дело. Тем не менее, чтобы не гонять читателя по ссылкам, думаю, что стоит описать принцип их работы и здесь. Стековая машина выполняет все операции над данными, которые организованы в виде стека. Каждая операция извлекает из стека нужное ей количество операндов, выполняет над ними действия и кладет результат обратно в стек. Такой подход позволяет создать легковесный байт-код с минимумом команд. Кроме того, он еще и довольно шустро работает.Байт-код - это набор команд, которые будет выполнять машина.
Каждая инструкция представляет собой однобайтовый код операции от 0 до 255, за которым следуют такие параметры, как регистры или адреса памяти (википедия).
В нашей машине команда будет иметь фиксированную длину и состоять из двух чисел - кода операции и аргумента операции. Каждая команда подразумевает набор действий над данными в стеке.
Например, псевдокод операции сложения «1+2» может выглядеть следующим образом:
Push 1
Push 2
Add
Первые две команды кладут в стек слагаемые, третья команда выполняет сложение и кладет результат в стек. В таком случае, операция присваивания «A = 1 + 2» может выглядеть так:
Push 1 ; поместить в стек "1"
Push 2 ; поместить в стек "2"
Add ; извлечь из стека "1" и "2", сложить и поместить результат в стек.
LoadVar A ; извлечь значение из стека и записать в переменную "А"
Видно, что команды Push и LoadVar имеют аргумент, команда Add в аргументе не нуждается.
Преимущество стековых вычислений в том, что операции выполняются в порядке их следования, не нужно обращать внимание на приоритеты операций. Что написано, то и выполняется. Перед выполнением операции ее операнды заталкиваются в стек. Такой способ описания выражений получил название "обратной польской записи "
Задача написания стековой машины сводится к «изобретению» необходимого набора команд, которые эта машина будет понимать.
Устройство компилятора
Задача компилятора - преобразовать код на заданном языке в байт-код машины, которая будет его выполнять. Классический компилятор имеет 3 компонента:- Лексический анализатор (парсер)
- Синтаксический анализатор
- Генератор кода
Синтаксический анализатор проверяет, что набор лексем, которые дал ему лексический анализатор является осмысленным, что перед нами программа, а не бессмысленный набор букв.
Короткое заключение
В рамках проекта разработан интерпретатор сценариев на языке 1С, включающий в себя стековую виртуальную машину, исполняющую сценарий и транслятор языка 1С в байт-код виртуальной машины.Производительность получилась примерно сравнимой с оригиналом. Если учесть, что это любительский проект, сделанный «на коленке», то результат, полагаю, можно считать неплохим. Каких-то серьезных исследований по скорости я не проводил. Ради интереса можно посравнивать скорость математики и больших чисел, но это уже немного отдельная тема.
Надеюсь, данный опус был вам интересен. Форкайте проект, критикуйте, мне будет приятно. Удачи.
P.S. В комментариях к статье про 1С обязательно должно быть сообщение «Как можно писать операторы на русском языке?»:)
Теги: Добавить метки
От автора:
Тянулся нудный осенний вечер; делать как всегда было нечего... И вдруг, ни с того ни с сего, пришла мне в голову идея написать статью по созданию интерпретатора. «Делать тебе нечего... – иди лучше к коллоквиуму по вышке готовься», - раздался внутренний голос. И я уже было потянулся к розетке, чтобы вырубить мой компьютер, но внезапно вспомнил. Вспомнил, как я сам писал систему обработки сценариев. Вспомнил, сколько времени, усилий и нервов было впустую затрачено на поиск исчерпывающей информации по этой теме. Вспомнил бессонные ночи, проведенные за отладкой. И еще много чего вспомнил, а потом... послал свой внутренний голос и принялся за работу.
Введение:
Этот цикл статей предназначен, прежде всего, для читателя, не имеющего опыта работы в области написания интерпретаторов. Я постараюсь рассмотреть этот процесс настолько подробно, на сколько позволяют мои знания и опыт. Итак:
Тема работы: написание системы обработки сценариев на С++.
Цель работы:
1) ознакомление читателя с темой;
2) создание работоспособного интерпретатора с нуля;
3) его «внедрение» в какое-либо приложение.
Приборы и оборудование: базовые навыки владения С++, ООП и STL.
Ход работы:
Постановка задачи:
Написание полноценного интерпретатора какого-либо языка – дело сверхтрудоемкое и для меня непосильное. Поэтому я ограничил скриптовый язык подмножеством языка Си и, следуя принципу «достижения результатов наименьшими усилиями» внес в это подмножество кое-какие изменения. Итак, вот что получилось:
По существу, наша система обработки сценариев состоит из следующих основных компонентов:
- Lexer – преобразует входные данные (обычно, файл) в поток лексем (таких как ключевые слова, операторы и т.д.);
- Generator – генерирует байт код для последующего выполнения виртуальной машиной;
- Executor – выполняет байт код.
А вот наглядное изображение взаимодействия этих компонентов:
Термины и понятия:
Ниже я привожу словарь терминов и понятий, которые будут периодически использоваться в последующих статьях цикла. Все нижеперечисленные определения рассматриваются в контексте скриптов ESL.
аргумент (или параметр ) – это значение, передаваемое в функцию. Например в случае вызова функции IntToStr(123) аргументов является число 123.
выражение – это то, что приводит к некоторому значению. Например, как простая переменная, так и формула (x*n-1)/y2k являются выражениями. Любое выражение можно превратить в инструкцию, добавив после него «;». Операции присваивания также являются выражениями. Примеры выражений: x, y = x, func1(), y = func1().
идентификатор – это имя, определенное в скрипте. Любое слово в программе (за исключением комментариев и ключевых слов) является идентификатором. Все имена стандартных и игровых функций также являются идентификаторами.
инструкция – базовый элемент скрипта. Пример: for(...), if(...), a = b;.
ключевое слово – это имя, определенное в самом ESL. Сюда не включаются имена стандартных и программных функций, которые являются идентификаторами. Примеры: if, for, end.
Некоторое время назад мне захотелось написать свой небольшой интерпретируемый скриптовый язык, просто ради фана, не ставя перед собой каких-либо серьезных задач. Я тогда активно читал известную волшебную книгу SICP (Структура и интерпретация компьютерных программ), и мне захотелось реализовать описываемые в ней абстракции - функции как объекты первого класса, замыкания, макросы и т.п. Параллельно я интересовался языком Haskell, и решил совместить приятное с приятным, и написать интерпретатор языка на нем. В моем языке должна была быть строгая семантика с вызовом по значению и мутабельные переменные. Получившийся язык Lisp-семейства я в своем локальном окружении связал с именем Liscript, полная реализация которого уместилась в примерно 250 строк, включая парсер, ядро и консольный/файловый ввод-вывод. Этого более чем хватало, чтобы ради интереса решать любые задачки, какими обычно мучают студентов, которых угораздило изучать Lisp по учебной программе.
По прошествии времени мне захотелось сделать к интерпретатору кроссплатформенный GUI-интерфейс с перспективой портирования на Android, поэтому я реализовал второй вариант интерпретатора на Java, внешний вид которого вы можете видеть на картинке выше. Да, он поддерживает графический вывод и вообще interoperability с Java, и этот Тетрис написан на Liscript, видна часть его кода. Кому интересны подробности - прошу под кат.
В рамках одной статьи сложно уместить все особенности языка и его реализации, а писать сериал из многих статей, начиная с пространного описания реализации парсера с помощью стандартной библиотеки мне скромность не позволит. (К слову сказать, в обоих реализациях - и на Haskell и на Java я не пользовался никакими библиотеками парсинга, а писал все вручную - на Haskell это заняло аж целых 10 строк кода). Поэтому некоторые вещи буду писать в стиле «пришел, увидел, победил». В общем, написал я парсеры текста в AST типов. Единственно, хочу отметить пару моментов - я не фанат скобочек, но легкость парсинга, гомоиконность кода (код как данные) и отсутствие инфиксных бинарных операторов с необходимостью учета приоритета и ассоциативности и разбора через Польшу или сортировочные станции с лихвой перевешивает все претензии к подобному синтаксису. В результате парсинга я получаю список, который передается функции интерпретации. В Java-реализации я не стал пользоваться библиотечными типами списков, а навеловипедил свой - простой, односвязный, потоконебезопасный и т.п.:
Заголовок спойлера
/** тип языка Liscript - односвязный список */
public static class ConsList {
/** объект - значение головы текущего списка */
public Object car;
/** список - значение хвоста текущего списка */
public ConsList cdr;
/** Конструктор со значениями головы и хвоста.
* @param h объект - голова списка
* @param t список - хвост списка
*/
ConsList(Object h, ConsList t) { car = h; cdr = t; }
/** проверяет, является ли список пустым
* @return истина/ложь
*/
public boolean isEmpty() { return this.car == null && this.cdr == null; }
/** возвращает размер списка
* @return размер
*/
public int size() {
int r = 0;
ConsList p = this;
while (!p.isEmpty()) {r += 1; p = p.cdr;}
return r;
}
/** @return строковое представление текущего списка */
@Override
public String toString() { return showVal(this); }
}
Подобным же образом реализованы типы-классы для функции, макроса. Пример кода класса-типа функции:
Заголовок спойлера
/** тип языка Liscript - функция */
public static class Func {
/** односвязный список имен параметров функции */
public ConsList pars;
/** тело функции */
public Object body;
/** окружение, в котором создана функция */
public Env clojure;
/** Конструктор
* @param p односвязный список имен параметров функции
* @param b тело функции
* @param c окружение, в котором создана функция
*/
Func(ConsList p, Object b, Env c) { pars = p; body = b; clojure = c; }
/** @return строковое представление функции */
@Override
public String toString() { return showVal(this); }
}
Окружение
Реализовано в полном соответствии с SICP - иерархическая структура словарей, где каждый словарь - HashMapТакже мне захотелось реализовать переменную арность особых форм прямо в ядре языка, а не потом в стандартной библиотеке. Многие из них допускают передачу ряда параметров и/или работают не совсем так, как их одноименные аналоги в других диалектах Lisp - это не усложняет реализацию интерпретатора. Пример работы с окружением (после => идет ответ интерпретатора):
++ "a1 = " a1 ", b1 = " b1 ", c1 = " c1 => a1 = a1, b1 = b1, c1 = c1 def a1 1 b1 (+ a1 1) (++ "c" a1) (+ a1 b1) => OK ++ "a1 = " a1 ", b1 = " b1 ", c1 = " c1 => a1 = 1, b1 = 2, c1 = 3 set! (++ "a" 1) 5 c1 10 => OK ++ "a1 = " a1 ", b1 = " (get (++ "b" 1)) ", c1 = " c1 => a1 = 5, b1 = 2, c1 = 10
Функции
Являются объектами первого класса. При создании функция захватывает текущий контекст. При вызове аргументы вычисляются строго последовательно. Реализована автоматическая оптимизация хвостовых вызовов - ТСО:Defn is-even (n) (cond (= n 0) true (is-odd (- n 1)))
=> OK
defn is-odd (n) (cond (= n 0) false (is-even (- n 1)))
=> OK
is-even 10000
=> true
is-even 10001
=> false
Особая форма tray позволяет печатать стек вызовов при применении функции. Вот так, например, происходит вычисление факториала от 3:
Заголовок спойлера
defn f (i) (cond (< i 2) 1 (* i (f (- i 1))))
=> OK
tray f 3
=>
1 (lambda (i) (cond (< i 2) 1 (* i (f (- i 1)))))
2 3
3 > false
3 3
4 (lambda (i) (cond (< i 2) 1 (* i (f (- i 1)))))
5 3
5 > 2
5 2
6 > false
6 2
7 (lambda (i) (cond (< i 2) 1 (* i (f (- i 1)))))
8 2
8 > 1
8 1
9 > true
8 > 1
7 > 1
6 > 2
5 > 2
4 > 2
3 > 6
2 > 6
1 > 6
6
Если при вызове функции аргументов передано больше, чем количество формальных параметров, то последний формальный параметр свяжется со списком вычисленных оставшихся переданных аргументов. Если меньше - то эти формальные параметры окажутся не связаны в окружении вычисления функции и при вычислении ее тела будут искаться в окружениях верхнего уровня иерархии. Можно было бы выбрать вариант каррирования - возвращать частично примененную функцию, или выдавать ошибку несоответствия количества аргументов.
Макросы
Liscript поддерживает так называемые runtime-макросы, которые являются объектами первого класса языка. Их можно создавать, связывать с именами, возвращать как результат функций и выполнять в процессе работы (интерпретации кода). Полученное из текста исходного кода выражение сразу начинает интерпретироваться, без предварительной стадии раскрытия макросов, поэтому макросы остаются полноправными типами языка и раскрываются и вычисляются в процессе интерпретации по всем правилам вычисления макросов - сначала производится подстановка в тело макроса невычисленных переданных аргументов а затем это тело макроса вычисляется в текущем окружении (в отличие от тела функции, которое всегда вычисляется в отдельном собственном окружении, в котором уже присутствуют предварительно вычисленные значения фактических параметров):Def m (macro (i r) (cond (<= i 0) "r (m (- i 1) (cons i r)))) => OK m 5 nil => (cons (- (- (- (- 5 1) 1) 1) 1) (cons (- (- (- 5 1) 1) 1) (cons (- (- 5 1) 1) (cons (- 5 1) (cons 5 nil))))) eval (m 5 nil) => (1 2 3 4 5)
Interoperability с Java
Реализовано через механизм Java Reflection. Всего 2 особые формы: class - определяет класс по полному имени и java - вызывает метод класса с переданными параметрами. Поиск нужного метода среди одноименных перегруженных осуществляется с учетом количества и типов переданных параметров. Для ускорения работы однажды найденный и вызванный в текущем сеансе работы интерпретатора метод класса запоминается в таблице вызванных методов и при вызове любого метода сначала происходит поиск в таблице - мемоизация.Def m (java (class "java.util.HashMap") "new")
=> OK
java m "put" 1 "a"
=> OK
java m "put" "b" 2
=> OK
java m "get" 1
=> a
m
=> {1=a, b=2}
Таким образом мы можем получить доступ ко многим ресурсам языка реализации, в том числе и к графике. Вот такой код открывает отдельное окно с нарисованной красной линией на белом фоне:
(def image (java (class "java.awt.image.BufferedImage") "new" 100 100 1))
(def imageGraphics (java image "createGraphics"))
(java imageGraphics "setBackground" (java (class "java.awt.Color") "new" 255 255 255))
(java imageGraphics "clearRect" 0 0 100 100)
(java imageGraphics "setColor" (java (class "java.awt.Color") "new" 255 0 0))
(java imageGraphics "drawLine" 10 10 90 90)
(def icon (java (class "javax.swing.ImageIcon") "new"))
(java icon "setImage" image)
(def label (java (class "javax.swing.JLabel") "new"))
(java label "setIcon" icon)
(def window (java (class "javax.swing.JFrame") "new"))
(java window "setLayout" (java (class "java.awt.FlowLayout") "new"))
(java window "add" label)
(java window "setVisible" true)
(java window "pack")
Разумеется, можно выделить типичные блоки в отдельные функции или макросы и прописать их один раз в стандартной библиотеке, которая подгружается при старте интерпретатора. А поскольку интерпретатор реализует многопоточное выполнение задач в отдельных закладках с общим мутабельным окружением (да, я знаю, что выбранная в качестве хранилища словаря HashMap не является потокобезопасной и это может создать проблемы при одновременном изменении окружения из параллельных потоков, и лучше было применить HashTable), так вот, это позволяет в одной закладке запустить процедуру, вызывающую саму себя через определенное время ожидания по таймеру, а в другом окне (потоке) - процедуру, запрашивающую пользовательский ввод и выполняющую определенные действия. Так и был реализован Тетрис (с особенностью блокирующего пользовательского ввода - каждую команду надо подтверждать с помощью Ctrl+Enter).
Данный проект доступен на Github по адресу
Прям процитирую:
"Сам список трансформаций:
- ({} → nil) Заменить отсутствие кода на код, использующий нулевое значение.
- (nil → constant) Заменить нулевое значение константой.
- (constant → constant+) Заменить простую константу более сложной (строку из одной буквы на строку из нескольких букв, к примеру).
- (constant → scalar) Заменить константу на переменную, или аргумент.
- (statement → statements) Добавить безусловный оператор (break, continue, return и подобное).
- (unconditional → if) Разбить поток выполнения с помощью условного оператора.
- (scalar → array) Заменить переменную/аргумент массивом.
- (array → container) Заменить массив более сложным контейнером.
- (statement → recursion) Заменить выражение рекурсией.
- (if → while) Заменить условный оператор циклом.
- (expression → function) Заменить выражение функцией.
- (variable → assignment) Изменить значение переменной.
Скажем так - я интуитивно это понимал и сам использовал на уровне "подсознания", но вот так чётко и ясно - формулировку увидел впервые .
И вообще - мне сильно понравилось, что автор "практически формально" применяет подход - тест -> падает -> трансформация -> тест не падает -> рефакторинг -> тест не падает.
Не буду говорить о "своём пути" или "я шёл той же дорогой", но повторю то, что сказал выше - "я сам нередко применяю подобную практику". Видимо "на уровне подсознания".
Но теперь я нашёл обоснование для своей "работы на уровне подсознания".
Не знаю как это оценит аудитория, но мне лично кажется, что "The Transformation Priority Premise (TPP) " - это "бомба". Не "серебряная пуля" конечно, но бомба.
Понятное дело, что любой инструмент можно извратить и применять неправильно, но если обладать определённым "опытом" и "чутьём", то действительно можно писать код и тесты - "чисто формально". Не поймите меня неправильно.
Они - конечно же есть.
Самый волнующий меня вопрос - это почему операторы представляются enum"ами с char-константами. В духе:
Enum class Operator: wchar_t {
Plus = L"+",
Minus = L"-",
Mul = L"*",
Div = L"/",
LParen = L"(",
RParen = L")",
};
- меня это лично несколько "шокирует".
Но учитывая, что я встречал этот подход не раз и в частности у Антона Григорьева в его "парсере формул" и во множестве статей и книг, то мне кажется, что это некая такая "best practice", о которой я не в курсе.
Теперь о Хабре и "комментариях".
Прямо слово - комментарии "доставляют".
Есть конечно комментарии полезные и умные. О них я говорить не буду.
А есть такие за которые "глаз зацепился". О них скажу пару слов.
Не для того, чтобы кого-нибудь "покритиковать", а лишь для того, чтобы показать "свой виденье на чтение и писание статей".
Самое что "впечатлило", это конечно:
Программа будет писаться в Visual Studio 2013
Дальше не читал…
Хочется сказать - "молодец, самовыразился за счёт автора".
Всё то же самое можно сделать в Eclipse с установленным плагином C/C++ Unit, скачать Boost.Test, или GTest, скомпилировать их, прописать в путях проекта. Но в таком случае половина статьи будет касаться только настройки окружения. В Visual Studio 2012 и 2013 окружение, готовое к TDD создаётся за пару кликов. Хотя, для написания более сложных тесто, всё равно придётся ставить Boost.Test, или подобное.
Вот комментарий:
TDD и прочие практики экстремального программирования мне всегда казались извращением
Но опять же автор статьи на высоте:
Рекомендую к прочтению книгу Agile!: The Good, the Hype and the Ugly Paperback – Bertrand Meyer, 2014. В ней как раз даётся разбор, что из XP хорохо, а что не очень. TDD не является серебряной пулей, но зачастую является очень полезной техникой.
Ну и ещё из комментариев:
Вроде все хорошо, но почему строки по значению передаете?
А большинство push_back можно заменить на emplace_back.
Напоминает "студента", который узнал о "best practice" и пытается всем показать, что он "это знает".
Это напоминает "всем известные" споры о FreeAndNil, возникающие в контексте различных статей, которые вроде бы и не о FreeAndNil.
Тем более, что "передача по значению vs. передача по ссылке" в C++ это сложная и объёмная тема. Которая выходит далеко за рамки статьи. В этой теме даже корифеи - "до конца не договорились".
И есть множество статей на тему - "почему надо данные передавать по значению ".
Учитывая наличие в C++11 конструкторов с &&.
Ну и ещё:
Хорошие инструменты позволяют тратить меньше времени на написание и тестирование парсеров, так как отлаживать необходимо только генератор парсеров и только его авторам. Пользователи могут считать, что генератор безошибочно переводит специфицикацию в код.
В целом там комментарий хороший и вдумчивый.
Т.е. комментарий вообще-то хороший, правильный. На тему "парсеров". Но не совсем в "тему статьи".
Ведь статья как раз и призвана показать как сделать так, чтобы:
Пользователи могут считать
, что генератор безошибочно переводит специфицикацию в код.
Ну вот "я так вижу".
За основу я взял язык Brainfuck, он настолько мал, что можно немного расширив получить практически новый и достаточно функциональный язык программирования. И при этом не потерять изюминку исходного языка - мой язык будет все так же терзать мозг программиста, как и его родитель!
Итак, Brainfuck. Вкратце, идея такая, есть N регистров/ячеек. У программиста есть доступ к ним всем но перемещения по ним делаются явным образом. Т.е. из ячейки 2 нельзя перейти к ячейке 7 сразу, нужно последовательно.
"Ключевые слова" языка:
- > - перейти на ячейку вправо.
- < - перейти на ячейку влево.
- + - увеличить значение ячейки на единицу.
- - - уменьшить значение ячейки на единицу.
- , - прочесть значение в ячейку со стандартного устройства ввода.
- . - напечатать значение ячейки стандартным устройством вывода.
- [ - начать цикл while если значение текущей ячейки не равно 0 и перейти к следующей ячейке.
- ] - конец блока while. Продолжить цикл, если значение "условной" ячейки не равно 0 ("условная ячейка" - ячейка на которой начался цикл).
- $ - прочитать значение в ячейку как число (> переопределим как чтение в качестве ANCII символа)
- ! - напечатать как число
- { - начало функции, после начала идет имя функции (именем может служить любая последовательность букв между символами %<имя функции>%. Для любой функции создается копия ячеек, возвращаемое значение записывается в текущий регистр вызвавшего блока
- } - конец функции
- (- начало комментария
- ) - конец комментария
- @%<имя функции>% - вызов функции
- ^ - обнулить ячейку
Так как все множество ключевых слов состоит из ANCII символов, имеем:
// Искомые ключевые слова
const char bf_next = ">";
const char bf_prev = "<";
const char bf_incr = "+";
const char bf_decr = "-";
const char bf_prnt = ".";
const char bf_read = ",";
const char bf_wBeg = "[";
const char bf_wEnd = "]";
// Добавленные ключевые слова
const char bf_pNum = "!" ;
const char bf_rNum = "$";
const char bf_fBeg = "{";
const char bf_fEnd = "}";
const char bf_fNme = "%";
const char bf_comm= "(";
const char bf_call = "@";
const char bf_null = "^";
Без ограничения общности возьмем ограниченное количество ячеек, скажем 256 и в случае попытки перейти к недопустимой ячейке будем переходить к самой первой ячейке (если переход влево) или к самой последней (если переход вправо).
const unsigned long regSize = 256; // Количество регистров
long reg[ regSize ]; // Сами регистры
long stck[ regSize ]; // Стек, у каждой функции свой стек
void resetRegisters(); // Функция для обнуления регистров
void printRegistres(); // Показать состояние регистров
Теперь, скажем имеем test.bf, как входной файл, в котором находится код на моем языке или на родном Brainfuck. Интерпретатор должен обеспечивать "обратную совместимость".
Опять же, без ограничения общности, можем хранить весь код в некотором ограниченном массиве. Т.е. интепретатор будет работать с файлами ограниченного размера, скажем так:
const unsigned long maxCodeSize = 1024000; /* максимальный размер входного файла в символах */
unsigned long realCodeSize; // Размер кода в файле realCodeSize < maxCodeSize
char code; // Сам код
Интерпритатор читает весь код сразу. В один символьный массив, для этого будем использовать функцию readCode(). После прочтения не пустого текста m_realCodeSize будет содержать точное количество символов в коде, без учета комментариев, комментарии отбрасываются во время чтения.
int main(int argc, char** argv)
{
welcome();
resetRegisters();
readCode("test.bf ");
loop (0, realCodeSize - 1, regSize, reg);
return 0;
}
bool loop(unsigned long from,
unsigned long to,
unsigned long condRegIndx,
unsigned long currReg,
long* registers);
bool runFunction(unsigned long from,
unsigned int to,
unsigned int& retValue);
void copyRegistersTo(long* source, long* destination);
Первая будет выполнять цикл и вернет true если цикл выполнен без проблем, т.е. нет синтаксических ошибок.
Вторая собственно будет выполнять функцию, а возвращаемое значение запишется в retVal, которое в свою очередь присвоится регистру, на котором была вызвана функция. Возвращаемым значением будем считать первый регистр стека функции после ее окончания.
Кстати, о цикле while, в общем случае цикл может продолжаться бесконечно. Но, чтобы не столкнуться с проблемой зависания интерпретатора, введем переменную отвечающую за максимальное количество циклов.
const unsigned long maxLoopCycles = 999999;
Реализуем сначала обратную совместимость. Пусть пока наш интерпретатор сможет выполнять только код Brainfuck-а.
Нам понадобятся функции:
bool makeCommand(char command, long* registers, unsigned long currReg)
unsigned long findLoopEnd(const unsigned long from)
Второй и третий параметры первой функции обязательны. Третий параметр нужен для того, чтобы ориентироваться с какой ячейкой работать, второй нужен потому что регистры каждой функции отличаются, а операции над ними одинаковы.
Вторая функция исходя из названия находит конец цикла, т.е. символ соответствуюйщий "[".
Таким образом имеем интерпретатор для языка Brainfuck.
К записи прикрепил исходный код , моего интерпретатора с тестовым кодом
$[+<->]<<$>!<>>++++[++++++++++<->]<+++.++++++++++++++++++<<[<-<+>>]>>.<<
На код выше мой интерпретатор выведет сумму двух введённых чисел в виде а+b=c.
Удачного… программирования!