LR(0) Parsing Tables
What You'll Learn
You'll learn how to construct the action and goto tables from an LR(0) automaton to drive shift-reduce parsing decisions.
From Automaton to Tables
Once you've built the LR(0) automaton with its states and transitions, you need to convert it into concrete data structures the parser can use: the action table and the goto table.
Think of these tables as a decision matrix. When the parser is in a particular state and sees a specific token (or needs to handle a nonterminal), it looks up what to do in these tables.
The Action Table
The action table has rows for each state and columns for each terminal symbol (token). Each cell contains one of four possible actions:
- Shift n: Push the current token and move to state n
- Reduce r: Apply production rule r and pop corresponding symbols
- Accept: Parsing succeeds (only in the final state with end marker)
- Error: Invalid syntax detected
You populate this by examining each state's items:
- If an item has a dot before a terminal (like
E → E · + T), add a shift action - If an item is complete (dot at end, like
E → E + T ·), add a reduce action for that production
The Goto Table
The goto table has rows for each state and columns for each nonterminal. It tells the parser which state to transition to after performing a reduce operation.
You fill this using the automaton's transitions: if state i has a transition on nonterminal A to state j, then goto[i, A] = j.
Working Together
During parsing, the action table drives what to do with tokens, while the goto table handles where to go after reductions. Together, they implement the shift-reduce decision logic you learned about earlier.
Key Takeaway: LR(0) parsing tables translate the automaton's states and transitions into action (for terminals) and goto (for nonterminals) lookup tables that guide shift-reduce parsing decisions at runtime.