手寫編譯器-左遞歸消除

手寫編譯器

左遞歸消除

左遞歸文法是指表達式左側包含有和表達式開始符号一緻的非終結符号S->Sa （該生成式中包含和表達式開始符号的非終結符号S）； 結果及時S->Sa生成式可以解析成S->Saa… … (a個數不限)，同理生成式 S->Sa|ß 也有左遞歸問題(

此處列舉消除左遞歸的2個方法

//1,直接消除左遞歸

S->Sa|ß ==> S->Sa1| …|San|ß1|…|ßn 可從重寫成 S->ß1S’|…|ßnS’ S’-> a1S’|a2S’|…|anS’ (通過引入S’)；

因為S->Sa|ß ==> S->Sa1| …|San|ß1|…|ßn解析結束的時候ß肯定是第一個。

           

2, 間接消除左遞歸

// 原則

// 1） 若消除過程中出現了直接左遞歸，就按照直接左遞歸的方法，來消除

// 2） 若産生式右部最左的符号是非終結符，且這個非終結符序号大于等于左部非終結符， 則暫不處理（後面會處理到）

// 3） 若序号小于左部的非終結符，則用之前求到的式子的右部來替換



// arrange the nonterminals in some order AI , A2, .•• , An. 這裡将所有的産生式的非終結符号列出，排序比如

// 1）S → Qc | c

// 2）Q → Rb | b

// 3）R → Sa | a

//則這裡的A1,A2,A3就是S，Q，R，并嚴格按此順序執行，下表分别是1，2，3




for ( each i from 1 to n ) {

for ( each j from 1 to i-I ) {

replace each production of the form Ai -> Aj’Y by the productions Ai -> (∂1‘Y I ∂2’Y I . . . I ∂k‘Y, where Aj -> ∂1 I ∂2 I . . . I ∂k are all current Ai productions

//這裡j<i , Aj是每條比Ai标号小的産生式，如A1，A2 ，當i==2的時候 則找到生産式右側為A1-> ∂1的并将其用Ak (K>1) 來替換 Aj ，這裡的語義就是非終結符号 Ai 的産生式， 如果右側有非終結符号 Aj出現 j<i (如果等于i，可以用上述方法1說明的方法引入S’ 将産生式有直接左遞歸的先消除) 就用 非終結符号Aj的産生式将 Aj 替換 Ak∂ ，直到 k>1

}

}

//上述算法最終得到的結果就是 Ai->Ak∂ ， 其中k>1 (Ak 隻能被比Ak編号更高的非終結符号産生式表示，是以最終會将4說明中提到的間接左遞歸集合2，3 說明中的方法來間接消除間接左遞歸)




// 接着上面的例子

S，S->→ Qc | c （Q的下标大于S，不動）

Q，Q → Rb | b （R的下标大于Q，不動）

R，R → Sa | a （S的下标比R小）

==> R → Qca | ca | a (Q比R小)

==> R-> Rbca | bca |ca |a （采用原則1，采用直接消除原則，最終肯定會出現bca,ca,aq其中一個）

==> R-> bcaR‘ | caR’ | aR‘ ， R’ = bcaR‘|£ （最終的結果消除不可到達的非終結Q，S，如若讀者想先出R，Q，方法一樣）