FIRST set construction in compiler design

Question

I have the following grammar.I have calculated the FIRST sets for all non terminals.But I am not sure if these are correct or not.

The grammar is as follows:

    E->TE'
    E'->+E|epsilon
    T->FT'
    T'->T|epsilon
    F->PF'
    F->*F'|epsilon
    P->(E)|a|b|epsilon

The FIRST sets for non terminals are as follows:

    FIRST(E)={(,a,b,*,+,epsilon}
    FIRST(E')={+,epsilon}
    FIRST(T)={(,a,b,*,epsilon}
    FIRST(T')={(,a,b,*,epsilon}
    FIRST(F)={(,a,b,*,epsilon}
    FIRST(F')={*,epsilon}
    FIRST(P)={(,a,b,epsilon}

Can anybody guide me if I am correct or not.Any help will be appreciated.

Community · Accepted Answer · 2020-06-20 09:12:55Z

First of all, you have calculated the wrong First(F') because as per your production

F->PF'

F->*F'|EPSILON

That is,

F->PF'|F'|EPSILON

So in your above production F' is not given so we should consider F' as EPSILON that

F'->EPSILON

So now the production will be

E->TE'
E'->+E|EPSILON
T->FT'
T'->T|EPSILON
F->PF'|*F'|EPSILON
F->EPSILON
P->(E)|a|b|EPSILON

Now applying the FIRST rule we get

FIRST(E)=FIRST(T)-EPSILON U FIRST(E')

={(,a,b,* } U {+,EPSILON}

={ (,a,b,*,+,EPSILON }

FIRST(E')={+,EPSILON}

FIRST(T)=FIRST(F)-EPSILON U FIRST(T')

={(,a,b,} U {(,a,b,,EPSILON}

={(,a,b,*,EPSILON}

FIRST(T')=FIRST(T)-EPSILON U EPSILON

= FIRST(T')=FIRST(F)-EPSILON U FIRST(T') U EPSILON

={(,a,b,,EPSILON} / FIRST(T') is cancel out */

={(,a,b,*} U FIRST(T') U EPSILON

FIRST(F)=FIRST(P)-EPSILON U FIRST (F') U FIRST(*F') U EPSILON

={(,a,b} U EPSILON U * U EPSILON ={(,a,b,*,EPSILON}

FIRST(F')={EPSILON}

FIRST(P)=FIRST((E))-EPSILON U a U b U EPSILON

={(,a,b,EPSILON}

If you have any doubt or if you get confused from any of my above steps please feel free to ask any question.

Collectives™ on Stack Overflow

FIRST set construction in compiler design

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related