otherwise = [head r] where r = p xs

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

greedy= first . many

greedy1= first . many1

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

compulsion = first . option

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

£ сс

9. АРИФМЕТИЧЕСКИЕ ВЫРАЖЕНИЯ

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

data Expr=Con Int

Var String Fun String [Expr]

Expr Expr Expr Expr

Expr Expr Expr Expr

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

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

factParser Char Expr

fact= integer <@ Con <>

identifier <*>

(option (parenthesized (commaList expr))

<?@ (Var, flip Fun)) <@ ap <> parenthesized expr

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

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

term term

Parser Char Expr

chainr fact (symbol * <@ const (:*:) <>

symbol / <@ const (:/:))

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

Функция expr аналогична функции term с единственным отличием в том, что вместо мультипликативных операторов используются аддитивные операторы, а вместо функций factor - функции term:

expr:: Parser Char Expr

expr= chainr term (symbol + <@ const (:+:) <>

symbol - <@ const (:-:))

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