parsing - 左递归消除

Question

我有这个语法

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

我想知道如何从这个语法中消除左递归，因为这S+S真的很令人困惑......

Answer 1

让我们看看我们是否可以简化给定的语法。

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

我们可以写成；

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

现在，您可以在熟悉的领域消除左递归。

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

请注意，e 是 epsilon/lambda。

我们已经移除了左递归，所以我们不再需要 Q 和 B。

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

在处理左递归消除时，您会发现这很有用。

Answer 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| ^