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

[Mario Blažević]

On 2018-08-27 04:55 PM, Olaf Klinke wrote:

>> 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?

	If you're looking for a newer implementation of PEGs, there's my 
grammatical-parsers library. It's also closer to the formal grammar 
notation and it uses the standard parsing combinators, so it seems like 
it should tick off a few of your boxes.


> 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.

	This is a nice idea, but it's unlikely to ever have a reasonably fast 
compressor implementation. Most interesting questions you can ask about 
context-free grammars are undecidable, and PEGs are even more complex 
from the theoretical point of view.