Функциональные парсеры: различия между версиями

Задачей синтаксического анализа является построение дерева, описывающего структуру заданной строки. В функциональном языке мы можем определить тип данных <tt>Tree</tt> (дерево). Парсер может быть реализован посредством функции следующего типа:

type Parser = String -> Tree

Для разбора подструктур парсер может вызвать другие парсеры или рекурсивно самого себя. Этим вызовам необходимо обмениваться не только своими результатами, но и информацией о том, какая часть входной строки осталась необработанной. Поскольку это не может быть сделано при помощи глобальной переменной, необработанная часть входной строки должна быть частью результата работы анализатора. Два результата могут быть сгруппированы в кортеж. Более удачным определением для типа <tt>Parser</tt> является следующее:

type Parser = String -> (String, Tree)

Тип <tt>String</tt> определён в стандартнойстандартном вводноймодуле части<tt>Prelude</tt> как список символов. Однако, тип <tt>Tree</tt> ещё не определён. Тип возвращаемого дерева зависит от приложения. Поэтому лучше превратить тип анализатора в полиморфный тип, параметризируя его типом дерева разбора. Таким образом мы абстрагируемся от типа поступающего дерева разбора, заменяя его переменным типом <tt>а</tt>:

type Parser a = String -> (String, a)

Например, анализатор, возвращающий структуру типа <tt>Oak</tt> теперь имеет тип <tt>Parser Oak</tt>. Для деревьев разбора, представляющих структуру <tt>Expression</tt> (выражение) мы можем определить тип <tt>Expr</tt>, делая возможным разработку анализатора, возвращающего выражение: <tt>Parser Expr</tt>. Другим примером анализатора является функция, распознающая строку цифр и возвращающая число, представленное этой строкой, в качестве «дерева разбора». В этом случае данная функция имеет тип <tt>Parser Int</tt>.

До сих пор мы предполагали, что каждая строка может быть разобрана ровно одним способом. В общем случае это предположение не обязательно верно: одна строка может быть разобрана различными способами или может не существовать ни одного способа разбора строки. В качестве ещё одного усовершенствования определения типа мы допустим, что вместо одного дерева разбора (и связанной с ним необработанной частью строки) парсер возвращает список деревьев. Каждый элемент результата является списком, состоящим из дерева и части строки, оставшейся необработанной после разбора. Следовательно, более подходящим является следующее определение типа <tt>Parser</tt>:

type Parser a = String -> [(String, a)]

Этот метод называется «список благоприятных исходов», его описал Вадлер (Wadler) &nbsp;[5]. Он может быть использован в тех случаях, когда возможно применение поиска с возвратом. В учебнике Бёрда (Bird) и Вадлера (Wadler) он используется для решения комбинаторных задач, таких как задача о восьми ферзях &nbsp;[1]. Если необходимо получить только одно решение, а не все возможные, то вы можете взять голову списка благоприятных исходов. Благодаря отложенному вычислению, если требуется только первое значение, то не все элементы списка будут определены, так что потери эффективности не произойдетпроизойдёт. Отложенные вычисления позволяют использовать поиск с возвратом для получения первого решения.

Парсеры имеющий тип, описываемый нами до сих пор, работают со строками, которые являются списками символов. Однако, это не мешает допустить разбор строк, состоящих из элементов, отличных от символов. Можно предположить ситуацию, когда препроцессор подготавливает список лексем, который затем разбирается. Чтобы учесть этот случай, в качестве последнего усовершенствования типа парсера, мы снова абстрагируемся от типа — от типа элементов входной строки. Обозначив его <tt>а</tt>, а тип результата <tt>b</tt>, можно определить тип парсера следующим образом:

type Parser a b = [a] -> [([a], b)]

type Parser symbol result = [symbol] -> [([symbol], result)]