After reduction, which state will parser go?

Question

I use Bison output file to analyze the state (machine) transformation of parser, I find when parser deduce a rule, it goes back to a previous state, but sometimes it goes one state back, sometimes it goes two or three states back. Can anyone tell me what is the rule that determine to which state the state machine will go back, after finished a deduction?

Thanks in advance.

Answer 1

When an LR(k) machine performs a reduction, it pops the right-hand side of the production off the parser stack, revealing the state in which parsing of the production started. It then looks up the reduced non-terminal in the GOTO table for that state.

So the number of entries popped off the parser stack will be the number of symbols on the right-hand side of the reduced production. (In theory, an LR parser could optimize by not pushing all symbols onto the stack, which would allow it to pop fewer symbols off the stack. But as far as I know, bison doesn't do this particular optimization, because it would dramatically complicated the interface.)