Chapter Five: Bottom Up Parsing

Outlines:
✓ Introduction
✓ Shift Reduce Parsers
✓ LR Parsers

Compiler Design Dr. Salah Eldin Shaban

1
Introduction
❑ Parsing Techniques are:
Top-down parsers (LL(1), recursive descent)
 Start at the root of the parse tree from the start symbol and grow toward
leaves (similar to a derivation).
 Pick a production and try to match the input.
 Bad “pick”  may need to backtrack.
 Some grammars are backtrack-free (predictive parsing).
Bottom-up parsers (LR(1), operator precedence)
 Start at the leaves and grow toward root.
 We can think of the process as reducing the input string to the start symbol.
 At each reduction step a particular substring matching the right-side of a
production is replaced by the symbol on the left-side of the production.
 Bottom-up parsers handle a large class of grammars.

Compiler Design Dr. Salah Eldin Shaban 2

 Reverse
Introduction to Bottom-up Parsing abbcde
aAbcde order
aAde
❑ Consider the following aABe
grammar, S

✓ The rightmost derivation of the sentence abbcde is:

S  aABe  aAde  aAbcde  abbcde

More Example at Next Page to explain it.

Grammar parse
S → aABe The input string : abbcde.
A → Abc | b
B →d

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift a

INPUT: a b b c d e $ OUTPUT:

Production
S → aABe
Bottom-Up Parsing
A → Abc
A→b
Program
B→d

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift b
Reduce from b to A
INPUT: a b b c d e $ OUTPUT:

Production
S → aABe
Bottom-Up Parsing
A → Abc A
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift A

INPUT: a A b c d e $ OUTPUT:

Production
S → aABe
Bottom-Up Parsing
A → Abc A
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift b

INPUT: a A b c d e $ OUTPUT:

Production
S → aABe
Bottom-Up Parsing
A → Abc A
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift c
Reduce from Abc to A
INPUT: a A b c d e $ OUTPUT:

Production
A
S → aABe
Bottom-Up Parsing
A → Abc A b c
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift A

INPUT: a A d e $ OUTPUT:

Production
A
S → aABe
Bottom-Up Parsing
A → Abc A b c
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift d
Reduce from d to B
INPUT: a A d e $ OUTPUT:

Production
A B
S → aABe
Bottom-Up Parsing
A → Abc A b c d
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift B

INPUT: a A B e $ OUTPUT:

Production
A B
S → aABe
Bottom-Up Parsing
A → Abc A b c d
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift e
Reduce from aABe to S
INPUT: a A B e $ OUTPUT:
S
Production e
a A B
S → aABe
Bottom-Up Parsing
A → Abc A b c d
A→b
Program
B→d b

Compiler Design Dr. Salah Eldin Shaban

 Introduction to Bottom-up Parsing Cont.
Bottom-Up Parser Example
Shift S
Hit the target $
INPUT: S $ OUTPUT:
S
Production e
a A B
S → aABe
Bottom-Up Parsing
A → Abc A b c d
A→b
Program
B→d b

This parser is known as an LR Parser because

it scans the input from Left to right, and it constructs
a Rightmost derivation in reverse order.
Compiler Design Dr. Salah Eldin Shaban
 Introduction to Bottom-up Parsing Cont.
 Conclusion
 The scanning of productions for matching with handles in the input string.
 Backtracking makes the method used in this example very inefficient.

Can we do better? Discuss in later!!!

Previous Architecture Renew Architecture

Compiler Design Dr. Salah Eldin Shaban

Introduction to Bottom-up Parsing Cont.
❑ Bottom-up parsing is an attempt to reduce the input string w to the
start symbol of a grammar by tracing out the right-most derivation of
w in reverse. This is equivalent to constructing a parse tree for the
input string w in the reverse order.
❑ Bottom-up parsing involves:
✓ Selection of a substring that matches the right-side of a production rule.
✓ Position of this substring in the sentential form.

Compiler Design Dr. Salah Eldin Shaban 15

Introduction to Bottom-up Parsing Cont.
❑ A bottom-up parsing begins at the leaves and works up to the top of the
parse tree.
❑ The reduction steps trace a rightmost derivation on reverse.
❑ For example, given the grammar

G7:
1. E → E + T | T
2. T → T * F | F
3. F → (E) | id

Compiler Design Dr. Salah Eldin Shaban 16

Shift Reduce Parsing
❑ Bottom-up parsing is also known as shift-reduce parsing
because its two main actions are shift and reduce.
✓ At each shift action, the current symbol in the input string is
pushed to a stack.
✓ At each reduction step, the symbols at the top of the stack (this
symbol sequence is the right side of a production) will replaced
by the non-terminal at the left side of that production.
✓ There are also two more actions: accept and error.
❑ A shift-reduce parser tries to reduce the given input string
into the starting symbol.

Compiler Design Dr. Salah Eldin Shaban 17

 S → aABe
A → Abc | b
Shift Reduce Parsing Cont. B →d

❑ A Handle is a substring that matches a RHS of a production

rule in the grammar and whose reduction to the non-terminal
on the LHS of that grammar rule is a step along the reverse of
a right most derivation.
❑ A handle is the string of symbols being reduced.
❑ For example, based on the above grammar:
✓ The string “abbcde” can be parsed bottom-up as:
aAbcde aAde aABe S
✓ So, the handles are the first (b) in (abbcde), the (Abc) substring
in (aAbcde), the (d) in (aAde), the whole string, (aABe),

Compiler Design Dr. Salah Eldin Shaban 18

Shift Reduce Parsers
❑ Most bottom-up parsers are implemented as shift-reduce parsers.
❑ A shift-reduce parser
✓ Uses a stack to hold grammar symbols.
✓ Goes on shifting the input symbols onto the stack until a handle comes
on the top of the stack.
✓ When a handle appears on the top of the stack, it performs reduction.
✓ A reduce operation means replacing symbols on the top of the stack
with a non-terminal (a reverse derivation).
✓ $ terminates the input string and marks the bottom of the stack.
✓ Parsing ends successfully when the input is empty, and the stack
contains only the start symbol.

Compiler Design Dr. Salah Eldin Shaban 19

 1. E → E+ T | T
2. T → T * F | F
Shift Reduce Parsers Cont. 3. F → ( E ) | id

❑ There are four possible actions of a shift-reduce parser:

1. Shift: The next input symbol is shifted onto the top of the stack.
2. Reduce: Replace the handle on the top of the stack by the non-
terminal.
3. Accept: Successful completion of parsing.
4. Error: Parser discovers a syntax error and calls an error
recovery routine.
❑ For example, consider the above grammar:
✓ Shift-reduce parsing for the sentence id + id * id is shown below.
✓ Handles are red and underlined in the right-sentential forms

Compiler Design Dr. Salah Eldin Shaban 20

Shift Reduce Parsers Cont.
Stack Input Action
$ id+id*id$ shift
$ id +id*id$ reduce by F → id
$F +id*id$ reduce by T → F
$T +id*id$ reduce by E → T
$E +id*id$ shift
$E+ id*id$ shift
$ E + id *id$ reduce by F → id
$E+F *id$ reduce by T → F
$E+T *id$ shift
$E+T* id$ shift
$ E + T * id $ reduce by F → id
$E+T*F $ reduce by T → T*F
$E+T $ reduce by E → E+T
$E $ accept
Compiler Design Dr. Salah Eldin Shaban 21
Shift Reduce Parsers Cont.
❑ Another example, consider the following grammar:
G19:
1. S → S a B
2. S → c
3. B → ab

❑ A derivation tree for the string caabaab is shown.

❑ A sequence of stack frames parsing caabaab using G19 is:

Compiler Design Dr. Salah Eldin Shaban 22

Shift Reduce Parsers Cont.
Stack Input Action
$ caabaab$ shift
$c aabaab$ reduce by S → c
$S aabaab$ shift
$Sa abaab$ shift
$Saa baab$ shift
$Saab aab$ reduce by B → a b
$SaB aab$ reduce by S → S a B
$S aab$ shift
$Sa ab$ shift
$Saa b$ shift
$Saab $ reduce by B → a b
$SaB $ reduce by S → S a B
$S $ accept

Compiler Design Dr. Salah Eldin Shaban 23

 Shift-Reduce Conflicts
 There are CFGs for which shift-reduce parsers cannot be used.
 Stack contents and the next input symbol may not decide
action:
✓ shift/reduce conflict: Whether make a shift operation or a
reduction.
✓ reduce/reduce conflict: The parser cannot decide which of
several reductions to make.
 If a shift-reduce parser cannot be used for a grammar, that
grammar is called as non-LR(k) grammar (see next).
 An ambiguous grammar can never be an LR grammar.

Compiler Design Dr. Salah Eldin Shaban 24

Shift-Reduce Conflicts Cont.
❑ A grammar is LR if the parser for it can be implemented
with a shift reduce algorithm.
❑ This algorithm always performs a reduce operation when the
top of the stack corresponds to the right side of a rule.
❑ If the grammar is not LR, this is not the correct operation or
it is not clear which reduce operation should be performed.
❑ For example, consider the following grammar:
G20:
1. S → S a B
2. S → a
3. B → ab
Compiler Design Dr. Salah Eldin Shaban 25
Shift-Reduce Conflicts Cont.
❑ A Shift/Reduce conflict leading to an incorrect parse using G20
Stack Input Action
$ aaab$ shift
$a aab$ reduce by S → a
$S aab$ shift
$Sa ab$ shift/reduce conflict
$SS ab$ reduce by S → a (incorrect)
$SSa b$ shift
$SSab $ shift
$SSB $ reduce by B → a b
$SSB $ syntax error (incorrect)

Compiler Design Dr. Salah Eldin Shaban 26

 Shift-Reduce Conflicts Cont.
❑ A Reduce/Reduce Conflict leading to an incorrect parse using G21
G21:
1. S → S A

Stack Input Action 2. S → a

$ aa$ shift 3. A → a
$a a$ reduce/reduce conflict (2 and 3)
$A a$ reduce by A → a (incorrect)
$Aa $ shift
$Aa $ reduce/reduce conflict (2 and 3)
$ Aa $ reduce by S → a
$AS $ syntax error (incorrect)

Compiler Design Dr. Salah Eldin Shaban 27

 Types of Shift-Reduce Parsers
❑ The shift-reduce parsers are categorized into:
✓ Operator-Precedence Parsers: Simple, but only a small class of grammars.
✓ LR-Parsers: Covers wide range of grammars.
❑ The meaning of LR(k)
✓ L stands for left-to-right scanning, R stands for right-most derivation, and k stands
for the number of input symbols of look-ahead used to making parsing decision.
❑ LR-Parsers may be:
✓ SLR - Simple LR parsers,
✓ LALR – intermediate LR parsers (Look-ahead LR parsers) or
✓ LR - most general LR parsers.

Compiler Design Dr. Salah Eldin Shaban 28

 LR Parsers
❑ Advantages: LR parsers can
✓ recognize virtually all programming language constructs for which
grammar can be written.
G (LR) > G (Top-Down predictive parsing)
i. e. LL(1)-Grammars  LR (1)-Grammars
✓ be implemented as efficiently as other shift-reduce methods.
✓ detect a syntax error as early as possible on a left-to-right scan of input.
✓ An LR parser is the most general non-backtracking shift-reduce
parsing method known.
❑ Disadvantages: Too much work to construct a parser by hands: one
needs an LR parser generator such as YACC.

Compiler Design Dr. Salah Eldin Shaban 29

The LR Parsing Algorithm
❑ A block diagram of an LR parser has an input, an output,
a stack, a driver program, and a parsing table with two
parts (action and goto).
❑ The driver program is the same for all LR parsers.
✓ The driver program reads the input string one symbol at a
time and maintains a stack.
❑ All LR parser generators need parsing tables.
❑ A block diagram of LR Parser is illustrated as follow:

Compiler Design Dr. Salah Eldin Shaban 30

The LR Parsing Algorithm Cont.
a1 an Input
State
after Stack
action LR
Sm Output
Parsing Algorithm
Xm
handle
Sm-1 Shift/Reduce State after Reduction
State Xm-1
Action GOTO
before
action S0 Parsing Table

Initial State A Model of an LR Parser

Compiler Design Dr. Salah Eldin Shaban 31
The LR Parsing Algorithm Cont.
❑ Input:
– An input string w and an LR parsing table with functions
action and goto for a grammar G.
❑ Output:
– If w is in L(G), a bottom-up parse for w; otherwise, an error
indication.
❑ Method:
– Initially, the parser has the initial state s0 on its stack, and
w$ in the input buffer.
– Shift/reduce according to the parsing table.

Compiler Design Dr. Salah Eldin Shaban 32

The LR Parsing Algorithm Cont.
❑ The stack always maintains the following form:
So X1 S1 X2 S2 ... Xm-1 Sm-1 Xm Sm
✓ Sm is the top of stack, Si is a state, and Xm is a grammar symbol.
❑ Si essentially summarizes the information contained in the
stack and is used to guide the shift-reduce decision.
✓Initial Stack contains just S0
❑ The action of the driver program depends on action [Sm, ai]
where ai is the current input symbol.
❑ The following actions are possible:

Compiler Design Dr. Salah Eldin Shaban 33

Actions of an LR-Parser
1. Shift: if action [Sm, ai ] = shift S, the parser shifts the input symbol
ai into the stack, and then stacks state S. Now current input symbol
becomes ai+1.
Stack Input
So X1 S1 X2 S2 ... Xm-1 Sm-1 Xm Sm ai S ai+1, ai+2 ... an $
(So X1 S1 ... Xm Sm , ai ai+1 ... an $) ➔ (So X1 S1 ... Xm Sm ai S, ai+1 ... an $)
2. Reduce: if action [Sm, ai ] = reduce A → , the parser executes a
reduce move using the A →  production of the grammar. If  has r
grammar symbols, first 2r symbols are popped off the stack (r state
symbol and r grammar symbol).

Compiler Design Dr. Salah Eldin Shaban 34

Actions of an LR-Parser Cont.
So, the top of the stack now becomes Sm-r, then A is pushed on the
stack, and then state go to [Sm-r, A] is pushed on the stack. The current
input symbol is still ai
Stack Input
So X1 S1 X2 S2 ... Xm-r Sm-r A S ai, ai+1, ai+2 ... an $
(So X1 S1... Xm Sm, ai ai+1 ... an $) ➔ (So X1 S1... Xm-1 Sm-1 A S, ai ... an $)
where S = goto [Sm-r, A]
3. Accept: If action [Sm, ai] = accept, Parsing successfully completed.
4. Error: If action [Sm, ai] = error, the parser detected a syntax error
(an empty entry in the action table) and calls an error recovery
routine.
Compiler Design Dr. Salah Eldin Shaban 35
Actions of an LR-Parser Cont.
❑ For example, consider the given grammar and parsing table:
1. E → E+T
2. E → (T)
3. T → T*F
4. T→F
5. F → (E)
6. F → id
❑ In the following parsing table, Si means shift state i on stack,
rj means reduce by using production numbered j, and finally
blank means error.
❑ The parsing of string id * id + id $ is shown below.
Compiler Design Dr. Salah Eldin Shaban 36
 Actions of an LR-Parser Cont.
Action Table GOTO Table
State id + * ( ) $ E T F
0 S5 S4 1 2 3
1 S6 Accept
2 r2 S7 r2 r2
3 r4 r4 r4 r4
4 S5 S4 8 2 3
5 r6 r6 r6 r6
6 S5 S4 9 3
7 S5 S4 10
8 S6 S11
9 r1 S1 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5

Compiler Design Dr. Salah Eldin Shaban 37

 LR Parsing on id1*id2+id3
Stack Input shift/reduce + goto Action
(1) 0 id * id + id $ (0,id):s5 Shift
(2) 0 id 5 * id + id $ (5,*):r6; (0,F):3 Reduce by F → id
(3) 0F3 * id + id $ (3,*):r4; (0,T):2 Reduce by T → F
(4) 0T2 * id + id $ (2,*):s7 Shift
(5) 0T2*7 id + id $ (7,id):s5 Shift
(6) 0 T 2 * 7 id 5 + id $ (5,+):r6; (7,F):10 Reduce by F → id
(7) 0 T 2 * 7 F 10 + id $ (10,+):r3; (0,T):2 Reduce by T → T*F
(8) 0T2 + id $ (2,+):r2; (0,E):1 Reduce by E → T
(9) 0E1 + id $ (1,+):s6 Shift
(10) 0E1+6 id $ (6,id):s5 Shift
(11) 0 E 1 + 6 id 5 $ (5,$):r6; (6,F):3 Reduce by F → id
(12) 0E1+6F3 $ (3,$):r4; (6,T):9 Reduce by T → F
(13) 0E1+6T9 $ (9,$):r1; (0,E):1 Reduce by E → E+T
(14) 0E1 $ (1,$):acc Accept
LR Grammar
❑ An LR grammar is a grammar for which one can construct a
parsing table.
❑ A grammar is LR if a left-to-right shift-reduce parser can recognize
handles when they appear on the top of stack.
❑ Each state symbol summarizes the information contained in the
stack below it.
❑ The LR parser can determine from the state on the top of stack
everything it needs to know about what is in the stack.
❑ The next k input symbols can also help the LR parser to make shift-
reduce decisions.
❑ Grammar that can be parsed by an LR parser by examining up to k
input symbols on each move is called an LR(k) grammar.
Compiler Design Dr. Salah Eldin Shaban 39
 LR Grammar Cont.
❑ There are many different types of LR Parse Tables such as:
➢ LR(0)
✓ Weakest in terms of number of grammars it succeeds.
✓ Easiest to implement - uses LR (0) item sets.

➢ SLR(1) - Simple LR(1)

✓ Easiest to implement - uses LR(0) item sets.
✓ May fail to produce a table when other techniques may
succeed.

Compiler Design Dr. Salah Eldin Shaban 40

 LR Grammar Cont.
➢ LALR(1) – Look-ahead LR
✓ Of intermediate power between SLR(1) and LR(1) methods.
✓ Will work on most programming language grammars.
✓ With effort, can be implemented efficiently – uses LR(1) item
sets compacted.
➢ CLR(1) or LR(1) - Canonical LR
✓ Most powerful.
✓ Work on a large class of grammars.
✓ Can be very expensive to implement - Uses LR(1) item sets.

Compiler Design Dr. Salah Eldin Shaban 41

 Augmented Grammar
❑ The Augmented Grammar G’: is a grammar G with a unit production
rule S’→ S where S’ is the new starting symbol.
✓ i.e. G  {S’ → S} where S is the start state of G.
✓ The start state of G’ is S’.
✓ This is done to make it explicitly clear to parser when to accept the string.
❑ Why the grammar use S’→ S$ ? Easy to check the ending of parser!
✓ For example, If S’ is not exist, When we button up to reduce the original
symbol S, there are two paths to achieve it.
S → ID$ S’ → S$
S → $ S → ID|
Compiler Design Dr. Salah Eldin Shaban 42
 Constructing the SLR Parsing Tables
❑ They are Tables for LR(0) Parsers.
❑ To construct such tables
✓ find LR(0)/LR items or a canonical collection set of LR(0) items.
❑ Some basics to calculate that:
1) An item of a grammar G is a production with a dot at some position of
the right side.
For example: A → aBb (four different possibility)
Possible LR(0) items: A → .aBb, A → [Link], A → aB.b, A → aBb.
✓ Sets of items will be the states of action and goto tables.
✓ A production rule of the form A →  yields only one item A → .
✓ Intuitively, an item shows how much of a production we have
seen till the current point in the parsing procedure.
Compiler Design Dr. Salah Eldin Shaban 43
 Constructing the SLR Parsing Tables Cont.
2) The Closure operation on a set of items
✓ If I is a set of items for a grammar G, then closure (I) is a set of items
constructed from I by the following two rules:
I. Initially, every LR(0) item in I is added to closure (I).
II. If A → .B  is in closure (I) and B →  is a production rule of G;
then B → . will be in the closure (I). We will apply this rule until
no newer LR(0) items can be added to closure (I).
✓ For Example, for grammar G: 1. S → AA
2. A → a A | b
If set I = {S’ → .S} then closure (I) = {S’ → .S kernel item is A
S → .A A, A → .a A, A → .b}

Compiler Design Dr. Salah Eldin Shaban 44

 Constructing the SLR Parsing Tables Cont.

Another example,
E’ → E .
closure({E’ → E}) =
E → E+T { .
E’ → E kernel item is F
E→T .
E → E+T
T → T*F E→ T.
T→F .
T → T*F
F → (E) T→ F.
F → id .
F → (E)
F → .id
}
Compiler Design Dr. Salah Eldin Shaban 45
The Computation of Closure
• Given a set, I, of items
• Initially Closure (I) = I
• Loop: for all items [A → •B]…
• If [A → •B] is in Closure(I) and B →  is in P, then include
[B → •  ] into Closure(I).
• Repeat the Loop until no new dotted rules can be added
• Initial set of items for a grammar:
– I0 = Closure ({[S’ → •S]})
– (S: start symbol, S’: augmented start symbol)

Compiler Design Dr. Salah Eldin Shaban 46

The Computation of Closure Cont.
• Augment the grammar with: S’ → S
• Let I0 = Closure ({[S’ → •S] }), C = {I0}
while (not all elements of C are marked)
{
- select an unmarked item set of C (say “I”) and mark it;
-  X  (N or Σ), if goto(I, X) is not already in C, then add goto(I, X) to C
(unmarked);
}
Characteristic Finite State Machine (CFSM) Construction Algorithm.

Compiler Design Dr. Salah Eldin Shaban 47

Constructing the SLR Parsing Tables Cont.
3. The Go to operation:
✓ If I is a set of items and X is a grammar symbol (terminal or non-
terminal), then goto (I, X) is defined as follows:
I. If A → .X in I then every item in closure ({A → X.}) will be
in goto (I, X).
[Link] I is the set of items that are valid for some viable prefix , then
goto (I, X) is the set of items that are valid for the viable prefix X.
For example, see the next slide

Compiler Design Dr. Salah Eldin Shaban 48

The GOTO Operation - Example
I ={E’ → .E, E → .E+T, E → .T, T → .T*F, T → .F, F → .(E), F → .id}
goto (I, E) = {E’ → E., E → E.+T}
goto (I, T) = {E → T., T → T.*F}
goto (I, F) = {T → F.}
goto (I, id) = {F → id.}
goto (I, ( ) = {F → (.E), E → .E+T, E → .T, T → .T*F, T → .F,
F → .(E), F → .id}
goto (I, )) = {F → (E).}
goto (I, +) = {E → E+.T, T →.T*F, T →.F, F →.(E), F →.id}
goto (I, *) = {T →T*.F, F →.(E), F →.id}

Compiler Design Dr. Salah Eldin Shaban 49

The GOTO Computation
• Let I be a set of items which are valid for some viable prefix .
• Then goto (I, X), where X(N or Σ), is the set of items
which are valid for the viable prefix X.
• So [A → •X] in I implies
Closure ({[A →X • ]}) in goto (I, X)
S* d[A]w  d[ • X ]w  d{[ X • ]}w
([]: set of items I, including [A → •X] & others)
 = d

Compiler Design Dr. Salah Eldin Shaban 50

 Constructing the SLR ParsingTables Cont.
4. Constructing the Canonical Collection of Sets of LR(0) Items:
✓ A canonical collection of sets of items for an augmented
grammar C is structured as:
I. The first set in C is the closure of {[S’ → •S]}.
II. For each set I in C and each grammar symbol X where go to (I, X)
is non-empty and not in C add the set go to (I, X) to C.
The above steps can be understood by the following algorithm:

Compiler Design Dr. Salah Eldin Shaban 51

The Canonical Collection of Sets of LR(0) Items
Procedure items ( G’ )
begin
C = {closure ({S’→.S})}
repeat
for each set of items I in C and for each grammar symbol X
if goto (I, X) is not empty and not in C then
add goto (I, X) to C
until no more set of items can be added to C.
end

Compiler Design Dr. Salah Eldin Shaban 52

 G: 1. S → AA
2. A → a A | b
Canonical Collection of Sets of LR(0) Items: Example 1
I0: S’ → .S I4 : goto (I0, b) goto (I2 , b) = I4
S → .A A A → b.
A → .a A I5: goto (I2, A) I6: goto ( I3 , A)
A → .b S → A A. A → a A.
I1: goto (I0, S) goto (I2, a) = I3 goto (I3, a) = I3
S’ → S. goto (I3, b) = I4
I2: goto (I0, A)
S → A. A
A → .a A
A → .b C  {I0, I1, I2, I3, I4, I5, I6}
I3: goto (I0, a) Follow(S)={$}, Follow(A)={a, b, $}
A → a. A
A → .a A
A → .b
Compiler Design Dr. Salah Eldin Shaban 53
 G: 1. S → AA
2. A → a A | b
LR(0) Parsing Table: Example 1
Action Table GOTO Table
a b $ A S
0 S3 S4 2 1
1 Accept
2 S3 S4 5
3 S3 S4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2
Compiler Design Dr. Salah Eldin Shaban 54
 G: 1. S → AA
2. A → a A | b
SLR Parsing Table: Example 1
Action Table GOTO Table
a b $ A S
0 S3 S4 2 1
1 Accept
2 S3 S4 5
3 S3 S4 6
4 r3 r3 r3
5 r1
6 r2 r2 r2
Compiler Design Dr. Salah Eldin Shaban 55
Canonical Collection of Sets of LR(0) Items: Example 2
I0: E’ → .E I4 : goto (I0, ( ) I7: goto(I2 , *)
E → .E+T F → (.E) T → T*.F
E → .T E → .E+T F → .(E)
T → .T*F E → .T F → .id
T → .F T → .T*F
F → .(E) T → .F
F → .id F → .(E) I8: goto( I4 , E)
F → .id F → (E.)
I1: goto(I0, E) I5: goto(I0, id) E → E.+T
E’ → E. F → id. I9: goto (I6, T)
E → E.+T I6: goto(I1, +) E → E+T.
E → E+.T T → T.*F
I2: goto(I0, T) T → .T*F I10: goto(I7, F)
E → T. T → .F T → T*F.
T → T.*F F → .(E) I11 : goto(I8 , ) )
I3: goto(I0, F) F → .id F → (E).
T → F.
Compiler Design Dr. Salah Eldin Shaban 56
 Transition Diagram (DFA) of GOTO Function
The canonical collection of sets of LR(0) items C  {I0, I1, I2, I3, I4, I5, I6, I7, I8}
I0 E + T *
I1 I6 I9 to I7
F
( to I3
T
id to I4
to I5
F I2 * I7 F
I10
(
I3 id to I4
(
to I5
I4 E I8 )
id id T
F
to I2 + I11
I5 to I3 to I6
(
to I4
Compiler Design Dr. Salah Eldin Shaban 57
Constructing the SLR Parsing Tables Cont.
5. DFA for Canonical Collection:
6. Construction of a parsing action and go to table for an SLR
parser:
✓ Construct the LR(0) items sets and canonical collection set.
✓ Any number of canonical collection set Ii corresponds to a state i
of DFA.
✓ Construction of the action table.
✓ Construction of the go to table.

Compiler Design Dr. Salah Eldin Shaban 58

 Constructing SLR Parsing Tables
1. Construct the canonical collection of sets of LR(0) items for G’. C  {I0,...,In}
2. State i of DFA is constructed from Ii.
3. The parsing actions for state i are determined as follows:
• If a is a terminal, A → .a in Ii and goto (Ii, a) = Ij then action [i, a] is shift j.
• If A→ . is in Ii , then action [i, a] is reduce A→  for all a in FOLLOW(A)
where A  S’.
• If S’ → S. is in Ii , then action [i, $] is accept.
• If any conflicting actions generated by these rules, the grammar is not SLR(1).
4. Create the parsing goto table
• for all non-terminals A, if goto (Ii, A) = Ij then goto [i, A] = j
5. All entries not defined by (3) and (4) are errors.
6. Initial state of the parser is the one constructed from the sets of items containing
[S’→ .S]

Compiler Design Dr. Salah Eldin Shaban

Constructing SLR Parsing Tables Cont.
❑ α, β = any string of terminals and/or non‐terminals.
❑ X, S’, S = non‐terminals.
❑ When dot is in middle
1. If A → .a in Ii and read on ‘a’ produces Ij then action [i, a] =
shift j.
2. If A → .a in Ii and read on ‘X’ produces Ij then goto [i, X] = j.
❑ When dot is at end
1. If A→ . is in Ii , then action [i, a] = reduce on A→  for all a in
FOLLOW(A) where A  S’.
2. If S’ → S. is in Ii , then action [i, $] = accept.

Compiler Design Dr. Salah Eldin Shaban

Example: Grammar G for Math Expressions

(0) E’→ E
(1) E → E+T
(2) E → T
(3) T → T*F
(4) T → F
(5) F → (E)
(6) F → id

Follow(E)={+,),$}, Follow(T)={+,),$,*},
Follow(F)={+,),$,*}
 Canonical LR(0) Collection for G
I0: E’ → . E E I1: E’ → E . + I6: E → E + . T T I9: E → E + T .
E→.E+T E→E.+T T→.T*F T→T.*F
E→.T T→.F *
T ( id
T→.T*F I2: E → T . * F→.(E)
T→.F T→T.*F F → . id
F→.(E) F F
F → . id I3: T → F .
I10: T → T * F .
T
F I7: T → T * . F
F
I4: F → ( . E ) F→.(E)
E→.E+T F → . id
( E→.T ( id
T→.T*F +
( T→.F E I8: F → ( E . ) I11: F → ( E ) .
F→.(E) E→E.+T )
F → . id

id id
I5: F → id .
 GOTO Actions
I0: E’ → . E E I1: E’ → E .
E→.E+T E→E.+T
E→.T
T→.T*F T I2: E → T .
T→.F T→T.*F
F→.(E)
F
F → . id I3: T → F .
After I4: F → ( . E )
0E1 reduction E→.E+T
( E→.T
0T2 T→.T*F
T→.F
Before F→.(E)
0F3
reduction F → . id
0 id 5 id
I5: F → id .
Parsing Table for Expression Grammar
State Action Goto
id + * ( ) $ E T F
0 s5 s4 1 2 3
(0) E’ → E 1 s6 accept
(1) E → E + T 2 r2 s7 r2 r2
(2) E → T 3 r4 r4 r4 r4
(3) T → T * F 4 s5 s4 8 2 3
(4) T → F 5 r6 r6 r6 r6
(5) F → ( E ) 6 s5 s4 9 3
(6) F → id 7 s5 s4 10
8 s6 s11
Follow(E)={+,),$}
Follow(T)={+,),$,*}
9 r1 s7 r1 r1
Follow(F)={+,),$,*} 10 r3 r3 r3 r3
11 r5 r5 r5 r5
 LR Parsing on id1*id2+id3
Stack Input shift/reduce+goto Action
(1) 0 id * id + id $ (0,id):s5 Shift
(2) 0 id 5 * id + id $ (5,*):r6; (0,F):3 Reduce by F → id
(3) 0F3 * id + id $ (3,*):r4; (0,T):2 Reduce by T → F
(4) 0T2 * id + id $ (2,*):s7 Shift
(5) 0T2*7 id + id $ (7,id):s5 Shift
(6) 0 T 2 * 7 id 5 + id $ (5,+):r6; (7,F):10 Reduce by F → id
(7) 0 T 2 * 7 F 10 + id $ (10,+):r3; (0,T):2 Reduce by T → T*F
(8) 0T2 + id $ (2,+):r2; (0,E):1 Reduce by E → T
(9) 0E1 + id $ (1,+):s6 Shift
(10) 0E1+6 id $ (6,id):s5 Shift
(11) 0 E 1 + 6 id 5 $ (5,$):r6; (6,F):3 Reduce by F → id
(12) 0E1+6F3 $ (3,$):r4; (6,T):9 Reduce by T → F
(13) 0E1+6T9 $ (9,$):r1; (0,E):1 Reduce by E → E+T
(14) 0E1 $ (1,$):acc Accept
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 How to represent parsing states
so we can tell the right parsing
actions to take?
S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 How to represent parsing states
so we can tell the right parsing
actions to take?
S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 S0: . S → . a A B e

S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 S1: S → a . A B e (shift a)
 A→ .Abc|.b
S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d LR Parsing States
Input: abbcde

• S2: A → b .
• (shift b, to reduce A → b)

S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 S3: S → a A . B e
 B→. d
 A→A.b c
S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
S4: A → A b . c
(shift b)

S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
S5: A → A b c .
(shift c, reduce A → A b c )

S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 S6: S → a A . B e
 B→. d
S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 S7: B → d .
 (shift d, reduce B → d)
S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
S9: S → a A B e .
(shift e, reduce S → a A B e )

S 10

A B
6 8

A
3

a b b c d e $
0 1 2 4 5 7 9
G: S → a A B e
 A→ Abc|b
 B→ d
Input: abbcde LR Parsing States
 S0: . S → . a A B e
 S1: S → a . A B e (shift a) abbcde
 A→ .Abc|.b A
 A→ .Abc|.b (closed, no further expansion)
 S2: A → b . (shift b, reduce A → b) abbcde
 S3: S → a A . B e
A
 B→. d A
 A→[Link]
 S4: A → A b . c (shift b) abbcde S
 S5: A → A b c . (shift c, reduce A → A b c ) A B
 S6: S → a A . B e A B
A
 B→. d A
 S7: B → d . (shift d, reduce B → d) abbcde
 S8: S → a A B . e abbcde
 S9: S → a A B e . (shift e, reduce S → a A B e )
S10: S’ → S . (S reduced)
 ?

Compiler Design Dr. Salah Eldin Shaban 78