2 votes 2 votes $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?? Compiler Design compiler-design made-easy-test-series + – srestha asked May 15, 2019 srestha 2.0k views answer comment Share Follow See all 45 Comments See all 45 45 Comments reply Mk Utkarsh commented May 15, 2019 reply Follow Share getting 11 states 1 votes 1 votes !KARAN commented May 15, 2019 reply Follow Share 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 votes 0 votes srestha commented May 15, 2019 reply Follow Share @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 votes 0 votes srestha commented May 15, 2019 i edited by srestha May 15, 2019 reply Follow Share @!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 votes 0 votes !KARAN commented May 15, 2019 reply Follow Share 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 votes 0 votes srestha commented May 15, 2019 reply Follow Share yes, state 6 and 8 will merge. I mean different lookahead will be merged. Given ans $A\rightarrow d.,a$ let me chk 0 votes 0 votes srestha commented May 15, 2019 i edited by srestha May 15, 2019 reply Follow Share $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 votes 0 votes srestha commented May 15, 2019 reply Follow Share Ans given as 10 states 0 votes 0 votes !KARAN commented May 15, 2019 reply Follow Share Ans cannot be 10 it will be 11 and yes the two will not be merged together 0 votes 0 votes srestha commented May 16, 2019 reply Follow Share @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 votes 0 votes Mk Utkarsh commented May 16, 2019 reply Follow Share no it will be c What was in the follow of A? c 0 votes 0 votes srestha commented May 16, 2019 reply Follow Share Can u plz chk the book of ullman?? 0 votes 0 votes Mk Utkarsh commented May 16, 2019 reply Follow Share 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 0 votes 0 votes srestha commented May 16, 2019 reply Follow Share Chk the yellow box As it is in same box of S, So follow set also chaged to $ Am I missing something?? 0 votes 0 votes Mk Utkarsh commented May 16, 2019 reply Follow Share Answer here might clear your confusion and btw can you send link of that PDF of ullman? 0 votes 0 votes srestha commented May 16, 2019 reply Follow Share @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/ 0 votes 0 votes srestha commented May 16, 2019 reply Follow Share @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 votes 0 votes Mk Utkarsh commented May 16, 2019 reply Follow Share 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 votes 0 votes srestha commented May 16, 2019 reply Follow Share Can u derive lookaheads of $I_{2}$ and $I_{3}??$ I mean how those came?? 0 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share $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 votes 0 votes srestha commented May 17, 2019 reply Follow Share ϵ $ is after S in prodcution S′→.S so what is first($)? Why first($) is needed?? Is it not Follow(S)=$ 0 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share Follow (S) = $ \$$ Because of this reason we got lookahead $\$$ in augmented production Everything is explained on page 260 ullman 2nd edition 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share @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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share 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 $\$$ 0 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share 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 votes 0 votes srestha commented May 17, 2019 reply Follow Share @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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share yes 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share Then check this production $S\rightarrow .AA,Follow(S)$ lookahead will be ${\color{Red}{Follow(S)}}$ 0 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share yes your confusion is cleared? 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share @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?? 0 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share 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 votes 1 votes Mk Utkarsh commented May 17, 2019 reply Follow Share 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 1 votes 1 votes srestha commented May 17, 2019 reply Follow Share 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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share 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 votes 0 votes srestha commented May 17, 2019 reply Follow Share 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 votes 0 votes srestha commented May 17, 2019 reply Follow Share 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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share Then lookahead will be a both a and b 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share yes, merging is a shortcut for lookahead right?? 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share 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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share 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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share srestha that line is correct coz that production is not added in that state and it was added in $I_0$ 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share 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 votes 0 votes Mk Utkarsh commented May 17, 2019 reply Follow Share your basics are not clear lookaheads don't merge You should read from page 260 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share 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?? 0 votes 0 votes srestha commented May 17, 2019 reply Follow Share 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 0 votes Please log in or register to add a comment.