Началось (и закончилось) это всё как лаба по Vertallerbouw (построение компилеров), сдана, доцент в восторге. Это уже вторая моя прога более 20 строк на Haskell, из которой можно почерпнуть базовые приёмы.

Код не блещет, можно лучше. Отсылать буду частями, комментируя отдельные участки. Постараюсь разжевать подробно, пусть это и вызовет приторно сладкий привкус у знатоков, но для начинающих думаю будет полезно. Убедительная просьба писать замечания/улучшения после того как закончу.

И так: Simply

Simply это простой функциональный язык программирования со следующими свойствами:

•  Динамические типы -- это скорее недостаток     Но если вводить строгие типы + декомпозицию (patterns), то недалеко и до Haskell.
•  Ленивые вычисления -- конечно используя Haskell мы их получаем "в подарок", но интереса ради они были реализованы явно. Пока не будем думать о эффективности.
•  Higher order functions или всё это функция.
•  Традиционные для функциональных языков partial function application, т.е. передача не всех параметров функции, порождая новую функцию.
•  Static scoping, видимость функциями значений в своём (lexical) scope.

Simply работает только с целыми и действительными числами, а также с логическими значениями (true, false). Списков, строк и т.п. нет в целях простоты. Без структурной декомпозиции (голова:хвост) пробежаться по списку нельзя, а вводить "магические" built-in функции способные пробегаться по спискам как то не красиво.

Пример кода (чрезвычайно надуманный   ):


Первое что бросается в глаза это вычисления с функциями, такие как (sum + sum) приведёт к lambda(a, b, c, d). Оба операнда являются функциями с двумя аргументами, значит результат это новая функция, где (a, b) это аргументы первого операнда, а (c, d) аргументы второго. Вообще это удобно, хотелось бы видеть где нибудь в PHP 

Вызов функции выполняется через оператор ( arguments ), который на самом деле просто присваивает значения параметрам функции, что не приведёт к её немедленному исполнению. Только когда потребуется окончательное значение (например что бы напечатать на консоль), интерпретатор проверит для всех ли аргументов есть значение. Если да, то функция выполнится, иначе результат это функция (выводиться как "lambda(параметры)" ).

Видим что структура проги есть список LET определений, завершаемых одним return expression, который и скомбинирует все функции в некоторое окончательное значение. В языке всего две конструкции: if-else и with. Первое это условие, возвращающее значение одной из веток. Второе это подпрограмма (scoping), аналогичное выражениям let something in expression встречаемое в других функциональных языках. Подробнее об этом при рассмотрении формальной грамматики.

С языком определились, приступаем к формальной грамматике.

Для генерации parser'а воспользуемся parser generator'ом Happy. Этот генератор создаёт LALR(1) парсер, реализованный как recursive descent parser. Что это значит лучше почитать где нибудь в другом месте, просто запомним, что для грамматики Simply LALR(1) парсера с головой хватит. А вот то, что реализован он на функциях (recursive descent parser), потенциально может привести к переполнению стека. Именно по этому мы будем писать лево-рекурсивные правила грамматики, везде где только можно. При левой рекурсии стек не используется.

Синтаксис файла грамматики Happy почти идентичен yacc'у, так что всё будет знакомо. Всё что между { } как есть отсылается в код парсера. Там мы определяем все import'ы и название модуля. Далее декларируем "точки входа", это стартовые не-терминалы вместе с генерируемой функцией. В нашем случае их две, одна читает весь файл целиком, другая только выражения (используется позже shell'ом).



Мы хотим видеть нормальные ошибки, указывающие на строку и колонку, а не вылетать с убийственным (error "сообщение"). Для этого нужно скрыть как правильный результат, так и ошибки в один тип, иными словами пишем монад. В нашем монаде будет скрыта инфа о позиции в файле и собственно строка на ввод. Подробнее об этом позже, сейчас просто скажем Happy, что все actions в грамматике возвращают значение скрытое в монаде P.



Сканер (lexer) тоже монадный, что позволяет нам "скрыть" ввод. Тип функции lexer будет:

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

Далее декларируем все токены, что могут появится на входе в парсер:


Видим их много    Первой строкой декларируем тип токенов, мы его уже видели в типе функции lexer. Далее идут все конструкторы, что бы распознать значение. Специальное значение $$ указывает на то, что конструктор принимает одно значение и его нужно использовать как значение токена (об этом позже). Без $$ значением токена будет он сам. Мы передаём в каждом токене его позицию в исходном файле для более подробных сообщениях об ошибках.

На этом месте лучше прерваться с определением формальной грамматики и стоит перейти к lexer'у, что будет зачитывать выше названные токены.

Сканнер традиционно пишется на регулярных выражениях. В Haskell 98 нет регулярных выражений, но они есть в regexp библиотеке, поставляемой вместе с GHC.

В целях обучения Haskell'у мы не будем выходить за пределы Haskell 98 и попытаемся реализовать сканнер в ручную. Это простая задача, небольшие сложности возникнут только при чтении действительных чисел, которые в самом сложном варианте могут быть "45.23Е-3".

Перед тем как приступить к lexer'у стоит взглянуть на упоминавшийся ранее монад P, т.к. именно в него мы всё и завернём.



ParseResult заворачивает результат парсера в два возможных значения: собственно прочтённая и построенная прога или ошибка. Наследуем от Show для дебагга, удобно выводить в Hugs результат.

Монад P определён всего единственным конструктором, скрывающим строку ввода, текущую позицию и результат парсера. Конечно монадом новый тип станет только после создания instance.



Всё, теперь доступны return, fail и do выражения, жизнь становится проще 

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


nextCol мы будем далее вызывать в сканнере при чтении каждого следующего символа, nextLine при чтении '\n'. Остальные функции печатают текущую позицию как строку, используемую при выводе ошибок. startPos позволяет нам создать позицию в самом начале заданного файла.

Всё, теперь приступим к самому сканнеру.

Когда продолжение? На самом интересном месте остановился 
(потом этот пост удалю)

это вы что-то напутали. Лучше уберите.. LALR - look ahead LR парсер, то есть он явно не рекурсивный и явно не нисходящий (descent).. Он как бы наоборот,  как все LR() - восходящий.

 

Это неправда.. Он как правило пишется на конечном автомате. Потому что регулярки получаются гораздо медленнее, и их используют только в простых сканерах.. Или где скорость неважна вообще..