CSCI 310 Spring 2005, Day 7

1. Administrivia
   1. 4 February class: replaced by faculty candidate (stats)
   2. Also 4 Feb: gary leaves town early and gone the weekend
   3. Why is this important? Project 2 on the 7th... PLEASE start early!

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
      

      A simple parser class could deal with this by writing methods for S, L, and E, along with a method that calls for the next token from the lexer and analyzes it:

      class parse
      {
         Token t;
         Lexer lexer;
         void eat(Token target) { if t.equals(target) t = lexer.nextToken();
      else parseError();}
         
         public parse(Lexer l) { lexer = l; t = lexer.nextToken();}
         
         public void S() { switch(t) 
                            case IF: eat(IF); E(); eat(THEN); S();
                                     eat(ELSE); S(); break;
                            etc...
                         }
      
         public void L()
        
         public void E()
      }
      

   3. Walk through a parse of begin if 5=6 then print 5=5 else print 6=6 end
   4. Nearly the same questions: why does this work / will it work on our grammar from early in the day / what can go wrong?
   5. Recap and lead in to FIRST/FOLLOW

3. FIRST and FOLLOW sets (intro)
   1. Definition (from text): Given gamma, a string of terminals and non-terminals, FIRST(gamma) is the set of all terminal symbols that can begin a string derived from gamma.
   2. Example: FIRST(AS) = ? (AS from first grammar of the day)
      FIRST(T*EXP) = ?
   3. Alas, the ugliness:

      Z->d
      Z-> XYZ
      Y-> 
      Y->c
      X->Y
      X->a
      

      FIRST(XYZ) = ?
   4. Definition: a symbol is nullable if it derives the empty string. (We care because it means we need to know what follows it.)
   5. 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. Determining the nullable variables.

5. Determining FIRST(alpha), (may include epsilon)

6. Determining FOLLOW(V), V a variable (may include epsilon)

7. Determining FIRST(PRODUCTION) (what we really want; shouldn't include epsilon)