LR(0) and SLR(1) Parsing

• Bottom-Up Parsing and Shift-Reduce: handles, viable prefixes, shift-reduce and reduce-reduce conflicts.
• FIRST and FOLLOW sets (see the note FIRST and FOLLOW Sets): SLR reductions are placed on FOLLOW of the head.

CLOSURE(I)
    J <- I
    repeat
        for each item A -> alpha . B beta in J, B a nonterminal
            for each production B -> gamma
                add B -> . gamma to J
    until no item is added
    return J

GOTO(I, X)
    return CLOSURE({ A -> alpha X . beta : A -> alpha . X beta in I })

LR0-COLLECTION(G')
    C <- [ CLOSURE({ S' -> . S }) ]
    for each state I in C, in order
        for each symbol X appearing after a dot in I
            J <- GOTO(I, X); if J not in C then append J to C
    return C

Filling the table

1. If $A \to \alpha \cdot a \beta$ is in $I_i$ with $a$ a terminal and GOTO($I_i, a$) $= I_j$: ACTION[$i, a$] $=$ shift $j$.
2. If $A \to \alpha \cdot$ is in $I_i$ with $A \ne S'$:
   • LR(0): ACTION[$i, a$] $=$ reduce $A \to \alpha$ for every terminal $a$ and $\text{\textdollar}$.
   • SLR(1): ACTION[$i, a$] $=$ reduce $A \to \alpha$ for every $a \in \text{FOLLOW}(A)$ only.
3. If $S' \to S \cdot$ is in $I_i$: ACTION[$i, \text{\textdollar}$] $=$ accept.
4. GOTO[$i, B$] $= j$ for each nonterminal $B$ with GOTO($I_i, B$) $= I_j$.

The LR driver

LR-PARSE(ACTION, GOTO, input)
    push state 0
    a <- first token of input$
    loop
        s <- state on top of stack
        if ACTION[s, a] = shift t then push t; a <- next token
        else if ACTION[s, a] = reduce A -> beta
            pop |beta| states; t <- top state; push GOTO[t, A]
        else if ACTION[s, a] = accept then return success
        else error

A grammar that is LR(0)

S -> C C
C -> c C | d

A grammar that is SLR(1) but not LR(0)

• $I_2 = \{E \to T \cdot,\; T \to T \cdot * F\}$
• $I_9 = \{E \to E + T \cdot,\; T \to T \cdot * F\}$

A grammar that is not SLR(1)

S -> L = R | R
L -> * R | id
R -> L

Quick classification

• Conflict tests. An LR(0) state has a shift-reduce conflict if it has a complete non-augmented item (head other than the augmented start) and an item with a terminal after the dot; a reduce-reduce conflict if it has two complete reduction items. The augmented completed start item accepts only on the endmarker; it is not a reduce-on-all-terminals item. In SLR, a complete item $A \to \alpha \cdot$ conflicts with a shift on $a$ only if $a \in \text{FOLLOW}(A)$, and two complete items conflict only if their heads' FOLLOW sets intersect.
• SLR never has more conflicts than LR(0). Its reduce entries are a subset of LR(0)'s, on the same automaton. Every LR(0) grammar is SLR(1).
• Same states. LR(0) and SLR use the same automaton, so they have the same number of states; LALR also has that number (next note).
• Item sets and nonterminals. A state reached on a symbol $X$ has every kernel item with $X$ just before the dot; that is why the transitions on a symbol always go to states whose kernel items "just passed" that symbol.
• Error detection. An LR parser never shifts a token that cannot extend the viable prefix, so errors are found at the first wrong token. SLR (and LALR) may do a few extra reductions before reporting the error, but never an extra shift.
• Ambiguous grammars are never LR. A conflict will appear for any LR method. Parser generators still accept ambiguous expression grammars by resolving each conflict with declared precedence and associativity.
• $\varepsilon$-productions and LR(0). A production $A \to \varepsilon$ puts the complete item $A \to \cdot$ into every state whose closure adds $A$-items. If that state also shifts, LR(0) has a conflict. S -> a S b | eps fails LR(0) for this reason, while S -> a S b | a b, for the same language without the empty string, is LR(0).
• GOTO after a reduction is read from the state uncovered by popping $\lvert\beta\rvert$ states, not from the state that held the handle.

• "LR(0) parsers use no lookahead at all." They look at the next token to choose the shift target; they do not use it to decide whether to reduce.
• "SLR needs a different automaton." It reuses the LR(0) automaton; only the reduce entries change.
• "A shift-reduce conflict in SLR means the grammar is ambiguous." The L = R grammar is unambiguous and still conflicts.

• Count states. Build the canonical LR(0) collection carefully; the count is the same for LR(0), SLR and LALR tables.
• Closure and goto questions. "Which items are in GOTO($I_0$, ()?" Take the kernel items that move the dot past (, then close.
• Is the grammar LR(0) or SLR(1)? Find states with complete non-augmented reduction items; check what else they contain and, for SLR, FOLLOW of their heads. Handle the completed augmented-start accept action only on the endmarker.
• Count conflicts or reduce entries. In LR(0), a complete non-augmented production item reduces in every ACTION column (all terminals and $\text{\textdollar}$); in SLR, only in its head's FOLLOW columns. The completed augmented-start item instead accepts only on $\text{\textdollar}$.
• Trace the state stack. Questions give a table and ask for the stack after $k$ moves; pop $\lvert\beta\rvert$ states on each reduction and push GOTO of the uncovered state.
• Containment. LR(0) $\subset$ SLR(1) $\subset$ LALR(1) $\subset$ LR(1) as classes of grammars, all strict. LR(0) can fail with $\varepsilon$-productions or with lists such as A -> b A | b.

• Bottom-Up Parsing and Shift-Reduce: prerequisite. Handles, viable prefixes and conflicts.
• CLR(1) and LALR(1) Parsing: dependent. Lookahead in the items removes SLR's false conflicts.