Today in CS362: Predictive Parsing, Concluded

Missing
  Ananta, Erik, Mark

Admin
  Sorry about yesterday
  Darby
  Groups
  Sample grammar

Overview
  Predictive parsing of expressions
  Problems of predictive parsing
  Shift-reduce parsing [NOT COVERED]
  Some examples [ONE COVERED]
  Starting to formalize [NOT COVERED]

E -> E + T
  |  T
T -> T * F
  |  F
F -> num
  |  ( E )

Can we parse this grammar with a predictive parser?  
No, it's left recursive.

How else could you tell (in case you'd forgotten that rule)?
Try to build the predicitve parser.  Success: It can be.
Failure: It can't be.

Can we parse this language with a predictive parser?  
Yes

How?
Transform the grammar

E -> E + T
  |  T
T -> T * F
  |  F
F -> num
  |  ( E )

R1: E -> T AddStuff
R2: AddStuff -> + T AddStuff
R3:          |  epsilon
R4: T -> F MulStuff
R5: MulStuff -> * F MulStuff
R6:          |  epsilon
R7: F -> num
R8:   |  ( E )

Apply R1 when matching an E and see a num or lparen
Apply R2 when matching an AddStuff and see a +
Apply R3 when matching an AddStuff and see a rparen 
                                        OR end-of-string
Apply R4 when matching a T and see a num or lparen
Apply R5 when matching a MulStuff and see a *
Apply R6 when matching a MulStuff and see a +, rparen, EOS

Observation: Instead of building lots of procedures and
relying on the hidden "stack + state of procedure", we can
build the stack ourselves.

Whenever your apply a rule, shove the right-hand-side of the
rule on the stack in reverse order.

If the top of the stack is a token, make sure it matches the
next input value and consume that input value.

Stack | Input
Bottom-Stack ... Top-Stack | Start-Input ... End-Input

$ E | 3 + 4 * 5 + 6 $
$ AddStuff T | 3 + 4 * 5 + 6 $
$ AddStuff MulStuff F | 3 + 4 * 5 + 6 $
$ AddStuff MulStuff num | 3 + 4 * 5 + 6 $
$ AddStuff MulStuff | + 4 * 5 + 6 $
$ AddStuff | + 4 * 5 + 6 $
$ AddStuff T + | + 4 * 5 + 6 $
$ AddStuff T | 4 * 5 + 6 $
$ AddStuff MulStuff F | 4 * 5 + 6 $
$ AddStuff MulStuff num | 4 * 5 + 6 $
$ AddStuff MulStuff | * 5 + 6 $
$ AddStuff MulStuff F * | * 5 + 6 $
$ AddStuff MulStuff F | 5 + 6 $
$ AddStuff MulStuff num | 5 + 6 $
$ AddStuff MulStuff | + 6 $
$ AddStuff | + 6 $
$ AddStuff T + | + 6 $
$ AddStuff T | 6 $
$ AddStuff MulStuff F | 6 $
$ AddStuff MulStuff num | 6 $
$ AddStuff MulStuff | $
$ AddStuff | $
$ | $
|

Stop when input or stack is empty (or no rule to apply).
Succeed when both are empty.

Observation: "Boy that's easy to implement".

Question: What are the problems?
* Stack could overflow.  (Unlikely)
* Have to build the table (Have automated process)
* Won't work for all languages (Will they work for Pascal?).
* You've destroyed the grammar, so parse trees are less
  nice (but we can fix that problem with extra effort)