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.
- 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.
- 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:
- State: S03
- State: S04
- State: S05
- 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
- State: S13
- State: S14
- Rules
- factor ::= ( exp . )
- exp ::= exp . + term
- exp ::= exp . - term
- Edges
- ) -> S15
- + -> S08
- - -> S09
- State: S15
- State: S16
- Rules:
- exp ::= exp + term .
- term ::= term . * factor
- term ::= term . / factor
- Edges:
- 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?
- 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 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.