Today in CS362: Building Predictive Parsing Tables

Missing
  Ananta, Erik, Mark

Admin
  Project Phase 1 Due (Done?)
  HW2 assigned
  HW1 not yet graded

Overview
  Review: The parsing tables
  Building the First table
  Building the Nullable table
  Building the Follow table
  Using the tables
  Next class; Dealing with problems

Predictive or Recursive Descent Parsing
  Parse procedure for each nonterminal
    Looks at the next input token (or tokens)
    Picks RHS
    Executes parsing code for that RHS
  If we build three tables, it's easy to build 
  predictive parsers
    First[N] : All tokens that can begin strings
      derivable from N
    Nullable[N] : Can N derive epsilon?
    Follow[N] : All tokens that can follow N in
      a derived string of terminals and nonterminals
  We can use these to build two functions
    first(StringOfTerminalsAndNonterminals): All
      tokens that can begin strings derivable from
      SOTAN
    nullable(SOTAN): Can SOTAN derive epsilon

How can these tables and functions help us?

Consider a rule
  N -> SOTAN
When should we apply that rule (in attempting to parse N)

If nullable(SOTAN) and we see a symbol that can follow N,
  it makes sense to apply N->SOTAN
If we see a symbol in first(SOTAN)
  it makes sense to apply N->SOTAN
Otherwise, we hope there's some other rule for which 
  one of those two conditions hold.

Let's build the tables and functions (using the joy of
mutual recursion)

function first(SOTAN) {
  (1) If SOTAN is epsilon return EmptySet
  (2) Let murf be the first symbol in SOTAN
    (a) If murf is a terminal return SetOf(murf)
    (b) If murf is a nonterminal
        (i) If Nullable[murf]
            return First[murf] union first(rest of SOTAN)
        (ii) If not Nullable[murf]
            return First[murf]

How do we build First?  Using the function first.

a. Start with stupid assumptions
  For all nonterminal, N, First[N] = { }
b.
repeat
    For each production N -> SOTAN
      First[N] = First[N] union first(SOTAN)
until no more changes are made

Sample Grammar

S -> AB
A -> a A
A -> 
B -> b
}

First[S] = { }
  first(AB)
    murf = A
    A is nullable
     First[A] union first(B)
     {} union first(B)
  first(B)
    murf = B
    rest is nullable
     First[B] union first(epsilon)
     { } union { }
    
First[A] = { }
  first(a A)
    murf = a
    a is a token
    Add { a }
    First[A] is now { a }
  first(epsilon)
    Nothing to add
First[B] = { }
  Add { b }

New state of knowledge

First[S] = { }
First[A] = { a }
First[B] = { b }

------------------------------------------------------------

Next step: Build Nullable and nullable

boolean nullable(SOTAN)
(1) If SOTAN is epsilon, return true
(2) Let murf be the first element of SOTAN
(3) If murf is a terminal return false
(4) Otherwise return Nullable[murf] AND nullable(rest-of-SOTAN)

Now let's build Nullable
a. Start with stupid assumptions
  For all nonterminal, N, Nullable[N] = false
b.
repeat
    For each production N -> SOTAN
      Nullable[N] = Nullable[N] OR nullable(SOTAN)
until no more changes are made

------------------------------------------------------------

Next step: Build the Follow table
  Follow[N] = all terminals/tokens that can follow N in
   a derived string

a. Start with stupid assumptions
  For all nonterminal, N, Follow[N] = { }
b. Add a new symbol, end-of-string, and assumption
  Follow[StartSymbol] = { end-of-string }
c.
repeat 
  for each production N -> s1 s2 s3 ... sk
    For each si
      If si is a nonterminal
        Follow[si] = Follow[si] union first(s(i+1) ... sk)
until no more changes are made

ONE MORE THING, LEFT AS AN EXERCISE FOR YOU TO THINK ABOUT

What can we say about the relationship of Follow[N] and
Follow[sk]?

Consider
 
S -> A B
A -> C D
B -> b