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