CODEWITHSUNDEEP
parsingcompiler-construction
coding_ninza
coding_ninza

Reputation: 405

How to find FIRST and FOLLOW set of a recursive grammar?

Suppose I have the following CFG:

S->aACD|BcAe

A->b | EPSILON

B->cf | d

C->fe

Now I apply the FIRST rule on the CFG:

FIRST(S)=FIRST(aAcd) U FIRST(BcAe)

={a} U FIRST(BcAe)

= {a} U FIRST(B)-{EPSILON} U FIRST(cAe)

= {a} U FIRST(B)-{EPSILON} U {c}

= {a} U FIRST(Cf) U FIRST(d) -{EPSILON} U {c}

= {a,f,d,c,EPSILON}

FIRST(A)=FIRST(b) U FIRST(EPSILON)= ={B,EPSILON}

FIRST(B)=FIRST(Cf) U FIRST(d)={d,f}

FIRST(C)=FIRST(fe)={F}

Now I apply the FOLLOW rule on the CFG:

FOLLOW(S)={$}

FOLLOW(A)={c,e}

FOLLOW(B)={c}

FOLLOW(C)={f}

Is there any wrong? If it is wrong please show me how to do it.

Upvotes: 0

Views: 1525

Answers (1)

Mathews Sunny
Mathews Sunny

Reputation: 1642

Your work above (question) suggest that you are not good in basic concepts. So you can make use of the this tutorial.

Grammer :

S->aACD|BcAe

A->b | EPSILON

B->cf | d

C->fe

No production means EPSILON so,

D-> EPSILON

On applying first rule :

FIRST(A)=FIRST(b) U FIRST(EPSILON)= ={b,EPSILON}

FIRST(B)=FIRST(cf) U FIRST(d)={c} U {d} = {c,d}

FIRST(C)=FIRST(fe)={f}

FIRST(D)={EPSILON}

FIRST(S)=FIRST(aACD) U FIRST(BcAe)

={a} U FIRST(BcAe)

= {a} U FIRST(B)

= {a} U {c,d}

= {a,c,d}

on applying follow rule :

FOLLOW(S)={$}

FOLLOW(A)= FIRST(C) U FIRST(e) = {f,e}

FOLLOW(B)={c}

FOLLOW(C)={$}

FOLLOW(D)={$}

Upvotes: 1

Related Questions