Комбинаторные разборщики.
Пост ниже является литературным кодом - его можно скопировать в файл и загрузить в интерпретатор.
>-- |ParsersFunc.hs
>-- Реализация комбинаторов синтаксического разбора наиболее конкретным образом.
>module ParsersFunc where
Синтаксический разбор - это извлечение структуры предложения из строки. Или "извлечение структуры текста из его представления в виде букв". Ну, как-то так. На входе у нас текст, на выходе - структура.
Что интересно, обычно описывается преобразование структуры в текст через правила. Например, plus ::= expr + expr это правило, по которому создаётся текст, когда нам надо создать выражение с оператором +. В этом случае текст, созданный для левого и правого вхождений expr произвольный. И задача разборщика - определить, был ли текст создан по правилам, или нет.
Вполне возможно, мы рассматриваем только часть правил, например, выражение языка программирования в тексте программы. В таком случае нам надо определить, что часть текста принадлежит к части грамматики, а следующая за разобранной нами часть текста будет разбираться другими частями грамматики.
Обычно у нас может быть некая неопределённость в распознавании правил. Мне нравится слово "уют", поскольку оно довольно страшное, если считать его глаголом. И предложение (вывеска) "Уют любимых" может быть разобрано как глагол и прилагательное или как существительное и прилагательное.
Вооружившись этими двумя соображениями, мы можем представить себе тип функции синтаксического разбора:
>type Parser a = String -> [(a, String)]Что это говорит в переводе на русский язык?
Тип разборщика это функция из строки (текста на разбор) в список из пар "разобранная структура и остаток текста".
Список означает, что мы можем получить несколько вариантов разбора и даже совсем ничего - список будет пуст. Список у нас ленивый, поэтому если мы будем разбирать в стиле "наиболее длинный разбор вперед", то, несмотря на экспоненциальную сложность, мы получим разбор довольно быстро - лишние варианты просмотрены не будут.
Итак, давайте попробуем собрать парочку-троечку комбинаторов и вспомогательных функций. Первой вспомогательной функцией будет запуск разборщика на строке текста:
>-- |Left "error" означает ошибку, Right value означает успех.
>parse :: String -> Parser a -> Either String a
>parse text parser = case parser text of
> [] -> Left "no parse"
> ((value,""):_) -> Right value
> ((value, unparsed):_) -> Left $ "error somewhere there: "++take 20 unparsedЭта функция запускает разборщик на тексте и анализирует результат. Она жадная - первый вариант разбора считается предпочтительным. У неё два варианта с ошибкой - не смогли разобрать ничего вообще и не разобрали до конца. Сейчас добавим комбинаторов и посмотрим, как она работает.
Самым простым комбинатором является комбинатор отказа. Он отказывается разбирать что-либо:
>stop :: Parser a
>stop _ = []
Не взирая на вход, он выдаст пустой список результатов, который совместим по типам с любой структурой.
Вторым простым комбинатором является получение очередного символа:
>item :: Parser Char
>item "" = [] -- ничего не можем прочитать.
>item (c:text) = [(c,text)] -- прочитали символ, вернули его и остаток текста
Вот его запуск:
*Main> parse "a" item
Right 'a'
*Main> parse "ab" item
Left "error somewhere there: b"
*Main> parse "Hello, world!" item
Left "error somewhere there: ello, world!"
*Main>
Диагностика оставляет желать лучшего, но это подождёт.
Третьим простым комбинатором является оператор альтернативы:
>infixl 3 <|>
>(<|>) :: Parser a -> Parser a -> Parser a
>(p <|> q) s = p s ++ q s
Тип показывает, что это функция от двух разборщиков некоей структуры в третий разборщик такой же структуры. Поэтому в скобках стоят p и q. А операнд за скобкой, s, это входной текст. Если развернуть последний Parser a в типе оператора альтернативы, то мы получим вот такое выражение: Parser a -> Parser a -> String -> [(a,String)]. То есть, три операнда, как и в нашем определении. Тело определения состоит в простом соединении результатов. Списки у нас ленивые и разбор q понадобится, только если p не смог и выдал пустой список.
Чтобы интересней было, добавим ещё условный разбор и разбор определенного символа:
>check :: (a -> Bool) -> Parser a -> Parser a
>check cond parser s = filter (cond . fst) (parser s)
>char :: Char -> Parser Char
>char c = check (==c) item
Запустим:
*Main> parse "a" (char 'a' <|> char 'b')
Right 'a'
*Main> parse "b" (char 'a' <|> char 'b')
Right 'b'
*Main> parse "c" (char 'a' <|> char 'b')
Left "no parse"Ожидаемый результат.
Чтобы добраться до более-менее мощных разборщиков, надо сделать оператор последовательного разбора. Тут уже начинается интереcная магия. Мы сделаем комбинатор, который будет принимать разборщик, конструирующий функции!
>infixl 4 <*>
>(<*>) :: Parser (a -> b) -> Parser a -> Parser b
>(p <*> q) s = [(f a, qs) | (f, ps) <- p s, (a, qs) <- q ps]
>pure :: a -> Parser a -- в текстах по синтаксическому разбору это называется эпсилон.
>pure a s = [(a,s)]
Второй разборщик тривиален - он возвращает какое-то значение, не забирая ничего из текста. А вот первый интересен. Он запускает разборщик p на исходном тексте s. Этот разборщик может вернуть несколько результатов-функций, со своим остатком. И для каждой функции и соответствующего остатка текста мы запускаем второй разборщик на остатке. Второй разборщик разбирает аргумент для функции-результата первого. Окончательный результат - применение разобранной функции к разобранному аргументу и остаток текста после разобранного аргумента.
Вот теперь можно собрать разборщик для списков, а туда войдёт и альтернатива, и пустой раборщик, и последовательный разбор:
>many, many1 :: Parser a -> Parser [a]
>many p = many1 p <|> pure []
>many1 p = pure (:) <*> p <*> many p
И немедленно запустим:
*Main> parse "abababa" (many (char 'a' <|> char 'b'))
Right "abababa"
*Main> parse "abababac" (many (char 'a' <|> char 'b'))
Left "error somewhere there: c"
*Main> parse "" (many (char 'a' <|> char 'b'))
Right ""
*Main> parse "" (many1 (char 'a' <|> char 'b'))
Left "no parse"
Вот. many1 не умеет разбирать пустой список, получили ошибку. many умеет - ошибки нет.
Вот на этом небольшом базисе можно сообразить лексический и даже синтаксический анализ. Поскольку у нас есть предикат для отказа на неправильном содержимом, мы можем собрать даже разбор контекстно-зависимых грамматик. Например, мы можем отвергать XML, если открывающий тэг не будет иметь того же имени, что и закрывающий.
Замечу, что я использовал имена операторов <|>, <*> и pure для удобства и для иллюстрации совместимости синтаксического разбора с классами Applicative и Alternative из Control.Applicative. Впервые они появились в библиотеке uu-parsinglib, имели такие же имена и потом просочились в отдельный классы после работы Конора МакБрайда.
>-- |ParsersFunc.hs
>-- Реализация комбинаторов синтаксического разбора наиболее конкретным образом.
>module ParsersFunc where
Синтаксический разбор - это извлечение структуры предложения из строки. Или "извлечение структуры текста из его представления в виде букв". Ну, как-то так. На входе у нас текст, на выходе - структура.
Что интересно, обычно описывается преобразование структуры в текст через правила. Например, plus ::= expr + expr это правило, по которому создаётся текст, когда нам надо создать выражение с оператором +. В этом случае текст, созданный для левого и правого вхождений expr произвольный. И задача разборщика - определить, был ли текст создан по правилам, или нет.
Вполне возможно, мы рассматриваем только часть правил, например, выражение языка программирования в тексте программы. В таком случае нам надо определить, что часть текста принадлежит к части грамматики, а следующая за разобранной нами часть текста будет разбираться другими частями грамматики.
Обычно у нас может быть некая неопределённость в распознавании правил. Мне нравится слово "уют", поскольку оно довольно страшное, если считать его глаголом. И предложение (вывеска) "Уют любимых" может быть разобрано как глагол и прилагательное или как существительное и прилагательное.
Вооружившись этими двумя соображениями, мы можем представить себе тип функции синтаксического разбора:
>type Parser a = String -> [(a, String)]Что это говорит в переводе на русский язык?
Тип разборщика это функция из строки (текста на разбор) в список из пар "разобранная структура и остаток текста".
Список означает, что мы можем получить несколько вариантов разбора и даже совсем ничего - список будет пуст. Список у нас ленивый, поэтому если мы будем разбирать в стиле "наиболее длинный разбор вперед", то, несмотря на экспоненциальную сложность, мы получим разбор довольно быстро - лишние варианты просмотрены не будут.
Итак, давайте попробуем собрать парочку-троечку комбинаторов и вспомогательных функций. Первой вспомогательной функцией будет запуск разборщика на строке текста:
>-- |Left "error" означает ошибку, Right value означает успех.
>parse :: String -> Parser a -> Either String a
>parse text parser = case parser text of
> [] -> Left "no parse"
> ((value,""):_) -> Right value
> ((value, unparsed):_) -> Left $ "error somewhere there: "++take 20 unparsedЭта функция запускает разборщик на тексте и анализирует результат. Она жадная - первый вариант разбора считается предпочтительным. У неё два варианта с ошибкой - не смогли разобрать ничего вообще и не разобрали до конца. Сейчас добавим комбинаторов и посмотрим, как она работает.
Самым простым комбинатором является комбинатор отказа. Он отказывается разбирать что-либо:
>stop :: Parser a
>stop _ = []
Не взирая на вход, он выдаст пустой список результатов, который совместим по типам с любой структурой.
Вторым простым комбинатором является получение очередного символа:
>item :: Parser Char
>item "" = [] -- ничего не можем прочитать.
>item (c:text) = [(c,text)] -- прочитали символ, вернули его и остаток текста
Вот его запуск:
*Main> parse "a" item
Right 'a'
*Main> parse "ab" item
Left "error somewhere there: b"
*Main> parse "Hello, world!" item
Left "error somewhere there: ello, world!"
*Main>
Диагностика оставляет желать лучшего, но это подождёт.
Третьим простым комбинатором является оператор альтернативы:
>infixl 3 <|>
>(<|>) :: Parser a -> Parser a -> Parser a
>(p <|> q) s = p s ++ q s
Тип показывает, что это функция от двух разборщиков некоей структуры в третий разборщик такой же структуры. Поэтому в скобках стоят p и q. А операнд за скобкой, s, это входной текст. Если развернуть последний Parser a в типе оператора альтернативы, то мы получим вот такое выражение: Parser a -> Parser a -> String -> [(a,String)]. То есть, три операнда, как и в нашем определении. Тело определения состоит в простом соединении результатов. Списки у нас ленивые и разбор q понадобится, только если p не смог и выдал пустой список.
Чтобы интересней было, добавим ещё условный разбор и разбор определенного символа:
>check :: (a -> Bool) -> Parser a -> Parser a
>check cond parser s = filter (cond . fst) (parser s)
>char :: Char -> Parser Char
>char c = check (==c) item
Запустим:
*Main> parse "a" (char 'a' <|> char 'b')
Right 'a'
*Main> parse "b" (char 'a' <|> char 'b')
Right 'b'
*Main> parse "c" (char 'a' <|> char 'b')
Left "no parse"Ожидаемый результат.
Чтобы добраться до более-менее мощных разборщиков, надо сделать оператор последовательного разбора. Тут уже начинается интереcная магия. Мы сделаем комбинатор, который будет принимать разборщик, конструирующий функции!
>infixl 4 <*>
>(<*>) :: Parser (a -> b) -> Parser a -> Parser b
>(p <*> q) s = [(f a, qs) | (f, ps) <- p s, (a, qs) <- q ps]
>pure :: a -> Parser a -- в текстах по синтаксическому разбору это называется эпсилон.
>pure a s = [(a,s)]
Второй разборщик тривиален - он возвращает какое-то значение, не забирая ничего из текста. А вот первый интересен. Он запускает разборщик p на исходном тексте s. Этот разборщик может вернуть несколько результатов-функций, со своим остатком. И для каждой функции и соответствующего остатка текста мы запускаем второй разборщик на остатке. Второй разборщик разбирает аргумент для функции-результата первого. Окончательный результат - применение разобранной функции к разобранному аргументу и остаток текста после разобранного аргумента.
Вот теперь можно собрать разборщик для списков, а туда войдёт и альтернатива, и пустой раборщик, и последовательный разбор:
>many, many1 :: Parser a -> Parser [a]
>many p = many1 p <|> pure []
>many1 p = pure (:) <*> p <*> many p
И немедленно запустим:
*Main> parse "abababa" (many (char 'a' <|> char 'b'))
Right "abababa"
*Main> parse "abababac" (many (char 'a' <|> char 'b'))
Left "error somewhere there: c"
*Main> parse "" (many (char 'a' <|> char 'b'))
Right ""
*Main> parse "" (many1 (char 'a' <|> char 'b'))
Left "no parse"
Вот. many1 не умеет разбирать пустой список, получили ошибку. many умеет - ошибки нет.
Вот на этом небольшом базисе можно сообразить лексический и даже синтаксический анализ. Поскольку у нас есть предикат для отказа на неправильном содержимом, мы можем собрать даже разбор контекстно-зависимых грамматик. Например, мы можем отвергать XML, если открывающий тэг не будет иметь того же имени, что и закрывающий.
Замечу, что я использовал имена операторов <|>, <*> и pure для удобства и для иллюстрации совместимости синтаксического разбора с классами Applicative и Alternative из Control.Applicative. Впервые они появились в библиотеке uu-parsinglib, имели такие же имена и потом просочились в отдельный классы после работы Конора МакБрайда.