LALRPOP, an LR(1) parser generator for Rust | Hacker News Reader

LALRPOP, an LR(1) parser generator for Rust

github.com

27 pointsibraheemdev11 comments

Maybe I'm being naive here, but the lalrpop grammer seems very similar to rust code. Couldn't this be a proc macro instead of a generator? You could define a parse tree as an enum. Each field of the parse tree should implement a Parse trait and then the enum can derive its own parse trait.

Perhaps the output won't be so smart if its only building the parser element by element rather than seeing the full picture. Also grammers like `"(" Term ")"` would probably be implemented as a struct and that's a bit less developer friendly to quickly code. (Although it could be tuple `(LParen, Term, RParen)` which isn't too far off)

Maybe I'll take a deeper look into the code when I have some free time, but I think I would prefer a proc macro based system

I believe there is a work in progress implementation of a proc-macro interface for lalrpop here [0]

0: https://github.com/dtolnay/lalrproc

Not saying it's ever sensible to go against dtolnay and his infinite wisdom when it comes to proc macros, but I think i might create my own alternative implementation. I'm not sure though, I'll need to play around with lalrpop some more first and figure out some complex scenarios before I decide

From Nim's tutorial: "Macros are very powerful. A piece of good advice is to use them as little as possible, but as much as necessary."

What advantage does a parser generator provide over a parser combinator library like nom?

It's harder to express complex grammars in combinator form.

Combinators excel best for relatively simply regular languages (eg., json, html, etc.).

Languages with lots of "modality" in parsing, ie., context switching, are easier to express in generator-form (eg., antlr).

Wouldn't the mode be encoded in the type system via the tokens your parser is generating? I mean, every mode would be a different enum containing all the tokens that are valid in that mode?

Sure, I imagine it's possible to express any parser-generator grammar in combinator form. It's just a question of how easy it is to do by hand, and how efficient the parsing process would be.

One of the main differences is that LALR parsers don't use backtracking to implement "choice". Parsing happens in a single pass over the input. With parser combinators, ambiguity is silently resolved by accepting the first option that the parser tries. Bottom up LR parsers also do a better job of dealing with left recursion, compared to top down parsers. If you want to parse something using a recursive descent parser (or combinators) you may need to rephrase the grammar to avoid left recursion.

Some of the main downsides of LR parsers are that you need to use a parser generator and you have to know how to resolve possible shift/reduce conflicts. It's more complicated than top down parser, which is just a bunch of regular recursive functions.

LALRPOP is one of the friendliest syntax parser generators that I ever worked with in any language.

If only issue [1] would be fixed, it would make it much better.

[1] https://github.com/lalrpop/lalrpop/issues/195

Unpopular opinion: anything that outputs an AST is, by definition, not a parser but a recognizer with extra steps. The reason for this is that an abstract tree has not yet been parsed. The input is only parsed once the AST has been traversed, presumably by a much-maligned recursive descent method.

Reply on news.ycombinator.com