CSC362 2011F, Class 19: Pause for Breath (1)
Overview:
* Assignment, Phase 2.
* The Follow Table
Admin:
* EC for next week's Thursday extra, by a visitor from UNL.
* EC for next week's Thursday panel on the future of the book.
* Don't forget tonight's CS picnic!
* Please try to behave responsibly this weekend.
* Happy Ada Lovelace day!
Assignment, Phase 2
* See Examples/Pparser
* Due Friday after break
* Next stage (short): Type checker
* Next stage (medium): Partial translation to TAC
* Next stage (medium): More translation
* Functions will come next
Detour Stack Frame and the Call Stack
* Need room for parameters
* Need room for return address
* Need room for local variables
Recall:
* Building predictive parsers
* First and Nullable tables gather some info
* first and nullable functions use the tables to give more info
* Last table to build
Follow[n]
* Contents:
Set of symbols that can follow n in some partial derivation
s -> ... -> a b C D e n F ....
* Purpose:
* If n is nullable and the next input token is in Follow[n]
* Apply the rule that nullifies n -
* That is, how to do epsilon rules
* How do we build Follow[n]?
* Look at all appearances of n in the right-hand-sides of the rule set
* If n is followed in one of these rules by a terminal, T
add T to Follow[n]
* Generalize: If n is followed in one of these rules by a
sequence of nonterminals and terminals
s : Stuff n MoreStuff
MoreStuff is a sequence of nonterminals and terminals, e.g.,
m q R S b pasd
for all T in first(MoreStuff)
add T to Follow[n]
* Issue: What if MoreStuff is nullable?
m : a B n
* What does this tell us about what can follow n or m?
* Think about this on Saturday night