逐步消除這種間接左遞歸

Question

我見過this algorithm應該可以使用它來刪除所有左遞歸。 然而，我正在與這個特定的語法問題：

A -> Cd 
B -> Ce 
C -> A | B | f 

無論我嘗試我在循環或語法仍然是間接的左遞歸的結束。

在此語法上正確實施this algorithm的步驟是什麼？

Answer 1

規則是你首先爲非終端建立某種順序，然後找到所有發生間接遞歸的路徑。對於非終端C遞歸

在這種情況下爲了將是一個<乙< C，和可能的路徑將是

C=> A => Cd 

和

C=> B => Ce 

對於C會如此新規則

C=> Cd | Ce | f 

現在你可以簡單地刪除直接的左遞歸：

C=> fC' 
C'=> dC' | eC' | eps 

所得非遞歸語法是：

A => Cd 
B => Ce 
C => fC' 
C' => dC' | eC' | eps 

Answer 2

已經算出來了。

我的疑惑是，按照這個順序，算法似乎什麼都不做，所以我認爲肯定是錯的，並開始在第一次迭代中替換A - > Cd（忽略j不能超越i）進入無限循環。

1）通過重排的規則：

C -> A | B | f 
A -> Cd 
B -> Ce 

2）中所述的替換C - >鎘

C -> A | B | f 
A -> Ad | Bd | fd 
B -> Ce 

3）乙尚未在j的範圍內，所以留給和替換直接的

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ce 

4左遞歸）在乙替換C - >鈰

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ae | Be | fe 

5）尚未完成！還需要更換新的規則B - > AE（製造用的是j的範圍內）

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> BdA'e | fdA'e | Be | fe 

6）B中

哇噢的

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> fdA'eB' | feB' 
B'-> dA'eB' | eB' | epsylon 

生產代替直接左遞歸！左遞歸自由語法！