-1
$\begingroup$

This question already has an answer here:

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
$\endgroup$

marked as duplicate by D.W., FrankW, vonbrand, Rick Decker, Juho May 15 '14 at 22:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ You need to define the precedence rules. $\endgroup$ – Jared May 14 '14 at 21:29
  • $\begingroup$ 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. $\endgroup$ – D.W. May 15 '14 at 5:37
2
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.