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