CSC362 2011F, Class 20: Predictive Parsing (3)
Overview:
* The Follow Table.
* Building the Follow Table.
* Using Predictive Parsing Tables.
* Potential Problems with Predictive Parsing.
* Reflecting on Predictive Parsing.
* Looking Ahead: Shift-Reduce Parsing.
Admin:
* Test is Wednesday after break.
* If you have not done so, read section 4.5.
* EC for the Thursday extra, by a visitor from UNL.
* EC for the Thursday's panel on the future of the Book, 4:15 in the gallery.
Notational Reminder:
* all lowercase: nonterminal
* ALL UPPERCASE: terminal
* CamelCase: variable representing string of terminals and nonterminals
Follow Table
* Tells us when to use epsilon productions.
* When reducing nonterminal n with next symbol S
if S is in Follow[n] then use a nullifying production
* For each rule of the form
m : Stuff n MoreStuff
add first(MoreStuff) to Follow[n]
* Problem left from last class
m : Stuff n
* Does this production tell us anything about what can follow m or
what can follow n?
* This may tell us that "end of input" can follow n.
(Only if m is the start state.)
* Presumably, there is some relationship between what can follow
m and what can follow n.
start -> ... -> S1 S2 S3 ... Sk m MoreJunk
-> S1 S2 S3 ... Sk Stuff n MoreJunk
So, for
m : Stuff n
add Follow[m] to Follow[n]
* What if we have
m : Stuff n MoreStuff
and MoreStuff is nullable
add Follow[m] to Follow[n]
Putting it all together
* Given First, Nullable, and Follow, you can
* Hand code the parser
* Build a table for a generic predictive parser
* Indexed by nonterminal/symbol
* If you are matching a nonterminal and see a particular symbol,
look in the table
* If you see a RHS, you now need to match the components of the
right-hand side.
* If you don't see a RHS, give up
So, how do we build this table?
* Build First, Follow, Nullable
* For each rule, n : Rhs
For each S in first(Rhs)
add Rhs to parse[n,S]
If nullable(Rhs)
For each S in Follow[n]
add Rhs to parse[n,S]
* If any of these changes led to a rewrite of a table cell, the
grammar is not amenable to prdictive parsing.
What do you do if your grammar is not amenable to predictive parsing?
* Try to rewrite the grammar so that it is amenable
* NOT ALL GRAMMARS (LANGUAGES) CAN BE MADE AMENABLE TO PREDICTIVE PARSING
* Go read Chomsky if you want to know more.
Some problems that can be fixed:
* Common right-hand sides
conditional: IF bexp THEN statement
conditional: IF bexp THEN statement ELSE statement
Given conditional/IF we can't immediately choose
* Solution: Factor out the common LHS
conditional: IF bexp THEN statement optional-else
optional-else: epsilon
| ELSE statement
* Left-recursion
lines: lines line
| line
;
Problem: When do we use the "base case" rule?
Solution: Move the recursion to the right
lines: line lines
| line
Whoops, previous problem
lines: line morelines
morelines: lines
| epsilon
Will these be an issue in Pascal? Yes. Where?
* Already had the case of conditionals. That was easy
statement : assignment
| procedure-call
First[assignment] = { ID }
First[procedure-call] = { ID }
* Expressions
expr : expr addop term
| term
Left recursive! Whoops. How do we rewrite that?
Rewriting
expr : term extra
extra : addop expr
| epsilon
* However we rewrite it, the parse tree is going to be UNHELPFUL
Is there something better than mangling our grammar?
* Use greater lookahead: Solves common lhs problems
* Choose a different approach.
Preview of new approach: Shift-Reduce parsing
* Basic idea: If you see a nonterminal and are unsure which RHS to apply,
just "put it to the side" and go on for further information
* One table, one stack, one state variable
* Table: Given a state and the next input symbol, gives one of three
choices
* SHIFT symbol onto the stack ("I don't know what to do yet") and
enter a new state
* REDUCE a rhs on top of the stack
* ERROR - invalid state/symbol combination
Goal for next few classes: How do we build one of these cool tables?
Wednesday: A sample grammar and table