LALRPOP, an LR(1) parser generator for Rust
smallcultfollowing.com
smallcultfollowing.com
Seems like the whole reason for LALR(1) parsers was performance, and parsing is no longer as significant an amount of time compared to the old days, while helpful feedback, which any parser generator approach tends to be bad at, is at a premium.
Maybe! I agree with the second half there but I think the first half is not totally spot on. For _small_ projects modern machines will parse through faster than you can perceive but as source code grows a pokey parser will out. Becomes increasingly frustrating as the parser sub-system is tied up with early analysis, making it difficult to modify without getting deeply involved in the rest of the compilation steps.
Does anyone know if there's a plan to move rusts own parser to a rust native tool? Now it apparently uses antlr4 along with some custom rust code:
Would there be a benefit to moving from hand coded to something like parent project for rustc? IIRC the rationale for hand-coding the parser was mostly speed (and a wish to avoid external (to rust) dependencies)?
https://github.com/rust-lang/rust/issues/28777
I'm not a compiler hacker, so I don't know how to weigh it really though.
In other words, it's not something I expect you can read a couple sentences about and hope to understand well...
So, if you have an item X that might call rules Y and Z, instead you have an item set {X, Y, Z}. This has the additional advantage that arbitrary left-recursion is handled naturally, since you're discarding the 'call graph' between rules when you build these sets.
To deal with the compressed stack frames that you've now built, you construct a goto table for each item set that tells you what to do based on what item has been returned to you, from the observation that only certain items could have 'called' certain other rules in the first place.
Finally, you add lookahead to your goto tables so that, in case of ambiguity, you can peek ahead to the next token and make your decision that way. This will not solve all ambiguity but it solves most cases in practice.
This is a very hand-wavy description, but I hope it is useful if you decide to look further into the Wikipedia article. Unfortunately I have never seen a complete description of an LR(1) parser that takes the conceptual approach, and I don't have time to write one here.
LR parsers build the tree from the bottom up. Productions / terminals get pushed onto a stack (shift) until there's enough information to decide what parent production to use, and children are popped off and replaced with the parent (reduce). The tree gets built post-order; the parents are built after the children are already built. The hard bit is figuring out whether the productions on the stack are enough to compose a parent rule or not.
LR parser generators figure out a state machine for making shift / reduce decisions quickly.
I'd say PEGs are easier to write as they're unambiguous. It's easy to understand what they do. I work on languages for a living, and I still have trouble wrapping my head around what an LR parser is doing.
LR parsers often exist just because that's how we've done things for decades and it's what everyone knows from their university language courses.
LR parser operate on a stream of tokens, so you have to force a distinction between syntax and parsing, which isn't always natural and just seems like unnecessary complication.
If you were writing a compiler, I'd recommend a PEG.
While that is technically true, it doesn't solve the actual issue of ambiguity, it just defines it away.
If you have a case in your language where two syntax rules both match, it's confusing to users because you have to arbitrarily decide that one of them is correct. The best-known example of this is the dangling else ambiguity: https://en.wikipedia.org/wiki/Dangling_else
Sure, PEGs by definition are unambiguous, but only because they arbitrarily decide that the first option always "wins." The language itself might still be ambiguous, but you aren't aware of it because the parser always chooses the first option.
Put another way, with PEGs you never know if:
a -> b / c;
a -> c / b;
Besides this, packrat parsing (the PEG parsing algorithm) is significantly more expensive than LR/LR parsing. Packrat parsing takes O(input length) memory -- significantly more than the O(tree depth) space of LL/LR.
I talk more about these issues in my blog article: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...
("a" / "aa") "a"
(This is because of how backtracking works in PEGs—or, more precisely, how it doesn't work. With the input string aaa, we'll first try to match ("a" / "aa") against the input in a left-biased way, which succeeds because "a" matches. Then we'll try to match the second expression—"a"—which also matches. Now we are done with the grammar but still have the last a in the input, so the grammar fails. There were untried alternatives, but they only appeared in earlier parts of the grammar which had already 'succeeded', so we never go back and try them.)
Additionally, both LR and PEG parsers take linear time to parse a given input, but PEG/packrat parsing has much larger constant factors. On small examples, this might not be a big deal (what's 0.2 seconds compared to 0.02 seconds when loading a file?) but when doing large amounts of parsing it can definitely be a minus on the PEG/Packrat side.