# Class 21: Shift-Reduce Parsing (2)

Back to Shift-Reduce Parsing (1). On to Shift-Reduce Parsing (3).

Held: Monday, 8 March 2004

Summary: Today we consider how to build shift-reduce automata and the tables that represent them.

Related Pages:

Overview:

• Building an LR(0) automaton for expressions
• Running the automaton
• Building LR(0) automata

## LR(0) Automata

• The simplest LR parsers are based on LR automata with no lookahead.
• Wait! You may say, How can we build a parser with no lookahead?
• It turns out the the 0 refers to the lookahead used in constructing the automata, not (in this case) to the lookahead in running them.
• The states of all LR parsers are sets of extended productions (also called items), representing the states of all possible parses of the input (more or less)
• Each production is extended with a position (where in the parse we may be)
• Each production is may be extended with lookahead symbols (none in LR(0) automata).
• We begin building an LR(0) parser by augmenting the grammar with a simple rule in which we add an end of input (\$) to the start symbol.
```S' ::= S \$
```
• The initial state of an LR(0) parser begins with
```s' ::= . s \$
```
• This means when we begin parsing, we are ready to match an `S` and the end-of-input symbol
• We then augment this with the other things that we might match on our way to building an S and end of input. What are those things? Anything that might build us an S. What have we seen of those things? Nothing, yet.
• For our expression grammar, we might write
```s ::= . exp \$
```
• Since we are ready to see an exp, we need to include the rules that might derive an exp.
```exp ::= . exp + term
exp ::= . exp - term
exp ::= . term
```
• Of course, in this case, if we're waiting to see a term, then we also need to add the term rules (and then the factor rules).
```S ::= . exp \$
exp ::= . exp + term
exp ::= . exp - term
exp ::= . term
term ::= . term MULOP factor
term ::= . factor
factor ::= . id
factor ::= . num
factor ::= . ( exp )
```
• We make new states in the automaton by choosing a symbol (terminal or nonterminal) and advancing the here mark (period) over that symbol in all rules, and then filling in the rest.
• For example, if we see an exp in state 0, we could be
```s ::= exp . \$
exp ::= exp . + term
exp ::= exp . - term
```
• If we see a plus sign in that state, we could only be making progress on one rule, giving us
```exp ::= exp + . t term
```
• But now, we're ready to see a `term`, so we need to fill in all the items that say ready to see a term
```exp ::= exp + . term
term ::= . term MULOP factor
term ::= . factor
factor ::= . id
factor ::= . num
factor ::= . ( exp )
```
• If we do indeed see a T, we advance the here mark and get to
```exp ::= exp + term .
term ::= term . MULOP factor
```
• The first part suggests that we may be at the end of an `exp`. The second suggests that we may be in the midst of a `term`. How do we decide which it is? By context (and a little lookahead in some cases).
• If the next symbol is a MULOP, apply the continuing rule
• If the next symbol is in Follow[exp], apply the completed rule

## Using the Automaton

• The stack keeps track of the state of the automaton and the partially processed trees.
• When you see a symbol that corresponds to an edge, shift that symbol and push the new state.
• When a state contains a completed production and you see a symbol in Follow[lhs], pop the state/symbol pairs and reduce. If all goes well, you can then follow an edge based on the lhs.
• Example in class.

## Constructing LR(0) Automata, Formalized

• Let us now formalize what we did.
• We need a method that fills in the rest whenever we advance the mark. We'll call this `closure`
```closure(State S)
repeat
for each item, n ::= alpha . m beta in S
for each production M ::= gamma
add m ::= . gamma to S
end for each production
end for each item
until no changes are made to S
return S
end closure
```
• We need a method that describes the edges in the automata. We'll call this `goto`
```goto(State S, Symbol sym)
newS = {}
for each item n ::= alpha . sym beta in S
newS = newS union { N ::= alpha sym . beta }
end for
return closure(newS)
end goto
```
• Finally, we can build the automaton as follows
```S0 = { s' ::= . s \$ }
S0 = closure(S0);
while there are unmarked states
pick an unmarked state, S
mark S
for each symbol, sym, add state goto(S,s) with edge labelled s
end while
```

Back to Shift-Reduce Parsing (1). On to Shift-Reduce Parsing (3).

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:06 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.21.html`.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu