第四章 自上向下语法分析方法

<IF语句> if E then S1 else S2; <IF语句> if E then S1;
提取左因子后：
<IF语句> if E then S1 B; B else S2 |ε ;
第4章语法分析——自上而下分析
LL(1)分析条件：
是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条 件，就一定能进行有效的自顶向下分析呢？
使A A。
如果是A A，则称为直接左递归，否则称为间接左递归。
例2：设有文法： (1) E->E+T|T
E E +T
(2) T->T*F|F
E +T
(3) F->(E)|i 现有输入串i*i+i, 其分析过程是：
E
+
T
…
产生的原因？
失败：由于使用最左推导，对左递归文法进 行自顶向下分析时，会导致死循环。
从推导的角度看，从开始符号出发，使用最左推导，试图 推导出与输入符号串相同的句子。
从语法树的角度看，从根节点出发，反复使用所有可能的 产生式，谋求输入串的匹配，试图向下构造一棵语法树， 其末端结点正好与输入符号串相同。
这是一个反复试探的过程。
第4章语法分析——自上而下分析
自顶向下分析面临的问题
第4章语法分析——自上而下分析
消除回溯的方法
反复使用“提取公共左因子”的方法来改造文法，使得文法 的每个非终结符号的各个候选式的首终结符两两不相交，来 避免回溯。
例：
设产生式为：
A→δα1|δα2|…|δαn 将其替换为：
AδA’
|…|α A’α1|α2
第4章语法分析——自上而下分析

例 S::=aABbcd|ε A::=ASd|ε B::=SAh|eC|ε C::=Sf|Cg|ε 求此文法的每一个非终结符号的FIRST集。
解： FIRST(S)=FIRST(aABbcd)∪FIRST(ε) ={a}∪{ε}={a,ε} FIRST(A)=FIRST(ASd)∪FIRST(ε) ={a,d}∪{ε}={a,d,ε} FIRST(B)=FIRST(SAh)∪FIRST(eC) ∪FIRST(ε) ={a,d,h}∪{e}∪{ε}={a,d,h,e,ε} FIRST(C)=FIRST(Sf)∪FIRST(Cg) ∪FIRST(ε) ={a,f}∪{a,f,g}∪{ε}={a,f,g,ε}
4.1自顶向下的分析方法（P61）
开始符号 输入符号串
自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输入串。即：
开始符号 输入符号串
自底向上的分析方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：
+ 归约 ←
自底向上
文法符号的FIRST集合构造方法：
对于文法中的符号X∈V，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止： 若X为终结符，则将X加入FIRST(X)集合中。 若X为非终结符，且具有形如X→aα的产生式(a∈Vt)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。 设X为非终结符且有形如X→Y1Y2…Yk的产生式，若Y1∈Vn，则把FIRST(Y1)中的一切非ε符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi)中的一切非ε符号加进FIRST(X)；但若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε符号加进FIRST(X)。

A' → β1|β2|…|βn
例4.7 文法G2[A]: A→ad A→Bc B→aA B→bB
1.化为： 2.化为： 3.化为：
A→ad A→a(d|Ac) A→aA'
A→aAc A→bBc A→bBc
A→bBc B→aA
A'→d
B→aA B→bB
A'→Ac例4.8
第1个“L”指的是由左向右地处理输入。 第2个“L”指的是它为输入串描绘出一个最左推导。 括号中的数字1意味着它只需向右看1个符号便可决
定如何推导即选择哪个产生式（规则）进行推导。
4.2 LL(1)文法的判别
求出能推出ε的非终结符 计算FIRST集 计算FOLLOW集 计算SELECT集 判别是否是LL(1)文法
Y到1F..YIRi-S1 T*(X))中,则;把特F别IR是S,T若(Y所j)有中的的F所IR有S非T(Y元j ,素都加
j=1,2,…,K)均含有,则把加到FRIST(X)中.
用关系图法求文法符号的FIRST集(自学)
3.计算FOLLOW集
根据定义计算 1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若Ａ→αBβ是一个产生式,则把 FIRST(β)-{}加至FOLLOW(B)中; 3.若Ａ→αB是一个产生式,或Ａ→αBβ是一个产
第一次扫描
是是
否
第二次扫描 是
否
2.计算FIRST集
根据定义计算 1.若XV,则FIRST(X)={X} 2.若XVN,且有产生式Xa…， a∈ V,则 a∈FIRST(X);若X也是一条产生式,则 ∈FIRST(X). 3.若XY…是一个产生式且YVN,则把FIRST(Y) 中的所有非元素都加到FIRST(X)中;若X Y1Y2…YK 是一个产生式,Y1,Y2,…,Yi-1都是非终结 符,而且对于任何j,1≤j ≤i-1,FIRST(Yj)都含有(即

经压缩后文法:
S→(abc|bc|c)S’ S’ →abc S’|ε
注意：由于对非终结符的排序不同,最后得到的文法在形 式上可能是不一样的,但是它们是等价的. 按S、Q、R排列, 代入后 S→Qc│c Q→Rb│b R→ Rbca│bca│ca│a 消除R中的直接左递归得 R→ bcaR’│caR’│aR’ R’→ bcaR’│
Z ·
c A d a Z · c A d a b
完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(G[Z]) 4. 回溯 即砍掉A的子树 改选A的第二右部 Aa 检查 a-a匹配 d-d匹配
分析工作要部 分地或全部地 退回去重做叫 回溯
建立语法树,末端结点为cad与输入cad相匹配, 建立了最左推导序列 EcAdcad ∴cadL(G(E))
2．回溯问题

什么是回溯?
分析工作要部分地或全部地退回去重做叫回溯

造成回溯的原因
公共左因子的存在 即A→1| 2 某个非终结符号的规则其右部有多个选择，形如
A → 1 | 2 | 3，根据所面临的输入符号不能 准确的确定所要选择时，就可能出现回溯。

回溯带来的问题
集合FIRST、FOLLOW： 1．FIRST集（与前同） 设α是文法G的一个符号串， α (VTVN)*,定义 FIRST（α）＝{a|α* a. . . , aVT} *ε,则εFIRST(α)。 特别若α
R→Sa|a
Q→Sab|ab|b
4.把Q代入S的右部选择 5.消除S的直接左递归
最后得到文法为:
S→Sabc|abc|bc|c S→(abc|bc|c)S’ S’ →abc S’|ε S→(abc|bc|c)S’ S’ →abc S’|ε