Course contentsShow
← Computer Science
Lesson 1965 of 2,87244. Lexical Analysis and ParsingFree lesson

Building the LR(0) Automaton

Constructing the canonical collection of LR(0) item sets using closure and goto operations.

Building the LR(0) Automaton

What you'll learn: How to systematically construct the complete collection of LR(0) item sets that drive a shift-reduce parser.

The Core Idea

Building the LR(0) automaton means creating a finite state machine where each state represents a set of LR(0) items—positions in production rules where the parser might be during bottom-up parsing. You construct this automaton using two key operations: closure (expanding item sets to include all possible parsing paths) and goto (transitioning between states based on grammar symbols).

Think of it like mapping out all possible "checkpoints" during parsing. Each checkpoint tracks what rules you might be in the middle of recognizing, and which symbols would advance you to the next checkpoint.

The Construction Process

1. Closure Operation

Starting with one or more items in a set, closure expands it by adding items for any non-terminals immediately after a dot. If you have A → α·Bβ, you add all items B → ·γ for every production B → γ.

Example: If your item is E → E·+T, and you have production T → T*F, closure doesn't add anything (no non-terminal after the dot). But E → ·T+F would trigger adding T → ·T*F and all other T-productions.

2. Goto Operation

goto(I, X) computes the next state when you see symbol X from state I. Move the dot past X in all applicable items, then apply closure to the result.

3. Building the Canonical Collection

Start with closure of S' → ·S (augmented start). Repeatedly apply goto on every state and every grammar symbol until no new states emerge. This creates your complete automaton.

Key Takeaway: The LR(0) automaton is built by systematically applying closure (to expand item sets) and goto (to transition between states), creating the canonical collection of all reachable parsing configurations.