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.