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)