消除立即左遞歸

Question

我明白，爲了消除包含生產形式A⇒Aα我需要A⇒βA'andA'⇒αA/∈

來取代它的語法立即左遞歸林具有如下製作，我需要消除立即左遞歸

E⇒E+ T/T

E⇒E+ T/T

T⇒T* F/T

F⇒（E）/（ID）

我可以看到取消後的第一個生產成爲

E⇒TE '

E'⇒+ TE'/T∈

燦有人解釋這如何

Answer 1

這真的只是一個算法以下的問題。我們來看一般情況。根據該算法具有以下形式的規則：

A => A a1 | ... | A aN | b1 | .. | bN 

其中A a1, ..., A aN是終端和非終結符和b1, ..., bN的非零左遞歸序列是終端和非終結點不與該終端A開始的序列。

該算法說，我們需要通過

A => b1 A' | ... | bN A' 
A' => a1 A' | ... | aN A' | epsilon 

替換此讓我們看看你的情況。在這裏，我們有

E => E + T | T 

所以，你能想到的a1是因爲E + T序列+ T是終端和終結符號的左遞歸序列。同樣，您可以將B1視爲T，因爲這是一個非左旋遞歸序列。現在我們使用這種方法來定義新的非終結E爲：

E => b1 E' 

而且由於b1是T這成爲

​​

定義E'我們得到

E' => a1 E' | epsilon 

而且由於a1是+ T這變成

E' => + T E' | epsilon 

因此你結束了語法

E => T E' 
E' => + T E' | epsilon