Q2Compiler Design

The grammar E→E+T|T and T→T*F|F has direct left recursion (E starts with E, T starts with T). Apply the transformation A→Aα|β becomes A→βA', A'→αA'|ε:

• E → E+T | T → E → TE', E' → +TE' | ε
• T → TF | F → T → FT', T' → FT' | ε
• F → (E) | id (no change — no left recursion)

After eliminating left recursion, check for common prefixes. The resulting grammar has no common prefixes (E'→+TE'|ε, alternatives +TE' and ε start differently; T'→FT'|ε, alternatives and ε start differently). No left factoring needed.

• FIRST(id) = {id}, FIRST(+) = {+}, FIRST() = {}, FIRST(() = {(}, FIRST()) = {)}
• FIRST(F) = {(, id} [from F→(E)|id]
• FIRST(T') = {, ε} [from T'→FT'|ε]
• FIRST(T) = FIRST(F) = {(, id} [from T→FT']
• FIRST(E') = {+, ε} [from E'→+TE'|ε]
• FIRST(E) = FIRST(T) = {(, id} [from E→TE']

• FOLLOW(E): E is the start symbol → add $. E appears in F→(E) → ) follows E. FOLLOW(E) = {$, )}
• FOLLOW(E'): E' appears in E→TE' at end → FOLLOW(E') ⊇ FOLLOW(E). FOLLOW(E') = {$, )}
• FOLLOW(T): T in E→TE', so FIRST(E')-{ε} = {+} ∈ FOLLOW(T). ε ∈ FIRST(E') so FOLLOW(E') ⊆ FOLLOW(T). FOLLOW(T) = {+, $, )}
• FOLLOW(T'): T' in T→FT' at end → FOLLOW(T') ⊇ FOLLOW(T). FOLLOW(T') = {+, $, )}
• FOLLOW(F): F in T→FT', FIRST(T')-{ε} = {*} ∈ FOLLOW(F). ε ∈ FIRST(T') so FOLLOW(T') ⊆ FOLLOW(F). FOLLOW(F) = {*, +, $, )}

Construct table M[Non-terminal, Terminal] using rules: for A→α, add to M[A,a] for a∈FIRST(α); if ε∈FIRST(α), add to M[A,b] for b∈FOLLOW(A).

• M[E, id] = E→TE', M[E, (] = E→TE'
• M[E', +] = E'→+TE', M[E', )] = E'→ε, M[E', $] = E'→ε
• M[T, id] = T→FT', M[T, (] = T→FT'
• M[T', *] = T'→*FT', M[T', +] = T'→ε, M[T', )] = T'→ε, M[T', $] = T'→ε
• M[F, id] = F→id, M[F, (] = F→(E)

No cell has multiple entries — the grammar is LL(1). The parser uses this table to deterministically parse any input string of arithmetic expressions without backtracking.