Repository navigation
(off topic) Modern parser generator for Haskell #1909
Description
Sorry for off topic here.
Recently, I asked the Haskell community (link) whether there was a modern parser generator. It turned out, there are some attempts that aren't production-ready. At least they're not mature enough to be used in GHC (haskellfoundation/tech-proposals#63, https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4711).
After some discussion and superficial studying of the works, I came to the following high-level requirements (link).
- a tool written in Haskell
- that produces an SGLL parser for a DDCFG
- the tool generates purely Haskell code
- or, the tool reads a grammar and generates a parser in memory (nice for prototyping)
- and the produced parser is
- fault-tolerant
- optionally incremental
Now, I have a couple of questions.
- What would be the correct requirements?
- Could you please roughly estimate the amount of work (in man-hours) of a project that implements such a tool? (relevant for Fault-tolerant GHC compilation pipeline haskellfoundation/tech-proposals#63)
Activity
jurgenvinju commentedon Jan 15, 2024
Always nice to meet a fellow parser generator. A really good parser generator can cost more than a man year to construct and test. Especially if you go and invent new algorithms. The expert on GLL and Haskell is Thomas van Binsbergen at universiteit van Amsterdam.
The requirements: for that I'd read the PhD thesis of Afroozeh and Izmaylova, Economopoulos, Eelco Visser and Jan Rekers. The treesitter community is also a valuable resource on context free general parsing.
Have fun!
deemp commentedon Jan 15, 2024
Thanks! Could you please recommend specific literature on error recovery in (S)GLL?
Afroozeh and Izmaylova left error recovery for future work:
I only found a paper about another formalism (LLR-system).
jurgenvinju commentedon Jan 16, 2024
Error recovery in GLR: Maartje de Jong (TU Delft), and some chapters in Jan Rekers' thesis.
Error recovery in GLL: Iguana's implementation has error recovery built in by Ali Afroozeh.
deemp commentedon Jan 16, 2024
Thank you!