Функциональные парсеры

Информация об авторе
Автор:	Ерун Фоккер (Jeroen Fokker)
Место работы:	Факультет вычислительной техники, Университет Утрехта
Электронный адрес:	jeroen@cs.ruu.nl
Адрес оригинала статьи:	Functional Parsers

Аннотация

В неформальном виде изложен метод «список благоприятных исходов», используемый для написания синтаксических анализаторов на функциональном языке с отложенными вычислениями Gofer. Для написания синтаксических анализаторов выражений с вложенными скобками и операторами используется разрабатываемая библиотека функций высшего порядка (известных как «комбинаторы синтаксического анализа»). Метод применён сам к себе для написания синтаксического анализатора грамматик, что позволяет получить синтаксический анализатор для языка, порождаемого такой грамматикой. Текст сопровождается упражнениями, решения которых приведены в конце статьи.

Ключевые слова́: парсер, список благоприятных исходов, синтаксический анализ, денотационная семантика.

Введение

Эта статья представляет собой неформальное введение в написание синтаксических анализаторов на ленивом функциональном языке с использованием «комбинаторов синтаксического анализа» (parser combinators). Большинство методов было описано Бурджем (Burge) [2], Вадлером (Wadler) [5] и Хаттоном (Hutton) [3]. В последнее время, в связи с комбинаторами синтаксического анализа [6, 7], стало довольно популярным использование так называемых монад. Однако, чтобы показать, что никакого волшебства в использовании комбинаторов синтаксического анализа нет, мы не будем пользоваться монадами в этой статье. Тем не менее, вам стоит познакомиться с ними, поскольку монады составляют полезное обобщение описанных здесь приёмов.

В данной статье мы придерживаемся таких конструкций стандартного функционального языка как функции высшего порядка, списки и алгебраические типы. Все программы написаны на языке Gofer [4]. В нескольких местах встречаются списочные структуры (list comprehensions), но их использование не является существенными и они могут быть легко заменены с помощью функций map, filter и concat. Типовые классы использованы только для перегрузки равенства и арифметических операций.

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

В разделе 4 представлены первые комбинаторы синтаксического анализа, которые могут быть использованы для последовательного или параллельного комбинирования анализаторов. В разделе 5 дано определение некоторых функций, позволяющих вычислять значение в процессе синтаксического анализа. Вы можете использовать эти функции для того, что традиционно называется «определением семантических функций»: некоторый полезный смысл может быть связан с синтаксическими структурами. В качестве примера, в разделе 6 мы строим синтаксический анализатор для строк, состоящих из согласующихся скобок, где вычисляются разные семантические величины: дерево, описывающее структуру, и целое число, показывающее глубину вложенности.

В разделах 7 и 8 мы рассматриваем новые комбинаторы синтаксического анализа, которые не только облегчат нам жизнь в будущем, но и их определения послужат хорошими примерами использования комбинаторов синтаксического анализа. Реальное приложение — разработанный парсер арифметических выражений — приведено в разделе 9. Далее приведено обобщение парсера для случая произвольного числа уровней старшинства (precedence level). Это сделано без указания приоритетов операторов с помощью чисел, и без использования индексов и многоточий.

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

Тип Parser

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

type Parser = String -> Tree

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

type Parser = String -> (String, Tree)

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

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

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

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

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

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

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

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

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

или так, если вы предпочитаете кратким идентификаторам более выразительные:

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

Мы будем использовать это определение типа в оставшейся части данной статьи.

Простейшие парсеры

Мы начнём с довольно простого, дав определение функции разбора, которая распознаёт символ «а». В этом случае типом символов входной строки будет Char и в качестве «дерева разбора» мы также просто используем Char:

symbola :: Parser Char Char 
symbola [] = []
symbola (x:xs) | x == ‘a’   = [(xs, ‘a’)]
               | otherwise  = []

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

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

symbol :: Eq s => s -> Parser s s
symbol a [] = []
symbol a (x:xs) | a == x    = [(xs, x)]
                | otherwise = []

Как обычно существует несколько способов определить ту же самую функцию. Если вам нравятся списки, то вы возможно предпочтете следующее определение:

symbol a []     = []
symbol a (x:xs) = [(xs, a) | a == x]

В языке Gofer список без генераторов, лишь с условием, определён как пустой или состоящий из одного элемента, в зависимости от условия.

Функция symbol — это функция, которая возвращает парсер для заданного символа. Парсер, в свою очередь также является функцией. Вот почему в определении функции symbol появилось два параметра.

Теперь мы определим некоторые простейшие парсеры, которые могут выполнять работу, традиционно выполняемую лексическими анализаторами. Например, полезным является парсер, распознающий фиксированную строку символов, такую как «begin» или «end». Мы назовем эту функцию token.

token k xs | k == take n xs = [ (drop n xs, k) ]
           | otherwise      = []
	where n = length k

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

token :: Eq [s] => [s] -> Parser s [s]

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

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

satisfy :: (s -> Bool) -> Parser s s
satisfy p []     = []
satisfy p (x:xs) = [(xs, x) | p x] 

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

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

epsilon :: Parser s ( ) 
epsilon xs = [(xs, ())]

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

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

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

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

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

fail :: Parser s r
fail xs = []

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

Комбинаторы синтаксического разбора

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

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

infixr 6 <*>
infixr 4 <|>

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

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

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

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

Результатом функции является список всех возможных кортежей (v1, v2) с оставшейся строкой xs2, где v1 — это дерево разбора, полученное с помощью p1, и где остаток строки xs1 используется в качестве входных данных для p2, в результате работы которого получаются v2 и xs2.

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

(<|>) :: Parser s a -> Parser s a -> Parser s a
(p1 <|> p2) xs = p1 xs ++ p2 xs

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

Упражнение 2. Определяя приоритет оператора <|>, с использованием ключевого слова infixr мы также указали, что оператор является правоассоциативным. Почему это более удачное решение по сравнению с левой ассоциативностью?

Результатом применения комбинаторов синтаксического анализа является снова парсер, который может быть соединён с другими парсерами. Деревья разбора, получаемые в результате, представляют собой сложные кортежи, отражающие способ, которым были соединены парсеры. Таким образом, термин «дерево разбора» является действительно подходящим. Например парсер р, где

p = symbol 'a' <*> symbol 'b' <*> symbol 'c'

имеет тип Parser Char (Char, (Char, Char)).

Несмотря на то, что кортежи ясно описывают структуру дерева разбора, существует трудность, заключающаяся в том, что мы не можем соединять парсеры случайным образом. Например, мы не можем параллельно соединить парсер p, описанный ранее и symbol ’a’, поскольку последний имеет тип Parser Char Char, а параллельно можно соединять только парсеры одного типа. Хуже того, невозможно рекурсивно соединить парсер с самим собой, так как это приведёт к возникновению типов, представляющих собой бесконечно вложенные кортежи. Нам необходимо иметь способ изменения структуры дерева разбора, возвращаемого данным парсером.

Преобразователи парсеров

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

Первым преобразователем парсеров является sp. Он опускает пробелы в строке, поступающей на вход, затем применяет заданный парсер:

sp :: Parser Char a -> Parser Char a
sp p =	p . dropWhile (== ' ')

или если вы предпочитаете функциональные определения:

sp = (. dropWhile (== ' '))

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

just :: Parser s a -> Parser s a
just p	= filter (null.fst) . p

Упражнение 3. Дайте определение функции just, используя списки вместо функции filter.

Наиболее важным преобразователем парсеров является тот, который выполняет преобразование парсера, изменяющее возвращаемое им значение. Мы определим такой преобразователь как оператор <@, применяющий заданную функцию к результирующим деревьям разбора заданного парсера. Мы выбрали символ для того, чтобы вы могли произносить это как «apply» (применять); стрелка указывает в направлении от функции. Для заданных парсера р и функции f оператор <@ возвращает парсер, который делает то же, что и р, но кроме того применяет f к результирующему дереву разбора. Легче всего это можно определить, используя понятие списка:

infixr 5 <@
(<@) :: Parser s a -> (a -> b) -> Parser s b
(p <@ f) xs = [(ys, f v) | (ys, v) <- p xs]

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

digit :: Parser Char Int
digit = satisfy isDigit <@ f
	    where f c = ord c — ord '0'

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

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

Мы зарезервировали слово «parser» для функции, которая возвращает все варианты разбора, сопровождаемые соответствующими им необработанными частями строк. Поэтому давайте определим новый тип для функции, которая разбирает текст, гарантирует получение пустой необработанной части строки, выбирает первое решение из списка и возвращает лишь дерево разбора (отбрасывая необработанную часть строки, поскольку известно, что она пустая на данном этапе). Функциональная программа для преобразования парсера в подобный «детерминированный синтаксический анализатор» является более лаконичной и удобочитаемой, чем определение, приведённое ранее:

type DetPars symbol result = [symbol] -> result

some :: Parser s a -> DetPars s a
some p	= snd . head . just p

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

Согласование скобок

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

parens	::	Parser Char ???
parens	=	(symbol '(' <*>
			 parens <*>
			 symbol ')' <*>
			 parens) <|> epsilon

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

data Tree		=	Nil | Bin (Tree, Tree)

Теперь мы можем добавить «семантические функции» к парсеру:

parens	::	Parser Char Tree
parens	=	(symbol '(' <*>
			 parens <*>
			 symbol ')' <*>
			 parens)	<@ (\(_, (x, (_, y))) -> Bin (x, y)) <|>
			 epsilon	<@ const Nil

Довольно непонятный текст \(_, (x, (_, y))) является лямбда образцом, описывающим функцию с первым параметром, являющимся кортежём, содержащим четыре части первой альтернативы, из которых лишь вторая и четвертая имеют значение.

Упражнение 4. Почему в лямбда образце вместо кортежа, у которого второй элемент является кортежём, у которого второй элемент является кортежём, мы не используем кортеж, состоящий из четырех элементов?

Упражнение 5. Почему нужна функция const, которая определена в стандартном модуле Prelude как const x y = x? Вы можете написать вторую альтернативу более лаконично без использования const и <@?

В лямбда образце символы подчеркивания используются в качестве «заполнителя» для деревьев разбора, возвращаемых symbol ‘(‘ и symbol ‘)’, которые не нужны в результате. Для того, чтобы не пришлось использовать эти сложные кортежи, возможно было бы легче отсеять деревья разбора для символов на более раннем этапе. Для этого мы вводим два вспомогательных комбинатора синтаксического разбора, которые пригодятся во многих ситуациях. Эти операторы ведут себя также как и <*>, за исключением того, что они отсеивают результат одного из двух парсеров, являющихся их аргументами:

(<*)		::	Parser s a -> Parser s b -> Parser s a
p <* q	=	p <*> q <@ fst

(*>)		::	Parser s a -> Parser s b -> Parser s b
p *> q	=	p <*> q <@ snd

Мы можем использовать эти новые комбинаторы синтаксического анализа для улучшения удобочитаемости парсера parens:

open		=	symbol '('
close	=	symbol ')'

parens	::	Parser Char Tree
parens	=	(open *> parens <* close) <*> parens <@ Bin <|> succeed Nil

Путём благоразумного выбора приоритетов используемых операторов:

infixr 6 <*>, <*, *>
infixl 5 <@
infixr 4 <|>

мы сводим к минимуму число необходимых скобок.

Упражнение 6. Скобки вокруг open > parens <* close в первой альтернативе необходимы несмотря на наши продуманные приоритеты. Что случится если мы опустим их?

Изменяя функцию, используемую после <@ («семантическую функцию»), мы можем получить нечто отличающееся от деревьев разбора. В качестве примера мы напишем парсер, подсчитывающий глубину вложенности скобок:

nesting	::	Parser Char Int
nesting	=	(open *> nesting <* close) <*> nesting <@ f <|> succeed 0
			where f (x, y) = (1 + x) `max` y

Если интерес представляют дополнительные варианты, то, возможно, стоит превратить семантическую функцию и величину, возвращаемую в «пустом» случае в два дополнительных параметра. Функция высшего порядка foldparens производит разбор вложенных скобок, используя данную семантическую функцию и константу соответственно, после разбора одной из двух альтернатив:

foldparens		::	((a, a) -> a) -> a -> Parser Char a
foldparens f e		=	p
					where	p = (open *> p <* close) <*> p <@ f <|>
							succeed e

Упражнение 7. Функция foldparens является обобщением функций parens и nesting. Напишите последние две как частный случай первой.

Пример использования nesting может выглядеть следующим образом:

? just nesting "()(())()"
[(2, [])]
? just nesting "())"
[]

В самом деле nesting лишь распознает корректно построенные вложенные скобки и вычисляет глубину вложенности в процессе разбора.

Упражнение 8. Что случится, если мы опустим преобразователь just в этих примерах?

Дополнительные комбинаторы синтаксического анализа

Несмотря на то, что в принципе вы можете построить парсеры для любого контекстно-свободного языка используя комбинаторы <*> и <|>, на практике проще иметь в распоряжении несколько дополнительных комбинаторов синтаксического анализа. В традиционных грамматических формализмах для описания, например, необязательных или повторяющихся конструкций также используются дополнительные символы. Например рассмотрим формализм БНФ, в котором изначально могли быть использованы только последовательное и параллельное соединения (обозначаемые размещение рядом и вертикальными линиями соответственно), а позже он был расширен таким образом, чтобы учитывать также повторение, обозначаемое звёздочками.

Очень просто сделать новые комбинаторы для расширений, подобных этому. В качестве первого примера мы рассмотрим повторение. Для данного парсера структуры, mаny создает разборщик для 0 или более вхождений этой структуры:

many		::	Parser s a -> Parser s [a]
many p	=	p <*> many p <@ list <|> succeed []

Дополнительная функция list является некаррированной версией конструктора списков:

list (x, xs)	=	x : xs

Рекурсивное определение парсера вытекает из рекурсивной структуры списков. Возможно даже лучшим является определение, в котором вместо succeed используется парсер epsilon.

many		::	Parser s a -> Parser s [a]
many p	=	p <*> many p <@ (\(x, xs) -> x : xs) <|> epsilon <@ (\_ -> [])

Упражнение 9. Чтобы достигнуть симметричности, мы можем также постараться и избежать оператора <@ в обоих альтернативах. Ранее мы определили оператор <* как сокращение применения <@ fst к результату, возвращаемому оператором <*>. В функции many результат <*> также подвергается последующей обработке. Определите служебную операцию <:*> для данного случая и используйте её для ещё большего упрощения определения many.

Порядок расположения альтернатив влияет только на порядок, в котором решения располагаются в списке благоприятных исходов.

Упражнение 10. Предположим, что парсер many (symbol ‘a’) применён к строке «ааа». В каком порядке появятся четыре возможных разбора в списке благоприятных исходов?

Пример, показывающий как комбинатор many может быть использован для разбора натурального числа:

natural	::	Parser Char Int
natural	=	many digit <@ foldl f 0
			where f a b = a * 10 + b

Определенный таким образом, парсер natural принимает пустую входную строку также за число. Если это нежелательно, то лучше использовать комбинатор синтаксического анализа many1, который допускает одно или более вхождений структуры.

Упражнение 11. Определите комбинатор синтаксического анализа many1.

Другой комбинатор, с которым вы возможно знакомы из других формализмов, это комбинатор option. Построенный парсер возвращает список из нуля или одного элемента в зависимости от того, была ли распознана структура или нет.

option	::	Parser s a -> Parser s [a]
option p	=	p <@ (\x -> [x]) <|> epsilon <@ (\x -> [])

По эстетическим соображениям мы использовали epsilon в данном определении; вторую альтернативу можно было написать другим способом — succeed [].

Комбинаторы many, many1 и option являются классическими структурами, входящими в состав компилятора, но нет необходимости оставлять всё как есть. Например, во многих языках, структуры часто заключены между двумя ничего не значащими символами, чаще всего это некоторого рода скобки. Для этого мы создадим комбинатор синтаксического анализа pack. Для заданных парсеров для открывающего символа, основной части и закрывающего символа он строит анализатор для вложенной основной части:

pack			::	Parser s a -> Parser s b -> Parser s c -> Parser s b
pack s1 p s2	=	s1 *> p <* s2

Особыми случаями данного комбинатора являются следующие:

parenthesized p	=	pack (symbol '(') p (symbol ')')
bracketed p		=	pack (symbol '[') p (symbol ']')
compound p		=	pack (token "begin") p (token "end")

Другой часто встречающейся конструкцией является повторение некоторой структуры, при котором элементы разделены некоторым символом. Вы можете представить себе список параметров (выражения, разделённые запятыми) или составные операторы (операторы, разделённые точкой с запятой). Для деревьев разбора разделители не представляют никакого интереса. Функция listOf, приведённая ниже, создает парсер для списка (возможно пустого) из заданных парсера для элементов и парсера для разделителей:

listOf		::	Parser s a -> Parser s b -> Parser s [a]
listOf p s	=	p <:*> many (s *> p) <|> succeed []

Полезными частными случаями являются:

commaList, semicList	::	Parser Char a -> Parser Char [a]
commaList p			=	listOf p (symbol ',')
semicList p			=	listOf p (symbol ';')

Упражнение 12. В качестве ещё одной вариации на тему «повторение», определите комбинатор синтаксического анализа sequence, преобразующий список парсеров для некоторого типа в парсер, возвращающий список элементов этого типа. Также определите комбинатор choice, выполняющий повторное применение оператора <|>.

Упражнение 13. В качестве приложения sequence определите функцию token, которая обсуждалась в 3-ей части. Несколько более сложным вариантом функции listOf является случай, когда разделители несут смысловую нагрузку. Например, арифметические выражения, в которых операторы, разделяющие подвыражения должны быть частью дерева разбора. Для этого случая мы разработаем функции chainr и chainl. Эти функции предполагают, что для разделителей парсер вернёт функцию (!); эта функция используется chain для комбинирования деревьев разбора для этих элементов. В случае функции chainr оператор применяется справа налево, в случае chainl — слева направо. Основная структура chainl такая же как у listOf. Но в том случае, когда функция listOf отбрасывает разделители с помощью оператора *>, мы оставим их в результате используя <*>. Более того, последующая обработка теперь более сложная, чем просто применение функции list.

сhainl		::	Parser s a -> Parser s (a->a->a) -> Parser s a
chainl p s	=	p <*> many (s <*> p) <@ f

Функция f должна подействовать на элемент и список кортежей, каждый из которых содержит оператор и элемент. Например, функция f (e0, [(1, e1), (2, e2), (3, e3)]) должна вернуть ((e0 1 e1) 2 e2) 3 e3. Вы можете узнать здесь версию foldl (хотя и некаррированную), в которой кортеж (, y) из списка и промежуточный результат x комбинируются применением x  y. Если мы определим

ap2 (op, y) x		=	x `op` y

или даже

ap2 (op, y)		=	(`op` y)

то мы можем определить

chainl		::	Parser s a -> Parser s (a->a->a) -> Parser s a
chainl p s	=	p <*> many (s <*> p) <@ uncurry (foldl (flip ap2))

Двойственной по отношению к данной является функция chainr, которая применяет операторы по ассоциации вправо.

Упражнение 14. Попробуйте определить chainr. Определение изумительно симметрично по отношению к chainl. Но ощутить его красоту вы сможете лишь открыв её самостоятельно...

Анализ необязательных элементов

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

option p <@ f where	f []		= a
					f [x]	= b x

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

p <?@ (no, yes)	=	p <@ f
					where	f []		= no
							f [x]	= yes x

Для того, чтобы применить его на практике, давайте расширим парсер натуральных чисел до парсера чисел с плавающей точкой:

natural	::	Parser Char Int
natural	=	many digit <@ foldl f 0
			where f n d = n * 10 + d

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

fract	::	Parser Char Float
fract	=	many digit <@ foldr f 0.0
			where f d x = (x + fromInteger d) / 10.0

Дробная часть является необязательной в числе с плавающей точкой.

fixed	::	Parser Char Float
fixed	=	(integer <@ fromInteger) <*>
			(option (symbol '.' *> fract) <?@ (0.0, id)) <@ uncurry (+)

Точка, отделяющая целую часть от дробной, нужна только для разделения, и поэтому сразу же отбрасывается оператором *>. Также необязательными являются точка, отделяющая целую часть от дробной вместе с дробной частью. Если они отсутствуют, то должно быть использовано число 0.0, если присутствуют — к дробной части должна быть применена функция распознавания. В конечном счете целая и дробная части складываются.

Упражнение 15. Дайте определение парсера для (возможно отрицательного) целого числа, которое состоит из необязательного знака минус и натурального числа, идущего за ним.

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

В решении к упражнению 15 вы найдёте интересную структуру, в которой первая структура после обработки возвращает функцию, которая затем применяется к результату разбора второй структуры. Мы можем использовать это для ещё одного усовершенствования функции chainr. Она была определена в предыдущей части с использованием функции many. Парсер возвращает список кортежей (оператор, элемент), который сразу после это уничтожается функцией foldr. Зачем же тогда беспокоится о создании списка? Мы можем применить функцию, которая свёрнута непосредственно в процессе разбора, без предварительного построения списка. Для этого нам необходимо заменить тело функции many в определении chainr. Далее мы можем сократить выражение p <|> epsilon до option p. Непосредственно применяя функцию, которая была ранее использована для foldr, мы получаем:

chainr' p s	=	q
				where q = p <*> (option (s <*> q) <?@ (id, ap2)) <@ flip ap

Упражнение 17. Хотите попробовать самостоятельно написать chainl?

Благодаря использованию функций option и many, становится доступным большое число возможных решений, полученных по возврату. Это не всегда полезно. Например, если определим парсер для идентификаторов как:

identifier	=	many1 (satisfy isAlpha)

Одно слово может также быть разобрано как два идентификатора. Благодаря порядку альтернатив в определении функции many, первым производится «жадный» разбор, при котором накапливается как можно большее число букв в идентификаторе, однако если разбор прекращается из-за ошибки в каком-либо месте предложения, то делается попытка произвести «менее жадный» разбор, но она уже тщетна.

В ситуациях, когда из способа построения грамматики мы можем предсказать, что поиск результатов с помощью «нежадного» разбора, предоставляемого функцией many, является бесполезным. Мы можем определить преобразователь парсеров first, который преобразует парсер таким образом, что он возвращает лишь первый возможный вариант разбора. Он делает это выбирая первый элемент из списка благоприятных исходов.

first		::	Parser a b -> Parser a b
first p xs	| null r		=	[]
			| otherwise	=	[head r]
			where r = p xs

Используя эту функцию мы можем создать специальную версию функции many «всё или ничего»:

greedy		=	first . many
greedy1		=	first . many1

Если мы соединим функцию first с комбинатором синтаксического анализа option:

compulsion	=	first . option

мы получим парсер, который предполагает наличие структуры, но не завершается с ошибкой в случае её отсутствия.

Арифметические выражения

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

data Expr		=	  Con Int
				| Var String
				| Fun String [Expr]
				| Expr :+: Expr
				| Expr :-: Expr
				| Expr :*: Expr
				| Expr :/: Expr

Для того, чтобы принимать во внимание приоритеты операторов, мы используем грамматики с нетерминалами «expression» (выражение), «term» (терм) и «factor» (фактор): выражение состоит из термов, разделённых символами «+» или «-»; терм состоит из факторов, разделённых символами «*» или «/», а фактор — это константа, переменная, вызов функции или выражение, заключенное в скобки.

Эта грамматика представлена следующими функциями:

fact		::	Parser Char Expr
fact		=	integer <@ Con <|>
			identifier <*>
			(option (parenthesized (commaList expr))
				<?@ (Var, flip Fun)) <@ ap' <|>
			parenthesized expr

Первой альтернативой является константа, которая направляется на вход «семантической функции» Var. Второй альтернативой является переменная или вызов функции, в зависимости от наличия списка параметров. Если последний отсутствует применяется функция Var, если присутствует — функция Fun. Для третьей альтернативы не существует семантической функции, поскольку значение выражения в скобках такое же, как и значение выражения, не заключенного в скобки.

Для определения терма как списка факторов, разделённых мультипликативными операторами, мы используем функцию chainr:

term		::	Parser Char Expr
term		=	chainr fact (symbol '*' <@ const (:*:) <|>
					    symbol '/' <@ const (:/:))

Повторный вызов chainr неоднократно распознает его первый параметр (fact), разделённый его вторым параметром (символом «*» или «/»). Деревья разбора отдельных факторов объединены с помощью функций-конструкторов, указанных после <@. Функция expr аналогична функции term с единственным отличием в том, что вместо мультипликативных операторов используются аддитивные операторы, а вместо функций factor — функции term:

expr		::	Parser Char Expr
expr		=	chainr term (symbol '+' <@ const (:+:) <|>
					    symbol '-' <@ const (:-:))

На этом примере ясно видно достоинство данного метода. Нет никакой необходимости в отдельных формализмах для грамматик; продукции грамматики объединены с использованием функций высокого порядка. Также не нужен отдельный генератор парсеров (как «yacc»); функции могут быть рассмотрены и как описание грамматики и как выполняемый анализатор.

Обобщённые выражения

Арифметические выражения, в которых операторы имеют более двух уровней приоритета, могут быть разобраны путём написания дополнительных вспомогательных функций, промежуточных между term и expr. Функция chainr, имеющая в качестве первого параметра функцию с приоритетом на один уровень ниже, чем у chainr, используется в каждом определении.

Если существует девять уровней приоритетов, то мы получаем девять копий почти что одинакового текста. Так не должно быть. Наличие функций, напоминающих друг друга, является сигналом о том, что нам следует написать обобщённую функцию, в которой различия описываются дополнительными параметрами. Поэтому давайте внимательно рассмотрим отличия функций term и expr. Вот они:

1. Операторы и связанные конструкторы деревьев, используемые во втором параметре chainr.
2. Парсер, используемый в качестве первого параметра chainr.

Обобщённая функция будет иметь эти два отличия в качестве дополнительных параметров: первое в виде списка пар, второе в виде функции разбора:

type Op a			=	(Char, a -> a -> a)

gen				::	[Op a] -> Parser Char a -> Parser Char a
gen ops p			=	chainr p (choice (map f ops))
where f (s, c)		=	symbol s <@ const c

Если, кроме того, мы определим для быстроты записи:

multis	=	[('*', (:*:)), ('/', (:/:))]
addis	=	[('+', (:+:)), ('-', (:-:))]

то expr и term могут быть определены как частичная параметризация функции gen:

expr		=	gen addis term
term		=	gen multis fact

Подставляя определение функции term в определение функции expr мы получаем:

expr		=	addis `gen` (multis `gen` fact)

что опытный функциональный программист сразу определит как применение функции foldr:

expr		=	foldr gen fact [addis, multis]

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

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

Применение к самому себе

Несмотря на то, что в предыдущих частях показано, что отдельные формализмы для грамматик не нужны, пользователи могут захотеть придерживаться, например, нотации БНФ для написания грамматик. Поэтому в этой части мы напишем функцию, преобразующую БНФ-грамматику в парсер. БНФ-грамматика задается в виде строки и подвергается анализу, конечно же, с помощью парсера. Этот парсер такой, что возвращаемое им «дерево» разбора также является парсером! Так что название этой части является обоснованным.

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

Окружение

Окружением является список пар, в котором может быть представлено конечное отображение. Функция assoc может быть использована для связывания величины со своим образом, полученным данным отображением.

type Env a b		=	[(a, b)]

assoc				::	Eq s => Env s d -> s -> d
assoc ((u, v) : ws) x 	| x == u		=	v
					| otherwise	=	assoc ws x

Мы также определим функцию mapenv, которая применяет некоторую функцию ко всем образам в окружении.

mapenv				::	(a -> b) -> Env s a -> Env s b
mapenv f []			=	[]
mapenv f ((x, v) : ws)	=	(x, f v) : mapenv f ws

Грамматика

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

data Symbol	=	Term String | Nont String

Правая часть порождающего правила состоит из некоторого количества альтернатив, каждая из которых является списком символов:

type Alt		= 	[Symbol]
type Rhs		= 	[Alt]

В конечном счёте грамматика является связью между символом (нетерминальным) и правой частью порождающего правила для него:

type Gram		=	Env Symbol Rhs

Грамматики можно легко описать, используя нотацию БНФ. Мы напишем анализатор для этой нотации, который в качестве дерева разбора будет возвращать величину типа Gram. Парсер БНФ-грамматик параметризирован анализатором нетерминалов и анализатором терминалов, так что позже мы сможем принять различные соглашения относительно их представления. Мы будем использовать элементарные парсеры sptoken и spsymbol вместо token и symbol для того, чтобы допустить дополнительную свободу в представлении грамматик.

bnf		::	Parser Char String ->
			Parser Char String ->
			Parser Char Gram

bnf nontp termp	=	many rule
					where rule = (nont <*>
								sptoken "::=" *> rhs <* spsymbol '.')
						 rhs = listOf alt (spsymbol '|')
						 alt = many (term <|> nont)
						 term = sp termp <@ Term
						 nont = sp nontp <@ Nont

БНФ-грамматика состоит из правил «many», каждое из которых состоит из нетерминала, отделённого символом «::=» от rhs и оканчивается точкой. rhs — это список альтернатив, разделённых символами «|», где каждая альтернатива состоит из символов «many», терминалов или нетерминалов. Терминалы и нетерминалы распознаются парсерами, заданными в качестве параметра функции bnf.

Примером представления грамматики, которое может быть разобрано этим парсером является грамматика для операторов, структурированных в виде блоков:

blockgram = "BLOCK ::= begin BLOCK end BLOCK | ."

Здесь мы использовали соглашение обозначать нетерминалы заглавными буквами, а терминалы — строчными. Мы укажем эти соглашения при вызове функций bnf. Например:

test			=	some (bnf nont term) blockgram
where nont	=	greedy1 (satisfy isUpper)
term			=	greedy1 (satisfy isLower)

Результатом работы этой функции test является следующее окружение:

[(Nont "BLOCK",[[Term "begin", Nont "BLOCK", Term "end", Nont "BLOCK"],[]])]

Деревья разбора

Мы больше не можем использовать структуры данных, специально созданные для одной конкретной грамматики, как, например, тип Expr из части 9. Вместо этого мы определим общую структуру данных, которая описывает деревья разбора для предложений произвольной грамматики. Мы просто назовём их Tree; они являются частными случаями сильноветвящихся деревьев:

data Tree		=	Node Symbol [Tree]

Парсеры вместо грамматик

Используя функцию bnf мы можем легко генерировать величины типа Gram. Но на практике действительно необходимым является парсер языка, описанного БНФ-грамматикой. Так что давайте определим функцию:

parsGram		::	Gram -> Symbol -> Parser Symbol Tree

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

Функция parsGram использует некоторые вспомогательные функции, создающие парсер для символа, альтернативы и части rhs правила соответственно:

parsGram				::	Gram -> Symbol -> Parser Symbol Tree
parsGram gram start	=	parsSym start
						where

	parsSym				::	Symbol -> Parser Symbol Tree
	parsSym s @ (Term t)	=	symbol s <@ const [] <@ Node s
	parsSym s @ (Nont n)	=	parsRhs (assoc gram s) <@ Node s

	parsAlt				::	Alt -> Parser Symbol [Tree]
	parsAlt				=	sequence . map parsSym

	parsRhs				::	Rhs -> Parser Symbol [Tree]
	parsRhs				=	choice . map parsAlt

Функция parsSym различает случаи функций для терминальных и нетерминальных символов. Для терминальных символов создается парсер, который просто распознаёт этот символ, а затем создается элемент Node для дерева разбора.

Упражнение 18. Для чего используется преобразование <@ const []?

В случае нетерминальных символов производится поиск соответствующего правила в грамматике, которое в итоге становится окружением. Затем используется функция parsRhs, создающая парсер для rhs. Функция parsRhs создаёт парсеры для каждой альтернативы и применяет к ним функцию choice. В заключение функция parseAlt создаёт парсеры для отдельных символов в альтернативе и комбинирует их с помощью функции sequence.

Генератор парсеров

В теоретических учебниках контекстно-свободная грамматика обычно описывается четверкой (N, T, R, S), состоящей из множества нетерминалов, множества терминалов, множества правил и начального символа. Давайте сделаем также, представляя множество символом с помощью парсера:

type SymbolSet		=	Parser Char String
type CFG			=	(SymbolSet, SymbolSet, String, Symbol)

Теперь мы дадим определение функции, которая берёт такую четвёрку и возвращает парсер для этого языка. Не будет ли слишком самонадеянно назвать это «генератором парсеров»?

parsgen	::	CFG -> Parser Symbol Tree
parsgen (nontp, termp, bnfstring, start)
	= some (bnf nontp termp <@ parsGram) bnfstring start

Множества нетерминалов и терминалов представлены их парсерами. Грамматикой является строка, записанная в нотации БНФ. Парсер, получающийся в результате, принимает на вход список элементов типа Symbol (терминальных символов), а возвращает величину типа Tree.

Лексические блоки трансляторов

Получаемый парсер принимает на вход элементы типа Symbol вместо элементов типа Char. Если мы хотим применить его к строке символов, эта строка предварительно должна быть представлена лексическим блоком транслятора в виде последовательности токенов. Для этого мы создадим библиотечную функцию twopass, которая использует два парсера: один преобразовывает символы в токены, а другой — токены в деревья. Эта функция не нуждается ни в одном из свойств «символ», «токен» и «дерево» и таким образом имеет полиморфный тип:

twopass				::	Parser a b -> Parser b c -> Parser a c
twopass lex synt xs	=	[(rest, tree) | (rest, tokens) <- many lex xs,
									  (_, tree) <- just synt tokens]

Используя эту функцию, мы можем окончательно разобрать строку, принадлежащую языку, описанному БНФ-грамматикой:

blockgram		=	"BLOCK ::= begin BLOCK end BLOCK | ."
block4tup		=	(upperId, lowerId, blockgram, Nont "BLOCK")
upperId		= 	greedy1 (satisfy isUpper)
lowered		= 	greedy1 (satisfy isLower)
final 		= 	twopass (sp lowerId <@ Term) (parsgen block4tup)
input 		= 	"begin end begin begin end end"

Вот то, что действительно может получиться:

? some final input
Node (Nont "BLOCK") [Node (Term "begin") [], Node (Nontс"BLOCK") [], Node (Term "end") [], Node (Nont "BLOCK") [Node (Term "begin") [], Node (Nont "BLOCK") [Node (Term "begin") [], Node (Nont "BLOCK") [], Node (Term "end")

[], Node (Nont "BLOCK") []], Node (Term "end") [], Node (Nont "BLOCK") []]]

(1061 reductions, 2722 cells)

Упражнение 19. Мы использовали идентификаторы, состоящие из заглавных и строчных букв для того, чтобы различать терминальные и нетерминальные символы. Если пространство имён терминалов и нетерминалов пересекутся, то нам придется принять новые механизмы их различения, например, угловые скобки вокруг нетерминалов и кавычки вокруг терминалов. Как это можно сделать?

Упражнение 20. Сделайте парсер для вашего любимого языка.

Благодарность

Я бы хотел поблагодарить Doaitse Swierstra и Erik Meijer за их комментарии к наброску данной статьи и стимулирующие идеи.

Ссылки

1. R. Bird and P. Wadler, Introduction to Functional Programming. Prentice Hall, 1988.
2. W.H. Burge, `Parsing'. In Recursive Programming Techniques, Addison-Wesley, 1975.
3. Graham Hutton, `Higher-order functions for parsing'. J. Functional Programming 2:323-343.
4. Mark Jones, Gofer 2.30 release notes. http://www.cs.nott.ac.uk:80/Department/Staff/mpj/ .
5. P. Wadler, `How to replace failure by a list of successes: a method for exception handling, backtracking, and pattern matching in lazy functional languages'. In Functional Programming Languages and Computer Architecture, (J.P.Jouannaud, ed.), Springer, 1985 (LNCS 201), pp. 113-128.
6. Philip Wadler, `Monads for functional programming'. In Program design calculi, proc. of the Marktoberdorf Summer School, (M. Broy, ed.) Springer, 1992.
7. Philip Wadler, `Monads for functional programming'. In Lecture notes of the First International Spring School on Advanced Programming Techniques, (J. Jeuring, ed.) Springer, 1995.

Решения для упражнений

1. Символ равный а удовлетворяет условию равенства а:

symbol a	=	satisfy (== a)

1. Поскольку <|> является версией ++ более высокого порядка, то он гораздо более эффективно вычисляется в случае ассоциации вправо.

1. Функция just может быть написана с использованием списков следующим образом:

just p xs		=	[([], v) | (ys, v) <- p xs, null ys]

1. Оператор <*> является правоассоциативным, таким образом выражение a <*> b <*> c <*> d на самом деле означает a <*> (b <*> (c <*> d)), что объясняет структуру результата.

1. Парсер epsilon возвращает пустой кортеж в качестве дерева разбора. Функция const Nil применена к результату, отбрасывая таким образом пустой кортеж и заменяя его значением Nil. Вместо epsilon <@ const Nil мы можем также написать succeed Nil.

1. Без скобок мы получим open *> (parens <* (close <*> parens)), и мы лишь сохраним результат первого рекурсивного вызова парсера parens.

1. Функции parens и nesting могут быть написаны как частичная параметризация функции foldparеns, обеспечивая применение функций к первой и второй альтернативам:

parens	=	foldparens Bin Nil
nesting	=	foldparens (max . (1 +)) 0

1. Без преобразователя just в списке благоприятных исходов окажутся только варианты частичного разбора:

? nesting "()(())()"
[([], 2), ("()", 2), ("(())()", 1), ("()(())()", 0)]
? nesting "())"
[(")", 1), ("())", 0)]

1. Пустая альтернатива идёт последней, потому что комбинатор <|> использует конкатенацию списков для объединения списков благоприятных исходов. Это также справедливо и для рекурсивных вызовов; таким образом первыми идут все три символа «а», полученные в результате «жадного» разбора, затем идут два символа «а» и единственный остаток строки, далее один символ «а» и в конце концов пустой результат с нетронутой исходной строкой в качестве необработанной части строки.

1. Мы определили <:*> как сокращенную запись заключительной обработки результата работы <*> функцией list:

p <:*> q		=	p <*> q <@ list

Тогда мы можем определить

many p		=	p <:*> many p <|> succeed []

1. Комбинатор many1 может быть определен с использованием комбинатора many:

many1	::	Parser s a -> Parser s [a]
many1 p	=	p <*> many p <@ list

sequence	::	[Parser s a] -> Parser s [a]
sequence	=	foldr (<:*>) (succeed [])

choice	::	[Parser s a] -> Parser s a
choice	=	foldr (<|>) fail

token	::	Eq [s] => [s] -> Parser s [s]
token	=	sequence . map symbol

1. Такое определение было дано для chainl:

chainl		::	Parser s a -> Parser s (a -> a -> a) -> Parser s a
chainl p s	=	p <*> many (s <*> p) <@ uncurry (foldl (flip ap2))

Чтобы получить chainr необходимо заменить foldl на foldr, поменять местами flip и fold, заменить ap2 на ap1 и переупорядочить распределение many, полученного применением операторов <*>:

chainr		::	Parser s a -> Parser s (a -> a -> a) -> Parser s a
chainr p s	=	many (p <*> s) <*> p <@ uncurry (flip (foldr ap1))

Вспомогательные функции:

ap2 (op, y)	=	(`op` y)
ap1 (x, op)	=	(x `op`)

1. Самым простым способом явного анализа случаев является:

integer	::	Parser Char Int
integer	=	option (symbol '-') <*> natural <@ f
			where	f ([], n)		=	n
					f (_ , n)		=	-n

Однако наиболее удачным является использование оператора <?@, возвращающего функцию тождественности или отрицания в зависимости от наличия или отсутствия знака минус, которая в конце концов применяется к натуральному числу:

integer	::	Parser Char Int
integer	=	(option (symbol '-') <?@ (id,const negate)) <*>
			 natural <@ ap
			where ap (f, x) = f x

1. Числом с плавающей точкой является число с фиксированной точкой с необязательным порядком числа:

float	::	Parser Char Float
float	=	fixed <*>
			(option (symbol 'E' *> integer) <?@ (0, id)) <@ f
			where f (m, e) = m * power e
			power e | e < 0	=	1.0 / power (-e)
				   | otherwise = fromInteger (10 ^ e)

1. Так было бы здорово:

chainl' p s	=	q
				where q	=	(option (q <*> s) <?@ (id, ap1)) <*> p <@ ap

Увы, эта функция не будет работать…

1. Разбираемый символ s отбрасывается, а вместо него подставляется пустой список. Затем функция Node s применяется к пустому списку, получая в результате Node s [], что является терминальной вершиной в дереве разбора.