The Gateway to Computer Science Excellence
+1 vote
282 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??

in Compiler Design by Veteran | 282 views
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

 @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

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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
201,103 comments
118,146 users