RTUComputer ScienceYr 2024 · Sem 52024

Q3Compiler Design

Question

10 marks

Explain the LALR parsing in detail. Construct LALR parsing table for a given grammar and demonstrate parsing of an input string.

Answer

LALR parsing merges LR(1) states with identical cores (LR(0) items) to produce a compact parser almost as powerful as canonical LR(1). It is the standard parsing method used in tools like yacc and bison.

LALR(1) parsing is a practical compromise between the large CLR(1) parser and the weaker SLR(1) parser. It constructs the canonical LR(1) collection, then merges states that have the same LR(0) core (same items ignoring lookaheads) and unions their lookahead sets.

An LR(1) item is a pair [A → α•β, a] where A→αβ is a production, • marks the current parser position, and a is a lookahead terminal. The lookahead a is used only when β = ε (i.e., the item is a reduce item) — reduce by A→αβ only when the next input symbol is a.

S' → S (new start production). Productions: (0) S'→S, (1) S→CC, (2) C→cC, (3) C→d.

  • I0: {[S'→•S, $], [S→•CC, $], [C→•cC, c/d], [C→•d, c/d]}
  • I1 (goto I0, S): {[S'→S•, $]} — accept state
  • I2 (goto I0, C): {[S→C•C, $], [C→•cC, $], [C→•d, $]}
  • I3 (goto I0, c): {[C→c•C, c/d], [C→•cC, c/d], [C→•d, c/d]}
  • I4 (goto I0, d): {[C→d•, c/d]} — reduce by C→d on c,d
  • I5 (goto I2, C): {[S→CC•, $]} — reduce by S→CC on $
  • I6 (goto I2, c): {[C→c•C, $], [C→•cC, $], [C→•d, $]}
  • I7 (goto I2, d): {[C→d•, $]} — reduce by C→d on $
  • I8 (goto I3/I6, C): {[C→cC•, c/d]} or {[C→cC•, $]} — same core!
  • I9 (goto I3/I6, d): {[C→d•, c/d]} same as I4 core

States with same LR(0) core are merged. I3 and I6 have the same core [C→c•C], so merge to I36 with lookaheads {c, d, $}. I4 and I7 have core [C→d•], merge to I47 with lookaheads {c, d, $}. The merged states form the LALR automaton with fewer states than CLR.

  • State 0: on c → shift to 36; on d → shift to 47; on S → goto 1; on C → goto 2
  • State 1: on $ → accept
  • State 2: on c → shift to 36; on d → shift to 47; on C → goto 5
  • State 36: on c → shift to 36; on d → shift to 47; on C → goto 8
  • State 47: on c/d/$ → reduce C→d
  • State 5: on $ → reduce S→CC
  • State 8: on c/d/$ → reduce C→cC

Stack: [0], Input: cdcd$. Shift c→[0,36]. Shift d→[0,36,47]. Reduce C→d: pop 47, goto(36,C)=8→[0,36,8]. Reduce C→cC: pop 8,36, goto(0,C)=2→[0,2]. Shift c→[0,2,36]. Shift d→[0,2,36,47]. Reduce C→d→[0,2,36,8]. Reduce C→cC→[0,2,5]. Reduce S→CC: pop 5,2, goto(0,S)=1→[0,1]. Accept.

Back to Paper