First and Follow (compiler)

The construction of a predictive parser is aided by two functions associated with a grammar G. These

functions, FIRST and FOLLOW, allow us to fill in the entries of a predictive parsing table for G, whenever

possible. Sets of tokens yielded by the FOLLOW function can also be used as synchronizing tokens during

panic-mode error recovery.

just suppose for a sec that you r ll(1) parser and you have n supernatural power of seeing the future of string by one step.

in above statement that supernatural power is nothing but finding follow of given non-terminal to predict the next items....

hope u got the point ...n ya dnt take super natural shit seriously ... ;)

FIRST(α)

If α is any string of grammar symbols, let FIRST(α) be the set of terminals that begin the strings derived

from α. If α ⇒ ε then ε is also in FIRST(α).

To compute FIRST(X) 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, then FIRST(X) is {X}.

2.If X → ε is a production, then add ε to FIRST(X).

3.If X is nonterminal and X →Y1 Y2 ... Yk . is a production, then place a in FIRST(X) if for some i, a is in

FIRST(Yi), and ε is in all of FIRST(Y1), ... , FIRST(Yi-1); that is, Y1, ... ,Yi-1 ⇒ ε. If ε is in FIRST(Yj) for

all j = 1, 2, ... , k, then add ε to FIRST(X). For example, everything in FIRST(Y1) is surely in

FIRST(X). If Y1 does not derive ε, then we add nothing more to FIRST(X), but if Y1⇒ ε, then we add

FIRST(Y2) and so on.

Now, we can compute FIRST for any string X1X2 . . . Xn as follows. Add to FIRST(X1X2 ... Xn) all the non-

ε symbols of FIRST(X1). Also add the non-ε symbols of FIRST(X2) if ε is in FIRST(X1), the non-ε symbols

of FIRST(X 3) if ε is in both FIRST(X 1) and FIRST(X2), and so on. Finally, add ε to FIRST(X1X2 ... Xn) if,

for all i, FIRST(X i) contains ε.

FOLLOW(A)

Define FOLLOW(A), for nonterminal A, to be the set of terminals a that can appear immediately to the right

of A in some sentential form, that is, the set of terminals a such that there exists a derivation of the form

S⇒αΑaβ for some α and β. Note that there may, at some time during the derivation, have been symbols

between A and a, but if so, they derived ε and disappeared. If A can be the rightmost symbol in some

sentential form, then $, representing the input right endmarker, is in FOLLOW(A).

To compute FOLLOW(A) for all nonterminals A, apply the following rules until nothing can be added to any

FOLLOW set:

1.Place $ in FOLLOW(S), where S is the start symbol and $ is the input right endmarker.

2.If there is a production A ⇒ αΒβ, then everything in FIRST(β), except for ε, is placed in FOLLOW(B).

3.If there is a production A ⇒ αΒ, or a production A ⇒ αΒβ where FIRST(β) contains ε (i.e., β ⇒ε),

then everything in FOLLOW(A) is in FOLLOW(B).

EXAMPLE

Consider the expression grammar :

E → T E’

E’→ + T E’ | ε

T → F T’

T’→ * F T’ | ε

F → ( E ) | id

Then:

FIRST(E) = FIRST(T) = FIRST(F) = {( , id}

FIRST(E’) = {+, ε}

FIRST(T’) = {*, ε}

FOLLOW(E) = FOLLOW(E’) = {) , $}

FOLLOW(T) = FOLLOW(T’) = {+, ), $}

FOLLOW(F) = {+, *, ), $

/*important point to note ...most of student do mistake while finding follow..please remember if u r finding follow and applying rule2 then that doesnt mean that now you dont have to check for condition 3,check for it also if condition applies then follow its rules also */

/* have any problem then feel free 2 comment*/