什么是编译器设计中的非直接左递归？

如果文法 G(V, T, P, S) 具有以下形式的产生式，则该文法为左递归。

A → Aα | β。

上述文法是左递归的，因为产生式的左边出现在产生式右边的第一个位置。可以通过用以下产生式对替换来消除左递归

A → βA′

A′ → αA′|ϵ

左递归的一般形式为

A → Aα1|Aα2| … |Aαm|β1|β2| … βn

可以替换为

A → β1A′|β2A′| … |βnA′

A′ → α1A′|α2A′| … |αmA′|ε

在下面的文法中，它没有直接或立即左递归。但是，它可能存在非直接左递归。

S → Ab

A → Sc|d

这里，S是左递归的，因为S ⇒ Ab ⇒ Scb

消除左递归的算法

输入 - 没有循环或 ε-产生式的文法 G。

输出 - 没有左递归的等价文法。

方法

  • 将非终结符排序为 A1, A2, … An

for i = 1 to n
{
   for j = 1 to i – 1
   {
      replace each production Ai → Ajγ
      by productions Ai → δ1γ| δ2γ| … … . . |δKγ
      where Aj → δ1|δ2| … … . |δK
   }
Remove immediate left Recursion among Ai productions.
}

示例1 - 从以下文法中消除左递归。

S → Ab

A → Sc | d

解答

这些产生式没有直接左递归。因此不能直接消除。我们可以在这里使用算法来消除左递归。

步骤1 - 将非终结符 S, A 排序为 A1, A2，即标记 S = A1, A = A2

代入值

∴ A1 → A2b …………… (1)

A2 → A1c|d …………… (2)

步骤2 - 将 (1) 中的值代入 (2)

∴ A1 → A2b

A2 → A1c|d

步骤3 - 再次代入 A1 = S 和 A2 = A

∴ S → Ab ……………. (3)

A → Abc | d ……………. (4)

步骤4 - 从 A → Abc | d 中消除直接左递归

因此，

示例2 - 从以下文法中消除左递归。

S → Aa | b

A → Ac | Sd | e

解答

由于没有直接左递归，因此我们必须在此应用算法。

步骤1 - 将 S, A 分别重命名为 A1, A2。

A1 → A2a | b …………… (1)

A2 → A2c | A1d | e ……………. (2)

步骤2 - 将语句 (1) 中 A1 的值代入语句 (2) 的右边。

A1 → A2a | b

A2 → A2c | A2ad | bd | e.

步骤3 - 再次代入 A1 = S, A2 = A

S → Aa | b …………….. (3)

A → Ac | Aad | bd | e ……………… (4)

步骤4 - 语句 (4) 具有直接左递归。消除直接左递归后，我们得到

更新于：2021年10月30日

浏览量：1K+

启动您的职业生涯

通过完成课程获得认证

开始学习
广告