Bottom-Up Parsing in Compiler Design: Shift-Reduce, LR Parsers, and Worked Examples

Many aspirants know the LR acronym ladder but freeze when tracing actions or counting states. Syntax analysis, also called parsing, is the second compiler phase. Bottom-up parsing, also called shift-reduce parsing, works from the tokens up to the start symbol using a stack and four actions, and a full parse of id + id * id takes fourteen of them. Once that stack discipline is clear, LR(0), SLR(1), LALR(1) and CLR(1) stop being acronyms and become differences in how much lookahead a single state is allowed to carry.

What bottom-up shift-reduce parsing actually does

The lexical analyser hands the parser a flat stream of tokens, one per lexeme; how that stream is produced is worked out in Lexical Analysis in Compiler Design. Syntax analysis takes over from there. It asks whether that token order can be generated by a context-free grammar, and builds the parse tree that proves it.

A bottom-up parser moves from leaves to root through four actions:

• SHIFT: push the next token.

• REDUCE: replace the top handle with a production's left-hand side.

• ACCEPT: finish with the start symbol and no input.

• ERROR: no valid action exists.

A handle matches a production's right-hand side and is the correct next reduction. The parse replays a rightmost derivation in reverse.

Worked shift-reduce parse of id + id * id

Use the classic expression grammar:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

Now parse id + id * id, with $ as the end marker.

At step 9 the parser shifts *, rather than reducing E + T by E -> E + T, because multiplication binds more tightly than addition. That choice is not a judgement call at parse time: the parser's action table already carries one entry for the pair (current state, lookahead *), and the entry says shift.

The handles pruned, in order, are id, F, T, id, F, id, T * F and E + T. Compare that sequence with this rightmost derivation:

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

Read bottom to top and it matches the reductions. The final tree groups the expression as id + (id * id), placing multiplication below addition.

LR parser family, power and state hierarchy

LR parsers automate handle finding. LR reads input Left to right and produces a Rightmost derivation in reverse. Grammar-handling power increases as follows:

LR(0) < SLR(1) < LALR(1) < CLR(1)

CLR(1), or canonical LR(1), accepts the largest class here. LL is top-down and leftmost. LR is bottom-up and rightmost-in-reverse. Every LL(1) grammar is LR(1), but not conversely.

For one grammar, LR(0), SLR(1) and LALR(1) have the same state count. LALR merges CLR states with identical LR(0) cores. CLR keeps lookahead-distinct states separate, so it has at least as many states. A grammar that separates all three, with the state counts and the shift/reduce conflict written out entry by entry, is worked in SLR, CLR and LALR Parsers Compared for GATE.

Yacc and bison generate LALR(1) parsers for strong coverage with compact tables. Operator-precedence parsing is a narrower shift-reduce technique.

Worked LR(0) item sets and state count

First augment the grammar to create a unique accept condition.

0. S' -> S
1. S -> C C
2. C -> c C
3. C -> d

An LR(0) item's dot shows how much has been recognised. closure expands a non-terminal after the dot. goto moves the dot over one symbol and takes closure.

I0 = { S' -> .S, S -> .C C, C -> .c C, C -> .d }
I1 = { S' -> S. }                  (accept)
I2 = { S -> C .C, C -> .c C, C -> .d }
I3 = { C -> c .C, C -> .c C, C -> .d }
I4 = { C -> d. }                   (reduce C -> d)
I5 = { S -> C C. }                 (reduce S -> C C)
I6 = { C -> c C. }                 (reduce C -> c C)

From I0, S, C, c and d reach I1, I2, I3 and I4. From I2, they lead to I5, I3 and I4 on C, c and d. From I3, those symbols reach I6, I3 and I4.

There are seven LR(0) states, I0 through I6. SLR(1) and LALR(1) also have seven. CLR(1) has ten, which LALR merges back to seven. Thus, CLR state count >= LALR state count = SLR state count = LR(0) state count.

Conflicts and traps that cost marks

A shift-reduce conflict offers both actions on one lookahead. In the dangling-else case, preferring shift attaches else to the nearest unmatched if. A reduce-reduce conflict offers two reductions on one lookahead.

Keep these corrections ready:

• LL is top-down and leftmost; LR is bottom-up and rightmost-in-reverse.

• LALR and SLR have the same state count, but reduce entries can differ.

• A grammar can be CLR(1) but not LALR(1). Merging CLR states may introduce a reduce-reduce conflict, but it cannot introduce a shift-reduce conflict.

• Always add S' -> S before constructing items, or the accept item will be missing.

• Do not reduce just because a right-hand side is on the stack. The lookahead may require a shift, as at step 9.

How GATE and interviews test bottom-up parsing

Questions ask you to trace moves, construct item sets, count states, classify grammars, identify conflicts, or compare LL and LR. The official GATE CS syllabus published by the organizing IIT lists Parsing and syntax-directed translation under Compiler Design. Marks split, question counts and paper rules change from cycle to cycle, so read those from that year's official GATE information brochure on the organizing IIT's portal.

The topic also appears in university, PSU, ISRO and UGC-NET questions and compiler-course vivas, but less often in product-company coding rounds. The GATE CS Exam Preparation hub places it within the full subject set.

The short version and your next step

Bottom-up parsing reduces tokens to the start symbol by reversing a rightmost derivation. LR power rises from LR(0) to CLR. LR(0), SLR and LALR share a state count; CLR may have more. Questions focus on traces, counts, conflicts and classification.

For full subject-wise Compiler Design teaching with parses worked live, use GATE Guidance by Sanchit Sir. To pressure-test parse-trace speed and state counting under exam conditions, use the GATE Test Series.

Redo the first example for id * id + id without looking. Then build LR(0) items for a fresh two-production grammar and count its states.