Search code examples
parsingcompiler-constructionlr-grammar

Why are the only the states 0 and 2 present in line 8?

LR Parsing:

LR parsing

LR Parsing Table:

LR Parsing Table

In line 7, we reduce by T->T*F.

And State 7 on T does not have any transition.

In line 8, why do we have only the states 0 and 2?

Solution

  • At step 7, we reduce T→T*F, which means that:

    1. We pop the right-hand side off of the stack, leaving only the state 0 corresponding to symbol $.

    2. We consult the goto transitions of state 0 (the new top of the stack) for the left-hand symbol T. That says we should goto state 2.

    3. We push the new state 2 onto the stack along with the associated symbol T.

    At the end, the stack is 0 2 with symbols $ T, as shown at step 8.

    This is well-described in the text and pseudocode algorithms of the excellent book from which those charts were copied.