Syntax Analysis — LL & LR Parsing

What is Parsing?

Analogy: Reading a sentence and identifying its grammatical structure. "The cat sat on the mat." → Subject: "The cat", Verb: "sat", Prepositional phrase: "on the mat"

A parser does the same for code:

x = a + b * c;
→ Assignment: x = (Expression)
  Expression: a + (Multiplication)
    Multiplication: b * c

---

FIRST and FOLLOW Sets — The Foundation

These sets tell us which token to expect at each point, allowing us to make deterministic parsing decisions.

FIRST(X) — "What can X start with?"

Rules:
1. If X is a terminal: FIRST(X) = {X}
2. If X → ε: add ε to FIRST(X)
3. If X → Y₁Y₂...Yₖ:
   - Add FIRST(Y₁) - {ε} to FIRST(X)
   - If ε ∈ FIRST(Y₁): also add FIRST(Y₂) - {ε}
   - If ε ∈ FIRST(Y₁) AND ε ∈ FIRST(Y₂): also add FIRST(Y₃) - {ε}
   - ... continue while ε keeps appearing
   - If ε ∈ FIRST(all Yᵢ): add ε to FIRST(X)

Worked Example:

Grammar:
  E → TE'
  E'→ +TE' | ε
  T → FT'
  T'→ *FT' | ε
  F → (E) | id

FIRST(F) = { (, id }
FIRST(T') = { *, ε }
FIRST(T) = FIRST(F) = { (, id }
  (Since ε ∉ FIRST(F), we stop)
FIRST(E') = { +, ε }
FIRST(E) = FIRST(T) = { (, id }

FOLLOW(A) — "What terminals can come after A?"

Rules:
1. If A is start symbol: add $ to FOLLOW(A)
2. If B → αAβ: add FIRST(β) - {ε} to FOLLOW(A)
3. If B → αA or B → αAβ where ε ∈ FIRST(β): add FOLLOW(B) to FOLLOW(A)

Worked Example (continuing above):

FOLLOW(E) = { ), $ }   (E appears inside (E), and is the start symbol)
FOLLOW(E') = FOLLOW(E) = { ), $ }  (E' is at end of E → TE')
FOLLOW(T) = FIRST(E') - {ε} ∪ FOLLOW(E') = {+} ∪ {), $} = {+, ), $}
FOLLOW(T') = FOLLOW(T) = {+, ), $}
FOLLOW(F) = FIRST(T') - {ε} ∪ FOLLOW(T') = {*} ∪ {+,),} = {*, +, ), $}

---

LL(1) Parsing — Top-Down, Left-to-Right, 1 Lookahead

Top-down = build tree from the root (start symbol) down. L = left-to-right scan; L = leftmost derivation; 1 = 1 token lookahead.

LL(1) Parse Table Construction:

For each production A → α:
  For each terminal a ∈ FIRST(α): put A→α in M[A, a]
  If ε ∈ FIRST(α):
    For each b ∈ FOLLOW(A): put A→α in M[A, b]

LL(1) condition: no cell has MORE THAN ONE entry
  Multiple entries → grammar is not LL(1)

Example parse table (expression grammar above):

       id    +    *    (    )    $
E:   E→TE' |    |    | E→TE' |    |
E':  |  E'→+TE'|    |    | E'→ε | E'→ε
T:   T→FT' |    |    | T→FT' |    |
T':  | T'→ε | T'→*FT'|   | T'→ε | T'→ε
F:   F→id  |    |    | F→(E) |    |

---

Obstacles to LL(1) Parsing

Left Recursion — Must Eliminate!

Left-recursive grammar: A → Aα | β
This LOOPS forever in top-down parsing!

Elimination:
A  → βA'
A' → αA' | ε

Example: E → E+T | T
→ E  → TE'
   E' → +TE' | ε

Left Factoring — Must Apply for Common Prefixes

A → αβ | αγ   (both start with α — ambiguous which rule to apply!)

Left factor:
A  → αA'
A' → β | γ

Example: stmt → if E then S else S | if E then S
→ stmt → if E then S stmt'
   stmt'→ else S | ε

---

LR Parsing — Bottom-Up, More Powerful

Bottom-up = start with tokens, reduce to the start symbol. More powerful than LL — can handle more grammars.

LR parser uses:
  STACK: stores states and grammar symbols
  ACTION table: shift (push token) or reduce (apply production)
  GOTO table: state transitions after reduce

Parsing loop:
  1. Look at top of stack and next input token
  2. Shift: push state for current token
  3. Reduce: pop RHS of some production, push LHS
  4. Accept: input consumed, start symbol on stack
  5. Error: no valid action

LR Variants (Increasing Power)

LR(0):   No lookahead. Weakest. May have many conflicts.
SLR(1):  Use FOLLOW sets to decide when to reduce.
         Reduces when input ∈ FOLLOW(A) for production A → α
LALR(1): Merge LR(1) states with same core.
         Practical: YACC/Bison use LALR(1). Most languages are LALR(1).
CLR(1) = LR(1): Most powerful. Exact 1-token lookahead per item.
         Largest tables. Every LALR(1) grammar is LR(1).

Power hierarchy:

LR(1) = CLR(1)  ← most powerful
    ↓ merge states
LALR(1)         ← practical choice (YACC)
    ↓ use FOLLOW instead of exact lookahead
SLR(1)
    ↓ no lookahead
LR(0)           ← weakest

Every LL(1) grammar is also LALR(1)

Conflicts in LR Parsing

Shift-Reduce conflict: should we shift the next token OR reduce current handle?
  Often caused by ambiguity (e.g., dangling else problem)
  Resolution: usually prefer SHIFT (implemented in most tools)

Reduce-Reduce conflict: two different productions applicable for reduction
  More serious — indicates grammar ambiguity
  Must resolve by rewriting grammar

---

Quick Check

Q1. Grammar: S → aA, A → bA | ε. Compute FIRST(A) and FOLLOW(A).

FIRST(A): A → bA → FIRST = {b}; A → ε → add ε; FIRST(A) = {b, ε}
FOLLOW(A): S → aA: nothing after A at end, so add FOLLOW(S) = {$}
           A → bA: after A comes end of A production → add FOLLOW(A) = {$}
           FOLLOW(A) = {$}

Q2. Why cannot left-recursive grammar be parsed by LL(1)? Answer: LL(1) is top-down and predictive. When parsing A → Aα, the parser tries to expand A, which requires expanding A again — infinite recursion with no progress through the input.

Q3. Is every LALR(1) grammar also LR(1)? Answer: Yes. LALR(1) is built by merging LR(1) states with the same core. Merging can only create conflicts, not resolve them. So if LALR(1) has no conflicts, LR(1) definitely does not either.