3 ms·
> Attoparsec and megaparsec don't backtrack. There are two notion of backtracking at play here. One is backtracking out of a failing first branch of <|> even t
by seagreen 6y ago
> Attoparsec and megaparsec don't backtrack.
There are two notion of backtracking at play here. One is backtracking out of a failing first branch of <|> even though it's consumed some input. The megaparsec authors consider this a form of backtracking (see https://hackage.haskell.org/package/megaparsec-9.0.1/docs/Text-Megaparsec.html#v:try https://hackage.haskell.org/package/megaparsec-9.0.1/docs/Te...).
The other is backtracking from a failure in the second argument to <> or <*>.
I agree that none of the libraries being considered do the latter. But the effect on memory use wouldn't just be slightly inefficient, it would mean keeping the entire input following a <|> in memory until the whole thing completes. Do you think this is the best way to do things in general, or just for specialized situations like parsing things with a fixed size such as config files?
- chowells 6y agoVery, very few parsers need to handle multiple gigabyte inputs. For those, sure, focus on performance first. Your tools should always be suited to your problem. None of that changes the fact that Parsec-like designs are especially obnoxious when it comes to backtracking. You need to be aware of their limitations and design the structure of your grammar around them. As an idea for a design somewhere in between, maybe try taking inspiration from Prolog. Add a cut combinator for limiting the scope of backtracking explicitly. It still solves the size issues on large inputs, but it allows more freedom in refactoring as long as you don't cross one of those explicit boundaries.