SYNTAX ANALYSIS

2ND PHASE OF COMPILER CONSTRUCTION

1
SECTION 2.1: BOTTOM UP PARSING

2
BOTTOM-UP PARSING

 A bottom-up parser creates the parse tree of the given input

starting from leaves towards the root.

 A bottom-up parser tries to find the right-most derivation of the

given input in the reverse order.
S  ...   (the right-most derivation of )
 (the bottom-up parser finds the right-most derivation in the reverse order)

3
BOTTOM-UP 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) is replaced by the non-terminal at the left
side of that production.
 There are two more actions: accept and error.
4
SHIFT-REDUCE PARSING

 A shift-reduce parser tries to reduce the given input string into the starting symbol.

a string  the starting symbol

reduced to

 At each reduction step, a substring of the input matching to the right side of a
production rule is replaced by the non-terminal at the left side of that production
rule.
 If the substring is chosen correctly, the right most derivation of that string is created
in the reverse order.
*
Rightmost Derivation: S
rm
rm rm
Shift-Reduce Parser finds:   ...  S
5
SHIFT-REDUCE PARSING -- EXAMPLE

S  aABb input string: aaabb

A  aA | a aaAbb
B  bB | b aAbb  reduction
aABb
S
S  aABb  aAbb  aaAbb  aaabb
rm rm rm rm

Right Sentential Forms

 How do we know which substring to be replaced at each reduction

6
step?
HANDLE

 Informally, a handle of a string is a substring that matches the right

side of a production rule.
 But not every substring matches the right side of a production rule is handle

 A handle of a right sentential form  ( ) is

a production rule A   and a position of 
where the string  may be found and replaced by A to produce
the previous right-sentential form in a rightmost derivation of .
* A  
S rm
rm

 If the grammar is unambiguous, then every right-sentential form of

the grammar has exactly one handle. 7
HANDLE PRUNING

 A right-most derivation in reverse can be obtained by handle-

pruning.
 1  2  ...  n-1  n= 
S=0 rm
rm rm rm rm
input string
 Start from n, find a handle Ann in n,
and replace n by An to get n-1.
 Then find a handle An-1n-1 in n-1,
and replace n-1 by An-1 to get n-2.
 Repeat this, until we reach S.

 A left-to-right, bottom-up parse works by iteratively searching for

a handle, then reducing the handle 8

A STACK IMPLEMENTATION OF A SHIFT-REDUCE
PARSER
 There are four possible actions of a shift-parser action:

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.

 Initial stack contains only the end-marker $.

 The end of the input string is marked by the end-marker $.
9
A SHIFT-REDUCE PARSER
Right-Most Derivation of
“id+id*id”
E  E+T | T E  E+T
T  T*F | F  E+T*F
F  (E) | id  E+T*id
Right-Most Sentential Form Reducing Production  E+F*id
 E+id*id
id+id*id F  id  T+id*id
F+id*id TF
 F+id*id
T+id*id ET
 id+id*id
E+id*id F  id
E+F*id TF
E+T*id F  id
E+T*F T  T*F
E+T E  E+T
E
Handles are red and underlined in the right-sentential forms. 10
SHIFT-REDUCE PARSERS

There are two main categories of shift-reduce parsers

CFG
1. Operator-Precedence Parser LR
 simple, but only a small class of grammars. LALR

2. LR-Parsers SLR
 covers wide range of grammars.
 SLR – simple LR parser
 LR – most general LR parser
 LALR – intermediate LR parser (lookahead LR parser)
 SLR, LR and LALR work in similar manner, only their parsing tables are
different.

11
LR PARSERS

 The most powerful shift-reduce parsing (yet efficient) is:

LR(k) parsing.

left to right right-most k lookahead

scanning derivation (k is omitted  it is 1)

 LR parsing is attractive because:

 LR parsing is most general non-backtracking shift-reduce parsing.
 The class of grammars that can be parsed using LR methods is a proper superset of the
class of grammars that can be parsed with predictive parsers.
LL(1)-Grammars  LR(1)-Grammars
 An LR-parser can detect a syntactic error as soon as it is possible to do so.
12
LR PARSING ALGORITHM
Input a1 ... ai ... an $
Stack
Sm
Xm
LR Parsing Algorithm Output
Sm-1
Xm-1
.
.
Action Table Goto Table
S1 terminals and $ non-terminal
X1 s s
t four different t each item is
S0 a actions a a state number
t t
e e
s s
13
A CONFIGURATION OF LR PARSING ALGORITHM

 A configuration of a LR parsing is:

( So X1 S1 ... Xm Sm, ai ai+1 ... an $ )

Stack Rest of Input

 Each state symbol summarizes the information contained in the stack below it,
and the combination of state symbol on top of the stack and input symbol are used
to index the parsing table and determine the shift-reduce action.

 Sm and ai decides the parser action by consulting the parsing action table.
(Initial Stack contains just So )

 A configuration of a LR parsing represents the right sentential form:

X1 ... Xm ai ai+1 ... an $ 14
ACTIONS OF A LR-PARSER

1. shift s -- shifts the next input symbol and the state s onto the stack
( So X1 S1 ... Xm Sm, ai ai+1 ... an $ )  ( So X1 S1 ... Xm Sm ai S, ai+1 ... an $ )

2. reduce A (or rn where n is a production number)

 pop 2*|| (=r) items from the stack; let us assume that  = Y1Y2...Yr
 then push A and s where s=goto[sm-r,A]

( So X1 S1 ... Xm Sm, ai ai+1 ... an $ )  ( So X1 S1 ... Xm-r Sm-r A s, ai ... an $ )

In fact, Y1Y2...Yr is a handle.

X1 ... Xm-r A ai ... an $  X1 ... Xm Y1...Yr ai ai+1 ... an $
 Output is the reducing production; reduce A

3. Accept – Parsing successfully completed 15

4. Error -- Parser detected an error (an empty entry in the action table)
THE CLOSURE OPERATION -- EXAMPLE
E'  E .
closure({E'  E}) =
E  E+T .
{ E'  E kernel items
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 }

16
THE CLOSURE OPERATION
 If I is a set of LR(0) items for a grammar G, then closure(I)
is the set of LR(0) items constructed from I by the two rules:

1.
2. ..
Initially, every LR(0) item in I is added to closure(I).
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 more new LR(0) items can be added


to closure(I).
Kernel items: which includes the initial item S'  S, and all
items whose dots are not at the left end
.
 Nonkernel Items, which have their dots at the left end

17
CONSTRUCTION OF THE CANONICAL LR(0)
COLLECTION
 To create the SLR parsing tables for a grammar G, we will
create the canonical LR(0) collection of the grammar G'.

 Algorithm:
.
C is { closure({S' S}) }
repeat the followings until no more set of LR(0) items can be added to C.
for each I in C and each grammar symbol X
if goto(I,X) is not empty and not in C
add goto(I,X) to C

 goto function is a DFA on the sets in C. 18

THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
Shift  From left of ‘E’
E'  E I1
to right of E
E  E+T E'  E (Complete)
E  T E  E+T
T  T*F
T  F
F   (E)
Add Productions of E since there is  before E.
F  id
Add Productions of T since there is  before T.

Initial Set Add Productions of F since there is  before F.

E'  E
1) E  E+T
2) E  T
3) T  T*F
4) T  F 19
5) F   (E)
6) F  id
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
E'  E
E  E+T Shift  From left of I2
E  T ‘T’ to right of T
E  T (Complete)
T  T*F T  T*F
T  F
F  (E)
F  id

Initial Set
E'  E
1) E  E+T
2) E  T
3) T  T*F
4) T  F 20
5) F   (E)
6) F  id
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
E'  E
E  E+T
E  T
T  T*F Shift  From left of ‘F’ I3
to right of F
T  F T  F (Complete)
F   (E)
F  id

Initial Set
E'  E
1) E  E+T
2) E  T
3) T  T*F
4) T  F 21
5) F   (E)
6) F   id
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
E’  E I4
E  E+T F (E)
E  T E E+T
T  T*F Shift  From left of ‘ (’ E T
to right of ‘(’
T  F T T*F
F   (E) T F
F  id F  (E)
F id

Initial Set
E'  E Add Productions of E since there is  before E.
1) E  E+T
2) E  T Add Productions of T since there is  before T.
3) T  T*F
Add Productions of F since there is  before F.
4) T  F 22
5) F   (E)
6) F  id
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
E'  E
E  E+T
E  T
T  T*F
T  F Shift  From left of ‘id’
F   (E) to right of ‘id’ I5
F  id F  id (Complete)

Initial Set
E’  E
1) E  E+T
2) E  T
3) T  T*F
4) T  F 23
5) F   (E)
6) F  id
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I1 I4
E'  E E'  E √ F  (E)
E  E+T E  E+T E  E+T
E  T E  T
T  T*F T  T*F
T  F T  F
F  (E) I2 F  (E)
F  id E  T √ F  id
T  T*F

I5
I3 F  id √
T  F √
24
THE CANONICAL LR(0) COLLECTION
I0 I4
E'  E F  (E)
E  E+T E  E+T
E  T E  T
T  T*F T  T*F
T  F T  F
F  (E) F  (E)
F  id F  id
Initial Set
I1 I6 E’  E
E'  E √ E E+T 1) E  E+T
E  E+T T T*F 2) E  T
Shift  From left of ‘+’ T  F 3) T  T*F
to right of ‘+’ F  (E) 4) T  F
I2
F id 5) F   (E)
E  T √ 6) F  id
T  T*F
I5 Add Productions of T since there is  before T. 25
I3 F  id √ Add Productions of F since there is  before F.
T  F √
THE CANONICAL LR(0) COLLECTION

I0 I3 I5
E'  E T  F √ F  id √
E  E+T
E  T
I4 I6
T  T*F
T  F F  (E) E E+T
F  (E) E  E+T T T*F
F  id E  T T F
T  T*F F  (E)
I1 T  F F id
E'  E √ F  (E)
F  id Initial Set
E  E+T
E’  E
I7 1) E  E+T
I2
T  T*F 2) E  T
E  T √
F  (E) 3) T  T*F
T  T*F Shift  From left of ‘*’ F  id 4) T  F 26
to right of ‘*’ 5) F   (E)
Add Productions of F since there is  before F. 6) F  id
THE CANONICAL LR(0) COLLECTION

I0 I3 I6

E'  E T  F √ E E+T
E  E+T T T*F
E  T T F
T  T*F F  (E)
T  F I4 F id
F  (E) F (E) I8
F  id E E+T F  (E)
E T Shift  From left of E  E+T
I1 T T*F ‘E’ to right of ‘E’
E'  E √ T F
E  E+T F  (E)
F id
I2 I7
E  T √ I5 T  T*F
T  T*F F  (E) 27
F  id √
F  id
THE CANONICAL LR(0) COLLECTION

I0 I3 I6
E'  E T  F √ E E+T
E  E+T T T*F
E  T T F
T  T*F F  (E)
T  F F id
F  (E) I4
F  id F (E) I7
E E+T
I1 E T T  T*F
T T*F F  (E)
E'  E √
T F F  id
E  E+T
F  (E)
I2 F id
I8
E  T √
T  T*F I5 F  (E) 28
E  E+T
F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6
E'  E T  F √ E E+T
E  E+T T T*F
E  T Shift  From left of T F
T  T*F ‘F’ to right of ‘F’ F  (E)
T  F F id
F  (E) I4
F  id F (E) I7
E E+T
I1 E T T  T*F
T T*F F  (E)
E'  E √
T F F  id
E  E+T
F  (E)
I2 F id
I8
E  T √
F  (E)
T  T*F I5 E  E+T 29

F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6
E'  E T  F √ E E+T
E  E+T T T*F
E  T T F
T  T*F F  (E)
T  F F id
F  (E) I4
F  id F (.E) I7
E E+T
I1 E T T  T*F
T T*F F  (E)
E'  E √
T F F  id
E  E+T
F  (E)
F id I8
I2
F  (E)
E  T √ I5 E  E+T 30
T  T*F
F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6
E'  E T  F √ E E+T
E  E+T T T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T I7
T T*F
I1 T F T  T*F
F  (E) F  (E)
E'  E √
F id F  id
E  E+T
Shift  From left of
I2 ‘id’ to right of ‘id’ I8
E  T √ I5 F  (E) 31
T  T*F E  E+T
F  id √
THE CANONICAL LR(0) COLLECTION

I0 Shift  From left of

I3 I6 I9
‘T’ to right of ‘T’
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T
I7
T T*F
I1 T F T  T*F
E'  E √ F  (E) F  (E)
E  E+T F id F  id

I2 I5 I8
E  T √ F  id √ F  (E)
32
T  T*F E  E+T
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T I7
T T*F
I1 T F T  T*F
F  (E) F  (E)
E'  E √
F id F  id
E  E+T

I8
I2
F  (E)
E  T √ I5
E  E+T 33
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) Shift  From left of F  id
F  (E) E E+T ‘(’ to right of ‘(’
F  id E T I7
T T*F
I1 T F T  T*F
F  (E) F  (E)
E'  E √
F id F  id
E  E+T

I8
I2
F  (E)
E  T √ I5
E  E+T 34
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T I7
T T*F
I1 T F T  T*F
F  (E) F  (E)
E'  E √
F id F  id
E  E+T

I8
I2
F  (E)
E  T √ I5
E  E+T 35
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T I7 Shift  From left of I10
‘F’ to right of ‘F’
T T*F T  T*F T  T*F √
I1 T F F  (E)
E'  E √ F  (E) F  id
E  E+T F id

I8
I2
F  (E)
E  T √ I5
E  E+T 36
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4 F  (E)
T  F F (E) F id
F  (E) E E+T I10
F  id E T I7 T  T*F √
T T*F T  T*F
I1 T F F  (E)
E'  E √ F  (E) F  id
E  E+T F id

I8
I2
F  (E)
E  T √ I5
E  E+T 37
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T I10
F  id E T I7
T  T*F √
T T*F T  T*F
I1 T F F  .(E)
E'  E √ F  (E) F  id
E  E+T F id

I8
I2
F  (E)
E  T √ I5
E  E+T 38
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T I7 I10
T T*F
T  T*F T  T*F √
I1 T F
F  (E) F  (E)
E'  E √
F id F  id
E  E+T
I8 Shift  From left of I11
‘)’ to right of ‘)’
I2 F  (E) F  (E)  √
E  T √ I5 E  E+T
39
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id I10
F  (E) E E+T T  T*F √
F  id E T I7
T T*F
I1 T F T  T*F
F  (E) F  (E) I11
E'  E √
F id F  id √
E  E+T F  (E) 
I8
I2 F  (E)
E  T √ I5 E  E+T
40
T  T*F F  id √
THE CANONICAL LR(0) COLLECTION

I0 I3 I6 I9
E'  E T  F √ E E+T E  E+T √
E  E+T T T*F T  T*F
E  T T F
T  T*F I4
F  (E) Shift  From left of
T  F F ‘*’ to right of ‘*’
(E) F id
F  (E) E E+T
F  id E T I7 I10
T T*F
I1 T  T*F T  T*F √
T F
E'  E √ F  (E) F  (E)
E  E+T F id F  id

I11
I2 I5 I8 F  (E)  √
E  T √ F  id √ F  (E) 41
T  T*F E  E+T
Initial Set
E’  E
THE CANONICAL LR(0) COLLECTION 1) E  E+T
2) E  T
3) T  T*F
I0 I3 I6 I9 4) T  F
E'  E T  F √ E E+T E  E+T √ 5) F   (E)
E  E+T T T*F T  T*F 6) F  id
E  T T F
T  T*F I4
F  (E)
T  F F (E) F id
F  (E) E E+T
F  id E T I7
T T*F I10
I1 T F T  T*F
T  T*F √
F  (E) F  (E)
E'  E √
F id F  id
E  E+T

I2 I5 I8 I11
E  T √ F  id √ F  (E) F  (E)  √ 42
T  T*F E  E+T
CONSTRUCTING SLR PARSING TABLE
(OF AN AUGUMENTED GRAMMAR G')

1. Construct the canonical collection of sets of LR(0) items for G'.

C{I0,...,In}
2. Create the parsing action table 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).

3. Create the parsing goto table

• for all non-terminals A, if goto(Ii,A)=Ij then goto[i,A]=j

4. All entries not defined by (2) and (3) are errors.

43
5. Initial state of the parser contains S’.S
CONSTRUCTING SLR PARSING TABLES

 An LR(0) item of a grammar G is a production of G a dot at the


some position of the right side.
Ex: A  aBb Possible LR(0) Items: A  aBb
A  a Bb
..
(four different possibility)
A  aB b
A  aBb
..
 Sets of LR(0) items will be the states of action and goto table of the
SLR parser.
 A collection of sets of LR(0) items (the canonical LR(0)
collection) is the basis for constructing SLR parsers.
 Augmented Grammar:
G' is G with a new production rule S'S where S' is the new 44
starting symbol.
GOTO OPERATION

 If I is a set of LR(0) items and X is a grammar symbol (terminal or non-

terminal), then goto(I,X) is defined as follows:
 . .
If A   X in I then every item in closure({A  X }) will be in goto(I,X).

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,() = { F  ( E), E  E+T, E  T, T  T*F, T
 F,
..
F  (E), F  id } . 45
goto(I,id) = { F  id }
TRANSITION DIAGRAM (DFA) OF GOTO FUNCTION

E + T
I0 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
46
FIRST AND FOLLOW SET

Consider the following Grammar

E  E+T
E T
T  T*F
T F
F  (E)
F  id

FIRST(E) = {(,id} FOLLOW (E) = {$, ),+}

FIRST (T)= {(,id} FOLLOW(T) ={$,),+,*}
FIRST (F)= {(,id} FOLLOW (F)= {$,),+,*}

47
ACTION GOTO
state id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
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 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5

FOLLOW (E) = {$, ),+}

E'  .E FOLLOW(T) ={$,),+,*}
1) E  E+T FOLLOW (F)= {$,),+,*}
2) E  T
3) T  T*F •Si means shift and stack state i
4) T  F •rj means reduce by production
numbered j 48
5) F  (E)
6) F  id •acc means accept state
•blank mean error
(SLR) PARSING TABLES FOR EXPRESSION GRAMMAR
Action Table Goto Table
1) E  E+T State id + * ( ) $ E T F
0 s5 s4 1 2 3
2) ET
1 s6 acc
3) T  T*F 2 r2 s7 r2 r2
4) TF 3 r4 r4 r4 r4
5) F  (E) 4 s5 s4 8 2 3
6) F  id 5 r6 r6 r6 r6

•Si means shift

6 s5 s4 9 3
and stack state i 7 s5 s4 10
•rj means reduce 8 s6 s11
by production
9 r1 s7 r1 r1
numbered j
•acc means accept state
10 r3 r3 r3 r3
•blank mean error 11 r5 r5 r5 r5 49
ACTIONS OF A (S)LR-PARSER -- EXAMPLE
Stack Input Action Output ACTION GOTO

0 id*id+id$ shift 5 State id + * ( ) $ E T F

0 s5 s4 1 2 3
0id5 *id+id$ reduce by Fid Fid
1 s6 acc
0F3 (GOTO) *id+id$ reduce by TF TF
2 r2 s7 r2 r2
0T2(GOTO) *id+id$ shift 7
3 r4 r4 r4 r4
0T2*7 id+id$ shift 5
4 s5 s4 8 2 3
0T2*7id5 +id$ reduce by Fid Fid 5 r6 r6 r6 r6
0T2*7F10 +id$ reduce by TT*F TT*F 6 s5 s4 9 3
(GOTO) 7 s5 s4 10
0T2 (GOTO) +id$ reduce by ET ET 8 s6 s11
0E1(GOTO) +id$ shift 6 9 r1 s7 r1 r1
0E1+6 id$ shift 5 10 r3 r3 r3 r3
0E1+6id5 $ reduce by Fid Fid 11 r5 r5 r5 r5

0E1+6F3 $ reduce by TF TF

(GOTO) E'  .E
1) E  E+T •Si means shift and stack state i
0E1+6T9 $ reduce by EE+T EE+T
2) E  T •rj means reduce by production
(GOTO)
3) T  T*F numbered j
0E1 $ accept 50
4) T  F acc means accept state
5) F  (E) •blank mean error
6) F  id
A STACK IMPLEMENTATION OF A SHIFT-REDUCE PARSER
Stack Input Action
$ id+id*id$ shift
$id +id*id$ reduce by F  id Parse Tree
$F +id*id$ reduce by T  F
$T +id*id$ reduce by E  T E 8
$E +id*id$ shift
$E+ id*id$ shift E 3 + T 7
$E+id *id$ reduce by F  id
$E+F *id$ reduce by T  F T 2 T 5 * F6
$E+T *id$ shift
$E+T* id$ shift F 1 F 4 id
$E+T*id $ reduce by F  id
$E+T*F $ reduce by T  T*F id id
$E+T $ reduce by E  E+T
$E $ accept 51
SLR EXAMPLE -II

Consider the following Grammar

S (L)
S x
L S
L L,S

52
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 Shift  From left of ‘S’

I1
to right of S
S'  S S’  S (Complete)
S  (L)
S  x

Initial Set
S'  S
1) S  (L)
2) S  x
3) L  S
4) L  L,S 53
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I2 Initial Set
Shift  From left of ‘(’
S'  S to right of ‘(‘ S (L) S'  S
S  (L) L S 1) S  (L)
S  x L L,S 2) S  x
S (L) 3) L  S
I1 S x 4) L  L,S
S’  S √

54
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
S'  S Shift  From left of ‘x’
S  (L) to right of ‘x’ I3
S  x S  x √

I1
S’  S √

I2
S (L)
L S
L L,S
S (L)
S x
55
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0
S'  S
S  (L)
S  x

I1
S’  S √

I2 Shift  From left of ‘L’ I4

to right of ‘L’
S (L) S  (L)
L S L  L,S
L L,S
S (L)
S x
56
I3
S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4 Initial Set
S'  S S  (L) S'  S
S  (L) L  L,S 1) S  (L)
S  x 2) S  x
3) L  S
I1 4) L  L,S
S’  S √

I2 Shift  From left of ‘S’

to right of ‘S’ I5
S (L)
L S L  S √
L L,S
S (L)
S x
57
I3
S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4
S'  S S  (L)
S  (L) L  L,S
S  x
I5
I1
L  S √
S’  S √

I2
S (L)
L S
L L,S
S (L)
S x
58
I3
S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4
S'  S S  (L)
S  (L) L  L,S
S  x
I5
I1
L  S √
S’  S √

I2
S (L)
L S Shift  From left of ‘(’
L L,S to right of ‘(’
S (L)
S x
59
I3
S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4
S'  S S  (L)
S  (L) L  L,S
S  x
I5
I1
L  S √
S’  S √

I2
S (L)
L S
L L,S
S (L)
S x
Shift  From left of ‘x’
60
I3 to right of ‘x’

S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4 I6
S'  S S  (L) S  (L) √
S  (L) L  L,S Shift  From left of ‘)’
S  x to right of ‘)’

I5
I1
L  S √
S’  S √

I2
S (L)
L S
L L,S
S (L)
S x
61
I3
S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4 I7
S'  S S  (L) L  L,S
S  (L) L  L,S S  (L)
S  x Shift  From left of ‘,’ S  x
to right of ‘,’
I5
I1
L  S √
S’  S √

I2 I6
S (L) S  (L) √
L S
L L,S
S (L)
S x
62
I3
S  x √
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4
S'  S S  (L)
S  (L) L  L,S
S  x
I5
I1
L  S √
S’  S √

I2 I6
S (L) S  (L) √
L S
L L,S
S (L)
S x I7 I8
L  L,S L  L,S √ 63
I3 S  (L) Shift  From left of ‘S’
to right of ‘S’
S  x √ S  x
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I4 I8
S'  S S  (L) L  L,S √
S  (L) L  L,S
S  x
I5
I1
L  S √
S’  S √

I2 I6
S (L) S  (L) √
L S
L L,S
S (L)
S x I7
L  L,S 64
I3 S  (L)
S  x √ S  x
THE CANONICAL LR(0) COLLECTION -- EXAMPLE

I0 I3 I7 I8
x x S
S'  S S  x √ L  L,S L  L,S √
S  (L) S  (L)
S  x x S  x
(
S I2
S (L) (
,
I1 L S
L L,S I4
S’  S √
S (L) S  (L)
S x L  L,S
L
S
)
I5
L  S √ I6
65
S  (L) √
SHIFT/REDUCE AND REDUCE/REDUCE CONFLICTS

 If a state does not know whether it will make a shift operation

or reduction for a terminal, we say that there is a shift/reduce
conflict.
 If a state does not know whether it will make a reduction
operation using the production rule i or j for a terminal, we
say that there is a reduce/reduce conflict.

 If the SLR parsing table of a grammar G has a conflict, we say

that grammar is not SLR grammar.

66
FIRST AND FOLLOW SET

Consider the following Grammar

S L=R
S R
L *R
L id
R L

FIRST(S) = {*,id} FOLLOW (S) = {$}

FIRST (L)= {*,id} FOLLOW(L) ={$,=}
FIRST (R)= {*,id} FOLLOW (R)= {$,=}

67
Initial Grammar

S'  S
CONFLICT EXAMPLE
1) S  L=R
2) S  R
3) L  *R I0 I3 I6
4) L  id R
S'  S S R √ S L=R
5) R  L
S  L=R R L
S  R L *R
L  *R I4 * L id
L  id *
L *R
R  L
R L I7
L *R R R
S L  *R √
L id L
L I1
L
S'  S √
id I8
*
id R  L √
I5
I2
L  id √
S  L=R I9 68

R  L √ = S  L=R √
I6
(SLR) PARSING TABLES FOR EXPRESSION GRAMMAR
Initial Grammar ACTION GOTO I2
S'  .S State id = * $ S L R S  L=R
1) S  .L=R R  L √
2) S  .R
3) L  .*R 0 s5 s4 1 2 3 =
4) L  .id 1 acc I6
5) R  .L
2 s6 r5 S L=R
r5 R L
L *R
3 r2 L id
4 s5 s4 8 7
5 r4 r4 FOLLOW (S) = {$}
Shift/ 6 s5 s4 8 9 FOLLOW(L) ={$,=}
Reduce FOLLOW (R)= {$,=}
7 r3 r3
Conflict 8 r5 r5
69
9 r1
Part II will include
LR(1) parsers and error
recovery

70