Compiler Design

LR(0) & SLR Parsing

PreviousNext

LR(0) Items & Augmented Grammar

An LR(0) item of a grammar is a production rule with a dot (•) inserted somewhere in the right-hand side. The dot indicates how much of a production we have scanned so far.

Example: For production rule A → X Y Z, we have four items:
  • A → • X Y Z (No symbols read yet)
  • A → X • Y Z (Just read X, expecting Y next)
  • A → X Y • Z (Read X and Y, expecting Z next)
  • A → X Y Z • (Fully read, ready to reduce)

An Augmented Grammar introduces a new start symbol S' and a production S' → S. This serves as a unique indicator that the parser should successfully halt and accept the input when it reduces to the start symbol.

Closure and Goto Operations

The parser builds a Deterministic Finite Automaton (DFA) whose states represent sets of items. Two functions, Closure and Goto, are used to construct these state sets.

If I is a set of items, CLOSURE(I) is constructed as follows:

  1. Initially, add every item in I to CLOSURE(I).
  2. If A → α • B β is in CLOSURE(I) and B → γ is a production, then add the item B → • γ to the closure, if it is not already there.
  3. Repeat until no more items can be added.

If I is a set of items and X is a grammar symbol (terminal or non-terminal), GOTO(I, X) is defined to be the closure of the set of all items of the form A → α X • β such that A → α • X β is in I.

Intuitively, GOTO describes the state transition in the parser DFA when the symbol X is successfully shifted.

Simple LR (SLR) Parsing Table

SLR(1) tables are constructed from the LR(0) states DFA, but it uses FOLLOW sets to place reduce actions.

SLR Table Construction Rules:

  1. If A → α • a β is in state I_i and GOTO(I_i, a) = I_j, set ACTION[i, a] = shift j (for terminal a).
  2. If A → α • is in state I_i, set ACTION[i, a] = reduce A → α for all terminals a in FOLLOW(A) (where A ≠ S').
  3. If S' → S • is in state I_i, set ACTION[i, $] = accept.
  4. If GOTO(I_i, A) = I_j, set GOTO[i, A] = j (for non-terminal A).

SLR Conflicts:

  • Shift/Reduce Conflict: A state contains both a shift item (expecting terminal a) and a reduce item, and a is in the FOLLOW set of the reduced non-terminal.
  • Reduce/Reduce Conflict: A state contains two different reduce items, and their FOLLOW sets share a common terminal, leaving the parser unable to decide which rule to apply.
Bottom-Up Parsing & Shift-ReduceSolved Problem: SLR