Bottom-Up Parsing in Compiler Design: Shift-Reduce Trace, LR Items and Conflicts

Handles, viable prefixes, LR item sets, stack actions and conflicts are often revised as separate definitions. A single question can require all of them at once. A nested-parentheses grammar keeps the symbols small enough to verify every representation, while a separate conflict state shows why parser families can disagree.

Bottom-up parsing is a reverse rightmost derivation

Bottom-up parsing starts with the input and replaces each handle by its production's left-side nonterminal until only the start symbol remains. A handle is not just a matching production body. It must be the next reduction in the reverse of a rightmost derivation.

A shift grows a viable prefix. A reduction prunes one handle. The top LR state records what may legally come next. Acceptance occurs when S' -> S . is reached with $ as lookahead.

For the expression trace and LR-family orientation, Bottom-Up Parsing in Compiler Design: Shift-Reduce, LR Parsers, and Worked Examples uses id + id * id and a seven-state S -> CC example. LR(0) Parser Explained: Bottom-Up Parsing, Item Sets and a Worked Example owns the full S -> CC construction and cdd$ trace. The nested-parentheses grammar below instead makes each handle, viable prefix, item set and stack state agree at every action. Syntax analysis sits in the wider CS Fundamentals for Exams & Placements path with automata and compiler design.

Worked example: parse ((n)) with a complete LR(0) table

Use this augmented grammar:

(0) S' -> S
(1) S  -> ( S )
(2) S  -> n

The input is ((n))$. The LR(0) ACTION and GOTO table follows:

A dash means error, not an epsilon move. The parser configurations proceed as follows:

For a production body of length k, reduction removes 2k stack entries because grammar symbols and states alternate. The handle-pruning sequence is:

((n)) => ((S)) => (S) => S

The handles are n, (S) and (S). The checked totals are 5 input shifts, 3 reductions, then accept. The repeated state 2 reflects the self-loop on an opening parenthesis, not a new item set.

Derive the states instead of memorising the table

The six LR(0) item sets are:

I0={S'->.S, S->.(S), S->.n}
I1={S'->S.}
I2={S->(.S), S->.(S), S->.n}
I3={S->n.}
I4={S->(S.)}
I5={S->(S).}

closure adds productions for the nonterminal after a dot. From S'->.S, add both S productions to get I0. GOTO moves the dot across one symbol and closes the result: GOTO(I0, '(') = I2, GOTO(I2, '(') = I2 and GOTO(I2, S) = I4.

A dot before ( or n creates a shift. A completed ordinary item creates an LR(0) reduction in every terminal column. S'->S. accepts only on $. The self-loop GOTO(I2, '(') = I2 follows because shifting another opening parenthesis restores the same closure.

Reducing n in state 3 exposes state 2, so GOTO(2,S)=4. Reducing the inner (S) pops six entries, exposes the earlier state 2 and returns to state 4. Neither reduction consumes input.

Handles, viable prefixes and stack states tell one story

Remove state numbers after every action. The symbol projections are epsilon, (, ((, ((n, ((S, ((S), (S, (S) and S. Each is a viable prefix that does not extend beyond the next handle in a right-sentential form.

Reverse the reductions and the rightmost derivation becomes:

S => (S) => ((S)) => ((n))

Each arrow expands the only available nonterminal, so it is also the rightmost nonterminal. The parser reverses those steps: the inner n reduces first, then the inner (S), then the outer (S). Reducing the outer parentheses earlier would fail because their interior is not yet a single S.

Why LR(0), SLR(1), CLR(1) and LALR(1) can disagree

Consider a separate grammar:

S' -> S
S  -> L = R | R
L  -> * R | id
R  -> L

In LR(0) core state J={S->L.=R, R->L.}, the first item shifts on =, while the completed second item reduces by R->L. That is a shift-reduce conflict.

SLR(1) does not fix it. S->L=R puts = in FOLLOW(L). End-position propagation through R->L, L->*R and both S productions gives FOLLOW(L)=FOLLOW(R)={=,$}. SLR still reduces R->L on =, alongside the shift.

Canonical LR(1) keeps [S->L.=R,$] and [R->L.,$]. Reduction is allowed only on $, leaving only shift on =. CLR(1) and LALR(1) handle this grammar, while SLR(1) and LR(0) do not. The SLR vs CLR vs LALR Parsers for GATE: States & Conflicts page owns the full cross-family state construction; this state-level check isolates why the conflicting ACTION cell changes.

Traps that break cross-concept questions

• Reducing any matching substring: reduce only the current handle.

• Popping symbols but not states: r1 has body (S), so it must pop six entries.

• Using FOLLOW in CLR(1): CLR decisions use the lookahead attached to each item.

• Forgetting augmentation: S'->S. on $ means accept, not an ordinary reduction.

SLR's failure in state J is not bad FOLLOW arithmetic. It loses item-specific $ by applying all of FOLLOW(R). Do not memorise only parser power order. A question may ask for a handle, action, reduction count, table cell, viable prefix or parser class.

How to practise and remember the full chain

Exam questions on this chain rarely stop at a single definition, so practise the whole sequence in one pass. Use one scratch-paper order: augment grammar, form items, fill transitions, mark reductions, trace the stack, classify conflicts.

Recall five facts: 6 LR(0) states, 5 shifts, 3 reductions, final stack 0 S 1, and accept on $. Input ()$ is rejected in state 2 because the table has no action on ); the grammar requires an S between the parentheses.

The short version is that the handle, viable prefix, item set and stack action must describe the same reverse-rightmost-derivation step. Reproduce the nine-row trace, then compare how LR(0), SLR(1), LALR(1) and CLR(1) place reductions. For a structured full-subject path, continue with Zero to Hero, Complete CS Course and rebuild the six-state automaton without the finished table.