Class 18: Shift-Reduce Parsing, Concluded

Held Wednesday, October 9, 2002

Summary

Today we conclude our discussion of shift-reduce parsing.

Notes

• Sorry, but the trustees voted to demolish Darby after Basketball and Volleyball seasons in 2003-2004. Since the trustees are responsible for managing Grinnell's resources, I think it's going to be harder to convince them it's a bad idea after that vote.
• For those of you interested in the strategic planning process, a Web site is available at http://www.grinnell.edu/offices/institutionalplanning/strategicplanning/
  • I found the overview of Grinnell College and its Environment particularly interesting.
• I don't know about you, but I always hated having big assignments due the day before break. I've therefore extended the due date for phase 2 of the project.
  • You should still start thinking about it before break.
• Warning: I'm ending today's class about 20 minutes early.
• Note that it's really frustrating to try to put groups together when you folks don't answer simple questions on time. I understand delaying on homework assignments, but not on things that should take less than ten minutes.
• We'll talk about groups at the start of class.

Assignments

• Project, Phase 2: Parser.

Overview

• Some potential problems
• Other tehcniques for computing shift-reduce automata

Using LR(0) Automata

• It is fairly easy to use these automata.
• Begin in state 0 with state 0 on the stack
• For each input token, follow the appropriate edge and push the token and destinatin state on the stack.
• If you hit a state containing N ::= alpha . then reduce (pop the rhs off the stack and push the left hand side)
  • After reducing, follow the edge corresponding to the left-hand side.

Other LR Issues

Conflicts in LR Automata

• At times, there are conflicts in LR automata. What kinds of conflicts?
• A state may include a final item (one in which the position marker is at the end) and a nonfinal item.
  • This is called a shift-reduce conflict
• A state may include two different final items.
  • This is called a reduce-reduce conflict
  • Can we have reduce-reduce conflicts in unambiguous grammars?
• Can we have a shift-shift conflict?

SLR Automata

• You may have noted (e.g., from our example in the previous class) that LR(0) automata can be overly aggressive in choosing to reduce.
  • Such automata typically reduce whenever we've reached the end of a right-hand side.
• SLR automata only reduce when the next token is in Follow of the left-hand side of the reduction.
• Such choices may help us resolve reduce-reduce conflicts.
• Hence, SLR automata are used more commonly in parser generators.

LR(1) Automata

• LR(1) automata require a more complicated construction process, one that involves lookahead.
• In effect, instead of using the Follow table (as SLR automata do), LR(1) automata build more specific follow tables that correspond to the possible follow symbols according to a particular context.
• Each LR(1) item contains not just an augmented production, but also a token that can follow the nonterminal when we've reached the current state.
• The tokens are inserted by the closure routine.
  • If we have N ::= alpha . M beta then when we insert the M items, we indicate that each of them can be followed by the tokens in first(beta)
  • If beta is nullable, then the M items can also be followed by whatever can follow N (in the given LR(1) item).
• That's all we're covering in this class.
  • Someone can make LR(k) and LALR parsing the topic of their presentation.