Eliminating Left Recursion/Left Factoring and Testing Suitability for Top-Down Parsing

We are given the context-free grammar:

• $S \rightarrow SS + \mid SS * \mid a$

Our goals are to:

1. Eliminate left recursion (more precisely: direct and indirect left recursion).
2. Eliminate left factoring (to help make decisions with limited lookahead).
3. Decide whether these removals make the grammar suitable for top-down parsing (typically meaning an LL-family parser, such as LL(1), that relies on lookahead).

Key definitions used below:

• left recursion
• left factoring
• LL(1) grammar
• top-down parsing

Note: With only $S$ as a nonterminal, the analysis is tight: eliminating left recursion may still leave ambiguity and/or FIRST/FOLLOW conflicts that prevent LL(1) parsing.

1) Identify left recursion

In the grammar

both alternatives $SS +$ and $SS *$ begin with $S$ (because the first symbol on the right-hand side is $S$). Therefore $S$ is directly left-recursive:

for $\alpha \in \{S+, S*\}$ (and the recursion can repeat because the leading $S$ can again expand to $SS+$ or $SS*$).

left recursion is present, so a top-down recursive-descent parser without extra machinery would loop.

2) Simplify/interpret the transformed grammar

After elimination we get:

and

This grammar is now free of direct left recursion (a derivation from $S$ no longer immediately starts with $S$ on the right-hand side; it must start with $a$ because of $S \rightarrow aS'$).

But note an important structural fact:

• The productions for $S'$ still begin with $S$ (because $S' \rightarrow SS+S'$ starts with $S$).
• However, left recursion is assessed per nonterminal: we no longer have a situation where $S$ derives strings starting with $S$ without first producing a terminal (or without passing through $S'$ in a way that reintroduces $S$ at the front). Here, $S$ is anchored by the initial $a$.

So left recursion is removed successfully, but this does not automatically imply LL(1) suitability.

3) Eliminate left factoring

Left factoring is needed when a nonterminal has alternatives with common prefixes (e.g., $A \rightarrow \gamma\beta_1 \mid \gamma\beta_2$).

In the transformed grammar:

• For $S$, alternatives are just one: $S \rightarrow aS'$. No factoring.
• For $S'$, alternatives are:
  • $SS+S'$
  • $SS*S'$
  • $\epsilon$

The first two alternatives share prefix $SS$ (i.e., both start with $S$ then immediately continue with either $+$ or $*$). This is not “left factoring” in the classic single-step syntactic-prefix sense until you consider how an LL parser would decide after seeing what it can derive from the prefix $S$.

Concretely:

• An LL parser must decide between $S' \rightarrow SS+S'$ and $S' \rightarrow SS*S'$ based on lookahead.
• After the parser expands the first $S$ and consumes whatever terminals it produces from that $S$, the next terminal is either $+$ or $*$.
• Because both alternatives share the same derivation prefix “$S$”, the decision can require lookahead beyond what would be available at the moment you choose the production for $S'$.

A typical factoring attempt would introduce intermediate nonterminals to delay the decision until after the $S$ part is recognized; but due to the recursive nature of $S$, the grammar still may not become LL(1).

Does this make the grammar suitable for top-down parsing?

What “suitable for top-down parsing” usually means

For a predictive recursive-descent parser (LL parsing), a common sufficient condition is that the grammar be LL(1), meaning:

• For each nonterminal $A$, the parser can choose the correct production using a single lookahead terminal.
• This is governed by FIRST and FOLLOW sets and constraints that avoid conflicts.

Why left recursion removal is necessary but not sufficient

Even if left recursion is eliminated:

• The grammar can still be ambiguous (multiple parse trees).
• Or it can still produce FIRST/FOLLOW conflicts, where LL(1) cannot decide with limited lookahead.
• Or the factoring is insufficient to make decisions deterministic.

In our transformed grammar:

• $S$ always begins with terminal $a$ (since $S \rightarrow aS'$). So $FIRST(S)=\{a\}$.
• But $S'$ can produce $\epsilon$ and also can begin with $S$; since $S$ begins with $a$, $FIRST(S')$ will also contain $a$.
• Therefore, when the parser is at $S'`, the choice between:
  • expanding $S'$ to $SS+S'$
  • expanding $S'$ to $SS*S'$
  • or using $\epsilon$ can require lookahead that may not be resolvable with $1$ token in all contexts.

Additionally, $S' \rightarrow SS+S' \mid SS*S'$ implies an expression-like structure where operands come from $S$ again, and the operator ($+$ or $*$) occurs after parsing an entire $S$. That tends to increase the need for lookahead or grammar refactoring to ensure deterministic prediction.

Bottom line (justification)

• Left recursion elimination makes the grammar terminating under naive top-down expansion (no immediate $S \Rightarrow^+ S\alpha$ loop).
• Left factoring, if performed, may improve decision points, but it does not by itself guarantee LL(1).
• For this grammar, the remaining nondeterminism stems from the fact that alternatives for $S'$ share a long shared prefix derived from $S$, and $S'$ also has an $\epsilon$ option—both of which are classic sources of LL parsing conflicts.

Therefore:

• The resulting grammar is not guaranteed suitable for predictive top-down parsing (LL(1)).
• It may still require either:
  • more than one-token lookahead (LL(k) with $k>1$),
  • or parser techniques like backtracking,
  • or a redesign into a conventional expression grammar with explicit precedence/associativity.