Chapter 12 of 33

Bottom-Up Parsing & Shift-Reduce Parsing

A top-down parser starts at the start symbol and works down to the tokens, predicting each production before it has seen the input it covers. A bottom-up parser does the opposite. It starts with the tokens, the leaves of the parse tree, and keeps combining them into bigger pieces until only the start symbol is left. It decides on a production only after it has seen everything that production covers, and that is why it can handle far more grammars than LL(1).

Almost every parser generator you will meet (Yacc, Bison and their relatives) produces a bottom-up parser. This chapter explains the general idea behind all of them: reductions, handles and the shift-reduce stack machine. The specific methods for deciding when to reduce follow in the next chapters.

Bottom-up parsing constructs the parse tree for an input string starting at the leaves and working up towards the root. Equivalently, it reduces the input string to the start symbol, and in doing so traces out a rightmost derivation in reverse.


The Idea: Reductions

A reduction is the reverse of a derivation step: a substring that matches the right side of a production is replaced by the non-terminal on its left side.

Take this grammar:

S → a A B e
A → A b c | b
B → d

and the input abbcde. A bottom-up parser reduces it like this:

a b b c d e      reduce the first b by A → b
a A b c d e      reduce A b c by A → A b c
a A d e          reduce d by B → d
a A B e          reduce a A B e by S → a A B e
S                done: the input is a sentence of the grammar

Four reductions, and we reached S. But look at the second line. It also contains a lone b that matches A → b. If we had reduced that instead, we would get a A A c d e, and no sequence of reductions can turn that into S: in every right side an A is followed by b (in A b c) or by B (in a A B e), and the second A can never become either of those. So the real question in bottom-up parsing is: which substring should be reduced next? The answer is the handle.


A Rightmost Derivation in Reverse

Read the reductions above from bottom to top and you get a derivation:

S ⇒ a A B e ⇒ a A d e ⇒ a A b c d e ⇒ a b b c d e

In each step the rightmost non-terminal is expanded: first B, then A, then the remaining A. So it is a rightmost derivation, and the bottom-up parser discovered it backwards. This is always true:

A bottom-up (shift-reduce) parser produces the rightmost derivation of the input in reverse order.

Why rightmost? In a rightmost derivation the right end of the string turns into terminals first, and the left end is finished last. So when you undo the derivation, you start at the left end of the input, which is exactly the part a left-to-right parser has already read. A parser that scans left to right and reduces as soon as a complete right side (the correct one) is in view is undoing a rightmost derivation step by step. Each string in such a derivation is called a right-sentential form.


Handles and Handle Pruning

A handle of a right-sentential form γ is a production A → β together with a position in γ where β can be found, such that replacing β by A at that position gives the previous right-sentential form in a rightmost derivation of γ. Formally, if S ⇒*rm αAw ⇒rm αβw, then A → β at the position after α is a handle of αβw.

Informally, a handle is "the substring that matches a right side and whose reduction is one step of the rightmost derivation in reverse". Two consequences matter:

  • The string w to the right of a handle contains only terminals, because A was the rightmost non-terminal.

  • Not every substring that matches a right side is a handle. In a A b c d e, the lone b matches A → b but is not a handle; A b c is the handle.

For an unambiguous grammar, every right-sentential form has exactly one handle. Repeatedly finding the handle and reducing it is called handle pruning, and it is the whole of bottom-up parsing.

Handles for id + id * id

We use the familiar left-recursive expression grammar. Bottom-up parsers have no problem with left recursion, so no rewriting is needed:

E → E + T | T
T → T * F | F
F → ( E ) | id

The rightmost derivation of id + id * id is:

E ⇒ E + T ⇒ E + T * F ⇒ E + T * id ⇒ E + F * id ⇒ E + id * id
  ⇒ T + id * id ⇒ F + id * id ⇒ id + id * id

Undoing it from the right end gives the handles in the order the parser must find them (we write id1, id2, id3 to tell the three ids apart):

Right-sentential form

Handle

Reducing production

id1 + id2 * id3

id1

F → id

F + id2 * id3

F

T → F

T + id2 * id3

T

E → T

E + id2 * id3

id2

F → id

E + F * id3

F

T → F

E + T * id3

id3

F → id

E + T * F

T * F

T → T * F

E + T

E + T

E → E + T

E

(start symbol reached)

accept

Notice the row E + T * id3. Both T (matching E → T) and E + T (matching E → E + T) appear as right sides, but neither is the handle. Reducing E + T there would group the expression as (id + id) * id, which is wrong. The handle is id3.


Shift-Reduce Parsing

A shift-reduce parser is the standard way to implement handle pruning. It uses a stack of grammar symbols and an input buffer. We write $ at the bottom of the stack and at the end of the input.

Initial configuration:   Stack: $          Input: w $
Final (accepting):       Stack: $ S        Input: $

The parser has exactly four kinds of moves:

Action

What it does

Shift

Move the next input token onto the top of the stack.

Reduce

The right end of the handle is on top of the stack. Locate its left end inside the stack, pop the handle and push the left-side non-terminal.

Accept

Stack is $ S and input is $: announce success.

Error

No valid move exists: call an error-recovery routine.

Trace 1: id + id * id

Stack top is on the right. The Action column shows the correct move at each step; how a real parser knows it is the topic of the next chapters.

Step

Stack

Input

Action

1

$

id + id * id $

shift id

2

$ id

+ id * id $

reduce by F → id

3

$ F

+ id * id $

reduce by T → F

4

$ T

+ id * id $

reduce by E → T

5

$ E

+ id * id $

shift +

6

$ E +

id * id $

shift id

7

$ E + id

* id $

reduce by F → id

8

$ E + F

* id $

reduce by T → F

9

$ E + T

* id $

shift *

10

$ E + T *

id $

shift id

11

$ E + T * id

$

reduce by F → id

12

$ E + T * F

$

reduce by T → T * F

13

$ E + T

$

reduce by E → E + T

14

$ E

$

accept

The parser made 5 shifts (one per token), 8 reductions and one accept. The reductions, in order, are exactly the handles from the table above. Look at step 9: the stack holds E + T and the next token is *. Reducing by E → E + T is possible, but the correct move is to shift the *, because the multiplication must be completed first. Making that choice correctly is what lookahead and parsing tables are for.

Trace 2: abbcde

Step

Stack

Input

Action

1

$

a b b c d e $

shift a

2

$ a

b b c d e $

shift b

3

$ a b

b c d e $

reduce by A → b

4

$ a A

b c d e $

shift b

5

$ a A b

c d e $

shift c

6

$ a A b c

d e $

reduce by A → A b c

7

$ a A

d e $

shift d

8

$ a A d

e $

reduce by B → d

9

$ a A B

e $

shift e

10

$ a A B e

$

reduce by S → a A B e

11

$ S

$

accept

6 shifts and 4 reductions. At step 4 the stack is $ a A and the next token is b. The parser shifts rather than trying anything with A, and after shifting b and c the handle A b c is on top of the stack.


Why the Handle Is Always on Top of the Stack

In both traces, every handle appeared at the top of the stack, never buried inside it. This is not luck. Consider two consecutive steps of a rightmost derivation. After reducing a handle to A, the next handle either includes A, or lies entirely to the right of A (because the next step expanded the rightmost non-terminal, and everything after A was already terminals). In both cases the parser never has to look below the top part of the stack. It only shifts zero or more tokens and then finds the next handle ending at the top.

This is why a simple stack is enough: the parser only ever needs to decide "is there a handle ending at the top of the stack right now, and if so, which one?"


Conflicts: When the Parser Cannot Decide

For some grammars, a shift-reduce parser reaches a configuration where, even knowing the whole stack and the next token, it cannot choose the right move. There are two kinds of conflict.

Shift/Reduce Conflict

Both a shift and a reduce are possible. The classic example is the ambiguous grammar E → E + E | E * E | id with input id + id * id. After a few moves the parser reaches:

Stack: $ E + E        Input: * id $

Option 1: reduce E + E to E, then shift * ...   gives (id + id) * id
Option 2: shift *, later reduce E * E first     gives id + (id * id)

Both lead to acceptance but with different trees, because the grammar is ambiguous. The dangling else produces the same kind of conflict: with if E then S on the stack and else as the next token, the parser can reduce (attach the else to an outer if) or shift (attach it to this if). Parser generators resolve this one by preferring shift, which gives the usual "else matches the nearest if" rule.

Reduce/Reduce Conflict

Two different reductions are possible. Consider:

S → A c | B d
A → a
B → a

After shifting a, the stack is $ a, which matches both A → a and B → a. Looking only at the stack, the parser cannot choose. Here the next token rescues us: if it is c, reduce to A; if it is d, reduce to B. A parser that uses lookahead in this way has no conflict, while one that ignores lookahead does. We will see precisely this difference between LR(0) and SLR parsing.

What Conflicts Tell You

  • An ambiguous grammar always causes a conflict in every LR-style parser, because two different rightmost derivations mean two different moves at some point.

  • An unambiguous grammar can still cause conflicts for a particular method. A conflict says "this grammar is not in the class this parser handles", not necessarily "this grammar is ambiguous".


How Does a Real Parser Find the Handle?

The traces above used an oracle that already knew the correct move. Real bottom-up parsers replace the oracle with a precomputed table. Two families exist:

  • Operator-precedence parsing uses precedence relations between pairs of terminals to find the ends of the handle. It is simple and works for expression-like grammars. It is covered in the next chapter, Operator Precedence Parsing.

  • LR parsing uses a finite automaton that tracks which productions could be in progress on the stack. The stack holds states as well as symbols, and a table of ACTION and GOTO entries tells the parser exactly when to shift and when to reduce.

The LR family, which takes up the next several chapters:

Method

How it decides to reduce

Number of states

Power

LR(0)

Reduce whenever a complete item is reached, without looking at the next token

LR(0) item sets

Weakest

SLR(1)

Reduce by A → β only if the next token is in FOLLOW(A)

Same as LR(0)

More than LR(0)

LALR(1)

Precise lookaheads, with states that have the same core merged

Same as LR(0)

More than SLR; used by Yacc and Bison

CLR(1) (canonical LR)

Exact lookahead carried in every item

Often many more

Most powerful of the four

For grammars: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1), each inclusion strict. Every LL(1) grammar is also LR(1).

  • They handle left recursion directly, so grammars stay natural.

  • They can recognize virtually all programming-language constructs that have a context-free grammar.

  • They detect a syntax error at the earliest possible token: an LR parser never shifts a token that cannot continue a valid prefix of some sentence.

  • The downside: the tables are too large and fiddly to build by hand for real languages, so they are generated by tools (see Yacc & Bison).


Top-Down vs Bottom-Up

Aspect

Top-down (LL)

Bottom-up (LR / shift-reduce)

Tree built

Root to leaves

Leaves to root

Derivation

Leftmost, in forward order

Rightmost, in reverse order

Decision point

Choose a production before seeing its input

Choose a production after seeing all of its right side

Stack holds

Symbols still expected

Symbols already seen (a prefix of a right-sentential form)

Main moves

Expand, match

Shift, reduce

Left recursion

Must be removed

No problem

Grammar class

LL(1): smaller

LR(1): larger, includes all LL(1)

Easy to write by hand?

Yes (recursive descent)

No, normally generated by a tool


Common Mistakes

  • Saying bottom-up parsing gives a leftmost derivation. It gives a rightmost derivation in reverse.

  • Reducing the first substring that matches a right side. A match is not necessarily a handle (E + T with * next is not a handle).

  • Looking for the handle in the middle of the stack. In shift-reduce parsing the handle always ends at the top of the stack.

  • Counting moves wrongly. Shifts equal the number of tokens; reductions equal the number of steps in the rightmost derivation (the number of interior nodes of the parse tree). The final accept is usually counted separately.

  • Assuming a conflict proves ambiguity. Ambiguity always causes conflicts, but conflicts can also come from a parsing method that is too weak for an unambiguous grammar.


GATE & Interview Questions

Q1. Which derivation does a shift-reduce parser construct?

A rightmost derivation, in reverse. The first reduction it performs corresponds to the last step of the rightmost derivation.

Q2. For S → aABe, A → Abc | b, B → d and input abbcde, list the handles in order and count the shift and reduce moves.

Handles: b (A → b), Abc (A → Abc), d (B → d), aABe (S → aABe). The parser makes 6 shifts (one per token) and 4 reductions.

Q3. Using E → E + T | T, T → T * F | F, F → (E) | id, how many reductions are needed to parse id + id * id?

The parse tree has 8 interior nodes: three F → id, two T → F, one E → T, one T → T * F and one E → E + T. So 8 reductions, along with 5 shifts.

Q4. With $ E + T on the stack and * as the next token, why must the parser shift instead of reducing by E → E + T?

Because E + T is not a handle in the right-sentential form E + T * id. In the rightmost derivation, E + T * id comes from E + T * F, which comes from E + T. The T must first grow into T * F. Reducing early would give (id + id) * id and violate the precedence of * over +.

Q5. Can a shift-reduce parser get a conflict on an unambiguous grammar?

Yes. Whether a conflict occurs depends on the method. For example, the unambiguous expression grammar above has shift/reduce conflicts in its LR(0) automaton (in the state containing E → T• and T → T•*F), but none with SLR(1).

Q6. Is it possible for the handle to appear somewhere other than the top of the stack?

No. Because the parser undoes a rightmost derivation, after each reduction the next handle either includes the newly pushed non-terminal or lies to its right, in input not yet shifted. So the handle always ends at the top.

Q7. Give the four actions of a shift-reduce parser and the condition for accept.

Shift, reduce, accept and error. Accept happens when the stack contains only the start symbol above $ and the input is exhausted ($ S on the stack, $ in the input).

Q8. What is a reduce/reduce conflict? Give a tiny example.

Two different productions could reduce the top of the stack. With S → Ac | Bd, A → a, B → a, the stack $ a matches both A → a and B → a. A parser without lookahead cannot decide; with lookahead, c chooses A and d chooses B.


Summary

  • Bottom-up parsing builds the tree from the leaves up by repeated reductions, and traces a rightmost derivation in reverse.

  • A handle is a right-side occurrence whose reduction is one step of that reverse derivation. Only terminals lie to its right. Not every match is a handle.

  • A shift-reduce parser uses a stack and four moves: shift, reduce, accept, error. The handle always ends at the top of the stack.

  • For id + id * id with the standard expression grammar: 5 shifts and 8 reductions. For abbcde: 6 shifts and 4 reductions.

  • Shift/reduce and reduce/reduce conflicts arise when the method cannot decide; ambiguous grammars always cause them.

  • Real parsers decide moves with tables: Operator Precedence Parsing (next chapter) and the LR family, starting with LR(0) Items & LR(0) Parsing.