A Typed, Algebraic Approach to Parsing (2019)
14 points by fanf
14 points by fanf
This pairs well with flap: A Deterministic Parser with Fused Lexing by the same authors.
How would you compare it to a parser written like this? Does it seem like the same idea?
https://github.com/bablr-lang/language-en-json/blob/trunk/lib/grammar.js
I would similarly call it "algebraic" in that the parser is defined by series of pure functions which do work by yielding algebraic effects to their calling coroutine and are able to make further parsing decisions based on the results.
The performance numbers they report for each of the parsers don't feel that impressive?
E.g. simdjson can parse JSON at GB/s. For mainstream programming languages, the recursive descent parsers usually run at N million SLoC/s on a single core, which ends up being ~35*N MB/s. The closest to that is the arith example, which has a throughput of 14 MB/s, which would would likely translate to probably something like 400K SLoC/s. That's faster than typical Tree-sitter throughput (150-250K SLoC/s), but not close to common imperative parsers.