[Haskell-cafe] Alternative instance for non-backtracking parsers

Olaf Klinke olf at aatal-apotheke.de
Mon Aug 27 20:55:30 UTC 2018

>Hello, Olaf. I have some distrust of elegant solutions (one of them are
>C.P. libs).
I am a mathematician, I trust a lot in elegance and beauty. As long as 
the performance penalty is not prohibitively large, I'd prefer a beautiful 
implementation over an aggressively optimized one. At least when 
the code does not live in some real-time system. Certainly there are 
cases where you absolutely need speed or low memory footprint.

> For example, I read that they have problems with memory
>consuming (famous article about arrow-based parsers), also your example
>(my own experience includes a lot of tricks which I don't like)... So
>(but this is my IMHO) for big and serious project with parsing of
>something complex I will use bindings to good known parser libraries... 
I consider Parsec and it descendants good and known. I could not write 
something like that. Currently I rely on megaparsec because of its 
informative error messages, knowing that I can switch to one of the 
siblings without much effort when I need more speed.

>Maybe something like this: https://github.com/markwright/antlrc.  Btw,
>Happy looks still live (https://github.com/simonmar/happy)
Have you used any of the above?

>I use "Read"-style parsers for small constructions only, so fail of such
>small parser is only case where error is producing and I do it
>explicitly (as biggest example: header of Git patch).
>Olaf, what do you think about
>   1. http://hackage.haskell.org/package/frisby
Frisby looks quite old, as it has idiosyncratic combinators for stuff now 
in Data.Functor. I've never used it, so I can't tell what its strengths 
are. Can you?
>   2. http://tanakh.github.io/Peggy
Notice that in the examples of bothy frisby and peggy, parsing a number 
only parses a string of digits, then passes it to 'read', i.e. another 
parser. Is that efficient, elegant parsing?

I'm nevertheless intrigued by PEG parsers, because I once read about the 
connection between grammars and compression: A set of production rules can 
be quite a bit smaller than the actual text. This turns parsing upside 
down: The text is constant, the grammar unknown.


More information about the Haskell-Cafe mailing list