CSCI 310 Day 12

1. Walking through state construction (informally) using

   0   Start -> S$
   1   S -> S; S
   2   S -> id := E
   3   S -> print(L)
   4   E -> id
   5   E -> num
   6   E -> E + E
   7   E -> (S,E)
   8   L -> E
   9   L -> L, E
   

2. An LR parsing table
   1. rows are states
   2. columns are terminals or variables
   3. for (i,j) j a terminal, we can either
      • shift (push the state of possible productions onto the stack) or
      • reduce by some production (pop as many states of the stack as there are symbols on right hand side, then transition.
      • accept (if $ was seen in a correct place)
   4. for (i,j) j a variable, we record a goto action -- the state we should transition to when a production has reduced to this variable.

   5. ideally, we only have one possibility for each (i,j). A shift/reduce error occurs when we could either do a reduction (because the configuration has the dot at the far right) or a shift. Sometimes we can get reduce/reduce errors as well...

3. More formally we discuss
   1. the closure of a state (adding productions for the variables to the right of the dot)
   2. the goto of a state and symbol (constructing a state that moves the dot past the symbol)
   3. the finite machine is then a matter of constructing the initial state and then repeatedly adding the state constructed by goto into the states, and the transition into the machine definition.