RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Pages

The LR goto action

Background

We've seen the LR shift, reduce and accept actions. We've also provided a motivation for state management in LR parsing. In this section, we will introduce the final LR parse action which is related to state management.

The goto action

Definition

In the LR(0) goto action, we transition from one parse state to a different parse state.

Application

Example

S → aA
S → aB
A → a
B → b

Recall that this grammar is not LL(1). However, it has the following conceptual states:

  1. aa - We are in a state where none of the input symbols have been reduced to a nonterminal
  2. aA - We are in an intermediate state where one reduction has occured but we have not yet reduced to our starting nonterminal
  3. S - We are in a state where we have reduced to our start symbol and can now accept the string as part of our language

Even though we've seen one conceptual example of what parse states mean, their use may still not be entirely clear. The use of parse states will become more apparent in formal LR(0) parse examples.

A rudimentary conceptual understanding of these states is helpful to understand the setup of the LR(0) parse table, which will be introduced shortly.

Conclusion

We have provided a rough introduction to the LR goto action. With this concept, we can now introduce the LR(0) parse table.