Predictive Parsing Table Construction for a Classic Expression Grammar (LL(1))

We are given the grammar (intended as an LL(1) expression grammar):

• $E \rightarrow E+T/T$
• $T \rightarrow T*F/F$
• $F \rightarrow (E)/id$

Interpreting the “/” as alternative productions, this means:

• $E \rightarrow E+T \mid T$
• $T \rightarrow T*F \mid F$
• $F \rightarrow (E) \mid id$

A predictive parsing table is typically built for an $LL(1)$ grammar using FIRST and FOLLOW sets, and the table is filled using the grammar’s productions and these sets. The standard method relies on the fact that each cell $(A,a)$ has at most one production for $LL(1)$ parsing.

Because the grammar uses direct left recursion ($E \rightarrow E+T$ and $T \rightarrow T*F$), predictive parsing tables are constructed after transforming to an equivalent $LL(1)$ grammar (eliminating left recursion and left-factoring where needed). Left-recursion elimination is a standard prerequisite for table-driven predictive parsing.

Key terms

• LL(1)
• FIRST
• FOLLOW
• Predictive parsing table

Mermaid view of the structure (operators by precedence):

Footnotes

1. (LL(1) parse table construction using FIRST/FOLLOW) - https://en.wikipedia.org/wiki/LL_parser - Explains predictive parsing tables and the use of FIRST/FOLLOW and $\\epsilon$ handling. ↩

2. (Left recursion elimination and expression grammar transformation) - https://en.wikipedia.org/wiki/Left_recursion - Describes elimination of left recursion and standard transformation patterns. ↩

Step 1: Convert to an $LL(1)$ grammar (eliminate left recursion)

A common equivalent $LL(1)$ form introduces helper nonterminals so that:

• addition ($+$) is handled by an $E'$ suffix chain
• multiplication ($*$) is handled by a $T'$ suffix chain

Use the transformations (standard form for left-recursive expressions):

Start from:

• $E \rightarrow E+T \mid T$
• $T \rightarrow T*F \mid F$
• $F \rightarrow (E) \mid id$

Eliminate left recursion:

1. For $E$:

• $E \rightarrow T\,E'$
• $E' \rightarrow +\,T\,E' \mid \epsilon$

2. For $T$:

• $T \rightarrow F\,T'$
• $T' \rightarrow *\,F\,T' \mid \epsilon$

3. $F$ stays the same:

• $F \rightarrow (E) \mid id$

So the $LL(1)$ grammar is:

• $E \rightarrow T E'$
• $E' \rightarrow + T E' \mid \epsilon$
• $T \rightarrow F T'$
• $T' \rightarrow * F T' \mid \epsilon$
• $F \rightarrow (E) \mid id$

This is the classical expression grammar that is LL(1) for operators and parentheses/identifiers.

[CalloutBlock]{type="tip"} title: "Pro Tip" content: "For predictive parsing tables, you almost always need the $LL(1)$ form. If a grammar is left-recursive, first eliminate left recursion (and left-factor if needed), then compute FIRST/FOLLOW and fill the table."

Footnotes

1. (Left recursion elimination and expression grammar transformation) - https://en.wikipedia.org/wiki/Left_recursion - Describes elimination of left recursion and standard transformation patterns. ↩

Step 2: Compute FIRST sets

Terminals: $(, ), +, *, id$ and end-marker $\\$.

Nonterminals: $E, E', T, T', F$.

From productions:

• $F \rightarrow (E) \mid id$

  • FIRST$(F)=\{ '(', id \}$

• $T \rightarrow F T'$

  • FIRST$(T)=\text{FIRST}(F)=\{ '(', id \}$

• $T' \rightarrow * F T' \mid \epsilon$

  • FIRST$(T')=\{ '*', \epsilon \}$

• $E \rightarrow T E'$

  • FIRST$(E)=\text{FIRST}(T)=\{ '(', id \}$

• $E' \rightarrow + T E' \mid \epsilon$

  • FIRST$(E')=\{ '+', \epsilon \}$

Step 3: Compute FOLLOW sets

Start symbol is $E$, so:

• FOLLOW$(E)$ contains $\\$.

We also use standard FOLLOW propagation rules:

• If there is a production $A \rightarrow \\alpha B \\beta$, then everything in FIRST$(\\beta)$ except $\epsilon$ goes into FOLLOW$(B)$.
• If $\epsilon \\in FIRST(\\beta)$ or $\\beta$ is empty, then FOLLOW$(A)$ is included in FOLLOW$(B)$.

Compute systematically:

1. From $E \rightarrow T E'$:

• FOLLOW$(T)$ includes FIRST$(E')$ excluding $\epsilon$:
  • FIRST$(E')=\{ '+', \epsilon \}$
  • so add $+$ to FOLLOW$(T)$
• Because $\epsilon \\in FIRST(E')$, also add FOLLOW$(E)$ to FOLLOW$(T)$:
  • FOLLOW$(E)$ currently contains $\\$ (and later may get $)$)

2. From $E' \rightarrow + T E'$:

• Again, $T$ is followed by $E'$, so:
  • add $+$ to FOLLOW$(T)$ (already)
  • and since $\epsilon \\in FIRST(E')$, add FOLLOW$(E')$ to FOLLOW$(T)$
• But FOLLOW$(E')$ depends on where $E'$ appears:
  • $E'$ appears only in $E \rightarrow T E'$ at the end, so FOLLOW$(E')$ includes FOLLOW$(E)$.

3. From $T \rightarrow F T'$:

• FOLLOW$(F)$ includes FIRST$(T')$ excluding $\epsilon$:
  • FIRST$(T')=\{ '*', \epsilon \}$
  • so add $*$ to FOLLOW$(F)$
• Since $\epsilon \\in FIRST(T')$, add FOLLOW$(T)$ to FOLLOW$(F)$

4. From $T' \rightarrow * F T'$:

• $F$ is followed by $T'$, so:
  • add $*$ to FOLLOW$(F)$
  • and since $\epsilon \\in FIRST(T')$, add FOLLOW$(T')$ to FOLLOW$(F)$
• $T'$ appears at the end of $T \rightarrow F T'$, so FOLLOW$(T')$ includes FOLLOW$(T)$.

5. From $F \rightarrow (E)$:

• $E$ is followed by $)$, so add $)$ to FOLLOW$(E)$.

Now assemble final FOLLOW sets:

• FOLLOW$(E)=\{\\$, ')'}$
• FOLLOW$(E')=FOLLOW$(E)={\$, ')'\}$
• FOLLOW$(T)=\{ '+', \\$, ')'}$
• FOLLOW$(T')=FOLLOW$(T)={ '+', \$', ')'\}$
• FOLLOW$(F)=\{ '*', '+', \\$, ')'}$

These computations follow the standard FIRST/FOLLOW table-construction methodology for LL(1) parsing. 2

Footnotes

1. (LL(1) parse table construction using FIRST/FOLLOW) - https://en.wikipedia.org/wiki/LL_parser - Explains predictive parsing tables and the use of FIRST/FOLLOW and $\\epsilon$ handling. ↩

2. (FIRST and FOLLOW set definitions and algorithms) - https://en.wikipedia.org/wiki/LL_parser#First_and_follow - Provides the FIRST/FOLLOW set computation concepts used for LL parsing tables. ↩

Step 4: Fill the predictive parsing table

We build $M[A,a]$ where:

• $A$ is a nonterminal
• $a$ is a lookahead terminal in $\{ '(', ')', '+', '*', id, \\$ }$

Rules for table entries are exactly:

• If $A \rightarrow \alpha$ and $a \in FIRST(\\alpha)$, then $M[A,a]=A\\rightarrow\\alpha$.
• If $\epsilon \in FIRST(\\alpha)$, then for all $b \\in FOLLOW(A)$, set $M[A,b]=A\\rightarrow\\alpha$.

Productions:

1. $E \rightarrow T E'$

• FIRST$(T E') = \{ '(', id \}$
• so:
  • $M[E,'(']=E \\rightarrow T E'$
  • $M[E,id]=E \\rightarrow T E'$

2. $E' \rightarrow + T E'$

• FIRST$(+ T E')=\{ '+' \}$
  • $M[E','+]=E' \\rightarrow + T E'$

3. $E' \rightarrow \epsilon$

• $\epsilon$ production: place in all columns in FOLLOW$(E')=\{\\$,')'}$
  • $M[E',')]=E' \\rightarrow \\epsilon$
  • $M[E','\\$]=E' \rightarrow \epsilon$

4. $T \rightarrow F T'$

• FIRST$(F T')=\{ '(', id \}$
  • $M[T,'(']=T \\rightarrow F T'$
  • $M[T,id]=T \\rightarrow F T'$

5. $T' \rightarrow * F T'$

• FIRST$( * F T')=\{ '*' \}$
  • $M[T','*]=T' \\rightarrow * F T'$

6. $T' \rightarrow \epsilon$

• place in all columns in FOLLOW$(T')=\{ '+', ')', \\$ }$
  • $M[T','+]=T' \\rightarrow \\epsilon$
  • $M[T',')]=T' \\rightarrow \\epsilon$
  • $M[T','\\$]=T' \rightarrow \epsilon$

7. $F \rightarrow (E)$

• $M[F,'(']=F \\rightarrow (E)$

8. $F \rightarrow id$

• $M[F,id]=F \\rightarrow id$

Footnotes

1. (LL(1) parse table construction using FIRST/FOLLOW) - https://en.wikipedia.org/wiki/LL_parser - Explains predictive parsing tables and the use of FIRST/FOLLOW and $\\epsilon$ handling. ↩

Table in explicit form (using productions)

This table is conflict-free for the LL(1) grammar above, enabling one-token lookahead predictive parsing. 2

[CalloutBlock]{type="warning"} title: "Warning" content: "The table above is for the transformed LL(1) grammar ($E',T'$). If you try to build a predictive table directly from the left-recursive form ($E \\rightarrow E+T$), you will not get a valid LL(1) parsing table."

Footnotes

1. (LL(1) parse table construction using FIRST/FOLLOW) - https://en.wikipedia.org/wiki/LL_parser - Explains predictive parsing tables and the use of FIRST/FOLLOW and $\\epsilon$ handling. ↩

2. (FIRST and FOLLOW set definitions and algorithms) - https://en.wikipedia.org/wiki/LL_parser#First_and_follow - Provides the FIRST/FOLLOW set computation concepts used for LL parsing tables. ↩