6.2 LR Items and LR Parsing Intuition

An LR parser does not remember the whole stack as raw tokens. It remembers a state from a finite automaton built from LR items. An item is a production annotated with a dot that records how much of its right side has been recognized:

E -> E + . T     // E + has been recognized; now expect T
E -> E + T .     // the production is complete and may be reducible

The dot is not a source token. It is a parser-design marker. A set of items describes all grammar situations compatible with the current viable prefix. That set becomes an automaton state.

Closure: Include What the Dot Implies

Start with an augmented grammar S' -> Program. The initial item is:

S' -> . Program

If the dot stands before a nonterminal, the parser may need to recognize any of that nonterminal's productions. closure adds them with their dots at the beginning, recursively:

Program -> . StmtList EOF
StmtList -> . Stmt StmtList
StmtList -> . epsilon
Stmt -> . let IDENT = Expr ;
Stmt -> . print Expr ;

An epsilon production is complete at once: StmtList -> . represents a possible reduction, but whether it is permitted depends on the LR family and lookahead. Closure is a statement of possible parser situations, not an instruction to reduce immediately.

GOTO: Advance the Dot Through a Symbol

GOTO(I, X) advances the dot over grammar symbol X in every item of state I where X follows the dot, then takes closure of the result. This becomes a labeled automaton edge.

I:  Expr -> Expr . + Term
    Expr -> Expr . - Term

GOTO(I, +):
    Expr -> Expr + . Term
    Term -> . Factor
    Factor -> . NUMBER
    Factor -> . ( Expr )

Edges labeled by terminals become shift transitions. Edges labeled by nonterminals become GOTO transitions after a reduction. The same construction makes a parser state machine rather than a pile of special cases: state plus lookahead determines one action, and a reduction followed by GOTO restores the context the reduced phrase belongs to.

From Item Sets to Actions

In a canonical LR(0) view:

• An item A -> alpha . a beta supplies a shift on terminal a to GOTO(I, a).

• An item A -> alpha . proposes a reduction by A -> alpha.

• S' -> Program . supplies accept on EOF.

The word proposes is important. LR(0) reduces completed items on every lookahead, which is often too coarse. SLR restricts reductions using FOLLOW; LR(1) keeps lookahead inside items. Those refinements are not different machines; they improve the information used to decide which proposals are valid.

Build One State by Hand

Take S' -> E, E -> E + n | n. Begin with S' -> . E. Closure adds both E -> . E + n and E -> . n, because the dot is before E. Now apply GOTO(I, n): only E -> . n advances, producing E -> n .. That state says a number has formed an E and is ready to reduce; it does not say every future token permits that reduction. The lookahead policy comes from the LR variant.

Apply GOTO(I, E) instead. The two relevant items become S' -> E . and E -> E . + n. One state can therefore contain both “the complete input may accept at EOF” and “a plus may extend this E.” That is the core LR insight: state summarizes exactly which continuations remain possible after the prefix, without reparsing that prefix.

The Full LR(0) Automaton

Continuing the hand construction, the grammar S' -> E, E -> E + n | n has only five LR(0) states:

I0: S' -> . E        I1: S' -> E .         I2: E -> n .
    E -> . E + n         E -> E . + n
    E -> . n
I3: E -> E + . n     I4: E -> E + n .

The edges between states (GOTO/shift) form a small table:

I1 holds both S' -> E . and E -> E . + n, showing one state can simultaneously propose accept and allow shifting +. I2 and I4 are reduce-only states with a single completed item. Comparing this automaton with the parse table from the previous section reveals exactly where the state numbers beside symbols come from.

Reading the Dot Correctly

• Dot before a terminal: a shift may be possible on that terminal.

• Dot before a nonterminal: closure must add ways to begin that nonterminal.

• Dot at the end: a reduction is a candidate, never an unconditional command.

• Identical item sets are the same state even if reached by different paths; reuse them rather than cloning the automaton.