《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析——自上而下分析

4.3(1)分析法 构造不带回溯的自上而下分析算法 ロ要消除文法的左递归性 克服回溯 编译原理

编译原理 4.3 LL(1)分析法 ◼ 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯

4.3.1左递归的消除 ■直接消除见诸于产生式中的左递归:假 定关于非终结符P的规则为 P→Pa|β 其中不以P开头。 我们可以把P的规则等价地改写为如下的 非直接左递归形式: P→左递归变 P→a右递归 编译原理

编译原理 4.3.1 左递归的消除 ◼ 直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为 P→P |  其中不以P开头。 我们可以把P的规则等价地改写为如下的 非直接左递归形式： P→P P→P| 左递归变 右递归

一般而言,假定P关于的全部产生式是 →papa 2l...2 Paml B11 其中,每个a都不等于,每个β都不以P开头 那么,消除P的直接左递归性就是把这些规 则改写成: P→p'2p'np '→ap'a2'amp'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+T|T T→T*F|F F→(E)|i 经消去直接左递归后变成: E→TE E'→+te'(4.2) T→FT P→a1pa2pam1 T'→fte B2l... Bn F→(E)|i P→p'2p'nP P'→ap'a'ap' 编译原理

编译原理 ◼ 例 文法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): →Q|c Q→Rb|b R→Sa|a (4.3) 虽没有直接左递归,但S、Q、R都是左递归的 Sq→bcSabc 一个文法消除左递归的条件: 不含以为右部的产生式 不含回路。 P→P 编译原理

编译原理 ◼ 例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc 一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。 P P + 