Bottom-Up Syntax Analysis Formula Sheet: LR Rules and Worked Trace
Revise bottom-up parsing through compact rules for handles, viable prefixes, LR items and SLR table construction, then follow one consistent grammar from augmentation to acceptance.
KnowledgeGate Team
Exam prep & CS education

Bottom-up parsing questions mix handles, viable prefixes, dotted items, FOLLOW sets, ACTION/GOTO entries and stack operations. Forgetting one rule can quickly spoil the complete construction. A compact SLR reference uses S' -> S, S -> a A, A -> b A | c and trace abbc$ to acceptance. For the full S -> C C grammar and cdd$ LR(0) construction, read LR(0) Parsing Explained: Closure, GOTO and Conflicts. For wider core CS study, explore the GATE, PSU, Engineering & Technical Exams.
1. Bottom-Up Parsing Formula Sheet in One View
Bottom-up parsing constructs a parse tree from leaves to root, reproducing a rightmost derivation in reverse. A configuration is a symbol-state stack plus unread input ending in $; top state and lookahead select ACTION[state, lookahead].
Rule | Formula or meaning | When to use |
|---|---|---|
Dot positions | A -> X1 X2 ... Xn has n + 1 LR(0) items | Count item forms. |
Closure | Add productions repeatedly for a nonterminal immediately after a dot | Complete an item set. |
GOTO | goto(I, X) = closure({A -> alpha X . beta | A -> alpha . X beta in I}) | Move the dot over X. |
Reduction | For A -> beta, pop 2 x |beta| entries from a combined symbol-state stack | Push A and GOTO[new top, A]. |
Epsilon reduction | Pop zero entries | Reduce A -> epsilon. |
ACTION is shift, reduce, accept or error. Consult GOTO only after pushing a reduced nonterminal.
2. Handle, Handle Pruning and Viable Prefix
A handle is a production body beta whose reduction to A is the next valid reversal of a rightmost derivation. Use it to choose the next reduction; a reducible-looking substring need not be the handle. Handle pruning replaces handles by their left-hand sides until only the start symbol remains. Use it to reconstruct the reverse derivation.
Take (0) S' -> S, (1) S -> a A, (2) A -> b A, (3) A -> c. The rightmost derivation is S => aA => abA => abbA => abbc. Its reverse handle sequence is abbc -> abbA -> abA -> aA -> S, matching reductions r3, r2, r2, r1 later.
A viable prefix is a prefix of a right-sentential form that does not pass its handle's right end. In this trace, a, ab, abb, aA and abA are viable prefixes represented by LR states.
3. LR(0) Items, Closure and GOTO for the Worked Grammar
An item A -> alpha . beta says that alpha is recognised and beta is still expected. Use the dot to represent parser progress. The grammar has 2 + 3 + 3 + 2 = 10 item forms: S' -> S contributes 2, S -> a A contributes 3, A -> b A contributes 3 and A -> c contributes 2. The same form may occur in multiple sets.
Complete collection:
I0 = {S' -> .S, S -> .a A}
I1 = {S' -> S.}
I2 = {S -> a . A, A -> .b A, A -> .c}
I3 = {A -> b . A, A -> .b A, A -> .c}
I4 = {A -> c.}
I5 = {S -> a A.}
I6 = {A -> b A.}
Transitions: I0 -S-> I1, I0 -a-> I2, I2 -A-> I5, I2 -b-> I3, I2 -c-> I4, I3 -A-> I6, I3 -b-> I3 and I3 -c-> I4. Use them to create shift and GOTO entries.
4. SLR ACTION and GOTO Construction Rules
FIRST(A) = {b, c}, FOLLOW(S) = {$} and FOLLOW(A) = {$}. FOLLOW(A) comes from the final A in S -> a A.
Construction rules:
If
goto(Ii, a) = Ijfor terminala, setACTION[i, a] = sj.If
A -> alpha .is inIiandA != S', setACTION[i, a] = r(A -> alpha)for eachainFOLLOW(A).If
S' -> S.is inIi, setACTION[i, $] = accept.If
goto(Ii, A) = Ijfor nonterminalA, setGOTO[i, A] = j.
Use the terminal rules to fill ACTION and the nonterminal rule to fill GOTO.
state | a | b | c | $ | S | A |
|---|---|---|---|---|---|---|
0 | s2 | 1 | ||||
1 | accept | |||||
2 | s3 | s4 | 5 | |||
3 | s3 | s4 | 6 | |||
4 | r3 | |||||
5 | r1 | |||||
6 | r2 |
No cell receives two actions, so this grammar has no SLR conflict.
5. Fully Worked Shift-Reduce Trace for abbc$
State 0 on a shifts to 2; state 2 on b shifts to 3; state 3 on b shifts to 3; state 3 on c shifts to 4. State 4 on $ applies r3: A -> c, then GOTO(3, A) = 6. State 6 on $ applies r2: A -> b A, then GOTO(3, A) = 6. State 6 on $ applies r2 again, then GOTO(2, A) = 5. State 5 on $ applies r1: S -> a A, then GOTO(0, S) = 1. State 1 on $ accepts.
The reductions are c -> A, bA -> A, bA -> A, aA -> S, giving abbc -> abbA -> abA -> aA -> S. On the combined stack, A -> b A pops 2 x 2 = 4 entries, while A -> c pops 2 x 1 = 2 entries.
6. LR(0), SLR(1), LALR(1) and CLR(1) Compared
Method | Basis | Reduction lookahead | State count | When to use |
|---|---|---|---|---|
LR(0) | LR(0) items | All terminals for a completed item | Same as SLR | Test the strictest method. |
SLR(1) | LR(0) items |
| Same as LR(0) | Restrict LR(0) reductions. |
CLR(1) |
| Item-specific | Usually more | Use precise lookahead. |
LALR(1) | Merged identical LR(0) cores | Union of lookaheads | Same as LR(0) | Keep stronger compact tables. |
In CLR closure, [A -> alpha . B beta, a] adds [B -> .gamma, b] for each b in FIRST(beta a). Use it when a nonterminal follows the dot. LALR merging can introduce a reduce-reduce conflict.
Remember LR(0) subset SLR(1) subset LALR(1) subset CLR(1) and states(LR(0)) = states(SLR) = states(LALR) <= states(CLR). See SLR vs CLR vs LALR Parsers for GATE for details.
7. Conflicts, Traps and How GATE-Style Questions Test the Sheet
A shift-reduce conflict puts a shift and reduction in one ACTION cell; a reduce-reduce conflict puts two reductions there. Use these while scanning. Every LR grammar is unambiguous, so an ambiguous grammar cannot be LR. Yet an unambiguous grammar can fail a chosen method. Precedence and associativity may resolve expression conflicts, but follow the question's convention.
Traps: forgetting augmentation; expanding a symbol not immediately after the dot; moving the dot without closure; using FIRST instead of FOLLOW for SLR reductions; reducing on every terminal as in LR(0); popping only
|RHS|combined-stack entries; using GOTO for a terminal; accepting a completed start production without lookahead$; or merging CLR states with different LR(0) cores.
Typical tasks ask you to count items, compute closure or GOTO, fill an ACTION cell, trace a string, find a conflict, or compare power and states. Use the linked LR(0) treatment for the separate C C grammar and cdd$ trace.
Augment the grammar.
Count dot positions.
Construct
closure(I0).Apply GOTO to every grammar symbol.
Calculate FOLLOW sets.
Fill shift, reduce, accept and GOTO entries.
Scan every cell for conflicts.
Trace the stack until
acceptor error.
Self-check: 7 states, 10 grammar-level item forms, reductions r3, r2, r2, r1, and accepted input abbc$. For structured lessons, continue with the GATE CS Compiler Design Course. For a broader preparation path, use GATE CS & IT 2027 Guidance by Sanchit Sir.
Keep learning
Bottom-Up Parsing in Compiler Design: Shift-Reduce, LR Parsers, and Worked Examples
Learn bottom-up parsing as a mechanical stack process, then work through an expression trace and a complete LR(0) automaton construction.
Bottom-Up Parsing in Compiler Design: Shift-Reduce Trace, LR Items and Conflicts
Follow a nested-parentheses LR(0) parse from input to acceptance, derive every item set, and see why lookahead changes parser-family conflicts.
Bottom-Up Parsing Mistakes for GATE: Fix Errors That Cost Marks
Prevent the small LR parsing errors that spoil an otherwise correct solution. Trace two examples and use a final check for handles, states, GOTO, closure and acceptance.
Top-Down Syntax Analysis Formula Sheet: FIRST, FOLLOW, LL(1) and Predictive Parsing Revision Notes
Revise top-down parsing as one connected workflow, from grammar rewriting and FIRST/FOLLOW sets to an LL(1) table and a complete stack trace.





