4 ms·

I find LR parsers to be conceptually simple--they're the same idea as recurisve descent parsers with the optimization that the many stack frames that result fro

I find LR parsers to be conceptually simple--they're the same idea as recurisve descent parsers with the optimization that the many stack frames that result from "recursively descending" are bundled up into a single stack frame, corresponding to an 'item set' that contains every parse item that you might recursively descend into. You do not actually add a stack frame until you consume a token of input and "call" the next item set based on what token of input it was. 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.

wfunction 11y ago
Sorry, but I find this more confusing than anything. I would explain it more in terms of nondeterministic parsing (i.e. delaying the choice of the production rather than picking the production immediately) or in terms of "bottom-up" parsing (going from the string to the start symbol rather than the other way around). That said, it's way easier to understand what it should be doing than it is to understand it well enough to write one yourself.

wfunction 11y ago

Sorry, but I find this more confusing than anything. I would explain it more in terms of nondeterministic parsing (i.e. delaying the choice of the production rather than picking the production immediately) or in terms of "bottom-up" parsing (going from the string to the start symbol rather than the other way around). That said, it's way easier to understand what it should be doing than it is to understand it well enough to write one yourself.