Left recursion elimination

问题:

I have this grammar

S->S+S|SS|(S)|S*|a

I want to know how to eliminate the left recursion from this grammar because the S+S is really confusing...

回答1:

Let's see if we can simplify the given grammar.

S -> S*|S+S|SS|(S)|a

We can write it as;

S -> S*|SQ|SS|B|a
Q -> +S
B -> (S)

Now, you can eliminate left recursion in familiar territory.

S  ->  BS'|aS'
S' ->  *S'|QS'|SS'|e
Q  ->  +S
B  ->  (S)

Note that e is epsilon/lambda.

We have removed the left recursion, so we no longer have need of Q and B.

S  ->  (S)S'|aS'
S' ->  *S'|+SS'|SS'|e

You'll find this useful when dealing with left recursion elimination.

回答2:

My answer using theory from this reference

How to Eliminate Left recursion in Context-Free-Grammar.

S -->  S+S | SS | S*    |        a | (S)
      --------------            -------   
      Sα form                   β form    
      Left-Recursive-Rules      Non-Left-Recursive-Rules       

We can write like

S ---> Sα₁ | Sα₂ | Sα₃ | β₁ | β₂

Rules to convert in equivalent Non-recursive grammar:

S ---> β₁ | β₂
Z ---> α₁ | α₂ | α₃
Z ---> α₁Z | α₂Z | α₃Z
S ---> β₁Z | β₂Z

Where

α₁ = +S
α₂ = S
α₃ = *

And β-productions not start starts with S:

β₁ = a
β₂ = (S)

Grammar without left-recursion:

Non- left recursive Productions S --> β_n

S -->  a | (S)   

Introduce new variable Z with following productions: Z ---> α_n and Z --> α_nZ

Z --> +S | S | * 

and 

Z --> +SZ | SZ | *Z  

And new S productions: S --> β_nZ

S -->  aZ | (S)Z     

---

Second form (answer)

Productions Z --> +S | S | * and Z --> +SZ | SZ | *Z can be combine as Z --> +SZ | SZ | *Z| ^ where ^ is null-symbol.

Z --> ^ use to remove Z from production rules.

So second answer:

S --> aZ | (S)Z and Z --> +SZ | SZ | *Z| ^