CSCI 310 Spring 2005, Day 8

1. Administrivia
   1. Office hours today: possibly a little late
   2. Office hours monday: 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. Resetting our story:
   1. We want to create sets, First(gamma) that let us predict which production we should use.
   2. some productions go to epsilon, which makes this harder.
   3. not all productions LL(1)
   4. our task: find a way to build FIRST(gamma). We're going to do this in steps (a much shorter algorithm is in the text, but of course it takes work to understand it).
4. Nullable productions
   1. Definition: a symbol is nullable if it derives the empty string. (We care because it means we need to know what follows it.)
   2. An algorithm for marking nullable productions.

5. Initializing FirstSetEpsilon for variables - the set of terminals following gamma but including epsilon (so not quite complete information).
6. Using FirstSetEpsilon for variables to compute FirstSetEpsilon(gamma) (almost).
7. Iterative solution to FirstSetEpsilon for gamma that works. :-)

8. 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.]