Today in CS362: Shift-Reduce Parsing Missing Adam, Erik Admin HW2 Due! Project, Phase 2 coming soon Read the Red Dragon Putnam Exam Grading conference papers Overview Ideas behind shift-reduce parsing Our fun expression example, revisited How to build a shift-reduce parser, started What is predictive-parsing? To build a predictive parser, you build three helper tables. Left-to-right parsing technique Involves looking at terminals Not all grammars are amenable You can tell from context and the next terminal what production to apply Top-down left-right parsing procedure Start with a nonterminal and repeatedly rpelace the leftmost nonterminal You can make the decision as to which production to use in replacing the leftmost nonterminal by looking at that nonterminal and a the next input symbol or symbols. What is shift reduce parsing? Bottom-up parsing technique Repeatedly replaces substrings with nonterminals until we hit start symbol or crash-and-burn Which substring do we replace? The leftmost one which matches a right-hand-side "appropriately" We call this a LR parsing (1) Looks at input from left to right (2) Simulates *rightmost* derivation What about "shifting" and "reducing"? key implementation ideas: * Use a stack * Two options upon seeing an input symbol: + SHIFT it onto the stack + REDUCE a RHS on the stack * Behind the scenes: The stack also contains some extra values that describe what's on the stack * Our decision is made by a table (that you'll soon learn how to build) Stack | Input Bottom Top | Front Back \$ | 3 + 4 * 5 + 6 \$ SHIFT \$ 3 | + 4 * 5 + 6 \$ REDUCE F -> num \$ F | + 4 * 5 + 6 \$ REDUCE T -> F \$ T | + 4 * 5 + 6 \$ REDUCE E -> T \$ E | + 4 * 5 + 6 \$ SHIFT \$ E + | 4 * 5 + 6 \$ SHIFT \$ E + 4 | * 5 + 6 \$ REDUCE F -> num \$ E + F | * 5 + 6 \$ REDUCE T -> F \$ E + T | * 5 + 6 \$ SHIFT \$ E + T * | 5 + 6 \$ SHIFT \$ E + T * 5 | + 6 \$ REDUCE F -> num \$ E + T * F | + 6 \$ REDUCE T -> T * F \$ E + T | + 6 \$ REDUCE E -> E + T \$ E | + 6 \$ How do we build the table (other than relying on intuition?) * There are a lot of similar different strategies for building shift-reduce tables * LR(k): Build the table using k tokens of lookahead * LR(0): No tokens of lookahead Idea: Build a automaton * States of that automaton are sets of "potential partial matches of RHS's" * Transitions are labeled by nonterminals and terminals * Need to add new special start production, S' -> S \$ * Notation: . marks "here's where I am in the RHS" State 0: S' -> . E \$ E -> . E + T E -> . T T -> . T * F T -> . F F -> . num F -> . ( E ) State 1: S' -> E . \$ E -> E . + T State 2: S' -> E \$ . MATCHED State 3: E -> T . REDUCE (sometimes) E -> T . * F State 4: E -> E + . T State 5: E -> E + T . REDUCE State 6: T -> F . REDUCE (sometimes) State 7: F -> num . REDUCE (always) Transition table (0,E) -> 1 (0,T) -> 3 (0,F) -> 6 (0,num) -> 7 (1,\$) -> 2 (1,+) -> 4 (4,T) -> 5 REALLY SIMPLE EXAMPLE \$ S0 E S1 \$ S2 |