《编译原理》课程教学资源：第二章（2-4）语法分析一自上而下分析

243LL(1)分析法 构造不带回溯的自上而下分析算法 ●要消除文法的左递归性 ●克服回溯

2.4.3 LL(1)分析法 构造不带回溯的自上而下分析算法 ⚫ 要消除文法的左递归性 ⚫ 克服回溯

2431左递归的消除 消除直接左递归 ●假定关于非终结符P的规则为 Pa|β 其中β不以P开头。 则可以把规则等价地改写为如下的非直接左 递归形式: →BP P/aPE

2.4.3.1 左递归的消除 消除直接左递归 ⚫ 假定关于非终结符P的规则为 P→P |  其中不以P开头。 ⚫ 则可以把规则等价地改写为如下的非直接左 递归形式： P→P P→P|

般而言,假定P关于的全部产生式是 P→Pa1|Pa2|….Pamβ1|β2,ln 其中,每个α都不等于e,而每个β都不以P 开头 那么,消除P的直接左递归性就是把这些 规则改写成: P→βP|β2P|…|βnP P→01P|a2P.lamP|e

一般而言，假定P关于的全部产生式是 P→P1 | P2 | … | Pm | 1 | 2 |…|n 其中，每个都不等于，而每个都不以P 开头 那么，消除P的直接左递归性就是把这些 规则改写成： P→1P | 2P | … | nP P→1P | 2P |… | mP | 

例文法G(E) E→E+TT T→T*F|F (E)|i 经消去直接左递归后变成: E→TE E→+TE|8 T→FT T→*T|8 F→(E)|i

例 文法G(E): E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE E→+TE |  T→FT T→*FT |  F→(E) | i (4.2)

例如文法G(S) s→Qc|c Q→Rbb SAla (43) 虽没有直接左递归,但S、Q、R都是左递归的 S→Qc→Rbc→Sabc 个文法消除左递归的条件: 不含回路。 P→Pa

例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc 一个文法消除左递归的条件： 不含回路。 P P + 