Today in CS362: Shift-Reduce Parsing, Formalized
Missing
Adam
Admin
Sorry that grading is taking so long
Project, Phase 2 assigned.
To be assigned to a group, send me
* Comments on your experiences with group work
* Comfort ratings (1-6 scale, 1=low, 6=high) for
Java, Assembly, the topics of this course
Please show up to lab tomorrow
Overview
Building LR(0) automata
The states
The transitions
Some potential problems
An improvement, SLR automata
Other techniques for building shift-reduce automata
Shift-Reduce Parsing
Move along the input string from left-to-right
For each token you find, either shift onto a stack
or reduce what's on the stack, which is a RHS,
to the corresponding LHS, which is a nonterminal
To do shift-reduce parsing, you need to build the
"black box" that tells you whether to shift or reduce
for each input token and each "state"
Formalizing the procedure we used on Friday
* Build sets of "extended productions" (each set is
a state)
* Made edges between them
* Set up the whole shebang
producedure closure(state)
repeat
If state includes an extended-production of the form
N -> stuff . Xi morestuff
then you should also add
Xi -> . whatever
for each production with Xi on the left-hand-side
until no more rules get added
end closure
procedure goto(state,symbol)
State nextState = new State();
for each extended production of the form
N -> stuff . symbol morestuff
in state
add N -> stuff symbol . morestuff to nextState
return closure(nextState)
end goto
To build the whole LR(0) automataton
S0 = closure({ S' -> . S $ })
while there are "unprocessed" states
pick some unprocessed state, Si
for each symbol, s
newstate = goto(Si,s)
if newstate is not already in the automaton
add it
end if
end for
note that Si is now processed
end while
Mark the state that contains
S' -> S $ .
as a "success state"
Let's try the procedure on a simple grammar
a^nb^n | a^nc^n
S -> B
| C
B -> a B b
| epsilon
C -> a C c
| epsilon
Symbols: S, B, C, a, b, c, $
S0 = closure({ S' -> . S $ })
S' -> . S $
S -> . B
S -> . C
B -> . a B b
B -> .
C -> . a C c
C -> .
goto(S0,S) = S1
goto(S0,B) = S2
goto(S0,C) = S3
goto(S0,a) = S4
goto(S0,b) = S5
goto(S0,c) = S5
goto(S0,$) = S5
S1:
S' -> S . $
S2:
S -> B .
S3:
S -> C .
S4
B -> a . B b
C -> a . C c
B -> . a B b
B -> .
C -> . a C c
C -> .
goto(S4,a) = S4
S5:
NOTHING (Our failure state)