CS606 - Compiler Construction - Lecture Handout 18

User Rating:  / 0
PoorBest 

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Computing FIRST Sets

Here is the algorithm for computing the FIRST sets.

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

  2. For all productions

Computing FIRST Sets

Example: consider the expression grammar again

consider the expression grammar

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 }

FOLLOW Sets

Definition:

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

Computing FOLLOW Sets:

  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 ) = { +, *, ), $ }