[Haskell-cafe] Alternative instance for non-backtracking parsers
mblazevic at stilo.com
Fri Aug 31 19:58:20 UTC 2018
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.
More information about the Haskell-Cafe