因为若文法中有左递归则会出现下列情况:
 |
例5.12 |
|
文法G5含有直接左递归:
S→Sa
S→b
所能产生的语言L={ban|n≥0},对输入串baaaa#是该语言的句子,但用自顶向下分析时可看出当输入符为b时,为与b匹配则应选用S→b来推导,但这样就推不出后边部分,而若用S→Sa推导则出现图5.6的情况,无法确定到什么时候才用S→b替换。另一方面,用递归子程序法时,在处理S的过程中,没有对当前输入符号匹配就又进入递归调用处理S的过程,这样就会造成死循环。
图 5.6 含直接左递归文法的语法分析树结构 |
 |
对含有间接左递归的文法同样可有上述现象。
含有间接左递归的文法例5.13 有文法G6为:
(1) A→aB
(2) A→Bb
(3) B→Ac
(4) B→d
若有输入串为adbcbcbc#,则分析过程的语法树为图5.7(a)。 |
图5.7 含间接左递归文法的语法分析树 |
 |
这时B若用产生式(4)替换,则推导到此终止,不能推出adbcbcbc#,而若选用(3)则有图5.7(b)。
而自左向右分析法在没有与当前输入符号匹配又进入A陷入死循环那么只能用带回溯的不确定分析方法。 |