Комбинаторные разборщики.

[thesz]

Пост ниже является литературным кодом - его можно скопировать в файл и загрузить в интерпретатор.

>-- |ParsersFunc.hs
>-- Реализация комбинаторов синтаксического разбора наиболее конкретным образом.
>module ParsersFunc where
Синтаксический разбор - это извлечение структуры предложения из строки. Или "извлечение структуры текста из его

Comments

[besm6]

С точки зрения примения обычных функций, результат разборки - не a, а [(a,String)]. К нему не так просто применить a->b.

[besm6]

В <*> окольность пути, во-первых, скрыта, а во-вторых, ограничена одной итерацией.

По сути, применение всех a->b снаружи эквивалентно изначальной задаче парсинга. А именно, вместо высказывания "many (char 'a' or char 'b')" нам придется сказать "many (any char) such that every char == 'a' or == 'b'". Иными словами, "возьмем изначальную строку целиком и построим из нее нужню нам структуру с нуля". Т.е. свели задачу к изначальной. На данной грамматике функция построения нужной структуры простая - проверим условие на каждом символе, если на всех срослось, то изначальная строка и есть нужная нам структура. Обычно же это далеко не так...

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

[thesz]

По традиции. У меня комбинаторы строятся по кальке одной из первых статей по теме, а там был many/many1.

[besm6]

Вопрос на понимание. Ну, строить пример с XML я не стал, для примера попроще - строка, ограниченная справа и слева одинаковым, но заранее неизвестным символом. У меня получилось

*Main> parse "/a/b/" (pure (\(_,s,_)->s) <*> check (\(x,_,y)->x==y) (pure (\l s r->(l,s,r)) <*> item <*> (many item) <*> item))
Right "a/b"

(Возможность разделителю содержаться в середине оставлена намеренно.) Я правильно понимаю, что на имеющихся комбинаторах проще не получится, чтобы сделать проще, нужна уже операция над a->Parser b, что и отличает монаду от аппликативного функтора?

Соответственно, если хочется добиться того, чтобы в середине не содержалось разделителя, то это уже запихивает половину парсера в аргумент check (\(x,s,y)->x==y && not elem x s)?

[thesz]

Именно так.

Монады в ближайшем будущем. ;)

[besm6]

Спасибо, кстати, за начало с аппликативного подхода. До сих пор как-то не было хорошего повода посмотреть повнимательнее на Applicative/Alternative, чуть что - сразу >>=, и вперед. И как я понимаю, это общее место у программистов на хаскеле. А между тем, эта парадигма стоит того, чтобы потратить мозг на ее освоение, даже если применяться будет нечасто.

[thesz]

Про её важность я тоже скажу. ;)

[besm6]

> Она жадная - первый вариант разбора считается предпочтительным

Я бы сказал, что она не столько жадная, сколько тупая, как пробка. В частности, она не найдет полный парсинг, если так случилось, что он оказался в списке не первым. Какой бы пример подобрать, чтобы и перестановка альтернатив не помогала?.. Ну вот, например: нам годится строка, начинающаяся с одиночного a, за которым следует серия b, или строка, начинающаяся с нескольких a, за которыми следует одиночный b:

*Main> parse "abb" (pure (\s c->s++[c]) <*> many (char 'a') <*> char 'b' <|> pure (:) <*> char 'a' <*> many (char 'b'))
Left "error somewhere there: b"
*Main> parse "aab" (pure (\s c->s++[c]) <*> many (char 'a') <*> char 'b' <|> pure (:) <*> char 'a' <*> many (char 'b'))
Right "aab"

а при перестановке альтернатив - ситуация обратная:

*Main> parse "abb" (pure (:) <*> char 'a' <*> many (char 'b') <|> pure (\s c->s++[c]) <*> many (char 'a') <*> char 'b')
Right "abb"
*Main> parse "aab" (pure (:) <*> char 'a' <*> many (char 'b') <|> pure (\s c->s++[c]) <*> many (

[thesz]

Ну, это исправимо - сперва надо посмотреть в списке, есть ли полный разбор. Думал я об этом, решил, что не стоит.

Надо сделать примерно вот так:
parse text parser = let r = parser text in case (filter (not . null . snd) r,r) of
([],[]) -> Left "no parse"
([],(_,rem):_) -> Left $ "error somewhere here: "++take 20 rem++"..."
((a,_):_,_) -> Right a(код не тестировал)

Но это и сложнее объяснять, и редко встречается.

[besm6]

Ну, типа да. Это было, с одной стороны, в порядке упражнения на понимание, а с другой - в порядке указания на неточность в тексте, которая может ввести в заблуждение. В иллюстративных целях я бы оставил parse из поста, только указал бы, что она может в заковыристом случае сломаться, и что в большинстве случаев жадность many спасает нас от этой поломки.