刪除帶終端的左遞歸

如何刪除以下規則的左遞歸：刪除帶終端的左遞歸

S - > aSAbb | aA

我明白如何在S - > SA | A

它變成S - > A |如'; S' - > A | AS'，但終端在這個問題上拋棄了我。

編輯：

對不起，顯然我很困惑，什麼左遞歸的。我應該問如何從右側移除左手符號。

2010-12-14 A B

它沒有左遞歸，這就是爲什麼你很難過。左遞歸要求規則開始時使用與它試圖產生的同一個非終結符，例如S-> S ...; – 2010-12-14 22:20:34

我不認爲這是可能的。語法似乎是'a^n aA（Abb）^ n'，我認爲沒有任何方法可以在沒有遞歸的情況下綁定這兩個'n'。 – BCS 2010-12-15 03:30:26

規則

S -> aSAbb | aA

沒有左遞歸。甲左遞歸規則具有以下形式

A -> Au

其中Ú是終端和非終結點的一個序列。要刪除的S規則右側的符號S，考慮：

S => aSAbb 
    => a(aSAbb)Abb 
    => a^n(aA)(Abb)^n

遞歸對S的作用是產生這一序列。等效語法是：

S -> aKAbb | aA 
K -> aSAbb | aA

的語法是等價的，因爲任何形式的

S => aSAbb 
    => a(aSAbb)Abb 
    => a(a(aSAbb)Abb)Abb

現在只是一個推導

S => aKAbb 
    => a(aSAbb)Abb 
    => a(a(aKAbb)Abb)Abb

和各導出由aA終止（我認爲：如果我錯了，請糾正我）。

2010-12-15 13:06:02 danportin

回答