如何消除有ε生產的左遞歸？

Question

我已經看到這link。但是我有點困惑如何消除這裏的∈生產。

我有以下的語法

S-->Sz|Sxw|xw|yw|∈ 

取出小量生產的語法後，我可以看到變成

S-->Sz|Sxw|xw|yw|z 

現在，如果我解決這個問題我有一個像下面

S-->xwS`|zS`|ywS` 
    S`-->zS`|xwS`|∈ 

現在我可以看到S - > xwS` | zS`和S` - > zS` | xwS`。這已經變得一樣。是正確的還是我正在做任何錯誤？

Answer 1

重複的規則沒有任何問題。

一種方式我試圖理解語法的時候經常會發現有用的，因爲它給了我整個語法很好的概述，並發現錯誤，有助於將其轉換爲一個正則表達式

S := (xw + yw + z)(z + xw)* 

。所以如果我把它分成這樣：

S := (xw + yw + z)S' 
S' := (z + xw)* 

它使得它更容易看到，如果我犯了任何錯誤。