什麼是編譯器設計中的非直接左遞迴？

如果文法 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+

啟動您的職業生涯

透過完成課程獲得認證

開始學習
廣告