Shift-Reduce Parsing Mechanics & LR(0) Canonical Items
“Handles, viable prefixes, closure and goto operations, and the canonical LR(0) collection.”
1.The Handle Pruning Engine
§ 3.1.Bottom-up parsers trace the reverse of a rightmost derivation: S = gamma_0 Rightarrow_{rm} gamma_1 Rightarrow_{rm} dots Rightarrow_{rm} gamma_n = w.
Starting with the input string w = gamma_n, the parser searches for the Handle eta_n inside gamma_n, replaces it with A_n (reduction) to obtain gamma_{n-1}, and repeats until reaching the start symbol S.
The Shift-Reduce Model: The parser maintains a stack and input buffer. It executes four fundamental actions:
1. Shift: Read the next input token and push it onto the stack.
2. Reduce: Pop the handle eta from the top of the stack and push the non-terminal A (where A o eta).
3. Accept: Successfully finish parsing when the stack contains only S' and input is exhausted ($$$).
4. Error: Raise syntax error when no valid shift or reduction is possible.
DFA of Viable Prefixes: The collection of sets of LR(0) items under the CLOSURE and GOTO operations forms the states and transitions of a DFA that accepts exactly the viable prefixes of the grammar.
In item A -> alpha . beta, alpha is already on the parser stack (seen), while beta is expected to appear in future input (predicted). When the dot reaches the far right A -> alpha beta ., the entire handle is present and ready for reduction.
2. Worked Analysis: Computing LR(0) State Item Count
Remember to augment the grammar with S' -> S before generating state I0.
Consider the grammar:
S -> C C
C -> c C | d
Determine the number of states in the canonical collection of LR(0) items.
Step 1: Augment the grammar: S' -> S.
Step 2: Compute I0 = CLOSURE({S' -> . S}):
- Add S' -> . S
- S has dot before it: add S -> . C C
- C has dot before it: add C -> . c C and C -> . d
I0 = {S' -> . S, S -> . C C, C -> . c C, C -> . d}.
Step 3: Compute transitions from I0:
- GOTO(I0, S) = CLOSURE({S' -> S .}) = I1 = {S' -> S .}
- GOTO(I0, C) = CLOSURE({S -> C . C}) = I2 = {S -> C . C, C -> . c C, C -> . d}
- GOTO(I0, c) = CLOSURE({C -> c . C}) = I3 = {C -> c . C, C -> . c C, C -> . d}
- GOTO(I0, d) = CLOSURE({C -> d .}) = I4 = {C -> d .}
Step 4: Compute transitions from remaining states:
- From I2 on C: GOTO(I2, C) = CLOSURE({S -> C C .}) = I5 = {S -> C C .}
- From I2 on c: GOTO(I2, c) = I3.
- From I2 on d: GOTO(I2, d) = I4.
- From I3 on C: GOTO(I3, C) = CLOSURE({C -> c C .}) = I6 = {C -> c C .}
- From I3 on c: GOTO(I3, c) = I3.
- From I3 on d: GOTO(I3, d) = I4.
- States I1, I4, I5, I6 have only complete items (no outgoing transitions).
Total States = {I0, I1, I2, I3, I4, I5, I6} = Exactly 7 states.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.