£ сс

token k xs k == take n xs = [ (drop n xs, k) ]

otherwise= []

where n = length k

Также как и в случае с функцией symbol, мы параметризировали эту функцию распознаваемой строкой, превращая её таким образом в семейство функций. Конечно же, область применения этой функции не ограничена строками символов. Однако, нам необходима проверка на равенство для типа входной строки; типом token является следующее:

tokenEq [s] => [s] -> Parser s [s]

Функция token является обобщением функции symbol, поскольку она распознаёт более одного символа.

Другим обобщением symbol является функция, которая может возвращать различные результаты разбора, в зависимости от входных данных. Функция satisfy является примером такого обобщения. Там, где в функции symbol находится проверка на равенство заданному символу, в satisfy может быть указан произвольный предикат. Функция satisfy, таким образом, опять же является семейством функций-анализаторов. Здесь приведено её определение с использованием списочной нотации:

satisfy satisfy p [] satisfy p (x:xs)

(s -> Bool) -> Parser s s

[(xs, x) p x]

Упражнение 1. Поскольку функция satisfty является обобщением функции symbol, функция symbol может быть определена как частный случай satisfy. Как это можно сделать?

В книгах по теории грамматик пустая строка часто называется «epsilon». Следуя этой традиции, мы определим функцию epsilon, «разбирающую» пустую строку. Она не принимает ничего на вход и соответственно всегда возвращает пустое дерево разбора и неизменённые входные данные. В качестве результирующей величины может быть использован кортеж, состоящий из 0 элементов: () является единственным значением типа ().

epsilon:

epsilon xs =

Parser s ( ) [(xs, ())]

Её разновидностью является функция succeed, которая также не принимает ничего на вход, но всегда возвращает данное, фиксированное значение (или «дерево разбора», если можно назвать результат обработки нуля символов деревом разбора...):

succeed

succeed v xs =

r -> Parser s r [(xs, v)]

Конечно же, функция epsilon может быть определена через функцию succeed:

epsilon :: Parser s () epsilon = succeed ()

Двойственной по отношению к функции succeed является функция fail, которая не распознаёт ни один символ входной строки. Она всегда возвращает пустой список благоприятных исходов:

fail:: Parser s r

fail xs = []

Позже нам понадобится этот тривиальный парсер в качестве нейтрального элемента для функции foldr. Обратите внимание на отличие от функции epsilon, которая имеет один элемент в своём списке благоприятных исходов (хотя и пустой).

4. КОМБИНАТОРЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

Используя элементарные парсеры из предыдущей части, можно сконструировать парсеры для терминальных символов грамматики. Более интересными являются синтаксические анализаторы для нетерминальных символов. Конечно, их можно написать вручную, но более удобно сконструировать их путём частичной параметризации функций высшего порядка.

Важными операциями над парсерами являются последовательное и параллельное соединение. Мы создадим для них две функции, которые для удобства обозначения определены как операторы: <*> для последовательного соединения и <\> для параллельного соединения. Приоритеты этих операторов определены таким образом, чтобы минимизировать использование скобок в практических ситуациях:

infixr 6 <*> infixr 4 <>

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

В определениях, приведённых ниже, функции действуют на парсеры pj и p2. Кроме параметров pj и p2, функция действует на строку, которую можно рассматривать как строку, разбираемую парсером, являющимся результатом комбинированияpj иp2.

Для начала напишем определение оператора <*>. Для последовательного соединения сначала к входным данным должен быть применён р1. После этого р2 применяется к оставшейся части строки, указанной в результате. Поскольку р1 возвращает список решений, мы используем списочную запись, согласно которой р2 применяется ко всем остаточным строкам в списке:

(<*>)

(p1 <*> p2) xs

:: Parser s a -> Parser s b -> Parser s (a, = [(xs2, (v1, v2)) (xs1, v1) <- p1 xs,

(xs2, v2) <- p2 xs1]

Результатом функции является список всех возможных кортежей (vjt с оставшейся строкой xs2, где vj - это дерево разбора, полученное с помощью pj, и где остаток строки xsj используется в качестве входных данных для p2, в результате работы которого получаются v2 и xs2.

Кроме «последовательного соединения» нам необходим комбинатор синтаксического разбора для представления «выбора». Для этого у нас есть оператор комбинатора синтаксического анализа <\>: