Как написать простой командный интерпретатор. Как создать свой язык программирования: теория, инструменты и советы от практика
Некоторое время назад мне захотелось написать свой небольшой интерпретируемый скриптовый язык, просто ради фана, не ставя перед собой каких-либо серьезных задач. Я тогда активно читал известную волшебную книгу 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 по адресу
За основу я взял язык 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.
Удачного… программирования!
Прям процитирую:
"Сам список трансформаций:
- ({} → 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 конструкторов с &&.
Ну и ещё:
Хорошие инструменты позволяют тратить меньше времени на написание и тестирование парсеров, так как отлаживать необходимо только генератор парсеров и только его авторам. Пользователи могут считать, что генератор безошибочно переводит специфицикацию в код.
В целом там комментарий хороший и вдумчивый.
Т.е. комментарий вообще-то хороший, правильный. На тему "парсеров". Но не совсем в "тему статьи".
Ведь статья как раз и призвана показать как сделать так, чтобы:
Пользователи могут считать
, что генератор безошибочно переводит специфицикацию в код.
Ну вот "я так вижу".
- Tutorial
Введение
Многие C++ программисты слышали про разработку через тестирование. Но почти все материалы по данной теме касаются более высокоуровневых языков и сосредоточены больше на общей теории, чем на практике. Итак, в данной статье я попробую привести пример пошаговой разработки через тестирование небольшого проекта на C++. А именно, как можно предположить из названия, простого интерпретатора математических выражений. Такой проект также является неплохой code kata, так как на его выполнение затрачивается не более часа (если не писать параллельно статью об этом).
Архитектура
Несмотря на то, что при использовании TDD архитектура приложения постепенно проявляется сама собой, начальная её проработка всё же необходима. Благодаря этому может значительно снизиться общее время, затраченное на реализацию. Это особенно эффективно в тех случаях, когда существуют готовые примеры подобных систем, которые можно взять за образец. В данном случае, существует вполне устоявшееся мнение о том, как должны быть устроены компиляторы и интерпретаторы , чем и можно воспользоваться.Существует множество библиотек и инструментов, которые могут облегчить разработку интерпретаторов и компиляторов. Начиная от Boost.Spirit и заканчивая ANTLR и Bison. Можно даже запустить канал интерпретатора командной строки через popen и вычислить выражение через него. Целью данной статье является пошаговая разработка достаточно сложной системы с помощью TDD, поэтому будет использоваться только стандартная библиотека C++ и встроенный в IDE тестовый фреймворк.
Для начала, составим список того, что должен уметь наш простой интерпретатор, в порядке убывания приоритета:
- Вычислять значение математического выражения, состоящего из чисел с плавающий точкой и математических операторов (-+/*).
- Учёт приоритета операторов.
- Учёт скобок.
- Унарные плюс и минус.
- Вычисление нескольких выражений, разделённых точкой с запятой (;).
- Встроенные константы (pi, e).
- Создание собственных констант с помощью оператора присваивания (=).
- Встроенные функции с переменным числом аргументов.
- Задание новых функций.
- Лексический анализатор. Преобразовывает входную строку в последовательность токенов.
- Синтаксический анализатор. Строит из токенов синтаксическое представление в виде постфиксной нотации . Делать это будем без рекурсии и таблиц, с помощью алгоритма сортировочной станции .
- Вычислитель. Вычисляет результат выражения на стековой машине.
- Собственно, интерпретатор. Служит фасадом для вышеперечисленных частей.
Инструментарий
Программа будет писаться в Visual Studio 2013 с установленным Visual C++ Compiler Nov 2013 CTP . Тесты будут на основе встроенного в студию тестового фреймворка для C++ проектов CppUnitTestFramework . Он предоставляет минимальную поддержку для написания модульных тестов (по сравнению с Boost.Test, или CppUTest), но, с другой стороны, хорошо интегрирован в среду разработки. Альтернативой может служить Eclipse с установленным плагином C/C++ Unit и настроенным Boost.Test, GTest, или QtTest. В такой конфигурации рекомендую использовать clang, так как он предоставляет несколько мощнейших compile- и runtime анализаторов, в результате чего, в связке с TDD, код становится совершенно неуязвимым для ошибок.Итак, создадим новый проект типа «Native Unit Test Project» и удостоверимся, что всё компилируется.
Лексер
Начнём с разработки лексера. Будем следовать привычному для TDD циклу Red-Green-Refactor:- Написать тест и заставить его падать (Red).
- Заставить его пройти (Green).
- Улучшить дизайн (Refactor).
- В ответ на пустое выражение, должен возвращаться пустой список токенов.
TEST_CLASS(LexerTests) {
public:
TEST_METHOD(Should_return_empty_token_list_when_put_empty_expression) {
Tokens tokens = Lexer::Tokenize("");
Assert::IsTrue(tokens.empty());
}
};
В CppUnitTestFramework макрос TEST_CLASS генерирует класс, в котором будут размещаться тестовые методы. Макрос TEST_METHOD , соответственно, создаёт сам тестовый метод. Необходимо учесть, что экземпляр класса создаётся только один раз перед запуском всех находящихся в нём тестов. В Boost.Test, к примеру, экземпляр класса создаётся каждый раз заново перед запуском каждого теста. Следовательно, тот, код, который необходимо выполнить перед каждым тестом, будет помещаться в метод, объявленный с помощью макроса TEST_METHOD_INITIALIZE , а тот, который после, в TEST_METHOD_CLEANUP . Все методы утверждений являются статическими и располагаются в классе Assert . Их немного, но основную функциональность они покрывают.
Вернёмся к нашему тесту. Он не то, чтобы не проходит, он даже не компилируется. Создадим функцию Tokenize в пространстве имён Lexer , принимающую строку и возвращающую std::vector, скрытый для удобства за псевдонимом Tokens . Я решил пока что не создавать дополнительные классы и ограничиться обычной функцией.
#pragma once;
#include
Сейчас проект компилируется, но тест, что было ожидаемо, падает. Для определения того, что же писать дальше, можно воспользоваться техникой The Transformation Priority Premise (TPP) авторства Роберта Мартина. Трансформации являются аналогами рефакторингов, но, в отличии от них, используются для изменения поведения кода, тогда как рефакторинг к изменению поведения не приводит. Каждая трансформация ведёт к изменению кода от более конкретного к более общему. Главная их особенность в том, что они имеют разные приоритеты, в зависимости от которых выбирается то, какой код писать для прохождения теста и какой будет следующий тест. А именно, те трансформации, которые проще (располагаются выше в списке) должны быть более предпочтительны, чем те, которые снизу. При намерении создать новый тест, выбирается такой, что для его прохождения нужно применить более простую трансформацию. Это не является строгим правилом, но следование TPP может вести к более простому коду за меньшее количество шагов.
Сам список трансформаций:
- ({} → 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) Изменить значение переменной.
Inline Tokens Tokenize(std::string expr) { return{}; }
Посмотрим, что должен уметь лексер для выполнения первого пункта требований. Занесём это в список тестов.
TEST_METHOD(Should_tokenize_single_plus_operator) {
Tokens tokens = Lexer::Tokenize(L"+");
AssertRange::AreEqual({ Operator::Plus }, tokens);
}
Здесь AssertRange - это пространство имён, в которое я поместил функцию утверждения AreEqual , сравнивающую две последовательности, а точнее, список инициализации и последовательность.
AssertRange
namespace AssertRange {
template
Также пришлось изменить определение токена и добавить перечисление Operator с названиями арифметических операторов. Можно было бы использовать для этой цели просто тип wchar_t с символом оператора, но тогда в будущем придётся иметь дело с тем, как различать бинарные и унарные операции.
Enum class Operator: wchar_t {
Plus = L"+",
};
typedef Operator Token;
Для успешной компиляции тестов, для каждого класса, экземпляр которого передаётся в статические методы класса Assert , необходимо определить функцию ToString , возвращающий его строковое представление.
std::wstring ToString(const Token &)
inline std::wstring ToString(const Token &token) {
return{ static_cast
После этого тест компилируется, но не проходит, так как мы продолжаем возвращать пустую последовательность токенов. Исправим это, применив трансформацию (unconditional → if).
Inline Tokens Tokenize(std::wstring expr) {
if(expr.empty()) { return{}; }
return{ static_cast
- В ответ на пустое выражение должен возвращаться пустой список токенов.
- В ответ на строку с оператором должен возвращаться токен с оператором.
- В ответ на строку с цифрой должен возвращаться токен с числом.
TEST_METHOD(Should_tokenize_single_digit) {
Tokens tokens = Lexer::Tokenize(L"1");
AssertRange::AreEqual({ 1.0 }, tokens);
}
Здесь возникает проблема представления токенов. С одной стороны, они должны хранить коды операторов, с другой - числа. Решений в данном случае, несколько:
- Создать два класса токенов для операторов и числе, унаследовав их от общего класса Token . После этого приводить его с помощью dynamic_cast для извлечения кода числа, или кода оператора.
- То же, что в варианте выше, но вместо каста использовать двойную диспетчеризацию.
- В качестве токенов может быть std::function в которой будет храниться замыкание с необходимыми данными. Получать данные из замыкания можно с помощью посетителя.
- Использовать Boost.Any, или что-либо подобное.
- Использовать обычную структуру с полями для каждого вида данный и флагом типа.
Enum class TokenType {
Operator,
Number
};
class Token {
public:
Token(Operator) {}
TokenType Type() const { return TokenType::Operator; }
};
…
TEST_CLASS(TokenTests) {
public:
TEST_METHOD(Should_get_type_for_operator_token) {
Token opToken(Operator::Plus);
Assert::AreEqual(TokenType::Operator, opToken.Type());
}
};
Добавив метод ToString для перечисления TokenType и подправив аналогичный метод для самого токена, заставим всё компилироваться, а тесты проходить. Напишем следующий тест из списка.
TEST_METHOD(Should_get_type_for_number_token) {
Token numToken(1.2);
Assert::AreEqual(TokenType::Number, numToken.Type());
}
Он не проходит. Примени трансформацию (constant → scalar) для класса токена.
Class Token { public: Token(Operator) :m_type(TokenType::Operator) {} Token(double) :m_type(TokenType::Number) {} TokenType Type() const { return m_type; } private: TokenType m_type; };
- Создать токен с оператором и получить его тип.
- Создать токен с числом и получить его тип.
- Создать токен с оператором и получить этот оператор.
- Создать токен с числом и получить это число.
TEST_METHOD(Should_get_operator_code_from_operator_token) {
Token token(Operator::Plus);
Assert::AreEqual
Для удобства преобразования токена к нужному типу будем использовать оператор неявного приведения.
Class Token {
public:
Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {}
operator Operator() const { return m_operator; }
…
Operator m_operator;
};
Аналогично напишем тест для числового токена.
TEST_METHOD(Should_get_number_value_from_number_token) {
Token token(1.23);
Assert::AreEqual
Так как в токене не может одновременно храниться и оператор, и число, то их поля можно объединить в union . Также добавим проверку на операцию приведения к неверному типу.
Token
class Token {
public:
Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {}
Token(double num) :m_type(TokenType::Number), m_number(num) {}
TokenType Type() const { return m_type; }
operator Operator() const {
if(m_type != TokenType::Operator) throw std::logic_error("Should be operator token.");
return m_operator;
}
operator double() const {
if(m_type != TokenType::Number) throw std::logic_error("Should be number token.");
return m_number;
}
private:
TokenType m_type;
union {
Operator m_operator;
double m_number;
};
};
inline std::wstring ToString(const Token &token) {
switch(token.Type()) {
case TokenType::Number: return std::to_wstring(static_cast
Все тесты, относящиеся к токену проходят, можно восстановить предыдущие тесты и убедиться, что ничего не сломалось. Последний тест всё так же не проходит. Приступим к его исправлению.
- В ответ на строку с цифрой должен возвращаться токен с числом.
- В ответ на строку с числом с плавающей точкой должен возвращаться токен с этим числом.
- В ответ на строку с простым выражением должен возвращаться список соответствующих токенов.
- Пробелы между числами и операторами должны игнорироваться.
If(expr >= "0" && expr <= "9") {
return{ (double) expr - "0" };
}
return{ static_cast
Выгладит пока что не очень симпатично, но тест проходит.
- В ответ на строку с цифрой должен возвращаться токен с числом.
- В ответ на строку с числом с плавающей точкой должен возвращаться токен с этим числом.
Вспомним, что в стандартной библиотеке C есть такие функции, как isdigit , проверяющая, что данный символ является цифрой и atof , преобразующая строку в число, а также их аналоги для wchar_t . Применим (expression → function). После этого небольшого изменения данный тест также начал проходить.
Inline Tokens Tokenize(std::wstring expr) {
const wchar_t *current = expr.c_str();
if(!*current) return{};
if(iswdigit(*current)) return{ _wtof(current) };
return{ static_cast
После этого можно приступить и к более сложным тестам. Попробуем обработать полюс и число одновременно.
TEST_METHOD(Should_tokenize_plus_and_number) {
Tokens tokens = Lexer::Tokenize(L"+12.34");
AssertRange::AreEqual({ Token(Operator::Plus), Token(12.34) }, tokens);
}
Тест не компилируется, так как не хватает оператора сравнения для токена. Исправим это, теперь тест просто не проходит. Для начала сделаем небольшой рефакторинг. Добавим переменную result , в которую будем помещать токены.
Inline Tokens Tokenize(std::wstring expr) {
Tokens result;
const wchar_t *current = expr.c_str();
if(!*current) return result;
if(iswdigit(*current)) {
result.push_back(_wtof(current));
}
else {
result.push_back(static_cast
Теперь заставить пройти тест довольно просто: применим трансформацию (if → while). Можно было бы использовать рекурсию, но я решил целенаправленно делать не рекурсивный алгоритм.
Inline Tokens Tokenize(std::wstring expr) {
Tokens result;
const wchar_t *current = expr.c_str();
while(*current) {
if(iswdigit(*current)) {
wchar_t *end = nullptr;
result.push_back(wcstod(current, &end));
current = end;
}
else {
result.push_back(static_cast
Функция wcstod делает то же самое, что и _wtof , но также возвращает указатель на следующий за числом символ в строке. Так как все операторы на данный момент состоят из одного символа, то во втором случае просто передвигаем указатель на текущий символ на одну позицию вперёд. Как видим, теперь все тесты проходят.
- В ответ на строку с простым выражением должен возвращаться список соответствующих токенов.
- Пробелы между числами и операторами должны игнорироваться.
TEST_METHOD(Should_skip_spaces) {
Tokens tokens = Lexer::Tokenize(L" 1 + 12.34 ");
AssertRange::AreEqual({ Token(1.0), Token(Operator::Plus), Token(12.34) }, tokens);
}
Применим (unconditional → if) добавив проверку на то, что символ является оператором.
While(*current) {
if(iswdigit(*current)) {
wchar_t *end = nullptr;
result.push_back(wcstod(current, &end));
current = end;
}
else if(*current == static_cast
На данном этапе проведём рефакторинг данной функции. Выделим логику в отдельный класс и разобьём на отдельный методы. Поместим этот класс в пространство имён Detail чтобы не засорять публичный интерфейс лексера. Теперь функция Tokenize просто будет служить фасадом для модуля лексера.
Inline Tokens Tokenize(const std::wstring &expr) {
Detail::Tokenizer tokenizer(expr);
tokenizer.Tokenize();
return tokenizer.Result();
}
Класс Detail::Tokenizer
namespace Detail {
class Tokenizer {
public:
Tokenizer(const std::wstring &expr) : m_current(expr.c_str()) {}
void Tokenize() {
while(!EndOfExperssion()) {
if(IsNumber()) {
ScanNumber();
}
else if(IsOperator()) {
ScanOperator();
}
else {
MoveNext();
}
}
}
const Tokens &Result() const { return m_result; }
private:
bool EndOfExperssion() const { return *m_current == L"\0"; }
bool IsNumber() const { return iswdigit(*m_current) != 0; }
void ScanNumber() {
wchar_t *end = nullptr;
m_result.push_back(wcstod(m_current, &end));
m_current = end;
}
bool IsOperator() const { return *m_current == static_cast
Как видно, извлечение класса сделало код гораздо понятнее. Без тестов такой рефакторинг был бы, как минимум, рискованным. Теперь добавим поддержку скобок и остальных операторов.
TEST_METHOD(Should_tokenize_complex_experssion) {
Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)");
AssertRange::AreEqual({
Token(1), Token(Operator::Plus), Token(2), Token(Operator::Mul), Token(3), Token(Operator::Div),
Token(Operator::LParen), Token(4), Token(Operator::Minus), Token(5), Token(Operator::RParen)
}, tokens);
}
Добавим необходимые операторы к перечислению Operator , чтобы заставить тест компилироваться.
Enum class Operator: wchar_t {
Plus = L"+",
Minus = L"-",
Mul = L"*",
Div = L"/",
LParen = L"(",
RParen = L")",
};
Тест не проходит. Чтобы это исправить необходимо всего лишь изменить метод IsOperator класса Tokenizer .
Bool IsOperator() const {
auto all = { Operator::Plus, Operator::Minus, Operator::Mul, Operator::Div, Operator::LParen, Operator::RParen };
return std::any_of(all.begin(), all.end(), (Operator o) {return *m_current == static_cast
Все тесты проходят и можно приступить к написанию парсера. Ниже приводится весь исходный код на данный момент.
Interpreter.h
#pragma once;
#include
InterpreterTests.cpp
#include "stdafx.h"
#include "CppUnitTest.h"
#include "Interpreter.h"
namespace InterpreterTests {
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
using namespace Interpreter;
using namespace std;
namespace AssertRange {
template
Примеры кода приведены на Python, однако подробные пояснения позволят читателю использовать для реализации любой другой удобный язык. В качестве интерпретируемого языка выбран Pascal, однако и здесь вы не будете ограничены - можно обратиться к любому другому языку, с семантикой которого вы хорошо знакомы.
Если вы не знаете, как работает компилятор, то вы не знаете, как работает компьютер. И если вы не уверены на 100%, что знаете, как работает компилятор, то вы не знаете, как он работает. - Стив Йиг
Небольшой ликбез перед прочтением. Компилятор - программа, которая переводит (транслирует) исходный код на языке программирования (высокого уровня) на язык, «более понятный компьютеру» (низкоуровневый). При этом программа сначала полностью транслируется, а затем выполняется. Интерпретатор - такой же транслятор, но выполняющий инструкции «на лету» (пооператорно, построчно), то есть без предварительной компиляции всего кода.
Различие между компилятором и интерпретатором
Почему вам нужно создать свой интерпретатор:
- Написать компилятор - значит задействовать и/или развить сразу несколько различных технических навыков. Причем навыков, которые окажутся полезными в программировании вообще, а не только при написании трансляторов.
- Вы станете чуть ближе к разгадке тайны, как же все-таки работают компьютеры. Компиляторы и интепретаторы - это магия. И нужно чувствовать себя комфортно при работе с этой магией.
- Вы сможете создать собственный язык программирования, восполняющий видимые вам недостатки существующих. А это, во-первых, сейчас модно, а во-вторых, при достаточном везении вы обретете мировую известность.
- Да ну и чем вам еще сейчас можно заняться? (Кстати, мы уже предлагали вам несколько вариантов и .)
Что приятно, статьи подробно иллюстрируются. Создается впечатление, что автор перед вами ведет настоящую лекцию. Вот, например, одна из синтаксических диаграмм:
В конце каждой части руководства дается несколько задач для самостоятельной реализации и список полезных книг для более полного изучения вопроса. Итак, теперь приступайте к чтению:
Часть 1 . Основные понятия, разбиение на токены и сложение однозначных чисел.
Часть 2 . Обработка пробельных символов, многозначные числа.
Часть 3 . Синтаксические диаграммы, одиночные умножение и деление.
Часть 4. Множественные умножения и деления, форма Бэкуса-Наура.
Часть 5 . Калькулятор с произвольным числом операций, ассоциативность и порядок выполнения операторов.
Часть 6 . Заканчиваем калькулятор: произвольный уровень вложенности.