2、直接左递归的消除 候选式： >消除方法： 若：A一>AaB,其中B不以A开头 则修改规则为：A一>BA' A'->aA'E
2、直接左递归的消除 候选式： A->Aα|β β βα βαα βααα … … A -> βA’ A’-> α A’ | ε ➢消除方法： 若：A —＞ Aα|β ，其中β不以A开头 则修改规则为：A —＞ βA′ A′—＞ αA′|ε
例5.2文法： >消除方法： E一>E+TIT 若：A一>Aa|B,(B不以P开头) T一>T*F|F 则修改规则为：A一>BA F->(E)li A'->aA's 消去直接左递归后： E一>TE' E'一>+TE'IE T一>FT' T'一>*FT'|e F一>（E)Ii
消去直接左递归后： E —＞ TE′ E′—＞ +TE′|ε T —＞ FT′ T′—＞ *FT′|ε F —＞（E）| i 例5.2 文法： E —＞ E+T | T T —＞ T*F | F F —＞（E）| i ➢消除方法： 若：A —＞ Aα|β ，(β不以P开头) 则修改规则为：A —＞ βA′ A′—＞ αA′|ε
3、间接和潜在左递归的消除 >代入法 N替 >间接和潜在左递归通常通过代入能转换为 的 直接左递归 式来 例5.3N->a|Bc|e在S->pNq中的代入结果为 S->paqlpBcqlpq
3、间接和潜在左递归的消除 ➢代入法 将一个产生式规则右部的α中的非终结符N替 换为N的候选式。如果N有n个候选式，右边的α 重复n次，而且每一次重复都有N的不同候选式来 代替N。 例5.3 N->a|Bc|ε在S->pNq中的代入结果为 S->paq|pBcq|pq ➢间接和潜在左递归通常通过代入能转换为 直接左递归
4、消除一个文法的一切左递归算法 。对文法G的所有非终结符进行排序 ●按上述顺序对每一个非终结符P1依次执行： >for(j=1;j<i-1;j++) 将Pj代入Pi的产生式（若可代入的话)； >消除关于P1的直接左递归； ●化简上述所得文法
4、消除一个文法的一切左递归算法 ⚫对文法G的所有非终结符进行排序 ⚫按上述顺序对每一个非终结符Pi依次执行: ➢for( j=1；j< i-1；j++) 将Pj代入Pi的产生式（若可代入的话）； ➢消除关于Pi的直接左递归； ⚫化简上述所得文法
5、消除回湖、提左因子 ●回湖原因 若当前特号=a,对A展开，而A->aa2…|am, 那么，要知道哪一个a:是获得以开头的串的唯一替换式。 即：选择哪一个，亦即通过查看第一个（当前）符号来发 现合适的替换式心i 怎样选择a? ①以a为头的a1 ②如有多个a:以a为头的，这是文法的问题
5、消除回溯、提左因子 ⚫回溯原因 若当前符号= a，对 A 展开，而A ->α1|α2|…|αm ， 那么，要知道哪一个αi是获得以a开头的串的唯一替换式。 即：选择哪一个αi，亦即通过查看第一个（当前）符号来发 现合适的替换式αi。 怎样选择αi？ ①以a为头的αi ②如有多个αi以a为头的，这是文法的问题