The ACTION and GOTO tables are essential data structures that guide the parser through the parsing process. These tables are precomputed based on the grammar and the states of the LR(1) automaton. Together, they tell the parser whether to shift, reduce, accept, or transition to a new state based on the current state and input.

Action table

The ACTION table dictates how the parser should act based on the current state and the next input token (the lookahead). The possible actions include:

1. Shift: The parser reads the next token from the input and transitions to a new state.
2. Reduce: The parser recognizes a complete production (right-hand side of a grammar rule) and applies a reduction to substitute the rule's left-hand side.
3. Accept: The parser successfully recognizes the entire input and ends the parsing process.
4. Error: If no valid action is found, it indicates a syntax error in the input.

The ACTION table is indexed by a combination of:

• Current state (which reflects the parser's current position in the input)
• Lookahead token (the next token in the input)

Conditions for an ACTION in the table

1. Shift Action:

   If a state contains an item of the form Anything -> ... . token ... (where the dot is before a token) and the token is in the input, the parser shifts to the next state specified by the transition for that token. This means the parser reads the token and moves forward.

2. Accept Action:

   If a state contains an item like S -> ... . (where the dot is at the end of the rule), and the token is the end-of-input symbol ($), and the current item corresponds to the start symbol of the grammar, the parser accepts the input, indicating that it has successfully parsed the input string.

3. Reduce Action:

   If a state contains an item like A -> ... . (where the dot is at the end of a rule), and the lookahead token matches the expected token, the parser reduces by applying the grammar rule. This involves replacing the right-hand side of the rule with its left-hand side (non-terminal) in the input stack.

GOTO table

The GOTO table controls transitions between states based on non-terminal symbols. After a reduce operation (where a rule's right-hand side is reduced to its left-hand side non-terminal), the parser needs to transition to a new state based on the non-terminal that was just reduced.

The GOTO table is indexed by:

• Current state (which reflects where the parser is after the reduction)
• Non-terminal symbol (the left-hand side of the rule that was just reduced)

Conditions for a GOTO in the table

If a state contains an item of the form Anything -> ... . Symbol ... (where the dot is before a non-terminal symbol), the parser follows the GOTO transition to the next state based on that non-terminal. This happens after a reduction, when the parser has recognized the non-terminal and needs to decide what to parse next.

Constructing the ACTION and GOTO tables

For more info visit the dotlr library docs