国防科技大学：《编译原理》课程电子教案（PPT教学课件）第4章 语法分析——自上而下分析

4.3LL(1)分析法 ·■构造不带回溯的自上而下分析算法 口要消除文法的左递归性 口克服回溯 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 4.3 LL(1)分析法 ◼ 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯

4.3.1左递归的消除 直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为 P→PalB 其中B不以P开头。 我们可以把P的规则等价地改写为如下的 非直接左递归形式： P→BP 左递归变 P'→0P|8 右递归 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 4.3.1 左递归的消除 ◼ 直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为 P→P |  其中不以P开头。 我们可以把P的规则等价地改写为如下的 非直接左递归形式： P→P P→P| 左递归变 右递归

■一般而言，假定P关于的全部产生式是 P→Pa1lPa2l.…I PamI B1lβ2lln 其中，每个都不等于e,每个B都不以P开头 那么，消除P的直接左递归性就是把这些规 则改写成： P→BPIB2P|.IBnP P'→0P'|o2P'.|0mP'|e 左递归变 右递归 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 一般而言，假定P关于的全部产生式是 P→P1 | P2 | … | Pm | 1 | 2 |…|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规 则改写成： P→1P | 2P | … | nP P→1P | 2P |… | mP |  左递归变 右递归

■ 例文法GE): E-E+TIT T→T*F|F F→(E)1i 经消去直接左递归后变成： E→TE' E'→+TE'|8 (4.2) T→FT' P→Pa1lPa2l…I PamI B1l T'→*FT'|8 B21---18n F→(E)1i P→BPIB2P1.IBnP P'→01P'|02P'.|0mP'|e 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例 文法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) P→P1 | P2 | … | Pm | 1 | 2 |…|n P→1P | 2P | … | nP P→1P | 2P |… | mP | 

例如文法G(S): S→Qclc Q→Rbb R-Sala (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 S→Qc→Rbc→Sabc 一个文法消除左递归的条件： ©不含以为右部的产生式 ©不含回路。 P→P 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc 一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。 P P + 