LR Parsing Introduction
You'll learn: What LR(k) parsing is and why it scans left-to-right while building a rightmost derivation in reverse.
What is LR Parsing?
LR parsing is a powerful bottom-up parsing technique where LR stands for:
- L: Left-to-right scan of the input
- R: Rightmost derivation in reverse
The (k) in LR(k) indicates how many tokens of lookahead the parser uses to make decisions (typically k=1).
How It Works
Unlike top-down parsing that starts from the start symbol and predicts productions, LR parsing works backwards. It reads your token stream from left to right but discovers the parse tree from the leaves up to the root—essentially reversing a rightmost derivation.
Think of it like watching a time-lapse video of a tree growing, but played in reverse: you see the leaves first, then branches combine into bigger branches, until finally you reach the trunk (the start symbol).
Why "Rightmost Derivation in Reverse"?
In a rightmost derivation, you always expand the rightmost non-terminal first when building the parse tree top-down. LR parsing does the opposite: it reduces handles (the rightmost groups of symbols matching a production's right side) back into non-terminals, working from bottom to top.
The Power of LR
LR parsers are more powerful than LL parsers—they can handle a broader class of grammars and detect syntax errors as soon as possible (at the earliest point in the left-to-right scan where no valid continuation exists).
Key Takeaway: LR(k) parsing scans input left-to-right and builds the parse tree bottom-up by reversing a rightmost derivation, using k tokens of lookahead to make shift/reduce decisions.