SLR Parser (with Examples)

 Difficulty Level : Medium

 Last Updated : 03 Aug, 2021
Prerequisite : LR Parser
LR parsers :
It is an efficient bottom up syntax analysis technique that can be used to parse a large
classes of  context free grammar  is called LR(0) parsing. 
L stands for left to right scanning
R stands for rightmost  derivation in reverse
0 stands for no. of input symbols of lookahead
 
Advantages of LR parsing :
 It recognises virtually  all programming language constructs for which CFG
can be written
 It is able to detect syntatic errors
 It is an efficient non-backtracking shift reducing parsing method.
Types of LR parsing methods :
1. SLR
2. CLR
3. LALR
SLR Parser :
SLR is simple LR.It is the smallest class of grammar having few number of states.
SLR is very easy to construct and is similar to LR parsing. The only difference
between SLR parser and LR(0) parser is that in LR(0) parsing table , theres a chance
of ‘shift reduced’ conflict because we are entering ‘reduce’ corresponding to all
terminal states.We can solve this problem by entering ‘reduce’ corresponding to
FOLLOW of LHS of production in the terminating state.This is called SLR(1)
collection of items
Steps for constructing the SLR parsing table :
1. Writing augmented grammar
2. LR(0) collection of items to be found
3. Find FOLLOW of LHS of production
4. Defining 2 functions:goto[list of terminals] and action[list of non-terminals]
in the parsing table
EXAMPLE – Construct LR parsing table for the given context free grammar
 S–>AA   
 A–>aA|b
Solution:
STEP1 – Find augmented grammar
The augmented grammar of the given grammar is:-
 S’–>.S    [0th production]    
 S–>.AA  [1st production]     
 A–>.aA [2nd production]      
 A–>.b  [3rd production]
STEP2 – Find LR(0) collection of items
Below is the figure showing the LR(0) collection of items. We will understand
everything one by one.

The terminals of this grammar are {a,b}.

The non-terminals of this grammar are {S,A}
RULE – 
If any non-terminal has ‘ . ‘ preceding it, we have to write all its production and add ‘ .
‘ preceding each of its production.
RULE – 
from each state to the next state, the ‘ . ‘ shifts to one place to the right.
 In the figure, I0 consists of augmented grammar.
 Io goes to I1 when  ‘ . ‘ of 0th production is shifted towards the right of
S(S’->S.). this state is the accept state . S is seen by the compiler.
 Io goes to I2 when  ‘ . ‘ of 1st production is shifted towards right (S->A.A) .
A is seen by the compiler
 I0 goes to I3 when  ‘ . ‘ of the 2nd production is shifted towards right (A-
>a.A) . a is seen by the compiler.
 I0 goes to I4 when  ‘ . ‘ of the 3rd production is shifted towards right (A-
>b.) . b is seen by the compiler.
  I2 goes to I5 when  ‘ . ‘ of 1st production is shifted towards right (S->AA.) .
A is seen by the compiler
 I2 goes to I4 when  ‘ . ‘ of 3rd production is shifted towards right (A->b.) .
b is seen by the compiler.
 I2 goes to I3 when  ‘ . ‘ of the 2nd production is shifted towards right (A-
>a.A) . a is seen by the compiler.
 I3 goes to I4 when  ‘ . ‘ of the 3rd production is shifted towards right (A-
>b.) . b is seen by the compiler.
 I3 goes to I6 when  ‘ . ‘ of 2nd production is shifted towards the right (A-
>aA.) . A is seen by the compiler
 I3 goes to I3 when  ‘ . ‘ of the 2nd production is shifted towards right (A-
>a.A) . a is seen by the compiler.
STEP3 – 
Find FOLLOW of LHS of production
FOLLOW(S)=$
FOLLOW(A)=a,b,$
To find FOLLOW of non-terminals, please read follow set in syntax analysis.
STEP 4- 
Defining 2 functions:goto[list of terminals] and action[list of non-terminals] in the
parsing table.Below is the SLR parsing table.

 $ is by default a non terminal which takes accepting state.

 0,1,2,3,4,5,6 denotes I0,I1,I2,I3,I4,I5,I6
 I0 gives A in I2, so 2 is added to the A column and 0 row.
 I0 gives S in I1,so 1 is added to the S column and 1 row.
 similarly  5 is written in  A column and 2 row, 6 is written in A column and
3 row.
 I0 gives a in I3 .so S3(shift 3) is added to a column and 0 row.
 I0 gives b in I4 .so S4(shift 4) is added to the b column and 0 row.
 Similarly, S3(shift 3) is added on a column and 2,3 row ,S4(shift 4) is added
on b column and 2,3 rows.
 I4 is reduced state as ‘ . ‘ is at the end. I4 is the 3rd production of
grammar(A–>.b).LHS of this production is A. FOLLOW(A)=a,b,$  . write
r3(reduced 3) in the columns of a,b,$ and 4th row
  I5 is reduced state as ‘ . ‘ is at the end. I5 is the 1st production of
grammar(S–>.AA). LHS of this production is S.
FOLLOW(S)=$  . write r1(reduced 1) in the column of $ and 5th row
 I6 is reduced state as ‘ . ‘ is at the end. I6 is the 2nd production of grammar(
A–>.aA). The LHS of this production is A.
FOLLOW(A)=a,b,$  . write r2(reduced 2) in the columns of a,b,$ and 6th
row
LALR Parser (with Examples)

LALR Parser :
LALR Parser is lookahead LR parser. It is  the most powerful parser which can handle large classes of
grammar. The size of CLR parsing table is quite large as compared to other parsing table. LALR
reduces the size of this table.LALR works similar to CLR. The only difference is , it combines the
similar states of CLR parsing table  into one single state. 
The general syntax becomes  [A->∝.B, a ]
where A->∝.B is production and a is a terminal or right end marker $
LR(1) items=LR(0) items + look ahead

How to add lookahead with the production?

CASE 1 –

A->∝.BC, a

Suppose this is the 0th production.Now, since ‘ . ‘ precedes B,so we have to write B’s productions as
well.

B->.D [1st production]

Suppose this is B’s production. The look ahead of this production is given as- we look at previous
production i.e. – 0th production. Whatever is after B, we find FIRST(of that value) , that is the
lookahead of 1st production. So, here in 0th production, after B, C is there. Assume FIRST(C)=d, then
1st production become.

B->.D, d

CASE 2  –
Now if the 0th production was like this,

A->∝.B, a

Here,we can see there’s nothing after B. So the lookahead of 0th production will be the lookahead of
1st production. ie-

B->.D, a

CASE 3 –
Assume a production A->a|b

A->a,$ [0th production]

A->b,$ [1st production]

Here, the 1st production is a part of the previous production, so the lookahead will be the same as
that of its previous production.
Steps for constructing the LALR parsing table :

1. Writing augmented grammar

2. LR(1) collection of items to be found

3. Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in the LALR

parsing table

EXAMPLE
Construct CLR parsing table for the given context free grammar

S-->AA

A-->aA|b

Solution:

STEP1- Find augmented grammar

The augmented grammar of the given grammar is:-

S'-->.S ,$ [0th production]

S-->.AA ,$ [1st production]

A-->.aA ,a|b [2nd production]

A-->.b ,a|b [3rd production]

Let’s apply the rule of lookahead to the above productions.

 The initial look ahead is always $

 Now,the 1st production came into existence because of ‘ . ‘ before ‘S’ in 0th
production.There is nothing after ‘S’, so the lookahead of 0th production will be the
lookahead of 1st production. i.e. :  S–>.AA ,$

 Now,the 2nd production came into existence because of ‘ . ‘ before ‘A’ in the 1st production.
After ‘A’, there’s  ‘A’. So, FIRST(A) is a,b. Therefore, the lookahead of the 2nd production
becomes a|b.

 Now,the 3rd production is a part of the 2nd production.So, the look ahead will be the same.

STEP2 – Find LR(0) collection of items

Below is the figure showing the LR(0) collection of items. We will understand everything one by one.
The terminals of this grammar are {a,b}
The non-terminals of this grammar are {S,A}

RULES –

1. If any non-terminal has ‘ . ‘ preceding it, we have to write all its production and add ‘ . ‘
preceding each of its production.

2. from each state to the next state, the ‘ . ‘ shifts to one place to the right.

 In the figure, I0 consists of augmented grammar.

 Io goes to I1 when  ‘ . ‘ of 0th production is shifted towards the right of S(S’->S.). This state is
the accept state . S is seen by the compiler. Since I1 is a part of the 0th production, the
lookahead is same i.e. $

 Io goes to I2 when  ‘ . ‘ of 1st production is shifted towards right (S->A.A) . A is seen by the
compiler. Since I2 is a part of the 1st production, the lookahead is  same i.e. $.

 I0 goes to I3 when  ‘ . ‘ of 2nd production is shifted towards the right (A->a.A) . a is seen by
the compiler.since I3 is a part of 2nd production, the lookahead is same i.e. a|b.

 I0 goes to I4 when  ‘ . ‘ of 3rd production is shifted towards right (A->b.) . b is seen by the
compiler. Since I4 is a part of 3rd production, the lookahead is same i.e. a|b.

 I2 goes to I5 when  ‘ . ‘ of 1st production is shifted towards right (S->AA.) . A is seen by the
compiler. Since I5 is a part of the 1st production, the lookahead is same i.e. $.

 I2 goes to I6 when  ‘ . ‘ of 2nd production is shifted towards the right (A->a.A) . A is seen by
the compiler. Since I6 is a part of the 2nd production, the lookahead is same i.e. $.

 I2 goes to I7 when  ‘ . ‘ of 3rd production is shifted towards right (A->b.) . A is seen by the
compiler. Since I6 is a part of the 3rd production, the lookahead is same i.e. $.
  I3 goes to I3 when  ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is seen by
the compiler. Since I3 is a part of the 2nd production, the lookahead is same i.e. a|b.

 I3 goes to I8 when  ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is seen by
the compiler. Since I8 is a part of the 2nd production, the lookahead is same i.e. a|b.

 I6 goes to I9 when  ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is seen by
the compiler. Since I9 is a part of the 2nd production, the lookahead is same i.e. $.

 I6 goes to I6 when  ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is seen by
the compiler. Since I6 is a part of the 2nd production, the lookahead is same i.e. $.

 I6 goes to I7 when  ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is seen by the
compiler. Since I6 is a part of the 3rd production, the lookahead is same i.e. $.

STEP 3 –
Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in the parsing
table.Below is the CLR parsing table

Once we make a CLR parsing table, we can easily make a LALR parsing table from it.

In the step2 diagram, we can see that 

 I3 and I6 are similar except their lookaheads.

 I4 and I7 are similar except their lookaheads.

 I8 and I9 are similar except their lookaheads.

In LALR parsing table construction , we merge these similar states. 

 Wherever there is 3 or 6, make it  36(combined form)

 Wherever there is 4 or 7, make it  47(combined form)

 Wherever there is 8 or 9, make it  89(combined form)

Below is the LALR parsing table. 

Now we have to remove the unwanted rows

 As we can see, 36 row has same data twice, so we delete 1 row.

 We combine two 47 row into one by combining each value in the single 47 row.

 We combine two 89 row into one by combining each value in the single 89 row.

The final LALR table looks like the below.

SLR Parser
SLR represents "Simple LR Parser". It is very easy and cost-effective to execute.
The SLR parsing action and goto function from the deterministic finite automata that
recognizes viable prefixes. It will not make specificially defined parsing action tables
for all grammars but does succeed on several grammars for programming
languages. Given a grammar G. It augment G to make G’, and from G’ it can
construct C, the canonical collection of a set of items for G’. It can construct ACTION
the parsing action function, and GOTO, the goto function, from C using the following
simple LR Parsing table construction technique. It needed us to understand
FOLLOW (A) for each non-terminal A of a grammar.
CLR Parser
CLR refers to canonical lookahead. CLR parsing uses the canonical collection of LR
(1) items to construct the CLR (1) parsing table. CLR (1) parsing table make more
number of states as compared to the SLR (1) parsing. In the CLR (1), it can locate
the reduce node only in the lookahead symbols.

LALR Parser
LALR Parser is Look Ahead LR Parser. It is intermediate in power between SLR and
CLR parser. It is the compaction of CLR Parser, and hence tables obtained in this
will be smaller than CLR Parsing Table.
For constructing the LALR (1) parsing table, the canonical collection of LR (1) items
is used. In the LALR (1) parsing, the LR (1) items with the equal productions but
have several look ahead are grouped to form an individual set of items. It is
frequently the similar as CLR (1) parsing except for the one difference that is the
parsing table.
The overall structure of all these LR Parsers is the same. There are some common
factors such as size, class of context-free grammar, which they support, and cost in
terms of time and space in which they differ.
Let us see the comparison between SLR, CLR, and LALR Parser.

SLR Parser LALR Parser CLR Parser

It is very easy and cheap to It is also easy and cheap to It is expensive

implement. implement. and difficult to
implement.

SLR Parser is the smallest in LALR and SLR have the same size. CLR Parser is
size. As they have less number of states. the largest. As
the number of
states is very
large.

Error detection is not immediate Error detection is not immediate in Error detection
in SLR. LALR. can be done
immediately in
CLR Parser.

SLR fails to produce a parsing It is intermediate in power between It is very

table for a certain class of SLR and CLR i.e., SLR ≤ LALR ≤ powerful and
grammars. CLR. works on a
large class of
grammar.
 SLR Parser LALR Parser CLR Parser

It requires less time and space It requires more time and space It also requires
complexity. complexity. more time and
space
complexity.

CLR Parser :
The CLR parser stands for canonical LR parser.It is a more powerful LR parser.It makes use of
lookahead symbols. This method uses a large set of items called LR(1) items.The main difference
between LR(0)  and LR(1) items is that,in LR(1) items ,its possible to carry more information in a
state,which will rule out useless reduction states.This extra information is incorporated into the
state by the lookahead symbol. The general syntax becomes  [A->∝.B, a ]
where A->∝.B is production and a is a terminal or right end marker $
LR(1) items=LR(0) items + look ahead

How to add lookahead with the production?

CASE 1 –

A->∝.BC, a

Suppose this is the 0th production.Now, since ‘ . ‘ precedes B,so we have to write B’s productions as
well.

B->.D [1st production]

Suppose this is B’s production. The look ahead of this production is given as we look at previous
productions ie 0th production. Whatever is after B, we find FIRST(of that value) , that is the
lookahead of 1st production.So,here in 0th production, after B, C is there. assume FIRST(C)=d, then
1st production become

B->.D, d

CASE 2 –
Now if the 0th production was like this,

A->∝.B, a

Here, we can see there’s nothing after B. So the lookahead of 0th production will be the lookahead
of 1st production. ie-

B->.D, a

CASE 3 –
Assume a production A->a|b

A->a,$ [0th production]

A->b,$ [1st production]

Here, the 1st production is a part of the previous production, so the lookahead will be the same as
that of its previous production.
These are the 2 rules of look ahead.

Steps for constructing CLR parsing table :

1. Writing augmented grammar

2. LR(1) collection of items to be found

3. Defining 2 functions:goto[list of terminals] and action[list of non-terminals] in the CLR

parsing table

EXAMPLE 
Construct a CLR parsing table for the given context free grammar

S-->AA

A-->aA|b

Solution :
STEP 1 – Find augmented grammar

The augmented grammar of the given grammar is:-

S'-->.S ,$ [0th production]

S-->.AA ,$ [1st production]

A-->.aA ,a|b [2nd production]

A-->.b ,a|b [3rd production]

Let’s apply the rule of lookahead to the above productions

 The initial look ahead is always $

 Now, the 1st production came into existence because of ‘ . ‘ Before ‘S’ in 0th
production.There is nothing after ‘S’, so the lookahead of 0th production will be the
lookahead of 1st production. ie:  S–>.AA ,$

 Now, the 2nd production came into existence because of ‘ . ‘ Before ‘A’ in the 1st
production.After ‘A’, there’s  ‘A’. So, FIRST(A) is a,b
Therefore,the look ahead for the 2nd production becomes a|b.

 Now, the 3rd production is a part of the 2nd production.So, the look ahead will be the same.

STEP 2 – Find LR(0) collection of items

Below is the figure showing the LR(0) collection of items. We will understand everything one by one.
The terminals of this grammar are {a,b}
The non-terminals of this grammar are {S,A}

RULE-

1. If any non-terminal has ‘ . ‘ preceding it, we have to write all its production and add ‘ . ‘
preceding each of its production.

2. from each state to the next state, the ‘ . ‘ shifts to one place to the right.

3. All the rules of lookahead apply here.

 In the figure, I0 consists of augmented grammar.

 Io goes to I1 when  ‘ . ‘ of 0th production is shifted towards the right of S(S’->S.). This state is
the accept state . S is seen by the compiler. Since I1 is a part of the 0th production, the
lookahead is the same ie $

 Io goes to I2 when  ‘ . ‘ of 1st production is shifted towards right (S->A.A) . A is seen by the
compiler. Since I2 is a part of the 1st production, the lookahead is the same i.e. $.

 I0 goes to I3 when  ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is seen by
the compiler. Since I3 is a part of the 2nd production, the lookahead is the same ie a|b.

 I0 goes to I4 when  ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is seen by the
compiler. Since I4 is a part of the 3rd production, the lookahead is the same i.e. a | b.

 I2 goes to I5 when  ‘ . ‘ of 1st production is shifted towards right (S->AA.) . A is seen by the
compiler. Since I5 is a part of the 1st production, the lookahead is the same i.e. $.
  I2 goes to I6 when  ‘ . ‘ of 2nd production is shifted towards the right (A->a.A) . A is seen by
the compiler. Since I6 is a part of the 2nd production, the lookahead is the same i.e. $.

 I2 goes to I7 when  ‘ . ‘ of 3rd production is shifted towards right (A->b.) . A is seen by the
compiler. Since I6 is a part of the 3rd production, the lookahead is the same i.e. $.

 I3 goes to I3 when  ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is seen by
the compiler. Since I3 is a part of the 2nd production, the lookahead is the same i.e. a|b.

 I3 goes to I8 when  ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is seen by
the compiler. Since I8 is a part of the 2nd production, the lookahead is the same i.e. a|b.

 I6 goes to I9 when  ‘ . ‘ of 2nd production is shifted towards the right (A->aA.) . A is seen by
the compiler. Since I9 is a part of the 2nd production, the lookahead is the same i.e. $.

 I6 goes to I6 when  ‘ . ‘ of the 2nd production is shifted towards right (A->a.A) . a is seen by
the compiler. Since I6 is a part of the 2nd production, the lookahead is the same i.e. $.

 I6 goes to I7 when  ‘ . ‘ of the 3rd production is shifted towards right (A->b.) . b is seen by the
compiler. Since I6 is a part of the 3rd production, the lookahead is the same ie $.

STEP 3-  defining 2 functions:goto[list of terminals] and action[list of non-terminals] in the parsing

table.Below is the CLR parsing table

 $ is by default a non terminal which takes accepting state.

 0,1,2,3,4,5,6,7,8,9 denotes I0,I1,I2,I3,I4,I5,I6,I7,I8,I9

 I0 gives A in I2, so 2 is added to the A column and 0 row.

 I0 gives S in I1,so 1 is added to the S column and 1st row.

 similarly  5 is written in  A column and 2nd  row, 8 is written in A column and 3rd row, 9 is
written in A column and 6th row.

 I0 gives a in I3, so S3(shift 3) is added to a column and 0 row.

 I0 gives b in I4, so S4(shift 4) is added to the b column and 0 row.

  Similarly, S6(shift 6) is added on ‘a’ column and 2,6 row ,S7(shift 7) is added on b column and
2,6 row,S3(shift 3) is added on ‘a’ column and 3 row ,S4(shift 4) is added on b column and 3
row.

 I4 is reduced as ‘ . ‘ is at the end. I4 is the 3rd production of grammar. So write r3(reduce 3)

in lookahead columns. The lookahead of I4 are a and b, so write R3 in a and b column.

 I5 is reduced as ‘ . ‘ is at the end. I5 is the 1st production of grammar. So write r1(reduce 1)

in lookahead columns. The lookahead of I5 is $ so write R1 in $ column.

 Similarly, write R2 in a,b column and 8th row, write R2 in $ column and 9th row.

Exercise

Consider the grammar E -> T+E | T

T ->id
Augmented grammar - E’ -> E
E -> T+E | T
T -> id