Your states and itemsets are not quite correct. The epsilon production must appear in relevant itemsets, and you have combined two states into one, which would produce a shift-reduce conflict if the epsilon production were added to the itemset (which should be done).
The following was generated with bison (using the
--report=all command-line option); it differs from the theoretic model because the grammar has been "augmented" with an extra start symbol and an explicit end-of-input marker (
$end). Also, it has done some table compression, so in the action tables, you can think of
$default as meaning "either
It is worth explaining how State 0 comes about, since it shows how epsilon productions are handled (no differently from other productions).
We start with
$accept: . S $end, by definition. (
$accept is the starting state). Then the closure rule is applied as long as possible. Remember that the closure rule is: If any item in the itemset, the
. is immediately before a non-terminal, add all the productions for that non-terminal with an initial
.. Hence we add:
S: . A
A: . B 'b'
B: . B 'a'
We can't apply closure any longer, so we're done. Since the state now has an item with the dot at the end (the epsilon production for B), a reduction is possible.
0 $accept: . S $end
1 S: . A
2 A: . B 'b'
3 B: . B 'a'
4 | .
$default reduce using rule 4 (B)
S go to state 1
A go to state 2
B go to state 3
0 $accept: S . $end
$end shift, and go to state 4
1 S: A .
$default reduce using rule 1 (S)
2 A: B . 'b'
3 B: B . 'a'
'b' shift, and go to state 5
'a' shift, and go to state 6
0 $accept: S $end .
2 A: B 'b' .
$default reduce using rule 2 (A)
3 B: B 'a' .
$default reduce using rule 3 (B)
In State 0, the closure rule has added the epsilon production (line 4). Furthermore, no item in the state 0 itemset has the point before a terminal. So with any lookahead, the parser is forced to reduce the epsilon production, after which it will use the
goto function for state 0 to decide to move to state 3. (In your state machine, states 0 and 3 are conflated, but I do not believe this is correct.) State 3 will definitely shift a terminal; with the input
ab$end, it will shift the
a and move to state 6, which will then reduce a
B. And so on.