Bottom up Parsing

Bottom up Parsers
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
 Bottom up Parsing
• A parse tree is created from the leaf upwards
• The symbols in the input are placed at the leaf nodes of the tree
• Starting from the leaves, the parser fills in the internal nodes of the parse tree
gradually eventually finding the root.
• The creation of an internal node involves replacing symbols from (VUT)* by a
single non terminal repeatedly
• The task is to identify the RHS of a production rule in the tree constructed so far
and replace it with the corresponding LHS of the production rule
• This is called reduction
• The crucial task in bottom up parsing is to find productions that have to be
used for reduction
 Shift Reduce Parsing
• A generic name for a family of parsers that employ the strategy of
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) will be replaced by the non-
terminal at the left side of that production.
• There are also two more actions: accept and error.
 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
Shift-Reduce Parser finds:   ...  S
 Handles
• Handle of a string: Substring that matches the RHS of some production AND whose
reduction to the non-terminal on the LHS represents one step along the reverse of
a rightmost derivation.

• 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 .
S  A  
i.e. A   is a handle of  at the location immediately after the end of ,
• If the grammar is unambiguous, then every right-sentential form of the grammar
has exactly one handle.
• The string  to the right of the handle contains terminal symbols only
 Handle Pruning
• A rightmost derivation in reverse can be obtained by handle pruning
• Start with a string of terminals,  that we wish to parse
• If  is a sentence of the grammar, then we start with n, where n is the nth right
sentential form of some at yet unknown rightmost derivation

• S=0  1  2  ...  n-1  n= 

Apply the following simple algorithm
• Start from n , locate n in n and replace with the LHS of the production Ann to
obtain the previous right sentential form n-1.
• Then find a n-1 in n-1 and reduce this handle with the LHS of the production
An-1n-1 to get n-2.
• Repeat this, until we reach S.
 Example
Consider:
S  aABe
A  Abc | b
Bd

S  aABe  aAde  aAbcde  abbcde

A  b is a handle of abbcde in location 2.

A  Abc is a handle of aAbcde in location 2.
B  d is a handle of aAde in location 3.
S  aABe is a handle of aABe in location 1.
 Handle
• Grammar • Rightmost • Shift Reduce
• E E+E Derivation Parsing
• E E*E id1+id2*id3
• E  E+E
• E (E) rm E+id2*id3
• E id  E+E*E
rm E+E*id3
 E+E*id3
rm E+E*E
 E+id2*id3
rm E+E
 id1+id2*id3
rm E
 Stack Implementation of Shift Reduce Parser
• Shift reduce parser can be implemented with a stack and an input
buffer
• Initial configuration: Stack: $, Input: w$
• Parser operates by shifting zero or more input symbols onto the stack until a
handle β is on top of the stack.
• Parser then reduces β to the left side of the appropriate production
• Parser repeats this process until it has discovered an error or until the stack
contains the start symbol and the input is empty.
• Final configuration: Stack: $S, Input: $
• The parser halts and announces successful completion of parsing
Stack Implementation of Shift Reduce Parsing
Four possible actions of a shift reduce parser

1. Shift : The next input symbol is shifted onto the top of the stack.

2. Reduce: The right end of the string to be reduced is on top of the stack.
Locate the left end of the string within the stack. Replace the handle on the
top of the stack by the nonterminal.

3. Accept: Successful completion of parsing.

4. Error: Parser discovers a syntax error, and calls an error recovery routine.
Stack Implementation of Shift Reduce Parsing
Stack Input Action
$ id+id*id$ shift
$id +id*id$ Reduce F→id
$F +id*id$ Reduce T→F
$T +id*id$ Reduce E→T
$E +id*id$ shift
$E+ id*id$ shift
$E+id *id$ Reduce F→id
$E+F *id$ Reduce T→F
$E+T *id$ shift
$E+T* id$ shift
$E+T*id $ Reduce F→id
$E+T*F $ Reduce T→T*F
$E+T $ Reduce E→E+T
$E $ Accept
 Conflicts During Shift Reduce Parsing
• Viable Prefix
• The set of prefixes of right sentential forms that can appear on the stack of a
shift reduce parser
• Stack contents and the next input symbol may not decide action
• shift/reduce conflict: Whether to make a shift operation or a reduction.
• reduce/reduce conflict: The parser cannot decide which of several
reductions to make.
• There are context-free grammars for which shift-reduce parsers cannot be
used.
• If a shift-reduce parser cannot be used for a grammar, that grammar is
called as non-LR(k) grammar.
• L: left to right scanning
• R: rightmost derivation in reverse
• k: lookahead
• An ambiguous grammar can never be a LR grammar.
 Shift Reduce Parsers
• Two main categories of shift reduce parsers
1. Operator Precedence Parser
• simple, but only a small class of grammars.
2. LR Parser
• covers wide range of grammars.
• SLR – simple LR parser
• Canonical LR – most general LR parser
• LALR – intermediate LR parser (lookahead LR parser)
• SLR, Canonical LR and LALR work same, only their parsing tables are
different.
 Operator Precedence Parser
• Operator grammar
• small, but an important class of grammars
• In an operator grammar, no production rule can have:
•  at the right side
• two adjacent non-terminals at the right side.

• Ex:
EAB EEAE EE+E
Aa Eid |E*E
Bb A+|*|/ | E/E | id
not operator grammar not operator grammar operator grammar
 Precedence Relations
• In operator-precedence parsing, we define three disjoint precedence
relations between certain pairs of terminals.

a <. b a yields precedence to b or b has higher precedence than a

a =· b a has same precedence as b
a .> b a takes precedence over b or b has lower precedence than a

• The determination of correct precedence relations between terminals are

based on the traditional notions of associativity and precedence of
operators. (Unary minus causes a problem).
• If * has higher precedence than +, then * .>+ and + <. *
 Using Operator-Precedence Relations
• The intention of the precedence relations is to find the handle of a
right-sentential form,
<. with marking the left end,
=· appearing in the interior of the handle, and
.> marking the right hand.

• Right sentential form: β0a1β1a2β2……. anβn

• Each βi is a single nonterminal and each ai is a single terminal
• In our input string, remove all nonterminals (β0, β1,β2…,βn) and place
precedence relations between all pairs of terminals ($a1a2...an$, )
• $ <. b and b .> $ for all terminals b
 Using Operator-Precedence Relations
• E  E+E | E-E | E*E | E/E | E^E | (E) | -E | id
The partial operator-precedence table for this grammar

• Input string: id+id*id

• Insert precedence relation

$ <. id .> + <. id .> * <. id .> $
 To Find The Handles
1. Scan the string from left end until the first .> is encountered.
2. Then scan backwards (to the left) over any =· until a <. is encountered.
3. The handle contains everything to left of the first .> and to the right of the <.
encountered in step 2 including any intervening or surrounding nonterminal

$ <. id .> + <. id .> * <. id .> $ E  id $ id + id * id $

$ <. + <. id .> * <. id .> $ E  id $ E + id * id $
$ <. + <. * <. id .> $ E  id $ E + E * id $
$ <. + <. * .> $ E  E*E E + E * .E $
$ <. + .> $ E  E+E E+E$
$$ $E$
 Operator Precedence Parsing Algorithm
Input: An input string w$ and a table of precedence relations
Output: If w is well formed, a skeletal parse tree with placeholder nonterminal E labelling all interior nodes,
otherwise an error indication
Method: Initially stack contains $ and input buffer the string w$
Algorithm:
set ip to point to the first symbol of w$ ;
repeat forever
if ( $ is on top of the stack and ip points to $ ) then return
else begin
let a be the symbol on top of the stack and let b be the symbol pointed to by ip;
if ( a <. b or a =· b ) then begin /* SHIFT */
push b onto the stack;
advance ip to the next input symbol;
end
else if ( a .> b ) then /* REDUCE */
repeat pop stack
until the top of stack terminal is related by <. to the terminal most recently popped ;
else error();
end
 Operator Precedence Parsing -Example
stack input action
$ id+id$ $ <. id shift
$id +id$ id .> +, reduce E  id
$ +id$ $ <. +, shift
$+ id$ + <. id, shift
$+id $ id .> $, reduce E  id
$+ $ $ <. +, + .> $, reduce E  E+E
$ $ accept
 Operator Precedence Parsing -Example
stack input action
$ id+id*id$ $ <. id shift
$id +id*id$ id .> + reduce E  id
$ +id*id$ $ <. + shift
$+ id*id$ + <. id shift
$+id *id$ id .> * reduce E  id
$+ *id$ + <. * shift
$+* id$ * <. id shift
$+*id $ id .> $ reduce E  id
$+* $ * .> $, pop *, reduce E  E*E
$+ $ + .> $, $ <. +, reduce E  E+E
$ $ accept
 How to Create Operator-Precedence Relations
We use associativity and precedence relations among operators.
1. If operator 1 has higher precedence than operator 2,  1 .> 2 and 2<. 1

2. If operator 1 and operator 2 have equal precedence,

they are left-associative  1 .> 2 and 2 .> 1
they are right-associative  1 <. 2 and 2 <. 1

3. For all operators ,

 <. id, id .> ,  <. (, (<. ,  .> ), ) .> ,  .> $, and $ <. 

4. (=·) $ <. ( id .> ) ) .>

( <. ( $ <. id id .> $ ) .> ) ( <. id
LR Parser
 LR Parser
• Efficient bottom up parser for a large class of grammar
LR(k)
left to right right-most k lookahead
scanning derivation in reverse (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 a left-to-
right scan of the input.
• Can recognize virtually all programming language constructs for which CFG can be
written
• Drawback: Too much work to construct LR parser by hand
• Specialized parser generators are required
 LR Parser
• LR Parsers
• covers wide range of grammars.
• SLR – simple LR parser
• Canonical LR – most general LR parser
• LALR – look-ahead LR parser (intermediate LR parser)
• SLR, Canonical LR and LALR work same (they use the same algorithm), only
their parsing tables are different.
• LR Parser consists of two parts: driver routine and parsing table
• Driver routine same for all LR parsers
• Parsing table is different
 LR Parser
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 a
S0 a actions a state number
t t
e e
s s
 SLR Parsing Table for Grammar, G
Action Goto
1) E  E+T
state id + * ( ) $ E T F
2) ET 0 s5 s4 1 2 3
3) T  T*F 1 s6 acc
4) TF 2 r2 s7 r2 r2

5) F  (E) 3 r4 r4 r4 r4
4 s5 s4 8 2 3
6) F  id
5 r6 r6 r6 r6
6 s5 s4 9 3
• sj: shift current input symbol and
state j onto stack 7 s5 s4 10
• rj: reduce by production number j 8 s6 s11
• acc: accept 9 r1 s7 r1 r1
• Blank entries: error
10 r3 r3 r3 r3
11 r5 r5 r5 r5
 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

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

X1 ... Xm ai ai+1 ... an $
• Initial Stack contains just So
• Sm and ai decides the parser action by consulting the parsing action table entry
action[Sm,ai]
 LR Parser
1. action[Sm, ai] = 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 $ )

Input * id + id $ Input id + id $

7
*
2 action(2,*) = s7 2
T
T
0
0
Stack
Stack
 LR Parser
2. action[Sm, ai] = reduce A
pop 2|| (=2r) items from the stack;
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 $)
• Output the reducing production reduce A
Input Input
+ id $ + id $

10
Stack
F 2
2*3 items • Pop 3 grammar
7 Reduce T→T*F T symbols and 3 state
* 0 symbols
2 • Push T
Stack • Push goto(0,T)
T
0
 LR Parser
3. If action[Sm , ai ] = accept , Parsing successfully completed

4. If action[Sm , ai ] = error, Parser detected an error (an empty

entry in the action table) and calls an error recovery routine.
 LR Parsing Algorithm
• Input: An input string w and an LR parsing table with action and goto for grammar G
• Output: If w is in L(G), a bottom up parse for w, otherwise an error indication
• Method: Initially the parser has S0 on the stack where S0 is the initial state and w$ in the input buffer
set ip to point to the first symbol in w$
repeat forever begin
let ‘s’ be state on top of the stack and ‘a’ be symbol pointed to by ip
if action[s,a+ = shift s’ then begin
push a then s’ onto stack
advance ip to next input symbol
end
else if action[s,a] = reduce A   then begin
pop 2*|  | symbols off stack
let s’ be state now on top of stack
push A, then push goto[s’,A] onto stack
output production A  
end
else if action[s,a] = accept
return success
else
error()
end
 1) E  E+T
Moves of LR Parser on id*id+id 2) ET
3) T  T*F
Stack Input Action Output
4) TF
0 id*id+id$ shift 5 5) F  (E)
0id5 *id+id$ reduce by Fid Fid 6) F  id
0F3 *id+id$ reduce by TF TF state id + * ( ) $ E T F
0T2 *id+id$ shift 7 0 s5 s4 1 2 3
0T2*7 id+id$ shift 5 1 s6 acc

0T2*7id5 +id$ reduce by Fid Fid 2 r2 s7 r2 r2

3 r4 r4 r4 r4
0T2*7F10 +id$ reduce by TT*F TT*F
4 s5 s4 8 2 3
0T2 +id$ reduce by ET ET
5 r6 r6 r6 r6
0E1 +id$ shift 6 6 s5 s4 9 3
0E1+6 id$ shift 5 7 s5 s4 10
0E1+6id5 $ reduce by Fid Fid 8 s6 s11
9 r1 s7 r1 r1
0E1+6F3 $ reduce by TF TF
10 r3 r3 r3 r3
0E1+6T9 $ reduce by EE+T EE+T
11 r5 r5 r5 r5
0E1 $ accept
 LR Grammar
• A grammar for which we can construct an LR parsing table in which every
entry is uniquely defined is an LR grammar.
• For an LR grammar, the shift reduce parser should be able to recognize
handles when they appear on top of the stack.
• Each state symbol summarizes the information contained in the stack
below it.
• The LR parser can determine from the state on top of the 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 upto k input
symbols on each move is called an LR(k) grammar.
 Constructing SLR Parsing Tables – LR(0) Item
• LR parser using SLR parsing table is called an SLR parser.
• A grammar for which an SLR parser can be constructed is an SLR grammar.
• LR(0) item:
• An LR(0) item (item) of a grammar G is a production of G with a dot at the some
position on the right side.
• Eg: A  XYZ Possible LR(0) Items: A  .XYZ
(four different possibility) A  [Link]
A  XY.Z
A  XYZ.
• Sets of LR(0) items will be the states of action and goto table of the SLR parser.
• The production A   yields only one item A  .
 Constructing SLR Parsing Tables – LR(0) Item
• Canonical LR(0) collection:
• A collection of sets of LR(0) items
• Basis for constructing SLR parsers.
• To construct the canonical LR(0) collection for a grammar we define an augmented
grammar and two functions- closure and goto.
• Augmented Grammar:
• If G is grammar with start symbol S, then augmented grammar G’ is grammar G with
a new production rule S’S where S’ is the new starting symbol. i.e G U ,S’  S}
• The start state of G’ = S’
• This is done to signal to the parser when the parsing should stop parsing and
announce acceptance of input.
 Constructing SLR Parsing Tables – LR(0) Item
• Complete and Incomplete Items:
• An LR(0) item is complete if ‘.’ is the last symbol in RHS else it is incomplete.
• For every rule A α, α≠ , there is only one complete item A α., but as
many incomplete items as there are grammar symbols in the RHS.

Kernel and Non-Kernel items:

• An LR(0) item is a kernel item if the dot is not at the left end.
• S’.S is an exception and is considered to be a kernel item.
• Non-kernel items are the items which have the dot at leftmost end.
• Sets of items are formed by taking the closure of a set of kernel items.
 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. Initially, every LR(0) item in I is added to closure(I).

2. If A  .B is in closure(I) and B is a production rule of G; then
add B. to closure(I) if it is not already there.
We will apply this rule until no more new LR(0) items can be added to
closure(I).
 The Closure Operation

E’  E .
closure(,E’  E}) =
E  E+T .
{ E’  E {rule 1}
ET .
E  E+T
T  T*F .
E T
TF .
T  T*F
F  (E) .
T F
{rule 2}

F  id .
F  (E)
.
F  id }
 Computation of Closure
function closure ( I )
begin
J := I;
repeat
for each item A  .B in J and each production
B of G such that B. is not in J do
add B. to J
until no more items can be added to J
return J
End
 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).

I =, E’  E., E  E.+T}

goto(I,+) = closure(E  E+.T)= { E  E+.T

T .T*F
T .F
F .(E)
F .id }
 Example
I = {E’ .E goto (I, F) = {T  F. }
E  .E+T
E  .T goto(I, id) = { F  id. }
T  .T*F
T  .F
goto (I, ( ) = { F  (.E)
F  .(E)
F  .id } E  .E+T
E  .T
T  .T*F
goto (I, E) = , E’  E. T  .F
E  E.+T } F  .(E)
F  .id }
goto (I, T) = { E  T.
T  T.*F }
 Sets of Items Construction
Algorithm to construct C, the canonical collection of LR(0) items for the augmented
grammar G’
Procedure items( G’ )
begin
C:= {closure ({[S’.S]}) }
repeat
for each set of items 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
until no more sets of LR(0) items can be added to C.
End

• goto function is a DFA on the sets in C.

 Canonical Collection of LR(0) Items
I0: E’ .E I4: goto(I0, () I7: goto(I2, *)
E .E+T F (.E) goto(I6, F)=I3
•a T T*.F
E .T E .E+T F .(E) goto(I6,()=I4
T .T*F E .T F .id goto(I6, id)=I5
T .F T .T*F
F .(E) T .F I8: goto(I4, E) I10 :goto(I7, F)
F .id F .(E) F (E.) T T*F.
F .id E E.+T
I1: goto(I0, E) goto(I7,()=I4
E’ E. I5: goto(I0, id) goto(I4, T)=I2 goto(I7, id)=I5
E E.+T F id. goto(I4, F)=I3
goto(I4, ()=I4 I11 :goto(I8, ))
I2: goto(I0,T) I6: goto(I1, +)
F (E).
E T. E E+.T goto(I4, id)=I5
T T.*F T .T*F
T .F I9: goto(I6, T) goto(I8,+) = I6
I3: goto(I0, F) F .(E) E E+T. goto(I9,*) = I7
T F. F .id T T.*F
Transition Diagram (DFA) of Goto Function
E + T
I0 I1 I6 I9 * to I7
F
( to I3
T
id to I4
to I5
F * I7
I2 F
( I10
I id to I4
( 3
to I5
E I8
id id
I4 T
)

F
to I2 + I11
I5 to I3 to I6
(
to I4
 Constructing SLR Parsing Table
Input: An augmented grammar G’
Output: The SLR parsing functions action and goto for grammar G’
1. Construct the canonical collection of sets of LR(0) items for G’, C={I0,...,In}
2. State i is constructed from Ii . The parsing actions for state i are determined as follows:
• If [A.a] is in Ii and goto(Ii,a)=Ij , then action[i,a] is shift j. Here a should be a
terminal
• If [A.] is in Ii , then set action[i,a] to 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. The goto transitions for state I are constructed for all nonterminals A using the rule
If goto(Ii,A)=Ij then goto[i,A]=j
4. All entries not defined by (2) and (3) are errors.
5. Initial state of the parser is the one constructed from the sets of items containing *S’.S]
 Canonical Collection of LR(0) Items
I0: E’ .E I4: goto(I0, () I7: goto(I2, *)
E .E+T F (.E) goto(I6, F)=I3
•a T T*.F
E .T E .E+T F .(E) goto(I6,()=I4
T .T*F E .T F .id goto(I6, id)=I5
T .F T .T*F
F .(E) T .F I8: goto(I4, E) I10 :goto(I7, F)
F .id F .(E) F (E.) T T*F.
F .id E E.+T
I1: goto(I0, E) goto(I7,()=I4
E’ E. I5: goto(I0, id) goto(I4, T)=I2 goto(I7, id)=I5
E E.+T F id. goto(I4, F)=I3
goto(I4, ()=I4 I11 :goto(I8, ))
I2: goto(I0,T) I6: goto(I1, +)
F (E).
E T. E E+.T goto(I4, id)=I5
T T.*F T .T*F
T .F I9: goto(I6, T) goto(I8,+) = I6
I3: goto(I0, F) F .(E) E E+T. goto(I9,*) = I7
T F. F .id T T.*F
 1) E  E+T
2) ET
SLR Parsing Table 3)
4)
T  T*F
TF
FOLLOW(E)= {+,),$}
FOLLOW(T)= {*,+,),$}
Action Goto 5) F  (E) FOLLOW(F)= {*,+,),$}
6) F  id
state id + * ( ) $ E T F
0 s5 s4 1 2 3
goto(I0, E)= I1
1 s6 acc goto(I0,T)= I2 goto(I6, T)= I9
2 r2 s7 r2 r2 goto(I0, F)= I3 goto(I6, F)=I3
3 r4 r4 r4 r4 goto(I0, ()= I4 goto(I6,()=I4
4 s5 s4 8 2 3 goto(I0, id)= I5 goto(I6, id)=I5
goto(I1, +)= I6 goto(I7, F)= I10
5 r6 r6 r6 r6
goto(I2, *)= I7
6 s5 s4 9 3 goto(I7,()=I4
goto(I4, E)= I8
7 s5 s4 10 goto(I7, id)=I5
goto(I4, T)=I2
8 s6 s11
goto(I8, ))= I11
goto(I4, F)=I3
goto(I8,+) = I6
9 r1 s7 r1 r1 goto(I4, ()=I4
goto(I9,*) = I7
10 r3 r3 r3 r3 goto(I4, id)=I5
11 r5 r5 r5 r5
 SLR(1) Grammar

• An LR parser using SLR(1) parsing tables for a grammar G is called as the

SLR(1) parser for G.

• If a grammar G has an SLR(1) parsing table, it is called SLR(1) grammar (or

SLR grammar in short).

• Every SLR grammar is unambiguous, but every unambiguous grammar is not

a SLR grammar.
 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 that
grammar is not SLR grammar.
 SLR Parser-Example
• S→L=R
• S →R
• L→*R
• L →id
• R →L
 Conflict Example-1
I7: goto (I4, R)
S→L=R I5: goto (I0, id)
•S →R
. I1: goto (I0, S)
L →id.
L→*R.
S’ →S.
L→*R I8: goto (I4, L)
L →id I2: goto (I0, L) I6: goto (I2, =)
R →L.
R →L S→L.=R S→L=.R
R →L. R →.L
I9: goto (I6, R)
L→.*R
S→L=R.
I0: I3: goto (I0, R) L →.id
S’ →.S S →R. goto(I6, L) =I8
S→.L=R goto(I6, *) =I4
S →.R I4: goto (I0, *) goto(I4, *) =I4
goto(I6, id) =I5
L→.*R L→*.R goto(I4, *) d=I5
L →.id R →.L Action[2,=] = shift 6
R →.L L→.*R Action[2,=] = reduce by R  L
L →.id [ S L=R *R=R] so follow(R) contains, =
 Conflict Example2
S  AaAb I0: S’  .S
S  BbBa S  .AaAb
A S  .BbBa
B A.
B.

I0: A . I0: B .
FOLLOW(A)={a,b} FOLLOW(B)={a,b}
Problem: reduce/reduce
action(0,a)=reduce by A   action(0,a)=reduce by B  
conflict
action(0,b)=reduce by A   action(0,b)=reduce by B  
 Canonical LR(1) Parser
• Most general technique for constructing an LR parsing table.
• In SLR method, the state i makes a reduction by A
• if the set of items Ii contains the item [A.] and
• a is FOLLOW(A)

• In some situations, when state i appears on top of the stack and

the viable prefix  on the stack is such that
• A cannot be followed by the terminal a in a right-sentential form
• This means that making reduction in this case is not correct.
 LR(1) Item
• To avoid some of invalid reductions, the states need to carry more information.
• By splitting states when necessary, we can arrange to have each state of an LR parser
indicate exactly which input symbols can follow a handle  for which there is a
possible reduction to A
• Extra information is put into a state by including a terminal symbol as a second
component in an item.
• A LR(1) item is:
.
A   ,a where a is the look ahead of the LR(1) item (a is a terminal or the
right end marker, $)
• 1 refers to the length of the second component, the look ahead symbol
 LR(1) Item
• The lookahead has no effect in an item of the form [A  .,a], where  is
not .
• An item of the form [A  .,a] calls for a reduction by A   only if the
next input symbol is a.
• The set of such a’s will be a subset of FOLLOW(A), but it could be a proper
subset.
• A state will contain .
A   ,a1 where {a1,...,an}  FOLLOW(A)
...
.
A   ,an
.
• Can be written as A   , a1/a2/../an
 Construction of sets of LR(1) Items
function closure(I)
begin
repeat
for each item *A→α.Bβ,a] in I
each production B → γ in G’,
and each terminal b in FIRST(βa),
such that [B → .γ, b+ is not in I do
add [B → .γ, b+ to I
until no more items can be added to I
return I
end
 Construction of sets of LR(1) Items
function goto(I,X)
begin
let J be the sets of items ([A  X.,a])
such that ([A  .X,a]) is in I
return closure(J)
end

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

terminal), then goto(I,X) is defined as follows:
• If A  .X,a in I then every item in closure([A  X.,a]) will be in
goto(I,X).
 Construction of The Canonical LR(1) Collection
procedure items(G’)
begin
C is , closure(,*S’.S,$]}) }
repeat
for each set of items 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
until no more set of LR(1) items can be added to C.
end

• goto function is a DFA on the sets in C.

 Canonical LR(1) Collection- Example
S   CC, $
I0: closure([S’  S, $])
1. S’  S match with A  α.Bβ,a
A=S, α=ε, B=C, β= C, a=$
2. S  CC S’  S, $
FIRST(βa)=FIRST(C$)={c,d}
3. C  cC match with A  α.Bβ,a
4. C  d A=S’, α=ε, B=S, β= ε, a=$
Hence, add the items
FIRST(βa)=FIRST($)={$}
C  cC, c
C  cC, d
I 0: S’   S, $ Hence, add the item
C  d, c
S   CC, $ S   CC, $
C  d, d
C   cC, c/d to
C   d, c/d closure([ S’   S, $])
to
closure([ S’   S, $])
 S’  S
Canonical LR(1) Collection- Example S  CC
C  cC
C d
I0: S’  S, $
S  CC, $ I3: goto(I0, c) = I6: goto(I2, c) = goto(I3, c) = I3
C  cC, c/d C  cC, c/d C  cC, $
C  d, c/d C  cC, c/d C  cC, $ goto(I3, d) = I4
C  d, c/d C  d, $
I1: goto(I0, S)= I9: goto(I6, C) =
S’  S, $ I4: goto(I0, d) = I7: goto(I2, d) = C  cC, $
C  d, c/d C  d, $
I2: goto(I0, C) = goto(I6, c) = I6
S  CC, $ I5: goto(I2, C) = I8: goto(I3, C) =
C  cC, $ S  CC, $ C  cC, c/d goto(I6, d) = I7
C  d, $
 S’   S, $ S
S   C C, $
I1
(S’  S  , $
C   c C, c/d
C   d, c/d
I0 S  C  C, $ I5
C C
C   c C, $ S  C C , $
C   d, $
I2
c I6
c
C  c  C, $ C
C   c C, $
d C   d, $ I9
d C  cC , $
I7
c C  d , $

C  c  C, c/d C I8
c C   c C, c/d
C   d, c/d C  c C , c/d
I3
I4 d
d
C  d , c/d
 Construction of LR(1) Parsing Tables
Algorithm: Construction of Canonical LR Parsing Tables
Input: An augmented grammar G’
Output: The canonical LR parsing table functions, action and goto for grammar G’

1. Construct C’= {I0,...,In}, the canonical collection of sets of LR(1) items for G’.
2. State i of the parser is constructed from Ii. The parsing action for state i is determined as
follows
• If [A.a,b] in Ii and goto(Ii,a)=Ij then set action[i,a] to shift j. Here a should be a terminal
• If [A.,a] is in Ii and AS’, then set action*i,a] to reduce A
• If [S’S.,$] is in Ii , then action[i,$] to accept.

If any conflicting actions generated by these rules, the grammar is not LR(1).
3. The goto transitions for state i are constructed for all nonterminals A using the rule:
if goto(Ii,A)=Ij then goto[i,A]=j
4. All entries not defined by (2) and (3) are errors.
5. Initial state of the parser is the one constructed from the set of items containing *S’.S, $]
 S’  S
Canonical LR(1) Collection- Example 1. S  CC
2. C  cC
3. C  d
I0: S’   S, $
S   CC, $ I3: goto(I0, c) = I6: goto(I2, c) = goto(I3, c) = I3
C  cC, c/) C  cC, c/d C  cC, $
C  d, c/) C  cC, c/d C  cC, $ goto(I3, d) = I4
C  d, c/d C  d, $
I1: goto(I0, S)= I9: goto(I6, C) =
S’  S , $ I4: goto(I0, d) = I7: goto(I2, d) = C  cC, $
C  d, c/d C  d, $
I2: goto(I0, C) = goto(I6, c) = I6
S  CC, $ I5: goto(I2, C) = I8: goto(I3, C) =
C  cC, $ S  CC, $ C  cC, c/d goto(I6, d) = I7
C  d, $
Canonical LR(1) Parsing Table for Grammar G’
ACTION GOTO goto(I0,S)=I1
State c d $ S C goto(I0,C)=I2
0 s3 s4 1 2 goto(I0,c)=I3
1 acc
goto(I0,d)=I4
goto(I2,C)=I5
2 s6 s7 5
goto(I2,c)=I6
3 s3 s4 8
goto(I2,d)=I7
4 r3 r3
goto(I3,C)=I8
5 r1
goto(I3,c)=I3
6 s6 s7 9
goto(I3,d)=I4
7 r3 goto(I6,C)=I9
8 r2 r2 goto(I6,c)=I6
9 r2 goto(I6,d)=I7
 LALR Parsing Tables
1. LALR stands for Lookahead LR.
2. LALR parsers are often used in practice because LALR parsing tables
are smaller than LR(1) parsing tables.
3. The number of states in SLR and LALR parsing tables for a grammar
G are equal.
4. But LALR parsers recognize more grammars than SLR parsers.
5. yacc creates a LALR parser for the given grammar.
6. A state of LALR parser will be again a set of LR(1) items.
 The Core of LR(1) Items
• The core of a set of LR(1) Items is the set of their first components (i.e.,
LR(0) items)
• The core of the set of LR(1) items
{ C  cC, c/d,
C  cC, c/d,
C  d, c/d }

is { C  cC, C  cC, C  d }
 Creating LALR Parsing Tables
Canonical LR(1) Parser  LALR Parser
shrink # of states
• Look for LR(1) items having the same core, i.e. the first set of components
• Merge the sets with common core into one set of items
• Eg; I4 and I7 form such a pair with core {C→d.}
• I3 and I6 with core {C→c.C, C→.cC, C→.d}
• I8 and I9 with core {C→cC.}
• Replace I4 and I7 by I47, [I4 = C  d, c/d ; I7 = C  d, $]
• I47={C→d., c/d/$}
 Creation of LALR Parsing Tables
Algorithm: An easy but space consuming LALR parsing table construction
Input: An augmented grammar G’
Output: The LALR paring table functions action and goto for grammar G’
Method:
1. Construct C={I0,...,In}, the collection LR(1) items for the given grammar.
2. For each core present among the sets of LR(1) items, find all sets having that core and
replace these sets by their union.
3. Let C’=,J1,...,Jm} be the resulting set of LR(1) items. The parsing actions for state i are
constructed from Ji in the same manner as in the algorithm for canonical LR parser. If
there is a parsing action conflict, the algorithm fails to produce a parser and the
grammar is not LALR(1).
4. The goto table is constructed as follows: If J is the union of one or more sets of LR(1)
items, i.e. J=I1  ...  Ik, then the cores of goto(I1,X),...,goto(I2,X) are the same since
I1,...,Ik have same cores. Let K be the union of all sets of items of goto(I,X). Then
goto(I,X)=K.
 S’   S, $ I1
S   C C, $ S’  S  , $
C   c C, c/d S
C   d, c/d
I0 S  C  C, $ I5
C C
C   c C, $ S  C C , $
C   d, $
I2
c I6
c C  c  C, $
C   c C, $ C
d C   d, $ I9
d C  cC , $
I7
C  d , $
c c
C  c  C, c/d
C   c C, c/d C I8
C   d, c/d
C  cC , c/d
I3
d d
I4
C  d , c/d
 S’   S, $ I1
S   C C, $ S’  S  , $
C   c C, c/d S
C   d, c/d
I0 S  C  C, $ I5
C C
C   c C, $ S  C C , $
C   d, $
I2
c I6
c
C  c  C, $
C   c C, $
C
d C   d, $

I7 d
C  d , $
c c
C  c  C, c/d
C   c C, c/d C I89
C   d, c/d
C  c C , c/d/$
I3
d
d I4
C  d , c/d
 S’   S, $ I1
S   C C, $ S’  S  , $
C   c C, c/d S
C   d, c/d
I0 S  C  C, $ I5
C C   c C, $ C
S  C C , $
C   d, $
I2
c I6
c
d C  c  C, $
C   c C, $
C
d C   d, $

I47 d
C  d , c/d/$
c
c d
C  c  C, c/d I89
C   c C, c/d
C
C   d, c/d C  c C , c/d/$
I3
 S’   S, $ I1
S   C C, $ S’  S  , $
C   c C, c/d S
C   d, c/d
I0 S  C  C, $ I5
C C
C   c C, $ S  C C , $
C   d, $
I2
c I36
c C  c  C, c/d/$
C   c C,c/d/$ C
C   d,c/d/$
d
c
I47 d
C  d , c/d/$
d
I89
C  c C , c/d/$
 LALR Parsing Table
• ACTION
States action goto •
•
GOTO
State
• c
• d
• $
c d $ S C
• S
• C
• 0
• s3
0 s36 s47 1 2
• s4
• 1
• 2
• 1
1 acc • acc
• 2
• s6
• s7
• 5
2 s36 s47 5
• 3
• s3
• s4
• 8
36 s36 s47 89
• 4
• r3
• r3
• 5
47 r3 r3 r3 • r1
• 6
• s6
• s7
5 r1 • 9
• 7
• r3
• 8
• r2
89 r2 r2 r2 • r2
• 9
• r2
 Canonical LR(1) Parsing Table
LALR Parsing Table
ACTION GOTO
State action goto State c d $ S C
s 0 s3 s4 1 2
c d $ S C 1 acc
0 s36 s47 1 2 2 s6 s7 5
1 acc 3 s3 s4 8
2 s36 s47 5 4 r3 r3
36 s36 s47 89 5 r1
47 r3 r3 r3 6 s6 s7 9
5 r1 7 r3
89 r2 r2 r2 8 r2 r2
9 r2