Compiler Design

Top-Down Parsing & LL(1) / Solved Problem: LL(1)

PreviousNext

Problem 1: LL(1) Table Construction

Analyze the following grammar representing conditional statements (if-else):

S  → iEtSS' | a S' → eS | ε E  → b

Where terminals are: i, e, t, a, b and the start symbol is S.

FIRST Sets:

  • FIRST(E) = { b }
  • FIRST(S') = { e, ε } (since S' → eS and S' → ε)
  • FIRST(S) = { i, a } (since S → iEtSS' and S → a)

FOLLOW Sets:

  • FOLLOW(S):
    • Start symbol receives $.
    • In production S → iEtSS', the symbol S is followed by S'. So add FIRST(S') - {ε} = { e }.
    • Since S' can derive ε, add FOLLOW(S) (already includes $, e).
    • Result: FOLLOW(S) = { e, $ }.
  • FOLLOW(S'):
    • S' appears at the end of S → iEtSS', so add FOLLOW(S).
    • Result: FOLLOW(S') = { e, $ }.
  • FOLLOW(E):
    • E appears in S → iEtSS' followed by t.
    • Result: FOLLOW(E) = { t }.

Place production A → α in cell M[A, a] for all a ∈ FIRST(α). If ε ∈ FIRST(α), place the production in M[A, b] for all b ∈ FOLLOW(A).

Non-Terminalabeit$
SS → a——S → iEtSS'——
S'——S' → eS——S' → ε
E—E → b————

✓ Analysis: Since every cell contains at most one production, there are no conflicts. Therefore, this grammar is LL(1).

Problem 2: Tracing Expression string in LL(1)

Consider the unambiguous Expression grammar:

E  → TE' E' → +TE' | ε T  → FT' T' → *FT' | ε F  → (E) | id
StepStackInput BufferProduction / Action Applied
1$ Eid + id * id $E → TE'
2$ E' Tid + id * id $T → FT'
3$ E' T' Fid + id * id $F → id
4$ E' T' idid + id * id $Match id (pop stack, advance input)
5$ E' T'+ id * id $T' → ε
6$ E'+ id * id $E' → +TE'
7$ E' T ++ id * id $Match + (pop stack, advance input)
8$ E' Tid * id $T → FT'
9$ E' T' Fid * id $F → id
10$ E' T' idid * id $Match id (pop stack, advance input)
11$ E' T'* id $T' → *FT'
12$ E' T' F ** id $Match * (pop stack, advance input)
13$ E' T' Fid $F → id
14$ E' T' idid $Match id (pop stack, advance input)
15$ E' T'$T' → ε
16$ E'$E' → ε
17$$Accept string successfully!
Back to Top-Down Parsing & LL(1)Bottom-Up Parsing & Shift-Reduce