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)