Как написать интерпретатор

Пишем простой интерпретатор на Haskell

Сегодня совместными усилиями мы с вами создадим простенький скриптовый язык программирования. В нем не будет массивов или условных операторов, зато будут целочисленные переменные и множество операций над ними. Писать, как вы уже поняли, будем на замечательном языке 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

TModifSet -> "="

TPlus -> "+"

Источник: eax.me

Категория: Программное обеспечение

Похожие статьи: