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

[thesz]

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

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

Comments

[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 (char 'a') <*> char 'b')
Left "error somewhere there: ab"

В примерах из поста нас спасает то, что 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 спасает нас от этой поломки.