CSCI 310 Spring 2005, Day 9

1. Administrivia
   1. Office hours today: possibly a little late

2. Predictive parsing
   1. Our first example grammar (from last time)

      S -> A $   // $ is EOF
      S -> A S
      S -> P $
      A -> id = EXP;
      P -> print EXP;
      EXP -> T * EXP
      EXP -> T + EXP
      EXP -> T - EXP
      EXP -> T / EXP
      EXP -> T ^ EXP    // ^ is exponentiation
      EXP -> T
      T -> id
      T -> int
      

   2. Example from book (3.11)

      S -> if E then S else S
      S -> begin S L
      S -> print E
      L -> end
      L -> ; S L
      E -> num = num
      

3. Definition: FOLLOW(X) is the set of terminals that can immediately follow X. terminal t is in FOLLOW(X) if there is a derivation Xt possible from the grammar. [Technicality: FOLLOW(X) is never empty except possibly for the start production because end-of-file ($) will be in the grammar.]

4. The Follow Algorithm

5. Putting it all together