context-free-grammar - 用终端去除左递归

Question

如何删除以下规则的左递归：

S -> aSAbb | 氨基酸

我了解如何在 S -> SA 上执行它 | 一个

变成 S -> A | 作为'; S' -> A | AS'，但终端在这个问题上让我失望。

编辑：

抱歉，显然我对左递归是什么感到困惑。我应该问如何从右侧删除左侧符号。

Answer 1

规则

S -> aSAbb | aA

不是左递归的。左递归规则具有以下形式

A -> Au

其中u是终结符和非终结符的序列。S要从规则右侧删除符号S，请考虑：

S => aSAbb
  => a(aSAbb)Abb
  => a^n(aA)(Abb)^n

递归的作用S就是产生这个序列。一个等价的语法是：

S -> aKAbb | aA
K -> aSAbb | aA

文法是等价的，因为任何推导

S => aSAbb
  => a(aSAbb)Abb
  => a(a(aSAbb)Abb)Abb

现在只是一个推导

S => aKAbb
  => a(aSAbb)Abb
  => a(a(aKAbb)Abb)Abb

并且每个推导都以aA（我认为：如果我错了请纠正我）终止。