Elimination of left recursion

LEFT RECURSION. Let G be a context-free grammar. A production of G is said left recursive if it has the form

$$\longmapsto \alpha$$ (20)

where A is a nonterminal and $\alpha$ is a string of grammar symbols. A nonterminal A of G is said left recursive if there exists a string of grammar symbols $\alpha$ such that we have

$$\;\stackrel{{{\ast}}}{{\Rightarrow}}\; \alpha$$ (21)

Such derivation is also said left recursive. The grammar G is left recursive if it has at least one left recursive nonterminal.

Remark 4   Top-down parsing is one of the methods that we will study for generating parse trees. This method cannot handle left recursive grammars. We present now an algorithm for transforming a left recursive grammar G into a grammar G' which is not left recursive and which generates the same language as G.

THE BASIC TRICK is to replace the production

$$\longmapsto \alpha \beta \left\{\vphantom{ \begin{array}{lll} A & \longmapsto & {\beta} A'... ... A' & \longmapsto & {\alpha} A' \ \mid \ {\varepsilon} \\ \end{array} }\right. \begin{array}{lll} A & \longmapsto & {\beta} A' \\ A' & \longmapsto & {\alpha} A' \ \mid \ {\varepsilon} \\ \end{array}$$ (22)

where $\alpha$ $\neq$ $\varepsilon$ is assumed. Observe that this trick eliminates left recursive productions. Applying this trick is not enough to remove all derivations of the form A $\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ A$\alpha$. However this trick is sufficient for many grammars.

Example 10   The following grammar which generates arithmetic expressions

E	$$\longmapsto$$	E + T  |  T
T	$$\longmapsto$$	T*F  |  F
F	$$\longmapsto$$	(E)  |  $$\bf id$$

(23)

has two left recursive productions. Applying the above trick leads to

E	$$\longmapsto$$	TE'
E'	$$\longmapsto$$	+ TE'  |  $$\varepsilon$$
T	$$\longmapsto$$	FT'
T'	$$\longmapsto$$	*FT'  |  $$\varepsilon$$
F	$$\longmapsto$$	(E)  |  $$\bf id$$

(24)

THE CASE OF SEVERAL LEFT RECURSIVE A-PRODUCTIONS. Assume that the set of all A-productions has the form

$$\longmapsto \alpha_{{1}}^{{}} \alpha_{{2}}^{{}} \alpha_{{m}}^{{}} \beta_{{1}}^{{}} \beta_{{2}}^{{}} \beta_{{n}}^{{}}$$ (25)

where no $\beta_{{i}}^{{}}$ begins with an A and where $\alpha_{{i}}^{{}}$ $\neq$ $\varepsilon$ holds for every i = 1 ^... m. Then we repalce these A-productions by

A	$$\longmapsto$$	$$\beta_{{1}}^{{}}$$A'  |  $$\beta_{{2}}^{{}}$$A'  |   ...  $$\beta_{{n}}^{{}}$$A'
A'	$$\longmapsto$$	$$\alpha_{{1}}^{{}}$$A'  |  $$\alpha_{{2}}^{{}}$$A'  |   ...  $$\alpha_{{m}}^{{}}$$A'  |  $$\varepsilon$$

(26)

Remark 5   Let us consider the following grammar.

S	$$\longmapsto$$	Aa  |  b
A	$$\longmapsto$$	Ac  |   Sd  |  $$\varepsilon$$

(27)

The nonterminal S is left recursive since we have

$$\Rightarrow \Rightarrow$$ (28)

However there is no left recursive S-productions. We show now how to deal with these left recursive derivations.

REMOVING ALL LEFT RECURSIVE DERIVATIONS. Let us assume that non-terminals are numbered: A₁, A₂,..., A_n. The goal is to remove any possible circuit for all 1 $\leq$ j < i $\leq$ n

$$\;\stackrel{{{\ast}}}{{\Rightarrow}}\; \delta_{{j}}^{{}} \;\stackrel{{{\ast}}}{{\Rightarrow}}\; \delta_{{i}}^{{}}$$ (29)

The idea is for i = 1 ^... n

• To make sure that every A_i-production does not have a form A_i $\longmapsto$ A_j$\delta$ for some j < i.
• To remove any left recursive A_i-production.

The method in more detail:

• remove all left recursive A₁-productions (by the above trick)
• remove A₁ from the right-hand side of each A₂-production of the form A₂ $\longmapsto$ A₁$\delta$ (by applying all A₁-productions)
• remove all left recursive A₂-productions
• remove A_j from the right-hand side of each A₃-production of the form A₃ $\longmapsto$ A_j$\delta$ for j = 1, 2.
• remove all left recursive A₃-productions
• ...
• remove A_j from the right-hand side of each A_i-production of the form A_i $\longmapsto$ A_j$\delta$ (for every j such that 1 $\leq$ j < i $\leq$ n)
• remove all left recursive A_i-productions
• ...

Observations:

• To remove A_j from the right-hand side of the A_i-production A_i $\longmapsto$ A_j$\delta$ (where 1 $\leq$ j < i $\leq$ n) replace

  $$\longmapsto \delta \longmapsto \gamma_{{1}}^{{}} \delta \gamma_{{k}}^{{}} \delta \longmapsto \gamma_{{1}}^{{}} \gamma_{{k}}^{{}}$$ (30)

  
  
  are all A_j-productions and $\gamma_{{i}}^{{}}$ $\neq$ $\varepsilon$ for i = 1 ^... k.
• This construction may not work if G constains initially a production of the form A  $\longmapsto$  $\varepsilon$. See Example 11. However we can always remove such productions. Explain how!
• Also, this construction may fail if the grammar G has a cycle, that is, if there exists a nonterminal A such that A $\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ A. This can happen with the following grammar fragment

  A1	$$\longmapsto$$	A2  |  $$\gamma_{{{1}}}^{{}}$$
  A2	$$\longmapsto$$	A1  |  $$\gamma_{{{2}}}^{{}}$$

  (31)

  
  
  where
  • $\gamma_{{1}}^{{}}$ is a string of grammar symbols not starting with A₁ (what we can assume by application of the basic trick given in Relation 22)
  • $\gamma_{{2}}^{{}}$ is a string of grammar symbols not starting with A₁ (what we can assume by application of the A₁-productions).
  Then we can replace the above fragment by

  A1	$$\longmapsto$$	$$\gamma_{{{2}}}^{{}}$$  |  $$\gamma_{{{1}}}^{{}}$$
  A2	$$\longmapsto$$	$$\gamma_{{{1}}}^{{}}$$  |  $$\gamma_{{{2}}}^{{}}$$

  (32)

  
  
  without changing the generated language. Unfortunately a cycle may be hidden in a more subtle manner. Indeed $\gamma_{{{2}}}^{{}}$ may write $\gamma_{{{21}}}^{{}}$A₂$\gamma_{{{22}}}^{{}}$ and $\gamma_{{{1}}}^{{}}$ may write $\gamma_{{{11}}}^{{}}$A₁$\gamma_{{{12}}}^{{}}$ with $\gamma_{{{21}}}^{{}}$$\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ $\varepsilon$, $\gamma_{{{22}}}^{{}}$$\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ $\varepsilon$, $\gamma_{{{11}}}^{{}}$$\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ $\varepsilon$ and $\gamma_{{{12}}}^{{}}$$\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ $\varepsilon$. However this may only happen if there are productions of the form A $\longmapsto$ $\varepsilon$.
• In conclusion, the above construction for removing all left recursive derivations should be performed after
  • removing all productions of the form A $\longmapsto$ $\varepsilon$,
  • removing cycles, that is derivations of the form A $\;\stackrel{{{\ast}}}{{\Rightarrow}}\;$ A.
  Now observe that the basic trick given in Relation 22 introduces productions of the form A $\longmapsto$ $\varepsilon$. However one can show that the above construction cannot reintroduce cycles.

Example 11   Consider the following grammar.

A3	$$\longmapsto$$	A2A1
A2	$$\longmapsto$$	$$\varepsilon$$
A1	$$\longmapsto$$	A2A1

(33)

Applying the previous algorithm for removing all possible left-recursive derivations fail on this grammar, because of the $\varepsilon$-production.

Example 12   Consider again the following grammar.

S	$$\longmapsto$$	Aa  |  b
A	$$\longmapsto$$	Ac  |  Sd  |  $$\varepsilon$$

(34)

We order the nonterminals: S < A. There is no left recursive S-productions. So the next step is to remove S from the right-hand side of the A-productions of the form A $\longmapsto$ S$\alpha$. Hence we obtain

S	$$\longmapsto$$	Aa  |  b
A	$$\longmapsto$$	Ac  |  Aad  |  bd  |  $$\varepsilon$$

(35)

Then we remove the left recursive A-productions.

S	$$\longmapsto$$	Aa  |  b
A	$$\longmapsto$$	bdA'  |  A'
A'	$$\longmapsto$$	cA'  |  adA'  |  $$\varepsilon$$

(36)