2
$\begingroup$

I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table.

Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an artificial start state. '$' is an artificial 'EOS' token.

0.    S -> A $
1.    A -> B b
2.    B -> B a
3.    B -> epsilon

Itemsets:

i0: S -> . A $
    A -> .B b
    B -> .B a
    A -> B . b  ! because B could -> epsilon
    B -> B . a  !    "

i1: S -> A . $

i2: S -> A $ .

i3: A -> B . b  ! from i0
    B -> B . a

i4: A -> B b .  ! from i0 or i3; the LALR algorithm compresses identical states.

i5: B -> B a .  ! from i0 or i3: the LALR algorithm compresses identical states.

I previously had a description on how this would work to parse a simple string. I removed it because I know less now than I did before. I can't even figure out a parse tree for 'ab'.

If someone could show me how I have mis-constructed my itemsets and how I'd reduce the epsilon transition I'd be grateful.

$\endgroup$
2
$\begingroup$

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 a or b".

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

continuing with A:

A: . B 'b'

continuing with B:

B: . B 'a'
B: .

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.

State 0
    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

State 1
    0 $accept: S . $end

    $end  shift, and go to state 4

State 2
    1 S: A .

    $default  reduce using rule 1 (S)

State 3
    2 A: B . 'b'
    3 B: B . 'a'

    'b'  shift, and go to state 5
    'a'  shift, and go to state 6

State 4
    0 $accept: S $end .

    $default  accept

State 5
    2 A: B 'b' .

    $default  reduce using rule 2 (A)

State 6
    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.

$\endgroup$
  • $\begingroup$ Sorry it took me so long to get back to this. I have slightly amended my question; I had an artificial start state already (S). I added the artificial EOI token. The description I had was non-sensical so I removed it. $\endgroup$ – Tony Ennis Dec 13 '14 at 15:19
  • $\begingroup$ ok, I just reread this again. I think per the LALR algorithm, conflating identical states happens. It's actually one of the reasons LALR algorithm makes smaller tables though at some cost - a full LR parser would generate fewer shift/reduce or shift/shift errors. $\endgroup$ – Tony Ennis Dec 13 '14 at 15:31
  • $\begingroup$ The idea that the epsilon transition ends up in state 0 is new to me. Compare to my post. This means that a 'GOTO' would be applied (and why not? there is a 'dot' at the end of the closure...) I was assuming that we had to shift first. I must cogitate on this for a while. $\endgroup$ – Tony Ennis Dec 13 '14 at 15:33
  • $\begingroup$ @TonyEnnis: The epsilon production is no different from any other production, so it gets added by the closure production. However, the closure construction does not add A -> B . b because the closure construction does not examine non-terminals to see if they are nullable. I will make the answer more explicit in a bit. $\endgroup$ – rici Dec 13 '14 at 17:37
  • $\begingroup$ Thank you. I think I have a handle on it now. But if you're bored, please add more detail! I have thought about this some, and I did not think to consider the epsilon as terminal. You were correct in thinking I considered it something that would modify the LALR algorithm. It still may a little later, but not during itemset construction. $\endgroup$ – Tony Ennis Dec 13 '14 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.