左遞歸消除

Question

我試圖通過消除間接遞歸然後直接遞歸來消除CFG的左遞歸，如algorithm所示。

我將使用這個語法：

A = A a | A B C | B C | D D 

當I = 1和J = 1我們正在尋找替代形式A的所有作品 - > A R與：

A→δ γ | δ γ | .. | δ _ķ γ

所以，當我看着A - >一個一個相匹配，我應該

A -> A a a | A B C a a | B C a | D D a 

更換其即時通訊肯定是不對的

任何人都可以點我當你用生產本身來取代產品時，如何取代產品的正確方向？

注：另外，我只是停留在第一個規則，以便省略了他人的簡單

任何幫助，將不勝感激

[更新]發現接近原來的希臘符號我可以。另外，我是否可能在錯誤的方向上接近這一點。當i = 1和j = 1，A _j→A a | A B C | B C | D D，但我應該使用A _j - > B C | d d 如果是這樣的話，我會得到：

A -> B C A | B C B C | D D A | D D B C | B C | D D 

至於那些然後消除在生產遞歸。這是一個更好的方向？

Answer 1

這是配方：

A → Aα1 | ... | Aαm | β1 | ... | βn 

應轉化爲：

A → β1 A' | ... | βn A' 
A' → α1 A' | ... | αm A' | ε 

即：

1. 新的作品中，遞歸是在更換遞歸作品對。爲此使用新的非終端符號。
2. 將一個空白右側的產品添加到新的非終端。
3. 在非遞歸作品的右側附加新的非終端符號。

對於你的語法：

A = A a | A B C | B C | D D 

你將獲得：

A = B C A' | D D A' 
A' = a A' | B C A' | ε