Difference between revisions 98891 and 99634 on ruwikibooks

{{К удалению|2014-11-01}}

{{Информация об авторе|Грэм Хаттон (Graham Hutton)|Университет Ноттингема, Великобритания|[mailto:[email protected] [email protected]]|[http://www.cs.nott.ac.uk/~gmh Личная страница Грэма Хаттона]}}

==Предисловие==

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

==Введение==

В функциональном программировании популярным подходом к построению рекурсивных  синтаксических анализаторов является моделирование парсеров как функций и определение функций высшего порядка (комбинаторов), которые снабжены грамматическими конструкциями, такими как  упорядочение, выбор и повторение. Основная идея берет начало в книге Burge  о методах рекурсивного программирования (Burge, 1975), и была сделана популярной в функциональном программировании Wadler (1985), Hutton (1992), Fokker (1995), и другими. Комбинаторы предоставляют быстрый и простой метод для создания функциональных парсеров (синтаксических анализаторов). Кроме того, метод имеет преимущества перед генераторами функциональных парсеров, такими как Ratatosk (Mogensen, 1993) и Happy (Gill & Marlow, 1995). Этот метод имеет полную мощность функционального языка, доступную для определения новых комбинаторов для  приложений (Ландин, 1966).
 
Раньше было известно (Wadler, 1990), что парсеры формируют пример монад, алгебраических структур из математики, которые доказали полезность при исследовании большого числа вычислительных задач. Интересное с математической точки зрения постижение унарной природы парсера приносит также практическую выгоду. Например, использование унарного упорядочивающего комбинатора для парсера позволяет избежать беспорядочных манипуляций с кортежами результатов, представленных в более ранних работах. Более того, использование унарных вложенных нотаций делает парсеры более компактными и понятными для чтения.

Рассматривая монадный метод дальше, монады парсеров могут быть выражены в модульном виде через две более простые монады. Непосредственная выгода состоит в том, что основные парсерные комбинаторы не нужно больше определять явно. Предпочтительно они возникают автоматически как специальный случай поднимающих операций монады от основной монады m к некоторой другой монаде параметризованной над m. Это означает так же, что если мы изменяем природу парсера модификацией основной монады (например, ограничивая парсер только на создание одного результата), тогда новые комбинаторы для модифицированной монады парсера также возникают через поднимающую конструкцию.

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

Боле глубокое знакомство с ФП оказалось бы весьма полезно при чтении этой статьи, но использование некоторых черт Gofer (Jones, 1995b) - нашего языка реализации - будет объяснено. Любой другой ленивый функциональный язык программирования, поддерживающий (многопараметрические) конструкторы классов и использование вложенной нотации монад, - так же бы подошел. Никакое предшествующее знание парсерных комбинаторов или монад не принимается. На самом деле, эта статья может также рассмотрена как первое введение в использование монад в программировании. Библиотека монадных парсерных комбинаторов, взятая из этой статьи доступна через World-Wide-Web.

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

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

 <code>type Parser = String -> Tree</code>

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

 <code>type Parser = String -> (Tree,String)</code>

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

 <code>type Parser = String -> [(Tree,String)]</code>

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

Наконец, различные парсеры могут возвращать различные типы деревьев, так что полезно абстрагировать специфичный тип Tree деревьев, и сделать тип возвращаемого значения в параметре типа Parser:

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

Этот тип парсеров мы будем использовать в оставшейся части статьи. Можно пойти дальше и абстрагировать тип String символов, но у нас сейчас нет потребности в таком обобщении.

=== Примитивные парсеры===

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

 result :: a -> Parser a
 result v = \inp -> [(v,inp)]

Выражение вида \x -> e называется  ламбда-абстракцией и обозначает функцию, которая берет на входе x и возвращает значение выражения e. Таким образом result v - функция, которая берет входную строку inp и возвращает единственный список [(v,inp)].С таким же успехом эта функция может быть определена как result v inp = [(v,inp)], но предпочтительнее предыдущее определение (в котором аргумент inp находится в теле определения), так как оно более соответствует типу result :: a -> Parser a, который утверждает что result - функция, которая берет на входе единственный параметр и возвращает синтаксический анализатор.

Также парсер zero всегда завершается неудачно, вне зависимости от входной строки:

 zero :: Parser a
 zero = \inp -> []

Наш последний примитив - item, который успешно поглощает первый символ во входной строке, если она не пуста, и завершается неудачно в противном случае:

 item :: Parser Char
 item = \inp -> case inp of
 [] -> []
 (x:xs) -> [(x,xs)]

===Парсерные комбинаторы===

Простые синтаксические анализаторы, определенные выше, не очень полезны сами по себе. В этом разделе мы рассмотрим, как они могут склеиваться вместе для формирования более полезных синтаксических анализаторов. Мы берем основу из БНФ нотации для специфицированных грамматик, в которых большие грамматики построены кусочно из меньших грамматик, с использованием оператора упорядочения, обозначаемого при помощи соединения, и оператора выбора, обозначаемый вертикальной чертой |. Мы определим соответствующие операторы для комбинирования парсеров, таким образом, что структура наших синтаксических анализаторов тесно следует из структуры основных грамматик.
В более ранних (не монадных) вариантах комбинаторного синтаксического анализа (Wadler, 1985; Hutton, 1992; Fokker, 1995), упорядочение парсеров обычно записывались через комбинаторы:

 seq :: Parser a -> Parser b -> Parser (a,b)
 p `seq` q = \inp -> [((v,w),inp'') | (v,inp') <- p inp, (w,inp'') <- q inp']

которые применяют один парсер после другого, объединяя результаты парсеров в пару. Инфиксная нотация p `seq` q является синтаксическим сахаром для seq p q; любая функция от двух аргументов может быть использована как инфиксный оператор в таком случае при заключении ее имени в обратные кавычки. На первый взгляд, комбинатор seq может показаться естественным примитивом композиции. На практике, тем не менее, применение seq приводит к парсерам с вложенными кортежами в качестве результата, которыми сложно управлять.

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

 bind :: Parser a -> (a -> Parser b) -> Parser b
 p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp]

Определение для комбинатора bind может быть интерпретировано следующим образом. Прежде всего, парсер р применяется ко входной строке, выдавая список (value,string) пар. Если f - это функция, которая берет значение и возвращает парсер, она может быть приложена к каждому значению (и к необработанной входной строке ) в свою очередь. В результате получается список списков (value,string) пар, который затем может быть преобразован, используя операцию конкатенации.

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

 p1 `bind` \x1 ->
 p2 `bind` \x2 ->
 ...
 pn `bind` \xn ->
 result (f x1 x2 ... xn)

и может быть интерпретирован следующим образом: применим парсер p1 и обозначим результат через x1, затем  применим парсер p2 и обозначим результат через x2,..., потом  применим парсер pn и обозначим результат через xn, и затем объединим результаты в одно значение применением функции f. Например, комбинатор seq может быть определен следующим образом:

 p `seq` q = p `bind` \x ->
 q `bind` \y ->
 result (x,y)

(С другой стороны bind не может быть определен через seq.)
Используя комбинатор bind, мы теперь можем определить некоторые простые, но очень полезные парсеры. Вспомните, что парсер item поглощает безусловно один символ. На практике нас интересует поглощение некоторых специфичных символов. По этой причине мы используем item для определения комбинатора sat, который берет на входе предикат (функцию с булевым значением) и выдает парсер, который поглощает символ, если тот удовлетворяет предикату, и завершает выполнение неудачно в противном случае:

 sat :: (Char -> Bool) -> Parser Char
 sat p = item `bind` \x ->
   if p x then result x else zero x

Следует отметить, что если item выполняется неудачно ( в случае если входная строка пустая ), тогда то же происходит с sat p, потому что легко заметить, что zero `bind` f = zero для любой функции f подходящего типа. На самом деле это уравнение не характерно для парсеров: оно справедливо для произвольной монады с нулем. Монады и их связь с парсерами будут обсуждены в следующем разделе.
Используя sat, мы можем определить синтаксические анализаторы для специфических символов, цифр, букв в нижнем регистре, букв в верхнем регистре:

 char :: Char -> Parser Char
 char x = sat (\y -> x == y)
 
 digit :: Parser Char
 digit = sat (\x -> '0' <= x && x <= '9')
 
 lower :: Parser Char
 lower = sat (\x -> 'a' <= x && x <= 'z')
 
 upper :: Parser Char
 upper = sat (\x -> 'A' <= x && x <= 'Z')

Например, применение парсера upper ко входной строке "Hello" выдает единственный правильный результат [('H',"ello")], т.е. парсер выдает в качестве результата 'H', а "ello" – это необработанный суффикс входной строки. С другой стороны, применение парсера lower к строке "Hello" выдаст результат [], так как'H'- не буква в нижнем регистре.

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

 lower `bind` \x ->
 lower `bind` \y ->
 result [x,y]

Применение этого синтаксического анализатора к строке "abcd" выдает результат [("ab","cd")].Применение того же синтаксического анализатора к "aBcd" возвращает [], поскольку даже если начальный символ 'a' может быть поглощен первым  парсером lower, следующий символ  'B' не может быть поглощен вторым  парсером lower.

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

 plus :: Parser a -> Parser a -> Parser a
 p `plus` q = \inp -> (p inp ++ q inp)

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

В качестве примера использования plus, некоторые ранее рассмотренные парсеры теперь могут быть объединены для образования парсеров для букв и буквенных-числовых символов:

 letter :: Parser Char
 letter = lower `plus` upper
 
 alphanum :: Parser Char
 alphanum = letter `plus` digit

Парсер для слов (последовательностей букв) определяется так:

 word :: Parser String
 word = neWord `plus` result ""
            where
                  neWord = letter `bind` \x ->
                                   word `bind` \xs ->
                                   result (x:xs)

<code>word</code> разбирает непустое слово ( единственный символ следующий за словом, рекурсивно вызывая word), в этом случае два результата объединяются для формирования строки, или выполняет  разбор пустого слова и  возвращает пустую строку.

Например, применение word ко входной строке "Yes!" выдает результат [("Yes","!"),("Ye","s!"), ("Y","es!"), ("","Yes!")]. Первый результат, ("Yes","!"), - ожидаемый результат: строка символов "Yes" обработана, и необработанная часть - "!". В последующих результатах, все меньшее количество символов обработано. Такое поведение возникает поскольку оператор выбора plus - недетерминированный: обе альтернативы могут быть рассмотрены, даже если первая альтернатива вполне успешна. Таким образом, в каждом применении letter, есть всегда возможность просто закончить выполнение грамматического разбора, даже если остались необработанные символы во входной строке.

==Парсеры и монады==
Позже мы определим множество полезных парсерных комбинаторов через простые парсеры и комбинаторы, которые только что определены. Но сначала мы становим наше внимание на монадной природе комбинаторных парсеров.

===Монада парсера===
Таким образом, мы определили следующие операции над парсерами:

 result :: a -> Parser a
 bind :: Parser a -> (a -> Parser b) -> Parser b

Обобщение специфичных случаев Parser до немного произвольного Конструктор типа  M дает понятие монады: монада является конструктором типа M ( функция от типов к типам), вместе с операциями result  и  bind  следующих типов:

 result :: a -> M a
 bind :: M a -> (a -> M b) -> M b

Таким образом, парсеры формируют монаду, для которой M является конструктором типа Parser, и result и bind определены выше. Технически, две операции монады должны также удовлетворять некоторым алгебраическим свойствам, но здесь мы не касаемся таких свойств. Смотрите (Wadler, 1992a; Wadler, 1992b) за дополнительной информацией.

Читатели, знакомые с категориальным определением монад могут ожидать две операции: map :: (a -> b) -> (M a -> M b) и join :: M (M a) -> M a вместо одного оператора bind. Тем не менее, наше определение является эквивалентом категориального и имеет преимущество в том, что bind является более удобным для унарного программирования, чем map и join.

Парсеры не являются единственным примером монады. На самом деле, мы увидим позже как монада парсера может быть переопределена через две простые монады. Это поднимает вопрос о том, что делать с присваиванием имен монадным комбинаторам result и bind. В функциональных языках, основанных на системе типов Hindley - Milner   (например, Miranda1 и Standard ML) невозможно использовать одинаковые имена для комбинаторов различных монад. Предпочтительно,  использовать различные имена, как например, resultM и bindM, для комбинаторов каждой монады M.

Гофер, однако, расширяет систему типов Hindley - Milner  перегружающим механизмом <!-- ??? --> 
, который разрешает использовать одно и то же имя для комбинаторов различных  монад. При этом перегружающем механизме, подходящая монада в  каждом случае использования имени вычисляется автоматически с помощью логического вывода типа.
Перегрузка в Gofer выполнена с использованием классов (Jones, 1995c). Класс для монад может быть объявлен следующим образом:

 class Monad m where
     result :: a -> m a
     bind :: m a -> (a -> m b) -> m b

Это определение можно сформулировать следующим образом: конструктор типа m является членом класса Monad,  если он содержит операторы result и bind соответствующих типов. Факт, что m должен быть конструктором типа (а не просто типом) вытекает из его использования в типах для операций.
Сейчас конструктор типа Parser может быть получен из класса Monad с использованием result и bind, описанных в предыдущем разделе:

 instance Monad Parser where
    -- result :: a -> Parser a
    result v = \inp -> [(v,inp)]

    -- bind :: Parser a -> (a -> Parser b) -> Parser b
    p `bind` f = \inp -> concat [f v out | (v,out) <- p inp]


Остановимся кратко на некоторых технических особенностях Gofer.Во-первых синонимы типа такого, как Parser должны быть обеспечены всеми своими аргументами. Следовательно, рассмотренный выше пример не является совсем правильным кодом Gofer, поскольку Parser был использован в первой строчке без аргумента. Проблема легко решается (переопределим Parser, используя data вместо type, или как ограниченный синоним типа), но для простоты в этой статье мы допустим, что синонимы типа могут быть частично применены. Во-вторых, синтаксис Gofer не позволяет явно задавать типы  описанных функций при объявлении сущностей.  Но для ясности мы включаем такие типы в комментарии.
Рассмотрим сейчас следующие операции над парсерами:

 zero :: Parser a
 plus :: Parser a -> Parser a -> Parser a

Обобщая снова частные случая конструктора типа Parser, мы приходим к нотации монады  через zero и plus, которая может быть инкапсулирована, используя систему классов Gofer следующим образом:

 class Monad m => Monad0Plus m where
     zero :: m a
     (++) :: m a -> m a -> m a

То есть, конструктор типа m является членом класса Monad0Plus, если он - член класса Monad (то есть, содержит result и bind) и если также содержит операторы zero и  (++)  соответствующих типов. Конечно, два дополнительных оператора должны также удовлетворить некоторым алгебраическим свойствам; эти обсуждается в (Wadler, 1992a; Wadler, 1992b). Заметим также, что использование (++) предпочтительнее чем plus, мы увидим позже примеры списков, которые  формируют монаду для которой операция plus похожа на операцию добавления (++).
Так как Parser является монадой, он может быть преобразован в монаду с zero и plus, используя следующее определение:


 instance Monad0Plus Parser where
   -- zero :: Parser a
   zero = \inp -> []

   -- (++) :: Parser a -> Parser a -> Parser a
  p  ++ q = \inp -> (p inp ++ q inp)

3.2. Вложенный синтаксис монады
Пока мы видели одно преимущество осознания монадной природы синтаксических анализаторов: монадный комбинатор упорядочения bind оперирует результирующими значениями лучше, чем стандартный комбинатор упорядочения seq. В этом разделе, мы рассмотрим другое преимущество монадного подхода, а именно, что вложенный синтаксис монады может быть использован, чтобы сделать синтаксические анализаторы более компактными и легко читаемыми.
Как упомянуто выше, много синтаксических анализаторов будет иметь в качестве структуры последовательность binds, сопровожденную единственным вызовом result:

 p1 `bind` \x1 ->
 p2 `bind` \x2 ->
 ...
 pn `bind` \xn ->
 result (f x1 x2 ... xn)

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

 [ f x1 x2 ... xn | x1 <- p1
  , x2 <- p2
                 , ...
                 , xn <- pn ]

Фактически, эта нотация не специфична для парсеров, но может быть использована с любой монадой (Jones, 1995c). Читатель мог обратить внимание на сходство с вложенной нотацией списка, поддерживаемой многими функциональными языками. Wadler (1990) первым заметил, что эта вложенная нотация специфична не только для списков, но имеет смысл для произвольной монады.  Оказывается, алгебраические свойства требуемые для монадных операций точно такие же, что и те, которые требуются для нотации, чтобы та имела смысл. К сведению, Gofer - первый язык, который поддерживает вложенную нотацию монады Wadler. Использование этой нотации может сделать парсер более удобочитаемым, и мы будем использовать эту нотацию в остальной части этой статьи.
В качестве первого примера использования вложенной нотации, мы определим синтаксический анализатор для распознавания специфичной строки, возвращающий саму строку как результат:

 string :: String -> Parser String
 string "" = [""]
 string (x:xs) = [x:xs | _ <- char x, _ <- string xs]
То есть, если строка, которую нужно разобрать, является пустой, мы просто возвращаем пустую строку в качестве результата; [""] - только вложенный синтаксис монады для result "". В противном случае, мы выполняем грамматический разбор первого символа  в строке, используя char, затем выполняем грамматический разбор остальных символов используя рекурсивный вызов string. Без помощи вложенной нотации, вышеуказанное определение выглядит следующим образом:

 string :: String -> Parser String
 string "" = result ""
 string (x:xs) = char x `bind` \_ ->
                       string xs `bind` \_ ->
                       result (x:xs) 

Парсер string xs выполняется неудачно, если только префикс данной строки xs есть  во входных данных. Например, применяя парсер string "hello" к входным данным  "hello there" дает успешный результат [("hello"," there")]. С другой стороны, применение того же парсера к  "helicopter" выполняется неудачно с результатом [], хотя префикс "hel" есть во входной строке.
Во вложенной нотации списка, мы не просто ограничены генераторами, которые связывают переменные с величинами, но можем также использовать булеву «защиту», которая ограничивает значения связанных переменных. Например, функция negs, которая выбирается все отрицательные числа из списка целых может быть выражена следующим образом:

 negs :: [Int] -> [Int]
 negs xs = [x | x <- xs, x < 0]


В этом случае, выражение x < 0является защитой, которая ограничивает переменную x (связанную генератором x <- xs), значениями меньше нуля.
Wadler (1990) заметил, что использование защиты имеет смысл для произвольной монады с нулем. Вложенная нотация монады в Gofer поддерживает использование защиты. Например, определим комбинатор:

 sat :: (Char -> Bool) -> Parser Char
 sat p = item `bind` \x ->
           if p x then result x else zero

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

 sat :: (Char -> Bool) -> Parser Char
 sat p = [x | x <- item, p x]

Завершая этот раздел, отметим, что есть другая нотация, которая может быть использована для упрощения монадных программ: так называемая нотация do (Jones, 1994; Jones & Launchbury, 1994). Например, используя эту нотацию, комбинаторы string и sat могут быть определены следующим образом:

 string :: String -> Parser String
 string "" = do { result "" }
 string (x:xs) = do { char x ; string xs ; result (x:xs) }

 sat :: (Char -> Bool) -> Parser Char
 sat p = do { x <- item ; if (p x) ; result x }

Нотация do имеет пару преимуществ перед вложенной нотацией монады: мы не ограничены в выражениях монады, которые заканчиваются с использованием result; и генераторы формы _ <- e, которые не связывают переменные, могут быть укорочены с использованием e. Нотация do  поддерживается Gofer, но выражения монады, содержащие парсеры, обычно заканчиваются с использованием result (для вычисления величины результата парсера), так что дополнительная общность не является действительно необходимой в этом случае. По этой причине, и для упрощения, в этой статье мы используем только вложенную нотацию.  Тем не менее, это было бы несложно перевести наши определения  в нотацию do.



4. комбинаторы для повторения
Генераторы парсеров такие, как, например, Lex и Yacc (Aho et al., 1986) для производства синтаксических анализаторов написанных на C, и Ratatosk (Mogensen, 1993) и Happy (Gill & Marlow, 1995) для производства синтаксических анализаторов написанных на Haskell, обычно предлагают фиксированный набор комбинаторов для описания грамматики. С другой стороны, с методом построения парсеров как представлено в этой статье, множество комбинаторов полностью расширяемо: парсеры являются величинами первого класса, и у нас есть полная мощность функционального языка в нашем расположении для определения нужных комбинаторов для конкретных приложений.
В этом разделе мы определим комбинаторы для множества общих моделей повторения. Эти комбинаторы не являются специфичными для парсеров, но могут быть использованы с произвольной монадой с zero и plus . Для ясности, тем не менее, мы специализируем типы комбинаторов в случае парсеров.
В последующих разделах мы введем комбинаторы для других целей, включая лексические вопросы обработки и сторонние правила Gofer.

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

 word :: Parser String
 word = [x:xs | x <- letter, xs <- word] ++ [""]

Мы можем легко представить себе множество других синтаксических анализаторов, структура которых похожа на word. Например, синтаксические анализаторы для строк цифр или строк пробелов могли бы быть определены таким же образом, единственное отличие в том, что компонентный парсер letter будет заменен на digit или char ' '. Для чтобы избежания определения множества других синтаксических анализаторов с аналогичной структурой, мы абстрагируем образец рекурсии в word и определим общий комбинатор, many, который выполняет грамматический разбор последовательности объектов.
Комбинатор many применяет p нуль или больше раз ко входной строке. Результаты каждого применения p возвращаются в список:

 many :: Parser a -> Parser [a]
 many p = [x:xs | x <- p, xs <- many p] ++ [[]]

Различные парсеры могут быть получены заменой различных парсеров - аргументов p. Например, парсер word может определен как many letter, и другие синтаксические анализаторы, упоминаемые выше, - как many digit и many (char ' ').
Подобно тому, как исходный текстовый синтаксический анализатор возвращает множественный результат  (количество результатов уменьшается в зависимости от числа обработанных букв во входной строке), то же самое делает  many p. Конечно, в большинстве случаев нас будет интересовать только первый грамматический разбор many p, в котором p успешно применен необходимое количество раз. Мы вернемся к этому вопросу в следующем разделе, когда будем рассматривать эффективность парсеров.
В качестве другого применения many, мы можем определить синтаксический анализатор для идентификаторов. Для простоты, будем считать идентификатором последовательность буквенно-числовых символов, первым символом в которой является буквой в нижнем регистре. Будет легко  расширить определение для обработки дополнительных символов, например, символа подчеркивания или обратных кавычек.

 ident :: Parser String
 ident = [x:xs | x <- lower, xs <- many alphanum]

Иногда мы будем рассматривать только непустые последовательности объектов. Поэтому определяем специальный комбинатор many1 через many:

 many1 :: Parser a -> Parser [a]
 many1 p = [x:xs | x <- p, xs <- many p]

Например, применение many1 (char 'a')  ко входной строке "aaab" дает результат [("aaa","b"), ("aa","ab"), ("a","aab")],который является таким же, как и для many (char'a'), кроме того, что конечной пары ("", "aaab") больше нет. Заметим также, что many1 p может выполниться неудачно, тогда, как many p всегда выполняется успешно.
Используя many1, мы можем определить парсер для натуральных чисел :

 nat :: Parser Int
 nat = [eval xs | xs <- many1 digit]
  where
   eval xs = foldl1 op [ord x - ord '0' | x <- xs]
   m `op` n = 10*m + n

Еще, nat может быть использован для определения парсера для целых чисел :

 int :: Parser Int
 int = [-n | _ <- char '-', n <- nat] ++ nat

Лучший способ для определения парсера int состоит в следующем. Сначала пытаемся выполнить грамматический разбор символа отрицания '-'. Если это выполняется успешно, тогда возвращается функция отрицания как результат грамматического разбора; в противном случае возвращается функция тождества. Конечный шаг состоит в разборе  натурального числа и использовании функции, возвращенной в результате грамматического разбора символа '-'для модифицирования результирующего числа:

 int :: Parser Int
 int = [f n | f <- op, n <- nat]
  where
      op = [negate | _ <- char '-'] ++ [id]

4.2. Повторения с разделителями
Комбинатор  many выполняет грамматический разбор последовательности  объектов. Теперь мы рассмотрим чуть более общий образец повторения, в который включены разделители между объектами. Рассмотрим проблему синтаксического анализа непустого списка целых чисел, как например, [1,-42,17].
Такой синтаксический анализатор может быть определен через комбинатор many следующим образом:

 ints :: Parser [Int]
 ints = [n:ns | _ <- char '['
                 , n <- int
                 , ns <- many [x | _ <- char ',', x <- int]
                 , _ <- char ']']

Как и в предыдущем разделе для синтаксического анализатора word, мы можем представить множество других синтаксических анализаторов с аналогичной ints структурой, так что будет полезно абстрагировать шаблон повторения и определить универсальный комбинатор, который мы назовем sepby1. Комбинатор sepby1 похож на many1 в том, что он распознает непустые последовательности, выданные парсером p, но отличается тем, что примеры p разделены синтаксическим анализатором sep, чьи результирующие значения игнорируются:

 sepby1 :: Parser a -> Parser b -> Parser [a]
 p `sepby1` sep = [x:xs | x <- p
                       , xs <- many [y | _ <- sep, y <- p]]

Отметим, что тот факт, что результаты парсера sep игнорируются, отражен в типе комбинатора sepby1 : парсер sep  дает результаты типа b, но этот тип не встречается в типе [a] результатов комбинатора.
Теперь ints может быть определен в более компактной форме:

 ints = [ns | _ <- char '['
           , ns <- int `sepby1` char ','
           , _ <- char ']']

Фактически мы можем пойти немного дальше. Заключение в скобки синтаксических анализаторов другими синтаксическими анализаторами, чьи результаты игнорируются - в случае, рассмотренном выше, заключающими в скобки синтаксическими анализаторами являются - char '[' и char ']'-  встречается довольно часто для определения соответствующего  комбинатора:

 bracket :: Parser a -> Parser b -> Parser c -> Parser b
 bracket open p close = [x | _ <- open, x <- p, _ <- close]

Сейчас можем определить ints следующим образом:

 ints = bracket (char '[')
    (int `sepby1` char ',')
               (char ']')

Наконец, когда many1 был определен через many, комбинатор sepby (для возможных пустых последовательностей), естественно определяется через sepby1:

 sepby :: Parser a -> Parser b -> Parser [a]
 p `sepby` sep = (p `sepby1` sep) ++ [[]]

4.3 Повторения со значимыми разделителями
Комбинатор  sepby выполняет синтаксический анализ последовательностей объектов, разделенных текстом, который может быть проигнорирован. В этом конечном разделе о повторениях, мы рассмотрим более общий случай, в котором сами разделители являются значимыми. Комбинаторы, определенные в этом разделе созданы Fokker (1995).
Рассмотрим проблему синтаксического анализа простых арифметических выражений таких как  1+2-(3+4), построенных из натуральных чисел, используя сложение, вычитание, и скобки. Два арифметических оператора лево ассоциативны (таким образом, например, 1-2-3 должно быть разобрано как (1-2)-3), и имеют один и тот же приоритет. Стандартная грамматика BNF для таких выражений записывается следующим образом:

 expr ::= expr addop factor | factor
 addop ::= +| -
 factor ::= nat | ( expr )

Эта грамматика может быть непосредственно переводена в комбинаторный парсер:

 expr :: Parser Int
 addop :: Parser (Int -> Int -> Int)
 factor :: Parser Int

 expr = [f x y | x <- expr, f <- addop, y <- factor] ++ factor

 addop = [(+) | _ <- char '+'] ++ [(-) | _ <- char '-']

 factor = nat ++ bracket (char '(') expr (char ')')

Фактически, вместо того, чтобы возвращать некоторый тип дерева грамматического разбора, синтаксический анализатор expr действительно вычисляет значение арифметического выражения: синтаксический анализатор addop возвращает функцию в качестве результирующего значения, которая используется для комбинирования результирующих значений, порожденных при синтаксическом разборе аргументов в операторы.
Конечно, тем не менее, есть некоторые проблемы с синтаксическим анализатором expr, определенным выше. То, что операторы лево ассоциативны учтено в том, что expr лево-рекурсивен ( первое,что он делает - рекурсивно вызывает самого себя). Таким образом, expr не совершает никакого прогресса, и следовательно не завершается. Известно, эта проблема незавершения для синтаксических анализаторов может быть решена заменой левой рекурсии итерацией. Смотря на грамматику expr, мы видим что выражение является последовательностью factors, разделенной addops. Таким образом синтаксический анализатор для выражений может быть переопределен используя many следующим образом:

 expr = [... | x <- factor
             , fys <- many [(f,y) | f <- addop, y <- factor]]

Это решает проблему о незавершении, но все еще остается проблема заполнения части "..." нового определения, которое вычисляет величину выражения. Полагаем теперь, что входной строкой является "1-2+3-4". Затем после синтаксического анализа с использованием expr, переменная x будет равна 1 и fys будет списком [((-),2), ((+),3), ((-),4)].
Он может быть уменьшен до единственного значения 1-2+3-4 = ((1-2)+3)-4 = -2 складывая: встроенная функция foldl – такова, что, например, foldl g [b,c,d,e] = (( `g b) `g c) `g d) `g e. В настоящем случае, нам нужно брать g как функцию \x (f,y) -> f x y, и а как целое x:

 expr = [foldl (\x (f,y) -> f x y) x fys
           | x <- factor
           , fys <- many [(f,y) | f <- addop, y <- factor]]

Теперь, например, применение expr ко входной строке "1+2-(3+4)" дает результат [(-4,""), (3,"-(3+4)", (1,"+2-(3+4)")], как и следовало ожидать.
Продолжая дальше обобщение, мы можем абстрагировать шаблон повторения в expr и определить новый комбинатор. Комбинатор chainl1 выполняет грамматический разбор непустых последовательностей объектов, разделенных операторами, которые левоассоциативны:

 chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
 p `chainl1` op = [foldl (\x (f,y) -> f x y) x fys
                   | x <- p
                   , fys <- many [(f,y) | f <- op, y <- p]]

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

 expr = factor `chainl1` addop

 addop = [(+) | _ <- char '+'] ++ [(-) | _ <- char '-']

 factor = nat ++ bracket (char '(') expr (char ')')

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

 ops :: [(Parser a, b)] -> Parser b
 ops xs = foldr1 (++) [[op | _ <- p] | (p,op) <- xs]

Встроенная функция foldr1 - такова что, например, foldr1 g [a,b,c,d] = `g (b `g (c `g d)). Она определена для любого непустого списка. В вышеуказанном случае потом,  foldr1 помещает оператор выбора (++) между каждым синтаксическим анализатором в списке. Используя ops, наш парсер addop может теперь быть определен :

 addop = ops [(char '+', (+)), (char '-', (-))]

Возможная  неэффективность в определении комбинатора chainl1  заключается в конструкции промежуточного списка fys. Это может быть решено использованием прямого рекурсивного определения chainl1, которое не использует foldl и many, используя накапливающий параметр, для создания конечного результата:

 chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
 p `chainl1` op = p `bind` rest
  where
   rest x = (op `bind` \f ->
    p `bind` \y ->
     rest (f x y)) ++ [x]

Это определение имеет стандартный способ чтения операций. Синтаксический анализатор p `chainl1 op сначала выполняет грамматический разбор p, результирующее значение становится начальным аккумулятором для функции rest. Затем  выполняется грамматический разбор оператора и единственного p. Если это завершается успешно, аккумулятор и результат p объединяются, используя функцию f, возвращенную из синтаксического анализа оператора, и результирующее значение становится новым аккумулятором при синтаксическом анализе остальной последовательности (используя рекурсивный вызов rest). В противном случае, последовательность завершается, и аккумулятор возвращается.
В качестве другого интересного применения chainl1, мы можем переопределить наш ранее определенный синтаксический анализатор nat для натуральных чисел таким образом, что он не создает промежуточный список цифр. В этом случае, парсер op не осуществляет никакой синтаксический анализ, но возвращает функцию, которая объединяет натурал и цифру:

 nat :: Parser Int
 nat = [ord x - ord '0' | x <- digit] `chainl1` [op]
  where
   m `op` n = 10*m + n

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

 chainr1 :: Parser a -> Parser (a -> a -> a) -> Parser a
 p `chainr1` op =
   p `bind` \x ->
      [f x y | f <- op, y <- p `chainr1` op] ++ [x]

То есть, p `chainr1` op сначала выполняет грамматический разбор единственного p. Затем он пытается выполнить грамматический разбор оператора и остальной части последовательности (используя рекурсивный вызов chainr1). Если он завершается успешно, пара результатов из первого p и остальной части последовательности объединяются, используя функцию f возвращенную из синтаксического анализа оператора. В противном случае, последовательность завершается, и результат из p возвращается.
Как пример использования chainr1, мы расширим наш синтаксический анализатор для арифметических выражений для того, чтобы оперировать возведением в степень; этот оператор имеет более высокий приоритет чем предшествующие два оператора, и право ассоциативен:

 expr = term `chainl1` addop

 term = factor `chainr1` expop

 factor = nat ++ bracket (char '(') expr (char ')')

 addop = ops [(char '+', (+)), (char '-', (-))]
 expop = ops [(char '^', (^))]

Для полноты, мы также определим комбинаторы chainl и chainr, которые имеют такое же поведение, что и chainl1 и chainr1, за исключением того что они могут также не поглощать никакой входной строки, в этом случае данная величина v возвращается как результат:

 chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
 chainl p op v = (p `chainl1` op) ++ [v]

 chainr :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
 chainr p op v = (p `chainr1` op) ++ [v]

В итоге , chainl и chainr предоставляют простой способ построения синтаксических анализаторов для грамматик наподобие выражения. Использование этих комбинаторов позволяет избежать потребности в преобразованиях для удаления левой рекурсии в грамматике, что в противном случае привело бы к незавершению синтаксического анализатора. Они также позволяют избежать потребности в левом разложении на элементарные операции грамматики, что в противном случае привело к необязательному возвращению в исходное состояние; мы возвратимся  к этому в следующем разделе.

5. эффективность парсеров
Использование комбинаторов - простой и гибкий метод построения синтаксических анализаторов. Тем не менее, мощь комбинаторов - на практике, их способности возвращаться в исходное состояние и возвращать множественные результаты - может провести к синтаксическим анализаторам с неожиданными пространственными и временными характеристиками, если не быть осторожным. В этом разделе, мы расскажем о некоторых простых методах, которые могут быть использованы для улучшения эффективности синтаксических анализаторов. Читателям заинтересовавшимся в их дальнейшем развитии предлагаю обратиться к Rojemo's thesis (1995), который содержит главу об использовании инструментальных средств, ориентированных на кучу,  в оптимизации парсерных комбинаторов.

5.1. Левостороннее разложение на множители
Рассмотрим простую проблему синтаксического анализа и вычисления двух натуральных чисел разделенных знаком сложения `+', или знаком вычитания `-'. Эта спецификация может переводиться непосредственно в следующий синтаксический анализатор:

 eval :: Parser Int
 eval = add ++ sub
       where
         add = [x+y | x <- nat, _ <- char '+', y <- nat]
         sub = [x-y | x <- nat, _ <- char '-', y <- nat]

Этот синтаксический анализатор дает правильный, но неэффективный результат. Например, при синтаксическом анализе строки "123-456" число 123 сначала будет разобрано парсером add, который завершится неудачно поскольку нет символа `+', следующего за числом. Правильный грамматический разбор  будет найден при возвращении в исходное состояние входной строки, и выполнении грамматического разбора числа 123 снова, на этот раз парсером sub.
Конечно, способ избежать возможности возвращения в исходное состояние и повторения синтаксического анализа состоит в левостороннем разложении на множители парсера eval . То есть, начальное использование nat в компонентных синтаксических анализаторах add и sub должно разложено на множители:

 eval = [v | x <- nat, v <- add x ++ sub x]
 where
         add x = [x+y | _ <- char '+', y <- nat]
         sub x = [x+y | _ <- char '-', y <- nat]

Эта новая версия eval дает те же результаты что и первоначальная, но не требует никаких возвращений в исходное состояние. Используя новый eval, строка "123-456" может теперь быть разобраны за меньшее время. Фактически мы можем пойти немного дальше, и выполнить правостороннее разложение на множители в остальных случаях использования nat в add и sub. Это не улучшает эффективность вычисления, но вероятно дает очищающий синтаксический анализатор:

 eval = [f x y | x <- nat
              , f <- ops [(char '+', (+)), (char '-', (-))]
              , y <- nat]

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

5.2. Улучшение ленивости
Вспомним определение комбинатора many:

 many :: Parser a -> Parser [a]
 many p = [x:xs | x <- p, xs <- many p] ++ [[]]

Например, применение many (char 'a') ко входной строке  "aaab"  дает результат [("aaa","b"), ("aa","ab"), ("a","aab"),("","aaab")].
Так как Gofer является ленивым, мы могли ожидать, что символы a в первом результате "aaa" будут доступными поочередно, пока они поглощаются из входной строки. На практике никакая часть результата "aaa" не будет произведена, пока весь все символы a не будут поглощены. Другими словами, many не такой ленивый как мы могли ожидать.
Но имеет  ли это значение? Да, потому что является обычным в функциональном программировании  положиться на ленивость для избежания создания больших промежуточных структур (Hughes, 1989). Как отмечено Wadler (1985; 1992b), для решения проблемы с many  необходимо сделать явным тот факт, что парсер many p всегда выполняется успешно. (Даже если p непосредственно всегда будет выполняться неудачно, то many p все равно будет завершаться успешно с пустым списком в качестве результирующего значения). В этом  цель мощи комбинаторов:  

 force :: Parser a -> Parser a
 force p = \inp -> let x = p inp in
                  (fst (head x), snd (head x)) : tail x

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

 many :: Parser a -> Parser [a]
 many p = force ([x:xs | x <- p, xs <- many p] ++ [[]])

Использование force гарантирует, что many p и все его рекурсивные вызовы возвращают по крайней мере один результат. Новое определение many теперь имеет ожидаемое с точки зрения ленивости поведение. Например, применение many (char 'a')  к частично- определенной строке 'a':┴ дает частично - определенный результат ('a':┴,┴):┴. В противовес, старая версия many выдает результат для этого примера - полностью неопределенную величину ┴.
Некоторые читатели могли удивиться почему force определен, используя следующие функции выбора, а не сопоставление с образцом?

 fst :: (a,b) -> a      head :: [a] -> a
 snd :: (a,b) -> b      tail :: [a] -> [a]

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

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

 number :: Parser Int
 number = nat ++ [0]

Тем не менее, оно не имеет требуемого поведения. Например, применение number ко входной строке "hello" дает правильный результат [(0,"hello")]. С другой стороны, применение number к "123" дает результат [(123,""), (0,"123")], тогда, когда мы ожидали получить единственный результат [(123,"")].
Одно решение вышеуказанной проблемы состоит в использовании детерминированных парсерных комбинаторов (смотри  раздел 7.5) - все синтаксические анализаторы, построенные, используя такие комбинаторы, ограничены конструкцией на создания самое большее одного результата. Более общее решение, тем не менее,
должно сохранить гибкость недетерминированных комбинаторов, но обеспечивать средства, позволяющие сделать явным тот факт, что нас интересует только первый результат, произведенный такими синтаксическими анализаторами, как например, number. Это  цель комбинатора first:

 first :: Parser a -> Parser a
 first p = \inp -> case p inp of
                   [] -> []
                   (x:xs) -> [x]

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

 (+++) :: Parser a -> Parser a -> Parser a
 p +++ q = first (p ++ q)

Замена (++) на  (+++) в number дает желаемое поведение.
Кроме использования для подтверждения корректного поведения парсеров, (+++)может также использоваться для улучшения их эффективность. Так, например, рассмотрим синтаксический анализатор, который принимает строку "yellow"  или "orange":

 colour :: Parser String
 colour = p1 ++ p2
    where
            p1 = string "yellow"
            p2 = string "orange"

Вспомним теперь поведение комбинатора выбора (++): он берет строку, применяет оба парсера - аргумента к этой строке и конкатенирует результирующие списки. Таким образом, в красочном примере, если p1 успешно применен, тогда p2 все еще будет применяться к той же строке, даже если гарантировано выполнится неудачно. Это неэффективность может быть устранена используя (+++), который гарантирует, что, если p1 выполняется успешно, тогда p2 никогда не применяется:

 colour = p1 +++ p2
 where
   p1 = string "yellow"
   p2 = string "orange"

Если мы знаем, что синтаксический анализатор формы p ++ q детерминирован (возвращает, самое большее, одну результирующую величину), тогда p +++ q имеет такое же поведение, но  более эффективное: если p выполняется успешно, тогда q никогда не применяется. В остальной части этой статьи  по большей части будет использоваться комбинатор выбора (+++). Из-за большей эффективности, в библиотеках комбинаторов, которые прилагаются в этой статье,  комбинатор повторения из предшествующего раздела определен используя (+++) а не (++).
Мы завершаем этот раздел, задавая вопрос почему first определен сопоставлением с образцом, а не используя функцию выбора       take :: Int -> [a] -> [a] (где, например, take 3 "parsing" = "par"):

 first p = \inp -> take 1 (p inp)

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

 first p = \inp -> case p inp of
                   [] -> []
                   (x:xs) -> x : take 0 xs

Когда подвыражение take 0 xs вычислено, оно дает []. Тем не менее, с точки зрения ленивости это вычисление будет приостановлено до тех пор, пока величина не потребуется. Но суть в том, что список xs может храниться в памяти в течение некоторого времени, когда фактически, он может спокойно быть отвергнутым немедленно. Это пример утечки пространства. Определение first, используя сопоставление с образцом, не позволяет решить эту проблему.

= НА ПЕРЕВОД =

6 Handling lexical issues
Traditionally, a string to be parsed is not supplied directly to a parser, but is
�rst passed through a lexical analysis phase (or lexer) that breaks the string into
a sequence of tokens (Aho et al., 1986). Lexical analysis is a convenient place to
remove white-space (spaces, newlines, and tabs) and comments from the input
string, and to distinguish between identi�ers and keywords.
Since lexers are just simple parsers, they can be built using parser combinators,
as discussed by Hutton (1992). However, as we shall see in this section, the need
for a separate lexer can often be avoided (even for substantial grammars such as
that for Gofer), with lexical issues being handled within the main parser by using
some special purpose combinators.
6.1 White-space, comments, and keywords
We begin by de�ning a parser that consumes white-space from the beginning of a
string, with a dummy value () returned as result:
spaces :: Parser ()
spaces = [() | _ <- many1 (sat isSpace)]
where
isSpace x =
(x == ' ') || (x == '\n') || (x == '\t')
Similarly, a single-line Gofer comment can be consumed as follows:
comment :: Parser ()
comment = [() | _ <- string "--"
, _ <- many (sat (\x -> x /= '\n'))]
We leave it as an exercise for the reader to de�ne a parser for consuming multi-line
Gofer comments f- ... -g, which can be nested.
After consuming white-space, there may still be a comment left to consume from
the input string. Dually, after a comment there may still be white-space. Thus we
are motivated to de�ned a special parser that repeatedly consumes white-space and
comments until no more remain:
junk :: Parser ()
junk = [() | _ <- many (spaces +++ comment)]
Note that while spaces and comment can fail, the junk parser always succeeds. We
de�ne two combinators in terms of junk: parse removes junk before applying a
given parser, and token removes junk after applying a parser:
parse :: Parser a -> Parser a
parse p = [v | _ <- junk, v <- p]
token :: Parser a -> Parser a
token p = [v | v <- p, _ <- junk]
With the aid of these two combinators, parsers can be modi�ed to ignore whitespace
and comments. Firstly, parse is applied once to the parser as a whole, ensuring
that input to the parser begins at a signi�cant character. And secondly, token
is applied once to all sub-parsers that consume complete tokens, thus ensuring that
the input always remains at a signi�cant character.
Examples of parsers for complete tokens are nat and int (for natural numbers
and integers), parsers of the form string xs (for symbols and keywords), and
ident (for identi�ers). It is useful to de�ne special versions of these parsers | and
more generally, special versions of any user-de�ned parsers for complete tokens |
that encapsulate the necessary application of token:
natural :: Parser Int
natural = token nat
integer :: Parser Int
integer = token int
symbol :: String -> Parser String
symbol xs = token (string xs)
identifier :: [String] -> Parser String
identifier ks = token [x | x <- ident, not (elem x ks)]
Note that identifier takes a list of keywords as an argument, where a keyword
is a string that is not permitted as an identi�er. For example, in Gofer the strings
\data" and \where" (among others) are keywords. Without the keyword check,
parsers de�ned in terms of identifier could produce unexpected results, or involve
unnecessary backtracking to construct the correct parse of the input string.
To illustrate the use of the new combinators given above, let us de�ne a parser for
simple �-expressions extended with a \let" construct for local de�nitions. Parsed
expressions will be represented in Gofer as follows:
data Expr = App Expr Expr -- application
| Lam String Expr -- lambda abstraction
| Let String Expr Expr -- local definition
| Var String -- variable
Now a parser expr :: Parser Expr can be de�ned by:
expr = atom `chainl1` [App]
atom = lam +++ local +++ var +++ paren
lam = [Lam x e | _ <- symbol "\\"
, x <- variable
, _ <- symbol "->"
, e <- expr]
local = [Let x e e' | _ <- symbol "let"
, x <- variable
, _ <- symbol "="
, e <- expr
, _ <- symbol "in"
, e' <- expr]
var = [Var x | x <- variable]
paren = bracket (symbol "(") expr (symbol ")")
variable = identifier ["let","in"]
Note how the expr parser handles white-space and comments by using the symbol
parser in place of string and char. Similarly, the keywords \let" and \in" are
handled by using identifier to de�ne the parser for variables. Finally, note how
applications (f e1 e2 ... en) are parsed in the form (((f e1) e2) ... ) by
using the chainl1 combinator.
7 Factorising the parser monad
Up to this point in the article, combinator parsers have been our only example of
the notion of a monad. In this section we de�ne a number of other monads related
to the parser monad, leading up to a modular reformulation of the parser monad
in terms of two simpler monads (Jones, 1995a). The immediate bene�t is that, as
we shall see, the basic parser combinators no longer need to be de�ned explicitly.
Rather, they arise automatically as a special case of lifting monad operations from
a base monad m to a certain other monad parameterised over m. This also means
that, if we change the nature of parsers by modifying the base monad (for example,
limiting parsers to producing at most one result), new combinators for the modi�ed
monad of parsers are also de�ned automatically.
7.1 The exception monad
Before starting to de�ne other monads, it is useful to �rst focus brie
y on the
intuition behind the use of monads in functional programming (Wadler, 1992a).
The basic idea behind monads is to distinguish the values that a computation
can produce from the computation itself. More speci�cally, given a monad m and
a type a, we can think of m a as the type of computations that yield results of
type a, with the nature of the computation captured by the type constructor m.
The combinators result and bind (with zero and (++) if appropriate) provide a
means to structure the building of such computations:
result :: m a
bind :: m a -> (a -> m b) -> m b
zero :: m a
(++) :: m a -> m a -> m a
From a computational point of view, result converts values into computations
that yield those values; bind chains two computations together in sequence, with
results of the �rst computation being made available for use in the second; zero is
the trivial computation that does nothing; and �nally, (++) is some kind of choice
operation for computations.
Consider, for example, the type constructor Maybe:
data Maybe a = Just a | Nothing
We can think of a value of type Maybe a as a computation that either succeeds with
a value of type a, or fails, producing no value. Thus, the type constructor Maybe
captures computations that have the possibility to fail.
De�ning the monad combinators for a given type constructor is usually just a
matter of making the \obvious de�nitions" suggested by the types of the combinators.
For example, the type constructor Maybe can be made into a monad with a
zero and plus using the following de�nitions:
instance Monad Maybe where
-- result :: a -> Maybe a
result x = Just x
-- bind :: Maybe a -> (a -> Maybe b) -> Maybe b
(Just x) `bind` f = f x
Nothing `bind` f = Nothing
instance Monad0Plus Maybe where
-- zero :: Maybe a
zero = Nothing
-- (++) :: Maybe a -> Maybe a -> Maybe a
Just x ++ y = Just x
Nothing ++ y = y
That is, result converts a value into a computation that succeeds with this value;
bind is a sequencing operator, with a successful result from the �rst computation
being available for use in the second computation; zero is the computation that
fails; and �nally, (++) is a (deterministic) choice operator that returns the �rst
computation if it succeeds, and the second otherwise.
Since failure can be viewed as a simple kind of exception, Maybe is sometimes
called the exception monad in the literature (Spivey, 1990).
7.2 The non-determinism monad
A natural generalisation of Maybe is the list type constructor []. While a value of
type Maybe a can be thought of as a computation that either succeeds with a single
result of type a or fails, a value of type [a] can be thought of as a computation
that has the possibility to succeed with any number of results of type a, including
zero (which represents failure). Thus the list type constructor [] can be used to
capture non-deterministic computations.
Now [] can be made into a monad with a zero and plus:
instance Monad [] where
-- result :: a -> [a]
result x = [x]
-- bind :: [a] -> (a -> [b]) -> [b]
[] `bind` f = []
(x:xs) `bind` f = f x ++ (xs `bind` f)
instance Monad0Plus [] where
-- zero :: [a]
zero = []
-- (++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
That is, result converts a value into a computation that succeeds with this single
value; bind is a sequencing operator for non-deterministic computations; zero always
fails; and �nally, (++) is a (non-deterministic) choice operator that appends
the results of the two argument computations.
7.3 The state-transformer monad
Consider the (binary) type constructor State:
type State s a = s -> (a,s)
Values of type State s a can be interpreted as follows: they are computations that
take an initial state of type s, and yield a value of type a together with a new state
of type s. Thus, the type constructor State s obtained by applying State to a
single type s captures computations that involve state of type s. We will refer to
values of type State s a as stateful computations.
Now State s can be made into a monad:
instance Monad (State s) where
-- result :: a -> State s a
result v = \s -> (v,s)
-- bind :: State s a -> (a -> State s b) -> State s b
st `bind` f = \s -> let (v,s') = st s in f v s'
That is, result converts a value into a stateful computation that returns that value
without modifying the internal state, and bind composes two stateful computations
in sequence, with the result value from the �rst being supplied as input to the
second. Thinking pictorially in terms of boxes and wires is a useful aid to becoming
familiar with these two operations (Jones & Launchbury, 1994).
The state-transformer monad State s does not have a zero and a plus. However,
as we shall see in the next section, the parameterised state-transformer monad over
a given based monad m does have a zero and a plus, provided that m does.
To allow us to access and modify the internal state, a few extra operations on
the monad State s are introduced. The �rst operation, update, modi�es the state
by applying a given function, and returns the old state as the result value of the
computation. The remaining two operations are de�ned in terms of update: set
replaces the state with a new state, and returns the old state as the result; fetch
returns the state without modifying it.
update :: (s -> s) -> State s s
set :: s -> State s s
fetch :: State s s
update f = \s -> (s, f s)
set s = update (\_ -> s)
fetch = update id
In fact State s is not the only monad for which it makes sense to de�ne these
operations. For this reason we encapsulate the extra operations in a class, so that
the same names can be used for the operations of di�erent monads:
class Monad m => StateMonad m s where
update :: (s -> s) -> m s
set :: s -> m s
fetch :: m s
set s = update (\_ -> s)
fetch = update id
This declaration can be read as follows: a type constructor m and a type s are
together a member of the class StateMonad if m is a member of the class Monad,
and if m is also equipped with update, set, and fetch operations of the speci�ed
types. Moreover, the fact that set and fetch can be de�ned in terms of update is
also re
ected in the declaration, by means of default de�nitions.
Now because State s is already a monad, it can be made into a state monad
using the update operation as de�ned earlier:
instance StateMonad (State s) s where
-- update :: (s -> s) -> State s s
update f = \s -> (s, f s)
7.4 The parameterised state-transformer monad
Recall now our type of combinator parsers:
type Parser a = String -> [(a,String)]
We see now that parsers combine two kinds of computation: non-deterministic computations
(the result of a parser is a list), and stateful computations (the state is the
string being parsed). Abstracting from the speci�c case of returning a list of results,
the Parser type gives rise to a generalised version of the State type constructor
that applies a given type constructor m to the result of the computation:
type StateM m s a = s -> m (a,s)
Now StateM m s can be made into a monad with a zero and a plus, by inheriting
the monad operations from the base monad m:
instance Monad m => Monad (StateM m s) where
-- result :: a -> StateM m s a
result v = \s -> result (v,s)
-- bind :: StateM m s a ->
-- (a -> StateM m s b) -> StateM m s b
stm `bind` f = \s -> stm s `bind` \(v,s') -> f v s'
instance Monad0Plus m => Monad0Plus (StateM m s) where
-- zero :: StateM m s a
zero = \s -> zero
-- (++) :: StateM m s a -> StateM m s a -> StateM m s a
stm ++ stm' = \s -> stm s ++ stm' s
That is, result converts a value into a computation that returns this value without
modifying the internal state; bind chains two computations together; zero is the
computation that fails regardless of the input state; and �nally, (++) is a choice
operation that passes the same input state through to both of the argument computations,
and combines their results.
In the previous section we de�ned the extra operations update, set and fetch
for the monad State s. Of course, these operations can also be de�ned for the
parameterised state-transformer monad StateM m s. As previously, we only need
to de�ne update, the remaining two operations being de�ned automatically via
default de�nitions:
instance Monad m => StateMonad (StateM m s) s where
-- update :: Monad m => (s -> s) -> StateM m s s
update f = \s -> result (s, f s)
7.5 The parser monad revisited
Recall once again our type of combinator parsers:
type Parser a = String -> [(a,String)]
This type can now be re-expressed using the parameterised state-transformer monad
StateM m s by taking [] for m, and String for s:
type Parser a = StateM [] String a
But why view the Parser type in this way? The answer is that all the basic parser
combinators no longer need to be de�ned explicitly (except one, the parser item for
single characters), but rather arise as an instance of the general case of extending
monad operations from a type constructor m to the type constructor StateM m s.
More speci�cally, since [] forms a monad with a zero and a plus, so does State []
String, and hence Gofer automatically provides the following combinators:
result :: a -> Parser a
bind :: Parser a -> (a -> Parser b) -> Parser b
zero :: Parser a
(++) :: Parser a -> Parser a -> Parser a
Moreover, de�ning the parser monad in this modular way in terms of StateM
means that, if we change the type of parsers, then new combinators for the modi�ed
type are also de�ned automatically. For example, consider replacing
type Parser a = StateM [] String a
by a new de�nition in which the list type constructor [] (which captures nondeterministic
computations that can return many results) is replaced by the Maybe
type constructor (which captures deterministic computations that either fail, returning
no result, or succeed with a single result):
data Maybe a = Just a | Nothing
type Parser a = StateM Maybe String a
Since Maybe forms a monad with a zero and a plus, so does the re-de�ned Parser
type constructor, and hence Gofer automatically provides result, bind, zero, and
(++) combinators for deterministic parsers. In earlier approaches that do not exploit
the monadic nature of parsers (Wadler, 1985; Hutton, 1992; Fokker, 1995), the basic
combinators would have to be re-de�ned by hand.
The only basic parsing primitive that does not arise from the monadic structure
of the Parser type is the parser item for consuming single characters:
item :: Parser Char
item = \inp -> case inp of
[] -> []
(x:xs) -> [(x,xs)]
However, item can now be re-de�ned in monadic style. We �rst fetch the current
state (the input string); if the string is empty then the item parser fails, otherwise
the �rst character is consumed (by applying the tail function to the state), and
returned as the result value of the parser:
item = [x | (x:_) <- update tail]
The advantage of the monadic de�nition of item is that it does not depend upon
the internal details of the Parser type. Thus, for example, it works equally well for
both the non-deterministic and deterministic versions of Parser.
8 Handling the o�side rule
Earlier (section 6) we showed that the need for a lexer to handle white-space,
comments, and keywords can be avoided by using special combinators within the
main parser. Another task usually performed by a lexer is handling the Gofer o�side
rule. This rule allows the grouping of de�nitions in a program to be indicated
using indentation, and is usually implemented by the lexer inserting extra tokens
(concerning indentation) into its output stream.
In this section we show that Gofer's o�side rule can be handled in a simple and
natural manner without a separate lexer, by once again using special combinators.
Our approach was inspired by the monadic view of parsers, and is a development
of an idea described earlier by Hutton (1992).
8.1 The o�side rule
Consider the following simple Gofer program:
a = b + c
where
b = 10
c = 15 - 5
d = a * 2
It is clear from the use of indentation that a and d are intended to be global
de�nitions, with b and c local de�nitions to a. Indeed, the above program can be
viewed as a shorthand for the following program, in which the grouping of de�nitions
is made explicit using special brackets and separators:
{ a = b + c
where
{ b = 10
; c = 15 - 5 }
; d = a * 2 }
How the grouping of Gofer de�nitions follows from their indentation is formally
speci�ed by the o�side rule. The essence of the rule is as follows: consecutive de�-
nitions that begin in the same column c are deemed to be part of the same group.
To make parsing easier, it is further required that the remainder of the text of each
de�nition (excluding white-space and comments, of course) in a group must occur
in a column strictly greater than c. In terms of the o�side rule then, de�nitions a
and d in the example program above are formally grouped together (and similarly
for b and c) because they start in the same column as one another.
8.2 Modifying the type of parsers
To implement the o�side rule, we will have to maintain some extra information
during parsing. First of all, since column numbers play a crucial role in the o�side
rule, parsers will need to know the column number of the �rst character in their
input string. In fact, it turns out that parsers will also require the current line
number. Thus our present type of combinator parsers,
type Parser a = StateM [] String a
is revised to the following type, in which the internal state of a parser now contains
a (line,column) position in addition to a string:
type Parser a = StateM [] Pstring a
type Pstring = (Pos,String)
type Pos = (Int,Int)
In addition, parsers will need to know the starting position of the current de�nition
being parsed | if the o�side rule is not in e�ect, this de�nition position can
be set with a negative column number. Thus our type of parsers is revised once
more, to take the current de�nition position as an extra argument:
type Parser a = Pos -> StateM [] Pstring a
Another option would have been to maintain the de�nition position in the parser
state, along with the current position and the string to be parsed. However, de�nition
positions can be nested, and supplying the position as an extra argument to
parsers | as opposed to within the parser state | is more natural from the point
of view of implementing nesting of positions.
Is the revised Parser type still a monad? Abstracting from the details, the body
of the Parser type de�nition is of the form s -> m a (in our case s is Pos, m is the
monad StateM [] Pstring, and a is the parameter type a.) We recognise this as
being similar to the type s -> m (a,s) of parameterised state-transformers, the
di�erence being that the type s of states no longer occurs in the type of the result:
in other words, the state can be read, but not modi�ed. Thus we can think of s ->
m a as the type of parameterised state-readers. The monadic nature of this type is
the topic of the next section.
8.3 The parameterised state-reader monad
Consider the type constructor ReaderM, de�ned as follows:
type ReaderM m s a = s -> m a
In a similar way to StateM m s, ReaderM m s can be made into a monad with a
zero and a plus, by inheriting the monad operations from the base monad m:
instance Monad m => Monad (ReaderM m s) where
-- result :: a -> ReaderM m s a
result v = \s -> result v
-- bind :: ReaderM m s a ->
-- (a -> ReaderM m s b) -> ReaderM m s b
srm `bind` f = \s -> srm s `bind` \v -> f v s
instance Monad0Plus m => Monad0Plus (ReaderM m s) where
-- zero :: ReaderM m s a
zero = \s -> zero
-- (++) :: ReaderM m s a ->
-- ReaderM m s a -> ReaderM m s a
srm ++ srm' = \s -> srm s ++ srm' s
That is, result converts a value into a computation that returns this value without
consulting the state; bind chains two computations together, with the same state
being passed to both computations (contrast with the bind operation for StateM,
in which the second computation receives the new state produced by the �rst computation);
zero is the computation that fails; and �nally, (++) is a choice operation
that passes the same state to both of the argument computations.
To allow us to access and set the state, a couple of extra operations on the
parameterised state-reader monad ReaderM m s are introduced. As for StateM, we
encapsulate the extra operations in a class. The operation env returns the state as
the result of the computation, while setenv replaces the current state for a given
computation with a new state:
class Monad m => ReaderMonad m s where
env :: m s
setenv :: s -> m a -> m a
instance Monad m => ReaderMonad (ReaderM m s) s where
-- env :: Monad m => ReaderM m s s
env = \s -> result s
-- setenv :: Monad m => s ->
-- ReaderM m s a -> ReaderM m s a
setenv s srm = \_ -> srm s
The name env comes from the fact that one can think of the state supplied to a
state-reader as being a kind of environment. Indeed, in the literature state-reader
monads are sometimes called environment monads.
8.4 The new parser combinators
Using the ReaderM type constructor, our revised type of parsers
type Parser a = Pos -> StateM [] Pstring a
can now be expressed as follows:
type Parser a = ReaderM (StateM [] Pstring) Pos a
Now since [] forms a monad with a zero and a plus, so does StateM [] Pstring,
and hence so does ReaderM (StateM [] Pstring) Pos. Thus Gofer automatically
provides result, bind, zero, and (++) operations for parsers that can handle the
o�side rule. Since the type of parsers is now de�ned in terms of ReaderM at the top
level, the extra operations env and setenv are also provided for parsers. Moreover,
the extra operation update (and the derived operations set and fetch) from the
underlying state monad can be lifted to the new type of parsers|or more generally,
to any parameterised state-reader monad | by ignoring the environment:
instance StateMonad m a => StateMonad (ReaderM m s) a where
-- update :: StateMonad m a => (a -> a) -> ReaderM m s a
update f = \_ -> update f
Now that the internal state of parsers has been modi�ed (from String to Pstring),
the parser item for consuming single characters from the input must also be modi
�ed. The new de�nition for item is similar to the old,
item :: Parser Char
item = [x | (x:_) <- update tail]
except that the item parser now fails if the position of the character to be consumed
is not onside with respect to current de�nition position:
item :: Parser Char
item = [x | (pos,x:_) <- update newstate
, defpos <- env
, onside pos defpos]
A position is onside if its column number is strictly greater than the current de�-
nition column. However, the �rst character of a new de�nition begins in the same
column as the de�nition column, so this is handled as a special case:
onside :: Pos -> Pos -> Bool
onside (l,c) (dl,dc) = (c > dc) || (l == dl)
The remaining auxiliary function, newstate, consumes the �rst character from the
input string, and updates the current position accordingly (for example, if a newline
character was consumed, the current line number is incremented, and the current
column number is set back to zero):
newstate :: Pstring -> Pstring
newstate ((l,c),x:xs)
= (newpos,xs)
where
newpos = case x of
'\n' -> (l+1,0)
'\t' -> (l,((c `div` 8)+1)*8)
_ -> (l,c+1)
One aspect of the o�side rule still remains to be addressed: for the purposes
of this rule, white-space and comments are not signi�cant, and should always be
successfully consumed even if they contain characters that are not onside. This can
be handled by temporarily setting the de�nition position to (0;􀀀1) within the junk
parser for white-space and comments:
junk :: Parser ()
junk = [() | _ <- setenv (0,-1) (many (spaces +++ comment))]
All that remains now is to de�ne a combinator that parses a sequence of de�nitions
subject to the Gofer o�side rule:
many1_offside :: Parser a -> Parser [a]
many1_offside p = [vs | (pos,_) <- fetch
, vs <- setenv pos (many1 (off p))]
That is, many1 offside p behaves just as many1 (off p), except that within this
parser the de�nition position is set to the current position. (There is no need to
skip white-space and comments before setting the position, since this will already
have been e�ected by proper use of the lexical combinators token and parse.) The
auxiliary combinator off takes care of setting the de�nition position locally for
each new de�nition in the sequence, where a new de�nition begins if the column
position equals the de�nition column position:
off :: Parser a -> Parser a
off p = [v | (dl,dc) <- env
, ((l,c),_) <- fetch
, c == dc
, v <- setenv (l,dc) p]
For completeness, we also de�ne a combinator many offside that has the same
behaviour as the combinator many1 offside, except that it can also parse an empty
sequence of de�nitions:
many_offside :: Parser a -> Parser [a]
many_offside p = many1_offside p +++ [[]]
To illustrate the use of the new combinators de�ned above, let us modify our
parser for �-expressions (section 6.2) so that the \let" construct permits nonempty
sequences of local de�nitions subject to the o�side rule. The datatype Expr of
expressions is �rst modi�ed so that the Let constructor has type [(String,Expr)]
-> Expr instead of String -> Expr -> Expr:
data Expr = ...
| Let [(String,Expr)] Expr
| ...
The only part of the parser that needs to be modi�ed is the parser local for local
de�nitions, which now accepts sequences:
local = [Let ds e | _ <- symbol "let"
, ds <- many1_offside defn
, _ <- symbol "in"
, e <- expr]
defn = [(x,e) | x <- identifier
, _ <- symbol "="
, e <- expr]
We conclude this section by noting that the use of the o�side rule when laying out
sequences of Gofer de�nitions is not mandatory. As shown in our initial example, one
also has the option to include explicit layout information in the form of parentheses
\f" and \g" around the sequence, with de�nitions separated by semi-colons \;".
We leave it as an exercise to the reader to use many offside to de�ne a combinator
that implements this convention.
In summary then, to permit combinator parsers to handle the Gofer o�side rule,
we changed the type of parsers to include some positional information, modi�ed
the item and junk combinators accordingly, and de�ned two new combinators:
many1 offside and many offside. All other necessary rede�ning of combinators
is done automatically by the Gofer type system.
9 Acknowledgements
The �rst author was employed by the University of Utrecht during part of the
writing of this article, for which funding is gratefully acknowledged.
Special thanks are due to Luc Duponcheel for many improvements to the implementation
of the combinator libraries in Gofer (particularly concerning the use
of type classes and restricted type synonyms), and to Mark P. Jones for detailed
comments on the �nal draft of this article.
10 Appendix: a parser for data de�nitions
To illustrate the monadic parser combinators developed in this article in a real-life
setting, we consider the problem of parsing a sequence of Gofer datatype de�nitions.
An example of such a sequence is as follows:
data List a = Nil | Cons a (List a)
data Tree a b = Leaf a
| Node (Tree a b, b, Tree a b)
Within the parser, datatypes will be represented as follows:
type Data = (String, -- type name
[String], -- parameters
[(String,[Type])]) -- constructors and arguments
The representation Type for types will be treated shortly. A parser datadecls ::
Parser [Data] for a sequence of datatypes can now be de�ned by
datadecls = many_offside datadecl
datadecl = [(x,xs,b) | _ <- symbol "data"
, x <- constructor
, xs <- many variable
, _ <- symbol "="
, b <- condecl `sepby1` symbol "|"]
constructor = token [(x:xs) | x <- upper
, xs <- many alphanum]
variable = identifier ["data"]
condecl = [(x,ts) | x <- constructor
, ts <- many type2]
There are a couple of points worth noting about this parser. Firstly, all lexical
issues (white-space and comments, the o�side rule, and keywords) are handled by
combinators. And secondly, since constructor is a parser for a complete token, the
token combinator is applied within its de�nition.
Within the parser, types will be represented as follows:
data Type = Arrow Type Type -- function
| Apply Type Type -- application
| Var String -- variable
| Con String -- constructor
| Tuple [Type] -- tuple
| List Type -- list
A parser type0 :: Parser Type for types can now be de�ned by
type0 = type1 `chainr1` [Arrow | _ <- symbol "->"]
type1 = type2 `chainl1` [Apply]
type2 = var +++ con +++ list +++ tuple
var = [Var x | x <- variable]
con = [Con x | x <- constructor]
list = [List x | x <- bracket
(symbol "[")
type0
(symbol "]")]
tuple = [f ts | ts <- bracket
(symbol "(")
(type0 `sepby` symbol ",")
(symbol ")")]
where f [t] = t
f ts = Tuple ts
Note how chainr1 and chainl1 are used to handle parsing of function-types and
application. Note also that (as in Gofer) building a singleton tuple (t) of a type t
is not possible, since (t) is treated as a parenthesised expression.
References
Aho, A., Sethi, R., & Ullman, J. (1986). Compilers | principles, techniques and tools.
Addison-Wesley.
Burge, W.H. (1975). Recursive programming techniques. Addison-Wesley.
Fokker, Jeroen. 1995 (May). Functional parsers. Lecture notes of the Baastad Spring
school on functional programming.
Gill, Andy, & Marlow, Simon. 1995 (Jan.). Happy: the parser generator for Haskell.
University of Glasgow.
Hughes, John. (1989). Why functional programming matters. The computer journal,
32(2), 98{107.
Hutton, Graham. (1992). Higher-order functions for parsing. Journal of functional programming,
2(3), 323{343.
Jones, Mark P. (1994). Gofer 2.30a release notes. Unpublished manuscript.
Jones, Mark P. (1995a). Functional programming beyond the Hindley/Milner type system.
Proc. lecture notes of the Baastad spring school on functional programming.
Jones, Mark P. (1995b). The Gofer distribution. Available from the University of Nottingham:
http://www.cs.nott.ac.uk/Department/Staff/mpj/.
Jones, Mark P. (1995c). A system of constructor classes: overloading and implicit higherorder
polymorphism. Journal of functional programming, 5(1), 1{35.
Jones, Simon Peyton, & Launchbury, John. (1994). State in Haskell. University of Glasgow.
Landin, Peter. (1966). The next 700 programming languages. Communications of the
ACM, 9(3).
Mogensen, Torben. (1993). Ratatosk: a parser generator and scanner generator for Gofer.
University of Copenhagen (DIKU).
Moggi, Eugenio. (1989). Computation lambda-calculus and monads. Proc. IEEE symposium
on logic in computer science. A extended version of the paper is available as a
technical report from the University of Edinburgh.
Rojemo, Niklas. (1995). Garbage collection and memory e�ciency in lazy functional languages.
Ph.D. thesis, Chalmers University of Technology.
Spivey, Mike. (1990). A functional theory of exceptions. Science of computer programming,
14, 25{42.
Wadler, Philip. (1985). How to replace failure by a list of successes. Proc. conference on
functional programming and computer architecture. Springer{Verlag.
Wadler, Philip. (1990). Comprehending monads. Proc. ACM conference on Lisp and
functional programming.
Wadler, Philip. (1992a). The essence of functional programming. Proc. principles of
programming languages.
Wadler, Philip. (1992b). Monads for functional programming. Broy, Manfred (ed), Proc.
Marktoberdorf Summer school on program design calculi. Springer{Verlag.

[[Категория:Функциональное программирование]]⏎
[[Категория:Статьи по функциональному программированию]]