左递归消去

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是/

我们去掉了左递归，所以我们不再需要Q和b了。

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

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

Answer 2

我的答案是使用这个参考

如何消除上下文无关语法中的左递归。

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

我们可以写成

——>年代α<子> 1 |年代α<子> 2 |年代α<子> 3 | 1β<子> |β2 <子>

转换为等效非递归语法的规则:

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

,

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

And β -productions not start started with S:

β₁ = a
β₂ = (S)

不含左递归的语法:

非左递归产物S --> β_n

S -->  a | (S)   

引入新的变量Z，产生如下结果:Z—> α_n和Z—> α_nZ

Z --> +S | S | * 
and 
Z --> +SZ | SZ | *Z  

和S新产品:S -> β_nZ

S -->  aZ | (S)Z     

---

第二种形式(答案)

产品Z --> +S | S | *和Z --> +SZ | SZ | *Z可以合并为Z --> +SZ | SZ | *Z| ^，其中^为空符号。

Z --> ^用于从生产规则中删除Z。

所以第二个答案:

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