CSC362 2011F, Class 23: Shift-Reduce Parsing (3) Overview: * Detour: About the Mid-Semester Examination. * Refresher: Shift-Reduce Parsers. * Some Potential Problems with LR(0) Parsers. * Other Techniques for Computing Shift-Reduce Automata. * Parser Generators. Admin: * The mid-semester examination will be held on Wednesday. * Book, EBoards, and Outlines should be resources for preparation * No EC for this week's Thursday extra: Discrete Structures and the future of math requirements in CS. * Due Friday: Phase 2 of your project. * Replace the .l file with your .l file (which may need a few modifications) * Identify lots and lots of grammatical rules from Pascal, and translate them to Yacc format. * Reading for Friday: 5.1-5.3. * EC for any of the Grinnell College Young Innovator for Social Justice events (Awards ceremony Tuesday night; Coffee break on Wednesday at 2:30; Symposium on Wednesday at 4:15; Symposium Wednesday at 8:00 p.m.; Morris Dees Convo). * Sam will be available in office for questions 8-10 Tuesday, and 9-10 Wednesday. Sam will be on email off and on other times We are building shift-reduce parsers * Basic runtime structures * Input stream (tokens) * Stack of symbols and states * Parse tree * A shift-reduce table tells us what to do for every state/token pair * Shift the token onto the stack * Reduce a RHS on the stack to the corresponding lhs * In both cases, enter a new state * Simplest shift-reduce parsers: LR(0) * Technique: Sets of items * An item is a production augmented with a "here" symbol (where we are in the RHS) Potential problems in LR(0) automata * shift-reduce conflict * Pure LR(0): Always reduce * SLR: If the next symbol is in Follow[lhs], reduce * Even with SLR, you have shift-reduce conflicts * reduce-reduce conflict E.g., s : a A s : b B a : X b : X What do you do about the state a : X . b : X . * shift-shift * Construction of automaton prevents that How do we deal with shift-reduce and reduce-reduce conflicts? * Fun with lookahead * Do you lookahead while RUNNING the automaton? * Or while BUILDING the automaton? * Technique: While building the automaton, when you add rules for a nonterminal, include the CONTEXT in which you want to apply that rule (the CONTEXT is the symbols that can legally come after that nonterminal) * This context resolves many of the shift-reduce and reduce-reduce conflicts we see in normal grammars * This technique: LR(1) * Too big * Alternatives: LALR(1): A clever hack on LR(1); smaller, not quite as accurate