Eliminating Left Recursion [duplicate]

Question

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

Answer 1

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$)