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