Today in CS362: Predictive Parsing Concluded; 
                Shift-Reduce Parsing Initiated

Missing
  Daren, Erik, Mark

Admin
  Questions on HW2?
  The Strategic Planning Steering Committee

Overview
  Predictive Parsing
    The Follow table
    Building the Follow table
    Problems with shift-reduce parsing
    Some solutions: Removing left recursion and left factoring
    Example: Expressions
  Alternatives
    Example of shift-reduce parsing

Three tables:
  First, Follow, Nullable
Two functions:
  first, nullable

Follow[N] is "the set of tokens/terminals that can
  follow N in a derived string of termin/nontermin"

Building the Follow table
  // Initialization
  for all nonterminals, N
    Follow[N] = { }
  for the start symbol, S
    Follow[S] = { end-of-string }

  // Filling in the details
  repeat
    For each production N -> s1, s2, ..., sn
      for each si
        if si is a nonterminal
         Follow[si] = Follow[si] union first(s(i+1) ... sn)
        end if
      end for
    end for
  until no more changes are made

Questions: What about sn?  More precisely, what about the
relationship between Follow[N] and Follow[sn]?

Example

S -> A B
A -> a C  ***** What does this tell you about F[A] or F[C]?
C -> epsilon
  |  q
  |  C C
B -> b

Daren's claim: They should be the same.
  (1) Anything that can follow A can follow C.
Nathan's counter-claim
  (2) There are things that can follow C that can't follow
      A

Proof of Daren's claim
  S =>* x1 x2 ... A f ... Xn 
    => x1 x2 ... a C f ... Xn

Fixed that loop to handle cases like the above!
  repeat
    for each production N -> s1, s2, ..., sn
      for each si
        if si is a nonterminal
          Follow[si] = Follow[si] union first(s(i+1) ... sn)
          if (nullable(s(i+1) ... sn))
            Follow[si] = Follow[si] union Follow[N]
        end if
      end for
    end for
  until no more changes are made

----

How do we use the three tables and two functions?

Given a nonterminal N, build parseN as follows

  for each production N -> stuff
    for each token, t, in first(stuff)
      add "case t: parseStuff" to parseN
    end for
    if nullable(stuff) then
      for each token, t, in follow[N]
        add "case t: parseStuff" to parseN
  end for 

Observation:
  If two rhs's have the same first, we can't decide
    The grammar is not amenable to predictive parsing
  If N is nullable and there's a token in follow[N] and 
  first(stuff)
    The grammar is not amenable to predictive parsing

Consider

S -> A B
A -> epsilon
A -> A a
B -> b c

You can make some grammars more amenable to predictive parsing.

Thm: There are languages, L, for which no grammar, G, exists
that is amenable to predictive parsing and for which a 
context-free grammar, C, exists.

SAM SHOULD LOOK FOR AN EXAMPLE

Here's a simple non-amenable grammar

S -> S a
   | b

First[S] = { b }
Follow[S] = { end-of-string }
Fullable[S] = false

Problem: The grammar is "Left Recursive"

  A grammar that includes a rule of the form

  N -> N blah

  is left recursive.

Solution?  Make it right-recursive

S -> b S'
S' -> a S'
S' -> epsilon

First[S] = { b}
First[S'] = { a }
Follow[S] = { end-of-string }
Follow[S'] = { end-of-string }
Nullable[S] = false
Nullable[S'] = true

parseS: 
  if peekToken == b
    match(b)
    parseSPrime
  else
    crashAndBurn

parseSPrime
  if peekToken == a
    match(a)
    parseSPrime
  else if peekToken == end-of-string
    derive-epsilon
  else
    crashAndBurn

Let's generalize the "make right recursive" technique

Given

N -> N alpha1
N -> N alpha2
N -> N alpha3
...
N -> N alphan
N -> beta1
N -> beta2
...
N -> betam

None of the betas start with N

The grammar says "N must start with one of the betas.
That beta is then followed by as many alphas as we want,
repeated as much as we want."

N -> beta1 N'
N -> beta2 N'
...
N -> betam N'

N' -> alpha1 N'
N' -> alpha2 N'
...
N' -> alphan N'
N' -> epsilon

Here's a new non-amenable grammar

S -> a A
S -> a B
A -> complete
B -> also-complete

Fixed

S -> a S'
S' -> A
S' -> B

----


S -> A
S -> B
A -> a A
A -> c
B -> a b

One possible solution:

S -> a A
S -> c
S -> a b
A -> a A
A -> c
B -> a b

Another problem
S -> a A
S -> c
S -> a B
S -> b
A -> a A
A -> c
B -> a B
B -> b

S -> a S'
S -> c
S -> b
S' -> A
S' -> B