# Class 22: Shift-Reduce Parsing (3)

Back to Shift-Reduce Parsing (2). On to Class Cancelled.

Held: Wednesday, 10 March 2004

Summary: Today we conclude our discussion of shift-reduce parsing.

Overview:

• The expression automaton, concluded.
• Some potential problems.
• Other techniques 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.

## The Expression Automaton, Revisited

• State: S00
• Rules:
• exp ::= . exp + term
• exp ::= . exp - term
• exp ::= . term
• term ::= . term * factor
• term ::= . term / factor
• term ::= . factor
• factor ::= . ID
• factor ::= . NUM
• factor ::= . ( exp )
• Edges:
• exp -> S01
• term -> S02
• factor -> S03
• ID -> S04
• NUM -> S05
• ( -> S06
• State: S01
• Rules:
• start ::= exp . EOI
• exp ::= exp . + term
• exp ::= exp . - term
• Edges:
• EOI -> ACCEPT
• + -> S08
• - -> S09
• State: S02
• Rules:
• exp ::= term .
• term ::= term . * factor
• term ::= term . / factor
• Edges:
• * -> S10
• / -> S11
• State: S03
• Rules:
• term ::= factor .
• State: S04
• Rules:
• factor ::= ID .
• State: S05
• Rules:
• factor ::= NUM .
• State: S06
• Rules
• factor ::= ( . exp )
• exp ::= . exp + term
• exp ::= . exp - term
• exp ::= . term
• term ::= . term * factor
• term ::= . term / factor
• term ::= . factor
• factor ::= . ID
• factor ::= . NUM
• factor ::= . ( exp )
• Edges
• exp > S14
• term -> S02
• factor -> S03
• ID -> S04
• NUM -> S05
• ( -> S06
• State: S08
• Rules:
• exp ::= exp + . term
• term ::= . term * factor
• term ::= . term / factor
• term ::= . factor
• factor ::= . ID
• factor ::= . NUM
• factor ::= . ( exp )
• Edges:
• term -> S16
• factor -> S03
• ID -> S04
• NUM -> S05
• ( -> S06
• State: S09
• Rules
• exp ::= exp - . term
• term ::= . term * factor
• term ::= . term / factor
• term ::= . factor
• factor ::= . ID
• factor ::= . NUM
• factor ::= . ( exp )
• Edges:
• term -> S17
• factor -> S03
• ID -> S04
• NUM -> S05
• ( -> S06
• State: S10
• Rules:
• term ::= term * . factor
• factor ::= . ID
• factor ::= . NUM
• factor ::= . ( exp )
• Edges:
• factor -> S12
• ID -> S04
• NUM -> S05
• ( -> S06
• State: S11
• Rules:
• term ::= term / . factor
• factor ::= . ID
• factor ::= . NUM
• factor ::= . ( exp )
• Edges:
• factor -> S13
• ID -> S04
• NUM -> S05
• ( -> S06
• State: S12
• Rules:
• term ::= term * factor .
• State: S13
• Rules:
• term ::= term / factor .
• State: S14
• Rules
• factor ::= ( exp . )
• exp ::= exp . + term
• exp ::= exp . - term
• Edges
• ) -> S15
• + -> S08
• - -> S09
• State: S15
• Rules
• factor ::= ( exp ) .
• State: S16
• Rules:
• exp ::= exp + term .
• term ::= term . * factor
• term ::= term . / factor
• Edges:
• * -> S10
• / -> S11

## 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.
• However, we still have similar conflicts.
• Shift-reduce conflicts include the case in which Follow of the final lhs of the final item overlaps with first of the remainder
• Reduce-reduce conflicts include the case Follow of both left-hand-sides overlap. of the nonfinal item.
• 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.

Back to Shift-Reduce Parsing (2). On to Class Cancelled.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 5 11:47:07 2004.
The source to the document was last modified on Tue Jan 20 23:06:46 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.22.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu