[Haskell-cafe] Parsec bug, or...?

S. Doaitse Swierstra doaitse at swierstra.net
Thu Oct 15 18:07:30 EDT 2009


On 15 okt 2009, at 16:58, Uwe Hollerbach wrote:

> Hi, all, thanks for the further inputs, all good stuff to think
> about... although it's going to be a little while before I can
> appreciate the inner beauty of Doaitse's version! :-)

The nice thing is that you do not have to understand the inner  
workings ;-} I basically builds a greedy parser for each word to be  
recognised which can stop and assume the rest is there if it can no  
longer proceed (the `opt` is greedy in its left alternative) . Hence  
it recognises the longest possible prefix.
Since my parsers pursue all alternatives in parallel you automatically  
get what you want, without having to indicate prefix lengths, calls to  
try, etc.

The "amb" combinator has type

amb :: Parser a -> Parser [a]

and collects the result from all alternatives its argument parser is  
constructed from; you might say it convert an ambiguous parser to a  
parser with a list as result, hence preventing the rest of the input  
being parsed over and over again. I am currently working on bringing  
back more abstract interpretation in the implementation (i.e. what we  
have had for almost 10 years in the uulib library), but I do not  
expect you to see a lot of that from the outside.

If you want to work with left-recursive parsers (which does not seem  
to be the case), you may revert to more complicated solutions such as  
found in the "christmastree" (Changing Haskell's Read Implementation  
Such That by Manipulationg Abstract Syntax Trees Read Evaluates  
Efficiently) package if you need to generate parsers online, or to  
happy-based solutions in case your grammar is fixed.


  If you have any questions do not hesitate to ask,
  Doaitse


> I had considered
> the approach of doing a post-parsec verification, but decided I wanted
> to keep it all inside the parser, hence the desire to match prefixes
> there (and lack of desire to write 'string "p" <|> string "pr" <|>
> string "pre" ...'.
>
> By way of background, the actual stuff I'm wanting to match is not
> food names, but some commands for a small ledger program I'm working
> on. I needed something like that and was tired of losing data to
> quicken every so often. I realize of course that there are other
> excellent ledger-type programs out there, but hey, I also needed
> another hacking project. I'll put this onto hackage in a while, once
> it does most of the basics of what I need. No doubt the main
> differentiator between mine and those other excellent ledger programs
> out there will be that mine has fewer features and more bugs...
>
> thanks again, all!
>
> Uwe



More information about the Haskell-Cafe mailing list