Смарт ТВ 

Пишем свой интерпретатор. Руководство по созданию интерпретатора языка Pascal на Python. Преимущества кастомных программ

В этой статье речь пойдет о довольно необычном проекте. Однажды меня посетило желание написать свой интерпретатор какого-нибудь скриптового языка и исполняющую машину для него. Просто для того, чтобы посмотреть, как оно внутри работает. Такая цель звучит не очень благородно и я отложил затею в долгий ящик, т.к. мне хотелось более полезной формулировки.
Как-то раз, один мой знакомый посетовал, что нужно написать скрипт автоматизации на 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. ({} → nil) Заменить отсутствие кода на код, использующий нулевое значение.
  2. (nil → constant) Заменить нулевое значение константой.
  3. (constant → constant+) Заменить простую константу более сложной (строку из одной буквы на строку из нескольких букв, к примеру).
  4. (constant → scalar) Заменить константу на переменную, или аргумент.
  5. (statement → statements) Добавить безусловный оператор (break, continue, return и подобное).
  6. (unconditional → if) Разбить поток выполнения с помощью условного оператора.
  7. (scalar → array) Заменить переменную/аргумент массивом.
  8. (array → container) Заменить массив более сложным контейнером.
  9. (statement → recursion) Заменить выражение рекурсией.
  10. (if → while) Заменить условный оператор циклом.
  11. (expression → function) Заменить выражение функцией.
  12. (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 конструкторов с &&.

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

В целом там комментарий хороший и вдумчивый.

Т.е. комментарий вообще-то хороший, правильный. На тему "парсеров". Но не совсем в "тему статьи".

Ведь статья как раз и призвана показать как сделать так, чтобы:
Пользователи могут считать , что генератор безошибочно переводит специфицикацию в код.

Ну вот "я так вижу".



Некоторое время назад мне захотелось написать свой небольшой интерпретируемый скриптовый язык, просто ради фана, не ставя перед собой каких-либо серьезных задач. Я тогда активно читал известную волшебную книгу 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 по адресу

Сегодня совместными усилиями мы с вами создадим простенький скриптовый язык программирования. В нем не будет массивов или условных операторов, зато будут целочисленные переменные и множество операций над ними. Писать, как вы уже поняли, будем на замечательном языке Haskell . Также мы познакомимся с «компиляторами компиляторов» Alex и Happy.

Вспоминаем теоретическую часть

Каким образом исходный код программы преобразуется в исполняемый файл? Это происходит в несколько шагов/этапов. Выходные данные, полученные на шаге N, служат входными данными для шага N+1. На вход такому «конвейеру» байт за байтом подается исходный код, а на выходе получается программа. Что же это за этапы?

Первый этап — это лексический анализ . На этом шаге код программы, скажем:

разбивается на лексемы (строки «foo», «=», «+», …), их которых затем получается последовательность токенов :

[ ИДЕНТ "foo", РАВНО, ИДЕНТ "foo", ПЛЮС, 1, ТОЧКА_С_ЗАПЯТОЙ ]

То есть, лексический анализатор разбивает программу на элементарные составные части — операторы, ключевые слова, имена переменных и тп. Также на этапе лексического анализа опционально удаляются комментарии, а запись 0b1101 преобразуется в число 13.

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

Дерево разбора представляет собой структуру наподобие следующих:

Рассмотрим левое дерево. Читая его снизу вверх, получим «взять значение переменной a и число 1, сложить их, а затем присвоить результат переменной a», что в точности описывает поведение программы. Правое дерево наглядно демонстрирует, что при его построении были учтены приоритеты операторов, то есть сначала производятся умножение и деление и только потом сложение.

Также вы можете заметить, что ни одно из деревьев не содержит токена «точка с запятой». Вообще-то, узлы дерева могут содержать не токены, а какие-то другие типы данных. Или токены, но не те, что пришли от лексического анализатора. Скажем, инкремент (оператор ++) может быть преобразован в дерево, представленное слева.

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

Наш интерпретатор не будет генерировать никакого кода, работая напрямую с синтаксическим деревом. Семантика будет проверяться прямо во время интерпретации. Оптимизация производиться не будет.

Поскольку редкий компилятор (интерпретатор, транслятор, …) обходится без лексического и синтаксического анализатора, была написана масса генераторов этих самых анализаторов. «Компиляторы компиляторов» экономят время и силы, а также существенно сокращают количество багов в создаваемых с их помощью компиляторах. Мы воспользуемся генераторами Alex и Happy . Устанавливаются они, как и следовало ожидать, с помощью утилиты cabal.

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

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

Код лексического анализатора находится в файле Lex.x. Он слишком объемен, чтобы приводить его здесь целиком, но при этом не содержит какой-то особой магии. Мы просто определяем тип данных «токен»:

data Token = TInt Int | TIdent String
| TPlus | TMinus | TMul | TDiv | TMod
| ...

instance Show Token where
show x = case x of
TInt i -> show i
TIdent s -> s
TModifSet -> "="
TPlus -> "+"
TMinus -> "-"
TMul -> "*"
TDiv -> "/"
TMod -> "%"
...

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

Если вы не знаете, как работает компилятор, то вы не знаете, как работает компьютер. И если вы не уверены на 100%, что знаете, как работает компилятор, то вы не знаете, как он работает. - Стив Йиг

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

Различие между компилятором и интерпретатором

Почему вам нужно создать свой интерпретатор:

  1. Написать компилятор - значит задействовать и/или развить сразу несколько различных технических навыков. Причем навыков, которые окажутся полезными в программировании вообще, а не только при написании трансляторов.
  2. Вы станете чуть ближе к разгадке тайны, как же все-таки работают компьютеры. Компиляторы и интепретаторы - это магия. И нужно чувствовать себя комфортно при работе с этой магией.
  3. Вы сможете создать собственный язык программирования, восполняющий видимые вам недостатки существующих. А это, во-первых, сейчас модно, а во-вторых, при достаточном везении вы обретете мировую известность.
  4. Да ну и чем вам еще сейчас можно заняться? (Кстати, мы уже предлагали вам несколько вариантов и .)

Что приятно, статьи подробно иллюстрируются. Создается впечатление, что автор перед вами ведет настоящую лекцию. Вот, например, одна из синтаксических диаграмм:

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

Часть 1 . Основные понятия, разбиение на токены и сложение однозначных чисел.

Часть 2 . Обработка пробельных символов, многозначные числа.

Часть 3 . Синтаксические диаграммы, одиночные умножение и деление.

Часть 4. Множественные умножения и деления, форма Бэкуса-Наура.

Часть 5 . Калькулятор с произвольным числом операций, ассоциативность и порядок выполнения операторов.

Часть 6 . Заканчиваем калькулятор: произвольный уровень вложенности.