Content

1. Shift-Reduce Parsing
   1. LR Parsing
      1. Table-Driven
   2. LR(0)
      1. Table Construction
   3. SLR(1)
      1. Table Construction
   4. LR(1)
      1. Table Construction
   5. LALR(1)
      1. Table Construction

Shift-Reduce Parsing

Handle: term to be replaced by non-terminal

LR Parsing

• Scanned from left to right (L)
• Rightmost derivation (R)
• Superset of LL(1)

Table-Driven

Action[s,a]: when state s on top of stack, a is next input token, what to do?
Goto[s,X]: when state s on top of stack, a reduction to non-terminal X, what's the new state?

If Action[st,a] is reduce Y -> X1...Xk, pop k states off, leaving su on top. Push new state Goto[su,Y] onto stack. Input token unchanged.

LR(0)

Table Construction

1. Let F = {I0,I1,...,In} be the collection of configurating sets for grammar G
2. Action[]
   1. If A -> u• in Ii && A != S', Action[i,a] = reduce A -> u for all input
   2. If S' -> S in Ii, Action[i,$] = accept
   3. If A -> u•av in Ii && successor(Ii,a) = Ij, Action[i,a] = shift j
3. Goto[]
   1. If successor(Ii,A) = Ij, Goto[i,A] = j
4. Else error
5. Initial state S' -> •S

Limitations

• Conflicts
  • Shift-reduce conflict
    • A -> u•av and B -> w• cannot be in the same set
  • Reduce-reduce conflict
    • Only one A -> u• in the same set
• Not many grammars meet the requirements
  • A -> •ε: shift-reduce conflict
  • T -> id[E]: T -> id• & T -> id•[E] shift-reduce conflict
• Only consider what it has seen so far (no lookahead)

SLR(1)

Simple version of LR(1). Every SLR(1) grammar is a LR(1) grammar. Takes the least space.

• 1 symbol lookahead (1): Follow()
• Avoid conflicts
  • Shift-reduce conflict
    • A -> u•av and B -> w• cannot be in the same set if a in Follow(B)
  • Reduce-reduce conflict
    • A -> u• and B -> w• in the same set only if Follow(A) ∩ Follow(B) = ∅

Table Construction

1. Let F = {I0,I1,...,In} be the collection of configurating sets for grammar G
2. Action[]
   1. If A -> u• in Ii && A != S', Action[i,a] = reduce A -> u for all a in Follow(A)
   2. If S' -> S in Ii, Action[i,$] = accept
   3. If A -> u•av in Ii && successor(Ii,a) = Ij, Action[i,a] = shift j
3. Goto[]
   1. If successor(Ii,A) = Ij, Goto[i,A] = j
4. Else error
5. Initial state S' -> •S

LR(1)

Canonical version of LR(1). Want's a smaller (more precise) set of lookahead symbols. Takes the most space.

• Expected lookahead symbols: a subset of Follow()
  • Only meaningful for reduction items
• Avoid conflicts happening from different contexts
  • Shift-reduce conflict
    • A -> u•av, b and B -> w•, a cannot be in the same set
  • Reduce-reduce conflict
    • A -> u•, a and B -> w•, a cannot be in the same set
• Splits states based on lookahead sets -> more states
  • Worst case: the power set of Follow() containing all terminals

Table Construction

• For transition A -> u•av to A -> ua•v, propagate expected lookaheads
• For B -> •C to be added as closure of A -> u•Bv which has expected lookaheads t,s,..., add First(vt) ∪ First(vs) ∪ ... to the expected lookaheads

• I4: parsing the first X; I7: parsing the second X

LALR(1)

Tradeoff version between SLR(1) and LR(1). Number of states same as for SLR(1) and LR(0). Subset of LR(1); superset of SLR(1).

• Reduce number of states from LR(1)
  • A -> a, s1 and A -> a, s2, combined into A -> a, s3 where s3 = s1 ∪ s2
  • May have come conflicts unresolved

• Conflicts

  • Shift-reduce conflict won't exist unless it exists in LR(1)

  • If reduce-reduce conflict, not LALR(1)

      C -> e, c
      B -> e, d
      merged with
      C -> e, d
      B -> e, c
    

Table Construction

1. Brute force: merge sets of LR(1)
2. Step-by-step: merge as you go