如果文法中任意一个非终结符P，若P并且在最左推导中有P
⑵间接左递归 + 在最左推导中有P=>PP
P（
VNUVT），
形式，称为直接左递归。
形式，称为间接左递归。
①消除直接左递归 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
12
n
i≠?
改写为：
……
P→ P→
1P2P………………
n Pm P
1P2P
③消除间接左递归
A→B…
B→C… 间接左递归: A C→A…
例：文法G
S→Qc|c Q→Rb|b R→Sa|a
最左推导：S?Qc?Rbc?Sabc（间接左递归）
⑶清除间接左递归
非终结符排序为R，Q，S。R不存在直接左递归，把R代入Q的规则：
Q→Sab | ab | b 再把Q代入S：
S→Sabc | abc | bc | c 消除S的左递归：
S→abcS
| bcS | ?
| cS
B…C…A…
S→abcS
Q和R的产生式不再被引用，将Q和R删除。
非终结符排序为S，Q，R。S不存在直接左递归，Q的产生式不包含S，再把S代入得到R:
R→Rbca | bca | ca | a 消除S的左递归：
R→bcaR
| caR
| aR
R→bcaR改写为：
| ?
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
12
…… m
提取公因子:
A→(
m
1
2
…… n)
12
……
改写后为:
A→A→
A
1
1
2
……
n
m
2
……
4、确定的自上而下分析方法 ⑴预测分析法（LL（1）分析法）。 ⑵递归子程序法。
第三节 预测分析法（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 1、若X
2、若X（X）。
3、若X4、若X
VN ，X
，则
FIRST（X） ，Yi
VN，
（VNUVT）*
VT ，则 FIRST（X）={X}。 VN ，且有产生式X
a
，a
VT，则a
FIRST
VN ，且Y1，Y2，
而有产生式X
*
Y1，，Yn。当Y1，Y2，，Yi-1都 =>
}，
，FIRST（Yi-1）
?时，（其中1≤i≤n），则FIRST（Y1，）-{
语法分析-自上而下分析
