search

objmagic / LR

explore different techniques to generate LR(k) parsing code
MIT License
14 stars 1 forks source link

Generation of stackless LR(1) parser #2

Open objmagic opened 8 years ago

objmagic commented 8 years ago

Good news: I finally decide to spend some time and dive into LR parsing again. The result is we have a stackless LR(1) parser for grammar 4.55 in ASU86. The idea of course comes from Ralf Hinze's paper. This is particular cool because no explicit stack data structure is present now. The procedure of how to write such stackless parser is also clear to me.

Bad news:

  1. MetaOCaml still cannot generate pattern matching.
  2. Even if 1 is resolved, the program to generate such parser could be horribly complex. I expect there will tons of GADT, memorization tricks, code generation hacks, etc... Anyway, it will definitely be a triumph if I can finish it
  3. Consider 2 is done. Menhir, as a very mature and advanced parser generator, has many advantages over our technique. Although the aim of this project is different, I still expect our parser can be usable in real world, which means extra tons of effort to bring it to usable condition. I still remember to original goal of this project, which is to design a more PEG-like parser generator.

any opinion? @yallop

Storyyeller commented 6 years ago

Hi, I just came across this project and noticed that the readme says that it is an "improvement" to Derivation of a Typed Functional LR Parser. In what ways do you improve on the algorithm described in the paper?

I've been studying stackless LR parsing recently as well, so I'm curious what you found.

objmagic commented 6 years ago

@Storyyeller sorry, this project started two years ago and was kind of abandoned. I couldn't give you a good answer now...