手写编译器-左递归消除

手写编译器

左递归消除

左递归语法是指表达式左侧包含有和表达式开始符号一致的非终结符号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，方法一样）