Made Easy Test Series:Compiler Design-CLR parser

Question

$S\rightarrow aA|bAc|dc$

$A\rightarrow d$

Number of states in $CLR\left ( 1 \right )$ parser construction _______________

---

Is

$S\rightarrow d.c|$$

$A\rightarrow d.,a$

will be in $1$ state or in $2$ different states??

Comments

getting 11 states

---

There will be 11 states in the DFA

The 2 productions will be there in the different states and even in the LALR(1) they will not be merged together as their lookahead symbols are different

---

@Mk Utkarsh

$S\rightarrow d.c|$$

$A\rightarrow d.|a$

Cannot go to same state 

right??

As their lookaheads are different in CLR(1) 

---

@!KARAN

even in the LALR(1) they will not be merged together as their lookahead symbols are different

LALR(1) will merge different lookahead in 1 state 

---

How is it possible? States 6 and 8 can be merged together but production is $A \rightarrow d. , c \text{  and not } A \rightarrow d. , a $

---

yes, state 6 and 8 will merge.

I mean different lookahead will be merged.

Given ans $A\rightarrow d.,a$

let me chk

---

$S\rightarrow d.c,$dolor
$A\rightarrow d.,a$

I think they have done these two transition in 1 state because, A is followed by a and c both. and $A\rightarrow d.,a$ this state is useless state, so merge it will not create any extra state.

But actually $A\rightarrow d.,a$ , should not merge with $S\rightarrow d.c,dolor$, as their lookahead are different

One is a and another $

Am I right??

---

Ans given as 10 states

---

Ans cannot be 10 it will be 11 and yes the two will not be merged together

---

@Mk Utkarsh

in ur pic, state 3, follow will be $

I mean this 

$A\rightarrow .d,$$

It will not be follow by c 

right??

---

no it will be c 

What was in the follow of A?
c 

---

Can u plz chk the book of ullman??

---

srestha mam at 3rd state 

$A \rightarrow .d $ came because of 

$S \rightarrow b.Ac , \$$

so what next input can we expect if next input is d from this state? c

https://en.wikipedia.org/wiki/Canonical_LR_parser

please check example under Constructing LR(1) parsing tables

---

Chk the yellow box

As it is in same box of S, So follow set also chaged to $

Am I missing something??

---

Answer here might clear your confusion and btw can you send link of that PDF of ullman?

---

@Mk Utkarsh

chk this diagram https://www.geeksforgeeks.org/wp-content/uploads/gq/2017/02/parser_20.png

Here $I_{2}$ state changed to $

https://www.geeksforgeeks.org/parsing-set-3-slr-clr-and-lalr-parsers/

---

@Mk Utkarsh

geekforgeeks pic can u tell me difference of lookahead of $I_{2}$ and $I_{3}??$

both are for follow(A)

right??

but both have different lookahead

So, can we not tell, that they r following prev table lookahead??

---

both have different lookaheads $I_2$ and $I_3$, yes

So, can we not tell, that they r following prev table lookahead??

I'm not able to understand your doubt

---

Can u derive lookaheads of $I_{2}$ and $I_{3}??$

I mean how those came??

---

$I_0$

$S' \rightarrow .S , \$$
$S \rightarrow . A A, \$$
$A \rightarrow .aA, a/b$
$\ \ \ \ \ \ \ \ \ \  .b,a / b $  

 

We begin calculating closure of $S' \rightarrow .S$

How $\$$ is lookahead of $S \rightarrow . A A$?

$\epsilon \ \$$ is after S in prodcution $S' \rightarrow .S$  so what is first($)?

It is $\$$, which is lookahead of $S \rightarrow . A A, \$$

How are $a/b$ lookaheads of $A \rightarrow .aA, a/b$ and $A \rightarrow .b,a / b ?$

Productions of A came because of $S \rightarrow . A A, \$$ and what is after A? 
A$, So first of A = {a,b} Hence, we got lookaheads  a,b 

 

You have confusion in $I_2$ and $I_3$

$\text{Goto}(I_0,A) \rightarrow I_2$

$I_2$

$S \rightarrow A.A, \$$
$A \rightarrow .aA, \$$
$A \rightarrow .b, \$$

How $\$$ is looahead for $A \rightarrow .aA, \$$ and $A \rightarrow .b, \$$? 

A's production came because of $S \rightarrow A.A, \$$ and what is after A? 

$\$$ so First$(\$)$ = ${\$}$

Now coming to $I_3$

$\text{GOTO}(I_0,a) \rightarrow I_3$

$I_3$

$A \rightarrow a.A , a/b$
$\color{red}{A \rightarrow .aA , a/b}$
$\color{red}{A \rightarrow .b , a/b}$

Why $a/b$ are lookaheads of $\color{red}{A \rightarrow .aA , a/b}$ and $\color{red}{A \rightarrow .b , a/b}$?

Because these productions came from closure of $A \rightarrow a.A , a/b$ and what is right of A? $\epsilon a/ b$

---

ϵ $ is after S in prodcution S′→.S  so what is first($)?

Why  first($) is needed?? Is it not Follow(S)=$

---

Follow (S) = $ \$$

Because of this reason we got lookahead $\$$ in augmented production

Everything is explained on page 260 ullman 2nd edition

---

@Mk Utkarsh

Tell me one thing

which is lookahead of S→.AA,

Now to find lookahead of this production, we need Follow(S) or Follow(A)?? 

It will be Follow(S)

right??

---

srestha why this production came?

because of $S' \rightarrow .S , \$$

what is after S?  $ \$ $

$ is itself a terminal we don't need to calculate first of it. 

look ahead of S→.AA will be $\$$

---

We need to calculate closure for $S' \rightarrow .S ,\$$

according to the algo above,

For each production of S,

We have only one prod which is $S \rightarrow .AA$

For each terminal b,

what is this b? it is lookahead

where to find it? First $(\beta a)$

$\beta$ in our production is $\epsilon$ as there is no terminal or non-terminal after S and

what is a? it is $\$$

so we got $\$$ as look ahead and we will add $S \rightarrow .AA ,\$$ in our set

---

@Mk Utkarsh

check this algo more carefully

When we are taking

$A\rightarrow \alpha .B\beta ,a$

That means lookahead here is $a$ for the nonterminal $A.$

Now what is lookahead for $B?$

It will be $Follow(B)$$=\beta =First(\beta )=b$

So, lookahead of $B$ production will be $b$, i.e. $B\rightarrow .\gamma ,b$

Am I going right direction??

---

yes

---

Then check this production

$S\rightarrow .AA,Follow(S)$

lookahead will be  ${\color{Red}{Follow(S)}}$

---

yes
your confusion is cleared?

---

@Mk Utkarsh

ok Now??

Now check this $I_{2}$ case

Here though we have to take Follow(A) in production $A\rightarrow .aA,$, but lookahead id $

Tell me how??

---

While taking closure of $S \rightarrow A.\color{red}{A} , \$$

what is following $\color{red}{A}$? nothing but a $\$$

so that will be the lookahead

---

we don't need to find follow of A for lookaheads
we just need to check which terminal is following A because of which this production is created in this set
only $ is following A

---

ok, now check $I_{3}$

$A\rightarrow a.A,\left \{ lookahead1 \right \}$

$A\rightarrow .aA,\left \{ lookahead2 \right \}$

$A\rightarrow .b,\left \{ lookahead3 \right \}$

Now what will be $lookahead1??$

Here $A$ is following nothing

right??

---

We don't need to find lookahead1 as we have it already found that in $I_0$

However Lookahead2 and 3 are same as Lookahead1

Why?

Because both productions came because of $A \rightarrow a. \color{red}{A}, a/b$

And what is following $\color{red}{A} $

a/b

---

Another point comes from book

Follow set merge on lookaheads

right?

$A\rightarrow a.A,a|b$

Comes  Follow(A)=First(Aa|b)=a|b

Is not it??

Lookahead just merge First(Aa|b)

---

Check the 3rd for loop, $First(\beta a)$

Now if $\beta =\epsilon$

Then lookahead will be $a$, i.e. lookahead for $A\rightarrow \alpha B\beta$

---

 

Then lookahead will be a

both a and b 

---

yes,
merging is a shortcut for lookahead

right??

---

this line of ur is not correct

 

We don't need to find lookahead1 as we have it already found that in $I_{0}$

 However , I understood it

---

by merging you mean
$A \rightarrow a.A , a $ and $A \rightarrow a.A ,  b$

can be writen as

$A \rightarrow a.A , a | b$ ?

---

srestha that line is correct coz that production is not added in that state 

and it was added in $I_0$

---

No

suppose for $A \rightarrow a.A , b $

here lookahead just merged with prev. grammar, when A has no terminal after it.

I mean this  $A \rightarrow a.A , b $ in next level becomes

$A \rightarrow a.Ab $

And Next we got look ahead for A will be $\left \{ b \right \}$

---

Check the 3rd for loop of the algo, u will get it

---

your basics are not clear

lookaheads don't merge

You should read from page 260

---

 that line is correct coz that production is not added in that state

 @Mk Utkarsh

yes, because it shouldnot add that state

Check the rule

lookahead1 is lookahead to that $A$ in red color ${\color{Red} A}\rightarrow a.A,a|b$

And that $A$ comes from prev. state

And in prev state 

we got $A\rightarrow .aA$ which again has no follow set

So, go to prev production again, i.e. $S\rightarrow .AA$

And from here we got value of $Follow\left ( A \right )=\left \{ a,b \right \}$

Ok??

---

your basics are not clear
 

I just looking for a shortcut : |

check the 3rd for loop

for(each terminal $b$ in $first\left ( \beta a \right )$) 

What is $a$ here??