你的浏览器禁用了JavaScript, 请开启后刷新浏览器获得更好的体验!

使用终端删除左递归

如何删除以下规则的左递归： S - > aSAbb | AA 我知道如何在S - > SA |上执行它一个变为S - > A |如'; S' - > A | AS'，但终端在这个问题上让我失望。编辑：对不起，显然我对于递归是什么感到困惑。我应该问一下如何从右侧移除左手符号。

已邀请:

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终止（我想：如果我错了，请纠正我）。

要回复问题请先登录或注册