Search code examples
parsingrecursioncompiler-constructiongrammar

First and follow in the following grammar

The following grammar is given:-

E->E+T|T 
T->T*F|F 
F->id

I have tried to find the first and follow. Can anyone verify it whether its correct???

First(E)={id}
First(T)={id}
First(F)={id}
Follow(E)={+,id}
Follow(T)={+}
Follow(F)={id,*}
Solution

  • FIRST sets are correct, 

    FOLLOW(A) of non-terminal A is the set of terminal symbols that can follow in the   
derivation sequence

    FOLLOW(E), check where it is there in the right-hand side of production. It is there in

        E->E+T

    what follows E when we consider this production for derivation is '+' and '$'(End of Input) is also added to the follow of start symbol

       FOLLOW(E) ={+,$}

    FOLLOW(T), it is there in right-hand side of three productions

       E-> E+T   E->T  T->T*F
   FOLLOW(T)={*} U FOLLOW(E)={*,+,$}

    FOLLOW(F), it is there in right-hand side of two productions

       T->T*F  T->F
   FOLLOW(F)=FOLLOW(T)={*,+,$}

    If you are doing this exercise for computing LL(1) parsing table then first eliminate left recursion and proceed.