Lecture No. 19

Dated: 09-04-2025

\(LL(1)\) Table Construction

Following is the algorithm to construct a predictive parsing table.¹

• For each production \(A \to \alpha\)
  • For each terminal \(a\) in \(\text{FIRST}(\alpha)\), add \(A \to \alpha\) to \(M[A, a]\).
  • If \(\epsilon \in \text{FIRST}(\alpha)\)
    • \(\$ \in \text{FOLLOW}(A) \implies \text{add } A \to \alpha\) to \(M[A, \$]\).
    • \(b \in \text{FOLLOW}(A) \implies \text{add } A \to \alpha\) to \(M[A, b]\).
• Make each undefined entry of \(M\) be an error.

	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)

Left Factoring

Consider the grammar

E ? T + E | T
T ? int   | int T | (E)

It is impossible to predict because for both T and E, the productions that from same symbols. (i.e. for T, it is int and for E, it is T).
A grammar must be left factored before use for predictive parsing.¹

Procedure

If \(\alpha \neq \epsilon\), replace all productions \(A \to \alpha \beta_1 | \alpha \beta_2 | \ldots | \alpha \beta_n | \gamma\) with \(A \to \alpha Z | \gamma\) and \(Z \to \beta_1 | \beta_2 | \ldots | \beta_n\) where \(Z\) is the new non terminal.

Graphical Representation

Example

Consider the following fragment of expression grammar.

Factor -> id
       |  id [ExprList]
       |  id (ExprList)

After left factoring, the grammar becomes

Factor -> id Args
Args   -> [ExprList]
       |  (ExprList)
       |  e

Given a context free grammar which doesn't meet the \(LL(1)\) condition, it is undecidable whether or not an equivalent \(LL(1)\) grammar exists or not.

References

---

1. Read more about predictive parsing tables. ↩↩