编译原理 第四章 语法分析—自上而下分析
+
在最左推导中有P=>P?形式，称为间接左递归。 ①消除直接左递归 P→P? | ? 改写为：P→?P ?
P ??? P ? ? ?
例：表达式文法 E? E+T ? T 改写为：E? TE?
E?? +TE? ? ? T? T*F ? F 改写为：T? FT?
T?? *FT? ? ? F? (E) ? i
②消除文法的左递归一般规则
P→P?1?P?2?…… P?m??1??2? …… ??n ?i≠? 改写为：
P→?1P???2P??………?n P? P→?1P???2P??………?m P? ?? ③消除间接左递归
A→B…
B→C… 间接左递归: A?B…?C…?A… C→A…
制作人：李明新 共28页第6页 13-3-24
编译原理 第四章 语法分析—自上而下分析
例：文法G
S→Qc|c Q→Rb|b R→Sa|a
最左推导：S?Qc?Rbc?Sabc（间接左递归）
⑶清除间接左递归
非终结符排序为R，Q，S。R不存在直接左递归，把的规则：
Q→Sab | ab | b 再把Q代入S：
S→Sabc | abc | bc | c 消除S的左递归：
S→abcS?
| bcS?
| cS?
S?→abcS?
| ?
Q和R的产生式不再被引用，将Q和R删除。
非终结符排序为S，Q，R。S不存在直接左递归，不包含S，再把S代入得到R:
R→Rbca | bca | ca | a 消除S的左递归：
R→bcaR?
| caR?
| aR?
R?→bcaR?
| ?
改写为：
制作人：李明新 共28页第7页 13-3-24
R代入QQ的产生式编译原理 第四章 语法分析—自上而下分析
S→Qc|c 不能删除 Q→Rb|b 不能删除
R→bcaR?|caR?|aR?
R?→bcaR?|?
3、消除回溯，提取左因子 ⑴消除回朔
文法G不包含左递归，则G中非终结符号的每个候选式首字符集FIRST（?）为：
** *
FIRST（?）={a??=>a…,a?VT ，??（VNUVT）}若?=>?，则
? ? FIRST（?）。
⑵提取最左公共因子
采用提取最左公共因子的方法改写文法，使得所有侯选式的首字符集两两不相交。
A→??1???2? …… ???n ??1??2? …… ??m 提取公因子:
A→?(?1??2? …… ??n) ??1??2? …… ??m 改写后为:
A→?A???1??2? …… ??m
A?→?1??2? …… ??n
4、确定的自上而下分析方法 ⑴预测分析法（LL（1）分析法）。 ⑵递归子程序法。
制作人：李明新 共28页第8页 13-3-24
编译原理 第四章 语法分析—自上而下分析
第三节 预测分析法（LL（1）分析法） 一、LL（1）分析方法
1、是按自左（第一个“L”）向右的顺序扫描输入字符串；
2、在分析过程中产生句子的最左（第二个“L”）推导； 3、 “1”表示在分析过程中，每一步推导，最多只能向前查 看（向右扫描）一个字符。 二、LL（K）分析方法
如果分析过程的每一步推导，要向前查看K个输入字符，则称为LL（K）分析法。 三、LL（1）文法的定义
该文法是上下文无关的一个子集，是自上而下分析技术的一类文法。
四、LL（1）分析法的必要条件
1、文法中的非终结符号不包含左递归；
2、对于文法中的每一个非终结符A的各个产生式的侯选首字符集两两不相交。对于产生式A????:
⑴若? ? ?，证明侯选式?，?的首字符集是否相交。
FIRST（?）∩FIRST（?）= Ф
⑵若?＝ε，证明FIRST（A）和FOLLOW（A）是否相交。
FIRST（A）∩FOLLOW（A）=φ
五、构造FIRST集合的算法 对每一文法符号X?（VNUVT）
制作人：李明新 共28页第9页 13-3-24
*
编译原理 第四章 语法分析—自上而下分析
1、若X?VT ，则 FIRST（X）={X}。
2、若X?VN ，且有产生式X?a?，a?VT，则a?FIRST（X）。 3、若X?VN ，X??，则??FIRST（X） 4、若X?VN ，且Y1，Y2，?，Yi ?VN，
*
而有产生式X? Y1，?，Yn。当Y1，Y2，?，Yi-1都 =>?时，（其中1≤i≤n），则FIRST（Y1，）-{?}，?，FIRST（Yi-1）-{?}， FIRST（Yi）都包含在FIRST（X）中。若FIRST（Yj）包含?把?加到FIRST（X）中。
例 文法G
E →TE` E`→+TE`|ε T →FT` T`→*FT`|ε F→（E）|i
FIRST（E）=FIRST（T）=FIRST（F）={（，i ）} FIRST（E?）={ +，ε} FIRST（T?）={ *，ε}
六、构造FOLLOW集合的算法
*
FOLLOW (A)={a | S=>….Aa…. , a? VT } *
若S=>…A, 则 #? FOLLOW (A)
FOLLOW (A)为所有句型中紧跟在非终结符A后面的所有终结符集合。
制作人：李明新 共28页第10页 13-3-24