4 ms·

Great explanation, thanks. Do you know of any haskell parser combinator libraries that exhibit the properties you're looking for?

• chowells 6y ago
  uu-parsinglib and Earley are interesting points in the space. The former[1] is monadic rather than Applicative, but it has a lot of interesting properties related to error correction and producing online results. Sometimes it feels magical to watch the error correction at work, and the online nature makes it good for memory use if your parser is constructed to take advantage of it. The latter[2] is strictly applicative, though it's inside an environment monad for making shared productions explicit. Because the grammar portions are strictly applicative, it actually supports turning a grammar around and producing a list of possible outputs from the parser associated with the input sequence that would produce them. It shows off the introspection capabilities nicely, but sometimes you really just want to write a context-sensitive parser, and the applicative interface doesn't give you that power. (Nor does the underlying algorithm support it, so it's nice to match the interface expressiveness to the algorithm power.) [1] https://hackage.haskell.org/package/uu-parsinglib https://hackage.haskell.org/package/uu-parsinglib [2] https://hackage.haskell.org/package/Earley https://hackage.haskell.org/package/Earley