Bottom-Up Parsing

A bottom-up parser builds the parse tree from the leaves up, tracing a rightmost derivation in reverse. At each step it finds a handle (a substring matching a production's right side) and reduces it.

Shift-Reduce Parsing

Text

Grammar: E → E + T | T,   T → T * F | F,   F → id
Input: id * id

Stack        Input      Action
$            id*id$     shift
$id          *id$       reduce F → id
$F           *id$       reduce T → F
$T           *id$       shift
$T*          id$        shift
$T*id        $          reduce F → id
$T*F         $          reduce T → T * F
$T           $          reduce E → T
$E           $          accept

Conflicts: shift/reduce (e.g. the dangling-else problem) and reduce/reduce.

LR(0) Items

An item is a production with a dot marking how much has been seen, e.g. E → E • + T. Build the canonical collection with CLOSURE and GOTO, starting from the augmented production S' → • S.

Text

Augmented grammar:  S' → S,  S → AA,  A → aA | b

I0: S' → •S      S → •AA     A → •aA     A → •b
I1 = GOTO(I0, S): S' → S•                          (accept)
I2 = GOTO(I0, A): S → A•A    A → •aA    A → •b
I3 = GOTO(I0, a): A → a•A    A → •aA    A → •b
I4 = GOTO(I0, b): A → b•
I5 = GOTO(I2, A): S → AA•
I6 = GOTO(I3, A): A → aA•

Comparing LR Parsers

Parser	Items	Reduce placed under	Power
LR(0)	LR(0)	All terminals	Weakest
SLR(1)	LR(0)	FOLLOW(A)	More
LALR(1)	LR(1), merged on core	Lookahead	More (used by Yacc/Bison)
CLR(1)	LR(1)	Lookahead	Most powerful, largest table

Text

LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1)
Number of states: SLR = LALR ≤ CLR
Merging CLR states into LALR may introduce reduce/reduce conflicts, never new shift/reduce conflicts.

Track your progress through the Compiler Design course

← Prev Next →