0

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.

xilpex
  • 3,097
  • 2
  • 14
  • 45

1 Answers1

2

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.

rici
  • 234,347
  • 28
  • 237
  • 341
  • Ah, ok. I forgot not to pop epsilon. Thanks! – xilpex May 08 '20 at 04:49
  • One last question-- I was reading a few posts about LR(1) and epsilon, and FOLLOW sets were mentioned. What do FOLLOW sets have to do with this? – xilpex May 08 '20 at 04:51
  • As with the pretty PDA diagrams, bison has a nice trace facility which will tell you exactly what the parser is doing at each step, including stack printouts. – rici May 08 '20 at 04:51
  • FOLLOW sets are not used in CLR, so nothing. – rici May 08 '20 at 04:53
  • Most likely got mixed up :-) – xilpex May 08 '20 at 04:53
  • They're used to compute SLR items, though. Maybe that's what the posts were about. Would have to see the posts. – rici May 08 '20 at 04:55