CODEWITHSUNDEEP
parsinghaskelltrifecta
peer
peer

Reputation: 4679

How to do a backtrack search with parser combinators?

I have a list of parsers e.g. [string "a",string "ab"] that are "overlapping". I can change neither the parsers themselves nor their order.

With these parsers I want to parse a sequence of tokens that would each be exact matches for one of the parsers e.g. "aaaab", "ab", "abab" but not "abb"

Without parsers I would just implement a dept first search, but I would like to solve this with parsers.

I get about this far:

import Control.Applicative
import Text.Trifecta

parsers = [string "a",string "ab"]

parseString (many (choice parsers) <* eof) mempty "aab"

This fails because it will parse "a" both times, and not backtrack because choice doesn't do that. And further, string "a" has succeeded both times so the consumed input probably can't be retrieved anymore. How can implement a parser that can backtrack and produce a list of parse results e.g. Success ["a","ab"]?

If I require the input to have the tokens separated, I still can't make it work:

This works:

parseString (try (string "a" <* eof) <|> (string "ab" <*eof)) mempty "ab"

But this does not:

parseString (try (foldl1 (<|>) $ map (\x -> x <* eof) parsers)) mempty "ab"

Upvotes: 1

Views: 278

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476503

The try level is performed too high. You should perform it on the individual parsers. For example:

parseString (foldl1 (<|>) $ map (\x -> try (x <* eof)) parsers) mempty "ab"

In the original parser you wrote:

parseString ((try (string "a" <* eof)) <|> (string "ab" <*eof)) mempty "ab"

Notice that the left operand of <|> is try (string "a" <* eof) with try included.

whereas in the one you performed with foldl1, you wrote:

parseString (try ((string "a" <* eof) <|> (string "ab" <*eof))) mempty "ab"

So here is the try not part of the left operand. As a result, if the first parser fails, the "cursor" will not return to the point where it made the decision to try the first operand.

We can improve the above, by making use of asum :: (Foldable t, Alternative f) -> t (f a) -> f a:

import Data.Foldable(asum)

parseString (asum (map (\x -> try (x <* eof)) parsers)) mempty "ab"

Upvotes: 2

Related Questions