[Solved]: How to eliminate the left recursion

Problem Detail: 

I've read the rules, but can't apply them to this grammar

S -> SS S -> (S) S -> () 

Could anyone provide some detailed explanation ?

Asked By : Mad Hollander

Answered By : Sayan Bandyapadhyay

By replacing $S$ using the other rules you can eliminate the left recursion.

Here in $S \Rightarrow SS$, replace the first $S$ after arrow with $(S)$ and $()$. Thus we get,

$S \Rightarrow (S)S$

$S \Rightarrow ()S$

$S \Rightarrow (S)$

$S \Rightarrow ()$

Now see there is no left recursion.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24662

3.2K people like this

 Download Related Notes/Documents