FIRST AND FOLLOWS

FIRST: 

If α is any string of grammar symbols, the FIRST (α) be the set of terminals that begins strings derived from α.

                 If αà€, then € is also in FIRST (α).

To compute FIRST (α) for all grammar symbols ’X’, apply the following rules until no more terminals or € can be added to any FIRST set.

     1)    If x is terminal ,the FIRST(x)={x}

     2)    If x is non terminal and xà aα is a production, then add a to FIRST(x), If xà€ is a production, then add € to FIRST(x).

     3)    If xày₁,y₂,y₃,…….y_k is a production ,then for all i such that of all y₁……y_i-1 are non terminals and FIRST(y_i) contains € for j=1,2,3….i-1 (i.e.,y_i,y₂,…..y_i-1à€) add every non-€ symbol in FIRST(y_i) to FIRST(x).

FOLLOW:    For a non terminal A, FOLLOW (A) to de the set of terminal a, that can appear immediately to the right of A in some sentential form i.e., sàαAaβ for some α and β.

      To compute FOLLOW (A) for all non-terminals A, apply the following rules until nothing can be added to any follow set.

1)      $ is in FOLLOW(S), where S is the start symbol.

2)      If there is a production Aàαbβ, then everything in FIRST (β) except for € is in FOLLOW (B).

Example :

Construct the predictive parser for the following grammar

        Sà(L)/a

        LàL,S/S

Sol: We have to eliminate left recursion LàL,S/S.

After eliminating the left recursion we obtain

           Sà(L)/a

           LàSL¹

           L¹à, SL¹/€

Then FIRST

FIRST (S) = { ( , a} by rule (2)

FIRST (L) = { ( ,a} by rule (3) and (1)

FIRST (L¹) = {, ,€} by rule (2)

FOLLOW

FOLLOW(S) = { $ , ) , ,}    =FIRST(L¹) U FOLLOW(L)

FOLLOW (L) = { )  ,}

FOLLOW (L¹) = { ) }

The parsing table

	(	)	a	,	$
S	Sà(L)		Sàa
L	LàSL1		LàSL1
L1		L1 à€		L1 à,SL1	L1  à€