CODEWITHSUNDEEP
parsingcompiler-constructiondfalr-grammar
xilpex
xilpex

Reputation: 3237

LR parser for epsilon

I've recently implemented an LR(1) parser (without epsilon), and have been wondering how I would implement epsilon in the parsing algorithm (note: not the table construction algorithm). This is my grammar:

start -> A b
b -> B | \epsilon

I've followed the steps listed here and got this as a result from my parser (table):

state 0 on symbol start: 1
state 0 on symbol A: shift and goto state 2
state 1 on symbol $: accept
state 2 on symbol b: 3
state 2 on symbol B: shift and goto state 4
state 2 on symbol $: reduce b → 
state 3 on symbol $: reduce start → A b
state 4 on symbol $: reduce b → B

The table listed above is correct, but when I try to parse A, there is no transition:

error: no transition in table for (0, 'b')

This is how my stack looks:

[0]
[0, 'A', 2]
[0, 'b'] # stack during the error

Now, I notice that there is not a state on the top, which is a problem, but I have no clue what to add after it. My paring code is based upon the one over here.

Upvotes: 0

Views: 652

Answers (1)

rici
rici

Reputation: 241911

That stack is definitely wrong, and it seems likely that it is leading to the error (although hard to say without seeing the code).

Here's what you would expect:

            LOOK
STACK       AHEAD   ACTION
[0]         A       shift, goto state 2    pushes A (shift) and new state (2)
[0 A 2]     $       reduce b ->            pops 0 pairs, pushes b (reduce) 
[0 A 2 b]           + goto 3               action for b in state 2
[0 A 2 b 3] $       reduce start -> A b    pops 2 pairs, pushes start (reduce)
[0 start]           + goto 1               action for start in state 0
[0 start 1] $       accept

If I had to wager a guess, I'd say that you are popping one symbol for an ε right-hand side. As I've mentioned elsewhere (including the answer you cite), ε is nothing. It is zero symbols and popping it pops nothing.

Upvotes: 2

Related Questions