左递归消除题

Question

我正在研究删除语法中的左递归。 （3 个语法）

1. A->Ab | aC
   B->BaBB | BA       
   C->bC | BA                     

2. T->Txxy | TaabT | TTa               


3. A-> BA | Baa         
   B-> Ab | Abb           

我试过这样做，但我不确定我的答案。 第一个，我不知道该怎么做。第二，第三个我认为它会失败。我的回答对吗？ 我该如何改变它？ 请哪位详细解释一下。

Answer 1

我写了解决方案。我没有太多时间来输入整个内容，而且我不确定这个问题是否会因为 offtopic 而不再可用。

在 first grammar solution

处查看第一个语法的解决方案

对于第二个文法，要么文法不完整，要么左递归无法去除，没有空产生式，也没有任何只有终结符的产生式。它是无限循环的，因此不能删除左递归。

对于第三种语法，我们可以做到

A-> BA | Baa         
B-> Ab | Abb  

Replace All B's into A
A-> AbA | Abaa | AbbA | Abbaa

现在所有的产品都是递归的，甚至不能终止语法。您要么需要一个空生产式，要么需要一个只有终端的生产式。