Course Section: Left Factoring, Eliminating Left Recursion, and Top-Down Parsing Suitability for

We study the grammar:

• CFG $S \rightarrow S(S)S \mid \epsilon$
• where $\epsilon$ denotes the empty string.

This grammar is left-recursive because the production $S \rightarrow S(S)S$ begins with $S$ on the right-hand side. Left recursion prevents standard top-down parsers (like predictive/LL(1) parsers) from directly making progress.

Key transformation goals:

1. Left factoring the grammar (useful for LL(1) when alternatives share prefixes).
2. Eliminating left recursion so top-down parsing becomes possible.
3. Decide whether the resulting grammar is suitable for Top-down parsing.

A useful mental model is:

• Left factoring addresses choice ambiguity among alternatives (common prefixes).
• Left recursion elimination addresses infinite descent (a nonterminal calling itself as the leftmost step).

First observations

• The grammar has only one nonterminal: $S$.
• Its productions are:
  1. $S \rightarrow S(S)S$
  2. $S \rightarrow \epsilon$

Because there is only one production with $S$ as the left-hand side, left factoring in the usual sense (when multiple alternatives share a common prefix) is not really applicable: there are no two competing right-hand sides that begin with the same terminal/nonterminal prefix that can be factored to make an LL decision earlier.

However, to be rigorous: left factoring looks for alternatives of the form: $A \rightarrow \alpha\beta_1 \mid \alpha\beta_2$ where both start with a common prefix $\alpha$. Here, the alternatives for $S$ are:

• $S(S)S$ (begins with $S$)
• $\epsilon$ (begins with “nothing”)

There is no pair of non-empty alternatives sharing a common prefix to factor in the standard way.

Key takeaway: (i) Left factoring does not change the grammar.

Why left factoring is often about LL(1)

LL(1) parsers fail when, for some nonterminal $A$, multiple alternatives have overlapping FIRST sets (and also potentially FOLLOW conditions). Left factoring attempts to rewrite: $A \rightarrow \\alpha\\beta_1 \\mid \\alpha\\beta_2$ into: $A \\rightarrow \\alpha A' \\, ; \\, A' \\rightarrow \\beta_1 \\mid \\beta_2$

In our grammar, there is no such pair of alternatives with a shared prefix to rewrite.

Final grammar after eliminating left recursion

A clean way to present it is to directly inline the trivial $S \rightarrow S'$:

Let the transformed grammar be:

• $S \rightarrow (S)SS' \mid \epsilon$
• $S' \rightarrow (S)SS' \mid \epsilon$

But that presentation accidentally duplicates structure if you inline too aggressively. The standard, unambiguous result from the construction is:

This is left-recursion-free: no production has a nonterminal on the immediate left of its own right-hand side.

(iii) Is the resulting grammar suitable for top-down parsing?

Clarify what “suitable” usually means

For top-down predictive parsing (LL(1)-style), the grammar typically needs:

• No left recursion (so recursive descent can progress).
• Left factoring (so one-token lookahead can choose the correct alternative).

Even after eliminating left recursion, a grammar might still be not LL(1) if choices are ambiguous with one-token lookahead.

Check for remaining predictive-choice issues

In the transformed grammar:

• $S \rightarrow S'$ only (deterministic)
• $S' \rightarrow (S)SS' \mid \epsilon$

The $S'$ alternatives are:

1. starting with terminal '(' (because the first symbol of $(S)SS'$ is '(')
2. $\epsilon$

For an LL(1) parser, selection is based on FIRST sets:

• FIRST of $(S)SS'$ is $\{ '(' \}$.
• FIRST of $\epsilon$ contributes via FOLLOW conditions (i.e., when lookahead indicates the parser can safely take $\epsilon$).

Since one alternative clearly starts with '(' and the other is $\epsilon$, this is a common pattern that can be LL(1) provided the FOLLOW sets do not conflict.

At minimum, the grammar is amenable to top-down parsing in the sense that it is not left-recursive and has a very structured single-choice at $S'$.

A compact decision

• After step (ii), the grammar is left-recursion-free, so it is generally suitable for top-down parsing algorithms that require no left recursion (e.g., standard recursive descent without left-recursive loops).
• For LL(1) specifically, the grammar’s structure suggests it can be predictive because the non-$\epsilon$ production begins with a fixed terminal '('; the $\epsilon$ option is handled via FOLLOW-based prediction.

So, yes: the transformed grammar is suitable for top-down parsing, and it is plausibly LL(1) due to the clear terminal prefix separation—though a full LL(1) proof would require computing FIRST/FOLLOW sets.