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

Updated 10 Nov 20266 min read
Bottom-Up Syntax Analysis Formula Sheet: LR Rules and Worked Trace

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) = Ij for terminal a, set ACTION[i, a] = sj.

  • If A -> alpha . is in Ii and A != S', set ACTION[i, a] = r(A -> alpha) for each a in FOLLOW(A).

  • If S' -> S. is in Ii, set ACTION[i, $] = accept.

  • If goto(Ii, A) = Ij for nonterminal A, set GOTO[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

FOLLOW(lhs)

Same as LR(0)

Restrict LR(0) reductions.

CLR(1)

[A -> alpha . beta, a]

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.

  1. Augment the grammar.

  2. Count dot positions.

  3. Construct closure(I0).

  4. Apply GOTO to every grammar symbol.

  5. Calculate FOLLOW sets.

  6. Fill shift, reduce, accept and GOTO entries.

  7. Scan every cell for conflicts.

  8. Trace the stack until accept or 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.