0 votes
204 views

$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?? | 204 views +1 getting 11 states 0 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 0 @Mk Utkarsh S\rightarrow d.c|$$$A\rightarrow d.|a$Cannot go to same state right?? As their lookaheads are different in CLR(1) 0 @!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 0 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 $0 yes, state 6 and 8 will merge. I mean different lookahead will be merged. Given ans$A\rightarrow d.,a$let me chk 0$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??
0
Ans given as 10 states
0
Ans cannot be 10 it will be 11 and yes the two will not be merged together
0

@Mk Utkarsh

in ur pic, state 3, follow will be $I mean this$A\rightarrow .d,$$It will not be follow by c right?? 0 no it will be c What was in the follow of A? 0 Can u plz chk the book of ullman?? 0 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

0 Chk the yellow box

As it is in same box of S, So follow set also chaged to $Am I missing something?? 0 Answer here might clear your confusion and btw can you send link of that PDF of ullman? 0 @Mk Utkarsh chk this diagram Here$I_{2}$state changed to$

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

0

@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??

0

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

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

I mean how those came??
0

$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 0 ϵ is after S in prodcution S′→.S so what is first()? Why first() is needed?? Is it not Follow(S)= 0 Follow (S) = \$$ Because of this reason we got lookahead$\$$in augmented production Everything is explained on page 260 ullman 2nd edition 0 @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?? 0 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 $\$$0 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 0 @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??

0
yes
0

Then check this production

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

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

0
yes
your confusion is cleared?
0

@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?? +1 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
+1
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 0 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?? 0 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 0 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) 0 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$0 Then lookahead will be a both a and b 0 yes, merging is a shortcut for lookahead right?? 0 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 0 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$? 0 that line is correct coz that production is not added in that state and it was added in$I_0$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 0 your basics are not clear lookaheads don't merge You should read from page 260 0 that line is correct coz that production is not added in that state 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?? 0 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??

0 votes
3 answers
3
0 votes
0 answers
5