Antoine Latter wrote:

For Parsec, in the absence of the "try" combinator, a parser will never back-track once it consumes a portion of the input.

Thanks for reminding me.

If "try" is pushed out into the leaves of you parser, you shouldn't run in to too much trouble with excessive backtracking.

I agree.

What problems are you running in to?

Unfortunately I have an existing, mostly working and quite complex parser which does indeed use Parsec.try quite close to the root of the tree. I have tried on a number of ocassions to refactor this to remove this particular usage of Parsec.try without success. Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

Stephen Tetley writes:

Hi Erik

Malcolm Wallace describes a commit combinator in the paper "Partial parsing: combining choice with commitment" which sounds like what you would want. It is implemented for Polyparse rather than Parsec though. From a quick scan of the paper and code, the implementation appears to be built into the Parser type, so it is a primitive rather than a definable combinator.

From the Polyparse homepage (http://www.cs.york.ac.uk/fp/polyparse/):

,---- | If you are familiar with the Parsec library, then the key insight for | using PolyParse is that the two libraries' approach to backtracking | are the duals of each another. In Parsec, you must explicitly add a | try combinator at any location where backtracking might be | necessary. Users often find this a bit of a black art. In PolyParse by | contrast, all parsers are backtracking unless you explicitly add a | commit (or one of its variations). It is easy to tell where to add a | commit point, because you have already parsed enough of a data | structure to know that only one outcome is possible. For instance, if | you are parsing a Haskell value produced by 'show', then as soon as | you have parsed the initial constructor, you know that no other | constructor of that datatype is possible, so you can commit to | returning it. `---- -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

Stephen Tetley wrote:

Malcolm Wallace describes a commit combinator in the paper "Partial parsing: combining choice with commitment" which sounds like what you would want. It is implemented for Polyparse rather than Parsec though.

Yes, I can see how that might help on some kinds of data. Thanks.

If your Parsec parser uses try because it is not especially left-factored, one extra combinator I have found useful for left-factoring on the cheap is optionalSuffix:

optionalSuffix :: (a -> c) -> (a -> b -> c) -> Parser a -> Parser b -> Parser c optionalSuffix f g pbody psuffix = do a <- pbody mb_b <- optionMaybe psuffix return $ maybe (f a) (\b -> g a b) mb_b

Funnily enough, while this function didn't help me directly, it did inspire me to take yet another look at the problem code (I've made at least 4 or 5 attempts to fix it over the last year). Revisiting the problem now, with your code in mind, I came up with a solution in about 5 minutes. Now that I've fixed it, it seems so obvious. That led me to wonder if there was a Parsec best-practices document. Does such a thing exist? Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/