Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
mrbackend
@mrbackend
Can sparse parsers be used in fs2 0.9.2 streams? If not, any plans to upgrade sparse? If this seems like a stupid question, it probably is; coming from a beginner who's taking on a task he's not at all competent to do :smile:
Daniel Spiewak
@djspiewak
At present, sparse cannot be used with fs2. It should be pretty easy to do though. Sparse primarily just relies on the State monad for the heavy lifting on its threading. fs2's equivalent of Process1 can do that pretty easily
mrbackend
@mrbackend
Thanks for your feedback! Easy for you, I guess :), I'll have to study this for a bit. BTW, do you know if all parser combinators create recursive descent parsers, or are there any, say, LR parser combinators out there?
Daniel Spiewak
@djspiewak
@mrbackend There are several different parser combinator algorithms. Sparse implements derivative parsing, which is sort of like a "breadth-first recursive descent" and is a very distinct algorithm. GLL combinators implements a unique algorithm which is sort of like a multi-path recursive descent (it runs multiple stacks in parallel, with common-suffix elimination, similar to RINGLR). I believe it was Swierstra who wrote some papers in the 90s about LALR-generating parser combinators, but they tend to be somewhat uninteresting since they're effectively just building expression trees and then compiling a standard LALR automaton in memory (i.e. not directly evaluated, so the combinators are just syntax). And looping back to more conventional algorithms… Most practical parser combinator libraries actually implement a form of Packrat parsing, which is to say a memoized form of PEG parsing (a construct which characterizes "ad-hoc" recursive-descent parsers). Packrat parsing has some advantages, such as worst-case O(n^2) and limited support for left-recursion, and the constant factors aren't terrible.
btw, I should warn you that I never completed sparse, and there are some bugs in the implementation that I never fixed. so… uh… very experimental scratch-pad software :-)