如何删除左递归和右递归都存在的文法中的左递归？

Question

语法如下：

E->a
E->E+E
E->S,E
E->(E)

S-> bS'
S'-> ;bS'
S'->

我不知道如何删除左递归，因为 E 包含终结符和非终结符。并且有左递归和右递归。

Answer 1

首先让我解释一下什么是左递归： 形式的任何语法

A &rarr; A&alpha;<sub>1</sub> | A&alpha;<sub>2</sub> |...|A&alpha;<sub>n</sub> | &beta;<sub>1</sub> |&beta;<sub>2</sub>|...|&beta;<sub>n</sub>

被称为包含左递归，因为非终结符 A 出现在产生式的左侧，并且也是产生式右侧的第一个符号。 通过应用以下转换，可以将这样的文法转换为无左递归的等价形式：

A &rarr; &beta;<sub>1</sub>A' |&beta;<sub>2</sub>A'|...|&beta;<sub>n</sub>A' <br/>
A' &rarr; &alpha;<sub>1</sub>A' | &alpha;<sub>2</sub>A' |...|&alpha;<sub>n</sub>A'

将你的语法放在相同的形式中，我们得到

E &rarr; E+E | a | S,E | (E) <br/>
S &rarr; bS'<br/>
S' &rarr; ;bS' | &epsilon;

我们可以看到左递归只发生在 E 产生式的情况下，并且也只发生在右边是 E+E 的情况下 所以我们可以在这里进行如下匹配：

&alpha; is equivalent to +E <br/>
&beta;<sub>1</sub> is equivalent to a<br/>
&beta;<sub>2</sub> is equivalent to S,E<br/>
&beta;<sub>3</sub> is equivalent to (E)<br/>

现在我们可以直接代入得到如下

E &rarr; aE' | S,EE' | (E)E' <br/>
E' &rarr; +EE' | &epsilon;

注意与S和S'相关的产生式保持不变。 这个文法没有左递归。