# CS606 - Compiler Construction - Lecture Handout 18

User Rating:  / 0
PoorBest

## Computing FIRST Sets

Here is the algorithm for computing the FIRST sets.

1. For all terminal symbols b,
FIRST(b) = {b}

Example: consider the expression grammar again

FIRST(id) = { id }
FIRST('(' ) = { ( }
FIRST(‘+' ) = { + }
FIRST(E ) = {FIRST(T ) - {e} }
FIRST(T ) = {FIRST(F ) - {e} }
FIRST(F ) = {FIRST( '(') - {e} } = { ( }
FIRST(F ) = { '(' } + {FIRST( id ) - {e} } = { ( , id}
FIRST(E' ) = { +, e }
FIRST(T' ) = { *, e }

Thus,

FIRST(E ) = FIRST(T ) = FIRST(F ) = { (, id }
FIRST(E' ) = { +, e }
FIRST(T' ) = { *, e }

### Definition:

FOLLOW(X) = { b | S ? * bXbw}

1. Add \$ to FOLLOW(S) where S is the start non-terminal.
2. If there is a production A ? aBb, then everything in FIRST(b) – {e} is in FOLLOW(B).
3. If there is a production A ? aB, or A ? aBb, where in e Î FIRST(b) (i.e., b ? * e), then everything in FOLLOW(A) is in FOLLOW(B)

The following procedure encodes this strategy.

for each A Î NT
FOLLOW(A) ? Ø
FOLLOW(S) ? {\$}
while ( FOLLOW sets are still changing)
for each A ? b1 b2... bk ÎP
FOLLOW(bk) ? FOLLOW(bk) È FOLLOW(A)
T ? FOLLOW(A)
for i ? k downto 2
if ( e Î FIRST(bi) )
FOLLOW(bi-1) ? FOLLOW(bi-1) È (FIRST(bi) – {e}) È T
else
FOLLOW(bi-1) ? FOLLOW(bi-1) ÈFIRST(bi)
T ? Ø

Let’s apply the algorithm to the expression grammar.

Put \$ in FOLLOW(E ). By rule (2) applied to production ? ( E ), ‘)’ is also in FOLLOW(E ). Thus, FOLLOW(E ) = { ), \$}. By rule (3) applied to production E ? T E' , \$ and ‘)’ are in FOLLOW(E' ). Thus, FOLLOW(E ) = FOLLOW (E' ) = { ), \$ }. Similarly, FOLLOW(T ) = FOLLOW (T' ) = { +, ), \$ } and FOLLOW(F ) = { +, *, ), \$ }