LR Parsing

LR Parsing

1. General Engine

LR parsing drives a stack + ACTION/GOTO tables (built by LR(0)/SLR/LR(1)/LALR methods). Same driver for all; only tables differ. Handles widest class of deterministic grammars, detects errors at earliest point.

stack = [$ , 0]; ip → first token
loop:
  s = top state; a = *ip
  if ACTION[s,a] = shift t: push a, t; ip++
  elif reduce A→β: pop 2*|β|; s'=top; push A, GOTO[s',A]; output production
  elif accept: return success
  else error()

Trace aab: shift a,a, shift b, reduce S→b, reduce S→aS twice, accept.

4. Error Detection

LR detects error as soon as prefix cannot extend to valid string (viable-prefix property) — earlier than LL. Panic recovery pops till state with goto on non-terminal.

5. Exam Points

• LR algorithm + trace with ACTION/GOTO — 7-10 marks, very frequent.
• Viable prefix / why earliest detection — 3 marks, frequent.
• ACTION vs GOTO roles — 3 marks, frequent.