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.

KnowledgeGate Team

Exam prep & CS education

Updated 1 Nov 20266 min read
Bottom-Up Parsing Mistakes for GATE: Fix Errors That Cost Marks

You may remember closure, GOTO and parsing tables, yet lose the answer after one premature reduction, one extra pop or one GOTO read from the wrong state. A premature reduction, an extra pop, or a GOTO from the wrong state changes the parser's next valid action. For the shift-reduce and LR-family foundation, revise Bottom-Up Parsing in Compiler Design first. That post supplies the full shift-reduce trace and LR-family overview. The key checks here are handle selection, derivation order, stack-state popping, GOTO source, reduction lookahead, closure completion, and acceptance. Keep one invariant throughout: the current state and lookahead choose ACTION; a reduction then exposes the state from which GOTO is taken.

Mistake 1: Treating every visible right-hand side as the handle

A production's right-hand side may be visible on the symbol stack without being the current handle. The handle is the substring reduced in one step of the reverse rightmost derivation. State and lookahead identify it, not visual resemblance.

Consider:

  • E -> E + T | T

  • T -> T * F | F

  • F -> id

  • Input: id + id * id $

Suppose the stack symbols are E + T and the lookahead is *. Although E + T matches a production right-hand side, reducing it now leaves the stack at E with unread input * id $, or E * id. That has no valid continuation in this grammar. The correct action is to shift *, complete T * F, reduce that to T, and only then reduce E + T to E.

Mistake 2: Reversing the wrong derivation order

Bottom-up reduction path from id + id * id to E, with the wrong early E + T reduction ending at E * id.

Top-down practice favours leftmost derivations. Bottom-up parsing reverses a rightmost derivation.

For the same input, the stack-symbol sequence is:

id + id * id => F + id * id => T + id * id => E + id * id => E + F * id => E + T * id => E + T * F => E + T => E

Here => records a parser reduction, not the forward direction of a grammar production. The decisive order is at the end: reduce T * F to T before reducing E + T to E. In the actual parser, reducing E + T as soon as it appears, before shifting the pending * id, leaves E * id. That form has no valid continuation in this grammar, so the parse gets stuck rather than accepting a different grouping.

Mistake 3: Popping grammar symbols but forgetting their states

Why: The error comes from counting grammar symbols instead of symbol-state pairs on the interleaved stack.

Wrong: For C -> c C, popping two entries from 0 c 3 C 6 removes only C 6. Taking GOTO(3,C)=6 recreates the same stack, so the reduction loops instead of producing 0 C 2.

Instead: For A -> beta, pop 2 x |beta| entries, then use GOTO from the exposed state. An epsilon production pops zero.

Use this LR(0) grammar:

  • (0) S' -> S

  • (1) S -> C C

  • (2) C -> c C

  • (3) C -> d

Now trace input c d d $:

Step

Stack

Unread input

ACTION

0

0

cdd$

s3

1

0 c 3

dd$

s4

2

0 c 3 d 4

d$

r3, pop d 4, GOTO(3,C)=6

3

0 c 3 C 6

d$

r2, pop c 3 C 6, GOTO(0,C)=2

4

0 C 2

d$

s4

5

0 C 2 d 4

$

r3, pop d 4, GOTO(2,C)=5

6

0 C 2 C 5

$

r1, pop C 2 C 5, GOTO(0,S)=1

7

0 S 1

$

accept

The counts are exact. Production 3 has one symbol on its right-hand side, so steps 2 and 5 each pop two entries. Productions 2 and 1 each have two symbols, so steps 3 and 6 each pop four entries.

Correct LR(0) cdd$ stack table with four GOTO arrows anchored to their resulting stack entries.

Mistake 4: Reading GOTO from the state that was removed

Why: The error comes from confusing the state that selected the reduction with the state exposed after the pop.

Wrong: Reducing C -> c C removes states 6 and 3. Using either for GOTO misses 0 C 2, so later ACTION lookups use the wrong state.

Instead: Pop c 3 C 6, expose 0, then push C and GOTO(0,C)=2. Rebuild the trace with these steps, then practise with these LR(0) solved questions.

Mistake 5: Applying one parser family's reduction rule to another

For a completed item A -> alpha ., assume FOLLOW(A) = { ), $ } while its CLR lookahead is { $ }.

Parser

Where this item reduces

LR(0)

Every terminal

SLR(1)

Only ) and $

CLR(1)

Only $ for this item

LALR(1)

On lookaheads obtained after merging identical LR(0) cores

Therefore, on lookahead +, LR(0) proposes the reduction, while this SLR(1) and CLR(1) example does not. Similar-looking item sets do not make their reduction rules interchangeable. For full item-specific lookahead practice, work through these CLR(1) parser items solved questions.

Mistake 6: Stopping closure early or merging states by a partial match

For the trace grammar:

I0 = { S' -> . S, S -> . C C, C -> . c C, C -> . d }

GOTO(I0,c) = I3 = { C -> c . C, C -> . c C, C -> . d }

Why: The error comes from treating one generated item or one shared core item as proof that the set is complete.

Wrong: Stopping I3 at { C -> c . C } removes shifts on c and d, so valid input cdd$ rejects at I3. Merging states with only one shared core item spreads lookaheads into unrelated contexts, creating invalid reductions or conflicts.

Instead: Apply closure until no item is added. For LALR, merge only states whose entire LR(0) cores are identical, union their lookaheads, then check the merged state for conflicts.

Mistake 7: Calling every completed item an accept state

Why: The error comes from using a right-end dot alone as the acceptance test.

Wrong: Accepting at C -> d . leaves d$ unread. Accepting at S -> C C . skips reduction 1 and GOTO(0,S)=1, so neither completes the augmented start production.

Instead: Reduce completed ordinary items on the parser family's allowed lookaheads. Accept only at S' -> S . with lookahead $, without shifting $.

Write this beside the table: Accept only on the completed augmented start item and end marker.

A 60-second bottom-up parsing error check

Before finalising an answer:

  1. Name the parser family.

  2. Read the current state and lookahead.

  3. Copy the exact ACTION.

  4. For A -> beta, count |beta|.

  5. Pop 2 x |beta| entries, then take GOTO from the newly exposed state.

  6. Accept only for S' -> S . on $.

The short version

Never reduce by visual pattern alone. Never separate a grammar symbol from its state. Never borrow a reduction rule from another LR family.

Use the Compiler Design course for structured revision, then test the process under time pressure with the GATE Test Series. When planning the rest of the syllabus, continue through the GATE CS exam resources.