• edited by
2,070 views
2 2 votes
What is the difference between $SLR(1)$ and $LALR(1)$ parser ? Both parser have same parsing table then how $SLR$ is subset of $LALR$ ?

2 Answers

9 9 votes

Who Said that Both have same Parsing table for every Grammar?

They do not. 

Let me explain LR(0), SLR(1),CLR(1), LALR(1) with a Simple scenario : 

Have you watched "Luck" movie of "Sanjay Dutt" ?? If you have then remember the Very first Stunt/Scene where Few people (Including Sanjay dutt) try to cross 4-5 Railway Tracks with their Eyes covered by black strip (i.e. They cross Railway tracks in Blind manner)..Everyone else dies but Sanjay Dutt Survives and successfully crosses the road. Here, Sanjay dutt is $LR(0)$ Grammar. Because the strategy that He applied while crossing the road was dull, Non-intelligent, but Yet He successfully crossed the road and everyone else died.

So, Now the Scenario is that $A,B,C,D,E$ are crossing the 5 Parallel Roads. 

$A$ crosses each road blindly without seeing left or right. Here, This method of Crossing all the roads blindly (Without seeing left or right) is $LR(0)$ Parsing table construction algorithm and $A$, If successfully crosses the road then $A$ is $LR(0)$ Grammar. And If $A$ dies anywhere (on any road) then $A$ is not $LR(0)$ Grammar. Sanjay Dutt in above paragraph  is $LR(0)$ Grammar since He crosses blindly but Yet Successfully.

Now, It's time for $B$ to cross the roads.

$B$ crosses all the roads blindly just like $A$ did, except the Last road. Before crossing the last road, He sees Left and right and then He crosses the 5th Road.  Here, This method of Crossing all the  roads blindly (Without seeing left or right), except the last road,  is $SLR(1)$ Parsing table construction algorithm and $B$, If successfully crosses the road then $B$ is $SLR(1)$ Grammar. And If $B$ dies anywhere (on any road) then $B$ is not $SLR(1)$ Grammar.

Now, It's time for $C$ to cross the roads. $C$ here is Our CLR(1) Grammar. 

$C$ is intelligent than $A,B$. $C$ crosses Each road carefully by seeing left and right. So, the probability/chances that $C$ will cross all the roads successfully is Higher than that of $A,B$.  This method of Crossing all the  roads carefully (by seeing left or right for each road)  is $LR(1)$ Parsing table construction algorithm and $C$, If successfully crosses the road then $C$ is $LR(1)$ Grammar. And If $C$ dies anywhere (on any road)(Being Intelligent doesn't mean He can't die...it's just that the chances are higher that He will successfully cross the roads than that of $A,B$) then $B$ is not $LR(1)$ Grammar.

Now what happened that Every person in this city heard of $C$. They got to know about the way $C$ crossed the roads. And They were happy to know this strategy of crossing the roads. So, What they did was that They taught their kids about $C$'s method of crossing the roads for their safety. In this city, just like every other parent, $Bankelal$ also taught his children $D \,\, and \,\,E$ about this method. But He did a mistake. He told them to cross the roads by Holding hands together.

Then on one Sunny day.. $D,E$'s were crossing the roads. They had $C$'s approach in mind that They should see left and right before crossing the roads...But they Held(merged) their hands and tried to cross the roads together. This was not a good idea because their thoughts of crossing the roads were not synchronized as you see/experience sometimes in daily life while crossing a busy road with your friends..  Just like that $D,E$ were having different timing and thoughts of crossing the road...When $D$ used to think that they should cross the road, $E$ used to think that they should let one more incoming vehicle pass and then should cross the road. So, This method of Crossing all the  roads carefully (by seeing left or right for each road) But with Holding(Merging) Hands with someone,  is $LALR(1)$ Parsing table construction algorithm and here $Bankelal$ is $LALR(1)$ Grammar and $D,E$ are states that were merged here.. Of course, Even this strategy of Holding hands and then carefully crossing the roads is better than Blindly crossing the roads like $A,B$ But It is Not better than $C$'s way of solely crossing the roads carefully...


Now let's derive the Facts about $LR(0), SLR(1), LALR(1),CLR(1)$ Parsing Tables from above Story.

1. Seeing left Or right before crossing the roads in the above Story resembles to the Look-ahead.

2. The chances of successfully crossing the roads  resembles to the chances of Parsing a Grammar. 

i.e. chances of successfully crossing the roads  = $A < B < (Bankelal,D,E) < C$

Chances/Probability of Parsing a Grammar : $LR(0) < SLR(1) < LALR(1) < CLR(1)$

3. The Better(Powerful) the Strategy of Crossing the roads, The Powerful(Better) the Parser.

4. Except the last road in case of $B$ resembles to the Finding Follow of a variable for marking reduce entries in the Parsing table of SLR(1) Parser.

5. Holding the Hands resembles to the Merging of States in LALR(1) parsers after applying LR(1) algorithm.

6. Sanjay Dutt is $LR(0)$ Grammar.

• edited by
1 1 vote
  • SLR and LALR both parser have diffrent parsing table.

  • LALR is more power full compare  to SLR.

  • If a grammar is SLR  then it is also LALR. BECZ it is more power full . 

  • But a grammar is LALR then it may or may not be SLR.

  • Look at the diagram SLR IS subset of LALR.

Position:
Show:

Related questions

2 2 votes
6 6 answers
14.3k
14.3k views
prasitamukherjee asked Jul 16, 2015
14,270 views
I know the parsing logic of bottom up parsers, that they start from the terminal and reduce it to the start symbol. But what really confuses me is the construction of LR(...
0 0 votes
1 1 answer
679
679 views
aditi19 asked Jul 6, 2018
679 views
Does bottom up parsers give postfix expression?
0 0 votes
2 2 answers
1.3k
1.3k views
prasitamukherjee asked Jul 16, 2015
1,285 views
q. 23 : can anyone explain why both statements are false? I thought option B is correct?
0 0 votes
1 1 answer
1.2k
1.2k views
Souvik33 asked Dec 11, 2022
1,173 views
Consider the following statements regarding the “Parsing Table” of a shift reduce parser, for any given grammarNo. of states/ size of parse table is same for all Shift-Re...