# Eliminating Left Recursion [duplicate]

Hello I have the above Context Free Grammar and I try to eliminate the left recursion so I can pass it to a tool. Any techniques I've read so far doesn't help me so a little help would be appreciated.

exp  ->   num | exp op exp | (exp)
op    ->   + | - | * | /


I don't have the slightest idea on how to proceed. The only technique I've seen on the internet is to transform a CFG where the symbol appears once with another one and not twice or anything like below.

foo->foo a
| b


which can be transformed:

foo-> a bar
bar-> b bar
| epsilon


## marked as duplicate by D.W.♦, FrankW, vonbrand, Rick Decker, JuhoMay 15 '14 at 22:35

• You need to define the precedence rules. – Jared May 14 '14 at 21:29
• Did you search on this site? in a textbook? This is well-covered in standard textbooks, and there are many other questions on this site that ask a similar question. – D.W. May 15 '14 at 5:37

Given a grammar $G=(V,\Sigma,P,S)$ You can eliminate left recursion with the following algorithm:

Let $A \rightarrow A\alpha_1 | A\alpha_2|...|A\alpha_n$

be the left recursions of a variable $A$, and $A \rightarrow \beta_1 |\beta_2|...|\beta_m$ such that each $\beta_i$ doesn't starts with $A$ (meaning $\beta_i \notin A\left \{ V \cup \Sigma \right \}^{*}$

We will construct a new grammaer $G'=(V\cup \left \{ B \right \} , \Sigma, P_1, S )$ by replacing all the left recursion derivations of $A$ with the following rules:

$A \rightarrow \beta_i \: |\: \beta_i B$ for $1\leq i \leq m$, and

$B \rightarrow \alpha_j \: |\: \alpha_jB$ for $1\leq j \leq n$

You can show that $L(G) = L(G')$

Applying this algorithm on your grammar yeilds the following rules:

$exp \rightarrow num \: |\: num\: B \: |\: (exp) \: | \: (exp)\: B$

$B \rightarrow op \: exp \: | \: op\: exp \: B$

$op \rightarrow + \: |\: - \: |\: * \: |\: \: /$ (as before)

(Note that your example is wrong, it should be that $foo \rightarrow b \: \: bar$)

• Yes , the example was a mistake on the rush I changed it. Thx for your answer! You also have a mistake. What is A? – Mario May 14 '14 at 21:28
• Should be exp. Fixed it – Roi Divon May 15 '14 at 7:41