Bottom-up Parsing

(BUP)
SLR(1) parsers
LR Parser Types
• Following LR parsers are in ascending
order from left to right by their efficiency.
▫Least efficient parser is LR(0) and
▫Highest efficient parser is CLR(1)

LR

LALR(1)
SLR(1) CLR(1)
LR(0) Look Ahead
Simple LR Canonical LR
LR
LR Parsers General Components

Input Buffer

STACK LR Parser

LR Parsing Table
LR Parser…
• “How to construct a parsing table?” is the only
difference between all types of LR parsers.
• Parsing algorithm remain same for all types of LR
parsers.
• In the construction of parsing table for:
▫ LR(0) and SLR(1) parser we use canonical
collection of LR(0) items.
▫ LALR(1) and CLR(1) parser we use canonical
collection of LR(1) items.
LR(1)/SLR(1) Parsing Table
• Reduce moves are changed in SLR(1)
parsing table than LR(0).
• Here we do not reduce blindly without
knowing what is in the look ahead.
• Using the previous example we will
construct the table for LR(1).
Syntax Analysis
Course Textbook (Chapter 4)

Faryal Shamsi
Department of Computer Science
Sukkur IBA University
Bottom-up Parsing (BUP)
LR(0) parsers
Bottom-up Parsing

• A bottom-up parse corresponds to the construction of a parse tree

for an input string beginning at the leaves (the bottom) and
working up towards the root (the top).

FE+T|T
TT*F|F
F(E)|id
Reductions

• At each reduction step , a specific substring matching the body of

a production is replaced by the non-terminal at the head of that
production.
FE+T|T
TT*F|F
F(E)|id
• First id reduced to F due to Fid
• Then F reduces to T due to TT production
• Then Second id reduced to F
• And so on
Shift-Reduce Parsing

• Shift-reduce parsing is a form of bottom-up parsing in which a

stack holds grammar symbols and an input buffer holds the rest of
the string to be parsed.
• We use $ to mark the bottom of the stack and also the right
end of the input.
• Initially, the stack is empty, and the string w is on the input , as
follows:
Shift Reduce Parser actions

Four possible actions a shift-reduce parser can make:

• 1. Shift. Shift the next input symbol onto the top of the stack.
• 2. Reduce. The right end of the string to be reduced must be at
the top of the stack. Locate the left end of the string within the
stack and decide with what non-terminal to replace the string.
• 3. Accept. Announce successful completion of parsing.
• 4. Error. Discover a syntax error and call an error recovery routine.
Conflict during Shift Reduce Parsing

• There are context-free grammars for which shift-reduce parsing

cannot be used.
• Every shift-reduce parser for such a grammar can reach a
configuration in which the parser,
• knowing the entire stack contents and
• the next input symbol,
• cannot decide whether to shift or to reduce ( a shift/reduce
conflict) ,
• or cannot decide which of several reductions to make ( a reduce
/reduce conflict).
• We see some examples of SR and RR conflict in next lecture slides.
LR Parser Types

• Following LR parsers are in ascending order from left to right by their

efficiency.
• Least efficient parser is LR(0) and
• Highest efficient parser is CLR(1)

LR

LALR(1)
SLR(1) CLR(1)
LR(0) Look Ahead
Simple LR Canonical LR
LR
Introduction to LR Parsing

• The most prevalent type of bottom-up parser today is

based on a concept called LR(k) parsing;
• the "L" is for lef t-to-right scanning of the input ,
• the "R" for constructing a rightmost derivation in
reverse, and
• the k for the number of input symbols of look
ahead that are used in making parsing decisions.
• The cases k=0 or k=1 are of practical interest, and
we shall only consider LR parsers with k <= 1 here.
• When (k) is omitted, k is assumed to be 1.
Why LR Parsers?

1. LR parsers can be constructed to recognize virtually all

programming language constructs for which context-free
grammars can be written.
2. The LR-parsing method is the most general non backtracking shift-
reduce parsing method known, yet it can be implemented as
efficiently as other, more primitive shift-reduce methods.
3. An LR parser can detect a syntactic error as soon as it is possible
to do so on a left-to-right scan of the input .
4. LR grammars can describe more languages than LL grammars.
Drawback of LR

• The principal drawback of the LR method is that it is too much

work to construct an LR parser by hand for a typical programming-
language grammar.

• A specialized tool , an LR parser generator, is needed.

• Fortunately, many such generators are available, and we shall

discuss one of the most commonly used ones, Yacc,
Tips for LR parser

• LR(0): Left to right scanning, Right most derivation in reverse order.

• Simple LR / SLR(1) / SLR / LR(1)

• Lookahead LR / LALR(1) / LALR
• Canonical LR / CLR(1) /CLR
• ONE is optional in LR parsers
• But ZERO is mandatory to mentioned
LR Parsers General Components

Input Buffer

STACK LR Parser

LR Parsing Table
LR Parser

• “How to construct a parsing table?” is the only difference between all types of LR
parsers.
• Parsing algorithm remain same for all types of LR parsers.
• In the construction of parsing table for:
• LR(0) and SLR(1) parser we use canonical collection of LR(0) items.
• LALR(1) and CLR(1) parser we use canonical collection of LR(1) items.
What are LR items?

• Suppose S. AA
• SAA This is called canonical collection of LR(0) item,
when dot is there.
• We use a DOT as shown in following production
• S. AA it means “not seen any thing”
• S A . A “Seen single A only”
• SAA . “Seen All”
• It actually shows reduction of AA . to S, i.e
LR(0) Parsing table Example

• In LL(1) parsing table construction we used FIRST and FOLLOW

functions.
• While in LR(0) parsing table we will use CLOSURE and GOTO
functions.
LR(0) Parsing table Example

• SAA
• AaA|b
• Convert into augmented grammar form
• S’S
• SAA
• AaA|b
• Perform CLOSURE
• Closure of S’ is as follows
• S’. S
• S. AA When we see dot on left of A, then add dot on all productions of A
• A . aA|.b
LR(0) Parsing table Example
S’S
SAA
• I0 AaA|b
• S’. S
• S. AA Dot is left of A, so that perform closure of A
• A . aA|.b
• Perform GOTO
• Shift dot one variable right for each terminal and nonterminal.
• I1 (GOTO for S)
• S’S. Its complete we have seen all productions
• I2 (GOTO for A)
• SA . A Dot is left of A, so we perform closure of A
• A a . A | .b
• And so on see next slide for complete solution.
LR(0) Parsing table Example

SAA S’S .
b
A aA|b
GOTO S
S
SA . A A S’AA .
A A . aA|. b
S’S S’. S
SAA S. AA a a
Cl o
Au

A aA|b A . aA|. b a
g

su
m

Aa . A A
en

re

AaA .
te

A . aA|. b
of
d

S’
fo

b
rm

Ab .
LR(0) Parsing table Example
I1
SAA S’S .
b
A aA|b
S I2
I5
SA . A A S’AA .
I0 A A . aA|. b
S’S S’. S
S. AA a a
SAA 1 I3
A aA 2 A . aA|. b a I6
|b 3 Aa . A A AaA .
A . aA|. b
b
b
I4
Ab .

•I0 to I6 are states called canonical collection of LR(0) items

•I1,I4,I5 and I6 are called completed items. i.e we have seen all productions and can be
reduced.
LR(0) Parsing table Example
•Action part of table contains terminals
•GOTO part will contain Non-terminal
•S means Shift
•I0 to I6 are states

I0 on S going to I1, so S contains 1 in table

 I0 on A going to I2, so A contains 1 in table
….
 I0 on a is going to I3, so a contains S3
 I1 on b is going to I4, so b contains S4 I ACTION GOTO
….. a b $ A S

0 S3 S4 2 1

1
This table is common for all types of parser like 2 S3 S4 5
LR(0), SLR(1), LALR(1),CLR(1)
3 S3 S4 6
Table can vary for final items(having dot on right
hand side) like I1,I4,I5,I6. 4
 Now assign numbers 1,2,3.. to the productions 5

6
LR(0) Parsing table Example
•Action part of table contains terminals
•GOTO part will contain Non-terminal
•S means Shift
•I0 to I6 are states

I ACTION GOTO
I0 on S going to I1, so S contains 1 in table a b $ A S
 I0 on A going to I2, so A contains 1 in table
0 S3 S4 2 1
….
 I0 on a is going to I3, so a contains S3 1 Accept
 I1 on b is going to I4, so b contains S4 2 S3 S4 5
…..
 I1 is augmented production, that means we have 3 S3 S4 6

seen all. So I1 on $ is accept in table 4 r3 r3 r3

I4 is b. and it is 3rd production so 4th row uses r3
5 r1 r1 r1
for a,b,$.
I5 is AA. And its 1st production so 5th row uses r1 6 r2 r2 r2
for a,b,$......
How to use Table in parsing
• Example:
• Reduce:
• INPUT: aabb$

$
• STACK:
How to use Table in parsing
• Example:

• Reduce:
• INPUT: aabb$

0
• STACK:
•Assign numbers to each production
•Add $ to input string
•Show pointer in input on first letter
•Zero state will be on top of the stack
How to use Table in parsing
• Example:
• Reduce:
• INPUT: aabb$

0
• STACK:
•Top of the stack is Zero and input is a
•See zero on a in table, it is S3
•So PUSH a and 3,
•Move input pointer one ahead
How to use Table in parsing
• Example:

• Reduce:
• INPUT: aabb$

0 a 3
• STACK:
•Top of the stack is 3 and input is a
•See 3 on a in table, it is S3
•So PUSH a and 3,
•Move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3
• STACK:
•Top of the stack is 3 and input is b
•See 3 on b in table, it is S4
•So PUSH b and 4,
•Move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4
• STACK:
•Top of the stack is 4 and input is b
•See 4 on b in table, it is r3
•R3 means see 3rd production i.e Ab
•Size of production A|b| is one element so
POP two/double elements.
•POP 4,b and PUSH A
•Reduce previous input that is aabb to A
•Don’t move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A
• STACK:
•We need state number for A so that
•See stack contains 3 and A
•See 3 on A in table, it is 6
•PUSH 6
•Now 6 is the state number for A
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6
• STACK:
•Top of the stack is 6 and input is b
•See 6 on b in table, it is r2
•r2 means see 2nd production i.e AaA
•Size of production A|aA| is two elements so
POP four/double elements.
•POP 6,A,3,a and PUSH A
•Reduce (i.e AaA)previous input that is aabb to A
•Don’t move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A
• STACK:
•We need state number for A so that
•See stack contains A and 3
•See 3 on A in table, it is 6
•PUSH 6
•6 is state number for A
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6
• STACK:
•Top of the stack is 6 and input is b
•See 6 on b in table, it is r2
•r2 means see 2nd production i.e AaA
•Size of production A|aA| is two elements so
POP four/double elements.
•POP 6,A,3,a and PUSH A
•Reduce (i.e AaA) previous input that is aabb to A
•Don’t move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A
• STACK:
•We need state number for A so that
•See stack contains A and 0
•See 0 on A in table, it is 2
•PUSH 2
•2 is state number for A
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A 2
• STACK:
•Top of the stack is 2 and input is b
•See 2 on b in table, it is S4
•So PUSH b and 4,
•Move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A 2 b 4
• STACK:
•Top of the stack is 4 and input is $
•See 4 on $ in table, it is r3
•r3 means see 3rd production i.e Ab
•Size of production A|b| is one element so POP
two/double elements.
•POP 4,b and PUSH A
•Reduce (i.e Ab) previous input that is aabb to A
•Don’t move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A 2 b 4 A
• STACK:
•See stack contains A and 2
•See 2 on A in table, it is 5
•PUSH 5
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A 2 b 4 A 5
• STACK:
•Top of the stack is 5 and input is $
•See 5 on $ in table, it is r1
•r1 means see 1st production i.e SAA
•Size of production S|AA| is two elements so
POP four/double elements.
•POP 5,A,2,A and PUSH S
•Reduce (i.e SAA)
•Don’t move input pointer one ahead
 • Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A 2 b 4 A 5 S
• STACK:
•See stack contains S and 0
•See 0 on S in table, it is 1
•PUSH 1
• Example:

• Reduce:
• INPUT: aabb$

0 a 3 a 3 b 4 A 6 A 6 A 2 b 4 A 5 S 1
• STACK:
•See 1 on $ in table, it is accepted
What is meaning of LR(0)

• We have zero look ahead

• It doest mean that we are not looking any symbol at all.
• Lets understand by given examples for recent parse table
• The input was aabb$
• Here while reading last last b (i.e aabb$), we reduced second last b to A.
(i.e aabb$)
• The 4th row in table is filled by r3 (three times)
• It means that if you read any letter a,b or $ you can reduce second last variable,
without knowing what is in the look ahead. That’s why called zero look ahead
• Due to r3 repetitions it may be difficult for LR(0) parser to detect errors more
efficiently.
• LR(0) is less efficient than SLR(1)
• In the table see
• I2 and $ is a blank entry that shows an error
• I3 and $ is also an error
LR Parsing Algorithm
LR(1)/SLR(1) Parsing Table
•Action part of table contains
terminals
•GOTO part will contain Non-
terminal
•S means Shift and r means
Reduce
•Only reduce moves(r1,r2,r3) will
LR(0) Table be changes for LR(1)
LR(1) Table
I ACTION GOTO I ACTION GOTO
a b $ A S a b $ A S
0 S3 S4 2 1 0 S3 S4 2 1
1 Accep 1 Accep
t t
2 S3 S4 5 2 S3 S4 5
3 S3 S4 6 3 S3 S4 6
4 r3 r3 r3 4
5 r1 r1 r1 5
 LR(1)/SLR(1) Parsing Table
•Action part of table contains
terminals
•GOTO part will contain Non-
terminal
•S means Shift
•Only reduce moves(r1,r2,r3) will
be changes for LR(1)

I ACTION GOTO
See I4, for canonical items i.e A.b, it is
a b $ A S
3rd production.
Find FOLLOW of A (LHS) i.e a,b,$ 0 S3 S4 2 1
So put r3 under a,b,$ in 4t row of 1 Accep
table t
2 S3 S4 5
3 S3 S4 6
4 r3 r3 r3
5
6
 LR(1)/SLR(1) Parsing Table
•Action part of table contains
terminals
•GOTO part will contain Non-
terminal
•S means Shift and r means
Reduce
•Only reduce moves(r1,r2,r3) will
be changes for LR(1)
I ACTION GOTO
See I4, for canonical items i.e A.b, its
a b $ A S
3rd production.
Find FOLLOW of A (LHS) i.e a,b,$ 0 S3 S4 2 1
So put r3 under a,b,$ in 4th row of 1 Accep
table t

See I5, for canonical items i.e SAA ., it 2 S3 S4 5

is 1st production. 3 S3 S4 6
Find FOLLOW of S (LHS) i.e $
4 r3 r3 r3
So put r1 under $ in 5th row of table
5 r1
6
 LR(1)/SLR(1) Parsing Table
•Action part of table contains
terminals
•GOTO part will contain Non-
terminal
•S means Shift and r means
Reduce
•Only reduce moves(r1,r2,r3) will
be changes for LR(1)
I ACTION GOTO
See I4, for canonical items i.e A.b, its 3rd
production. a b $ A S
Find FOLLOW of A (LHS) i.e a,b,$
So put r3 under a,b,$ in 4th row of table 0 S3 S4 2 1
See I5, for canonical items i.e SAA ., it is 1st 1 Accep
production.
Find FOLLOW of S (LHS) i.e $ t
So put r1 under $ in 5th row of table
2 S3 S4 5
See I6, for canonical items i.e AaA ., it 3 S3 S4 6
is 2nd production.
Find FOLLOW of A (LHS) i.e a,b,$ 4 r3 r3 r3
So put r2 under a,b,$ in 6th row of 5 r1
table 6 r2 r2 r2
LR(1)/SLR(1) Parsing Table
I ACTION GOTO
a b $ A S
0 S S 2 1
3 4
1 Acce
pt
2 S S 5
3 4
3 S S 6
3 4
 See the 5th row in table 4 r3 r3 r3
 It shows that if we have SAA then we 5 r1
reduce it when we have only AA$ 6 r2 r2 r2
 It is called SLR(1), and we looked
ahead one.
No of errors detection depends on the blank moves in the table.
SLR(1) have more blank moves than LR(0)
So SLR(1) is more efficient than LR(0) in error detection.
 On error parser may add, remove or replace any input character or
shows an error message.
Create Parsing Table using LR(1)
• Example: Suppose grammar is:
▫SdA|aB
▫AbA|c
▫BbB|c
Create Parsing Table
• Example: Suppose grammar is:
▫SdA|aB
▫AbA|c
▫BbB|c