Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[6]

£ то

7. ДОПОЛНИТЕЛЬНЫЕ КОМБИНАТОРЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

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

Очень просто сделать новые комбинаторы для расширений, подобных этому. В качестве первого примера мы рассмотрим повторение. Для данного парсера структуры, many создает разборщик для 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 (symbola) применён к строке «ааа». В каком порядке появятся четыре возможных разбора в списке благоприятных исходов?

ФП 02005-06 01

Лист 19

Копиоова Формат


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

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

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

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

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

option :: Parser s a -> Parser s [a]

option p = p <@ (\x -> [x]) <> epsilon <@ (\x -> [])

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

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

pack s1 p s2 =

Parser s a -> Parser s b -> Parser s c -> Parser s b

s1 *> p <* s2

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

parenthesized p bracketed p compound p

pack (symbol () p (symbol )) pack (symbol [) p (symbol ]) pack (token "begin") p (token "end")

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

ФП 02005-06 01

Лист 20

№ докум.

Копиоова Формат


listOf p s

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

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

commaList, semicList commaList p semicList p

Parser Char a -> Parser Char [a] listOf p (symbol ,) listOf p (symbol ;)

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

Упражнение 13. В качестве приложения sequence определите функцию token, которая обсуждалась в 3-ей части.

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

chainl chainl p s

Parser s a -> Parser s (a->a->a) -> Parser s a p <*> many (s <*> p) <@ f

Функция f должна подействовать на элемент и список кортежей, каждый из которых содержит оператор и элемент. Например, функция f (e0, [(Фи, e1), (Ф2, e2), (Ф3, e3)]) должна вернуть ((e0 Фи eu) Ф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))

ФП 02005-06 01

Лист 21

№ докум.

Копиоова Фоомат



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13]