CSC362 2011F, Class 22: Shift-Reduce Parsing (2) Overview: * Example: Building an LR(0) automaton for expressions. * Running LR(0) automata. * Example: Our automaton. * Building LR(0) automata. Admin: * Welcome to our visitor, Brady Garvin of UNL * RIP Dennis Ritchie * >= 2 great inventions * >= 1 great mistake * Have a great break! We've designed an automaton. How do we use it? A modified shift-reduce algorithm * Instead of table, we now have this automaton thing (states plus labeled edges) * Instead of stack of symbols, stack of symbol,state pairs Push (EOI,S0) While input remains * Let T be the next input token * If there is an edge from the top state labeled T, push (T,stateatendofedge) (and consume input) * If the top state contains "lhs -> RHS ." // Theory: RHS should be on the stack pop RHS push (lhs,edgefromtopstatelabeledwithlhs) // That is, follow the edge labeled with lhs * In any other case, crash and burn At this point, no input remains or we've crashed * We've crashed - Give up * (EOI,S0) is on top of the stack, and stack has size 1 - Accept * Anything else Let's try the algorithm 2-3*(11+1) Stack | Input [EOI,S0] | 2-3*(11+1) [EOI,S0] [2,S3] | -3*(11+1) [EOI,S0] [f,S10] | -3*(11+1) [EOI,S0] [t,S11] | -3*(11+1) [EOI,S0] [e,S1] | -3*(11+1) [EOI,S0] [e,S1] [-,S2] | 3*(11+1) [EOI,S0] [e,S1] [-,S2] [3,S3] | *(11+1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] | (11+1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] | 11+1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [11,S3] | +1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [f,S10] | +1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [t,S11] | +1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [e,S8] | +1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [e,S8] [+,S2] | 1) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [e,S8] [+,S2] [1,S3] | ) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [e,S8] [+,S2] [f,S10] | ) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [e,S8] [+,S2] [t,S4] | ) [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [(,S7] [e,S8] [),S9] | [EOI,S0] [e,S1] [-,S2] [t,S4] [*,S5] [f,S6] [EOI,S0] [e,S1] [-,S2] [f,S10] [EOI,S0] [e,S1] [-,S2] [t,s4] [EOI,S0] [e,S1] [EOI,S0] s Ta Dah!