Функциональные парсеры: различия между версиями

Нет изменений в размере ,  11 лет назад
Мы начнём с довольно простого, дав определение функции разбора, которая распознаёт символ «а». В этом случае типом символов входной строки будет Char и в качестве «дерева разбора» мы также просто используем Char:
 
symbola :: Parser Char Char
symbola [] = []
symbola (x:xs) | x == ‘a’ = [(xs, ‘a’)]
| otherwise = []
 
Сразу же становится очевидным преимущество списка благоприятных исходов, потому что теперь мы можем вернуть пустой список в том случае, когда разбор невозможен (так как входная строка пуста или не начинается с символа «а»).
Таким же образом мы можем написать парсеры, распознающие другие символы. Как всегда вместо того, чтобы определять много тесно связанных функций, лучше абстрагироваться от распознаваемого символа, сделав его дополнительным параметром функции. Также функция может оперировать со строками, состоящими из элементов, отличных от символов, таким образом, она может быть применена в приложениях, ориентированных на обработку не только символьных данных. Единственным необходимым условием является то, что символы, которые нужно разобрать могут пройти проверку на равенство. В языке Gofer это обозначается предикатом Eq в типе функции:
 
symbol :: Eq s => s -> Parser s s
symbol a [] = []
symbol a (x:xs) | a == x = [(xs, x)]
| otherwise = []
 
Как обычно существует несколько способов определить ту же самую функцию. Если вам нравятся списки, то вы возможно предпочтете следующее определение:
 
symbol a [] = []
symbol a (x:xs) = [(xs, a) | a == x]
 
В языке Gofer список без генераторов, лишь с условием, определён как пустой или состоящий из одного элемента, в зависимости от условия.
Теперь мы определим некоторые простейшие парсеры, которые могут выполнять работу, традиционно выполняемую лексическими анализаторами. Например, полезным является парсер, распознающий фиксированную строку символов, такую как «begin» или «end». Мы назовем эту функцию token.
 
token k xs | k == take n xs = [ (drop n xs, k) ]
| otherwise = []
where n = length k
 
Также как и в случае с функцией symbol, мы параметризировали эту функцию распознаваемой строкой, превращая её таким образом в семейство функций. Конечно же, область применения этой функции не ограничена строками символов. Однако, нам необходима проверка на равенство для типа входной строки; типом token является следующее:
 
token :: Eq [s] => [s] -> Parser s [s]
 
Функция token является обобщением функции symbol, поскольку она распознаёт более одного символа.
Другим обобщением symbol является функция, которая может возвращать различные результаты разбора, в зависимости от входных данных. Функция satisfy является примером такого обобщения. Там, где в функции symbol находится проверка на равенство заданному символу, в satisfy может быть указан произвольный предикат. Функция satisfy, таким образом, опять же является семейством функций-анализаторов. Здесь приведено её определение с использованием списочной нотации:
 
satisfy :: (s -> Bool) -> Parser s s
satisfy p [] = []
satisfy p (x:xs) = [(xs, x) | p x]
 
Упражнение 1. Поскольку функция satisfty является обобщением функции symbol, функция symbol может быть определена как частный случай satisfy. Как это можно сделать?
В книгах по теории грамматик пустая строка часто называется «epsilon». Следуя этой традиции, мы определим функцию epsilon, «разбирающую» пустую строку. Она не принимает ничего на вход и соответственно всегда возвращает пустое дерево разбора и неизменённые входные данные. В качестве результирующей величины может быть использован кортеж, состоящий из 0 элементов: () является единственным значением типа ().
 
epsilon :: Parser s ( )
epsilon xs = [(xs, ())]
 
Её разновидностью является функция succeed, которая также не принимает ничего на вход, но всегда возвращает данное, фиксированное значение (или «дерево разбора», если можно назвать результат обработки нуля символов деревом разбора...):
 
succeed :: r -> Parser s r
succeed v xs = [(xs, v)]
 
Конечно же, функция epsilon может быть определена через функцию succeed:
 
epsilon :: Parser s ()
epsilon = succeed ()
 
Двойственной по отношению к функции succeed является функция fail, которая не распознаёт ни один символ входной строки. Она всегда возвращает пустой список благоприятных исходов:
 
fail :: Parser s r
fail xs = []
 
Позже нам понадобится этот тривиальный парсер в качестве нейтрального элемента для функции foldr. Обратите внимание на отличие от функции epsilon, которая имеет один элемент в своём списке благоприятных исходов (хотя и пустой).
Анонимный участник