编译原理 之 自顶向下语法分析方法

第五章 自顶向下语法分析方法,本章要点 LL(1)分析 First 集合和Follow集合 使用递归下降分析算法进行自顶向下的分析 预测分析程序 非LL(1)文法的改造,自上而下分析算法,自顶向下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子,若输入串是给定的句子,则必能推出,反之必然出错。 自顶向下分析法又分为确定的和不确定的两种。,5.1 确定的自顶向下分析思想,确定的自顶向下分析方法，首先要解决从 文法的开始符号出发，如何根据当前的输 入符号（单词符号）唯一地确定选用哪个 产生式替换相应非终结符往下推导，或构 造一棵相应的语法树。,例5.1,若有文法G1S： S pA | qB A cAd | a B dB | b 若输入串W=pccadd。自顶向下推导过程为 S=>pA=>pcAd=>pccAdd=>pccadd,这个文法有以下两个特点：,每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。,例5.2,若有文法G2S为： S Ap S Bq A a A cA B b B db,当输入串W=ccap，那么试图推出输入串的推导过程为： S=>Ap=>cAp=>ccAp=>ccap,例5.2文法的特点是：,产生式的右部不全是由终结符开始 如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。 文法中无空产生式,定义5.1,设G=(VT,VN,P，S)是上下文无关文法 FIRST（）=a| a,aVT, ,V*若 则规定FRIST（）不难求出在文法G2中 FIRST(Ap) = a, c FIRST(Bq) = b, d,例5.3,若有文法GS: SaA Sd AbAS A 若输入串W=abd，则试图推导出abd串的推 导过程为：S=>aA=>abAS=>abS=>abd,从例5.3可以得出下列结论,当某一非终结符的产生式中含有空产生式 时，它的非空产生式右部的首符号集两两 不相交，并与在推导过程中紧跟该非终结 符右边可能出现的终结符集也不相交，则 仍可构造确定的自顶向下分析。,定义5.2,设G=(VT,VN,P，S)是上下文无关文法, AVN, S是文法开始符号 FOLLOW(A)=aS A 且aVT aFRIST()，V*，V+ 若S A ,且 ，则 #FOLLOW(A),定义5.3,给定上下文无关文法的产生式A, AVN, V*, 若>*，则 SELECT(A ) = FIRST() 如果 ，则 SELECT(A ) = (FIRST() - )FOLLOW(A),定义5.4,一个上下文无关文法是LL（1）文法的充 分必要条件是，对每个非终结符A的两个 不同产生式，A， A，满足 SELECT(A) SELECT(A ) = 其中、不能同时 。,LL(1)文法的含义：,第1个“L”指的是由左向右地处理输入。第2 个“L”指的是它为输入串描绘出一个最左推 导。括号中的数字1意味着它只需向右看一 个符号便可决定如何推导即选择哪个产生 式（规则）进行推导。,例5.3的文法,SaA Sd AbAS A,不难看出： SELECT(SaA) = a SELECT(Sd) = d SELECT(AbAS) = b SELECT(A) = a, d, # 所以 SELECT(SaA) SELECT(Sd) = SELECT(AbAS) SELECT(A)=,例5.4,设文法GS为： SaAS Sb AbA A,则 SELECT(SaAS) = aSELECT(Sb) = bSELECT(AbA) = bSELECT(A) = a, b SELECT(SaAS) SELECT(Sb)= SELECT(AbA)SELECT(A),5.2 LL(1)文法的判别,1求出推出的非终结符 2计算FIRST集 3计算FOLLOW集 4计算SELECT集,1求出推出的非终结符,扫描文法中的产生式 删除所有右部含有终结符的产生式, 若这使得以某个非终结符为左部的所有产生式都被删除，说明该非终结符不能推出. 若某个非终结符的某个产生式的右部为,说明该非终结符能推出. 删除以该非终结符为左部的所有产生式. 扫描产生式右部的每一个符号 若扫描到的非终结符能推出, 则删除该非终结符，如这样使产生式右部为空，说明该非终结符能推出. 删除以该非终结符为左部的所有产生式. 若扫描到的非终结符不能推出, 则删除该产生式，如这样使以该非终结符为左部的所有产生式都被删除，说明该非终结符不能推出. 重复，直到扫描完文法的产生式，数组中非终结符的特征在没有改变为止.,例5.5 若文法GS为：,SAB SbC A Ab B BaD CAD Cb DaS Dc,SAB A B CAD,SAB CAD,CAD,Step 1,Step 2,Step 3,定义法：求文法符号FIRST(X),若XV，则FIRST(X)=X； 若XVN，且有产生式Xa，则把a加入到FIRST(X)中； 若XVN，X 也是一条产生式，则把也加到FIRST(X)中； 若XVN， X Y1Y2Yn 是一个产生式，Y1, Y2,Yi-1(1in)都是非终结符，而且对于任何j，1ji-1, FIRST(Yj)都含有 (即Y1， ，Yi-1 )，则把FIRST(Yj)（1ji-1）中的所有非元素以及FIRST(Yi)，都加到FIRST(X)中； 在(d)中，若所有的FIRST(Yj , j=1,2,n)均能推出，则FIRST(X)= FIRST(Y1)FIRST(Y2)FIRST(Yn)。反复使用上述(b)-(e)步骤，直到每个符号的FIRST集合不再增大为止。,求符号串的FIRST(), = Y1Y2Yn 当Y1 >* 时，FIRST() = FIRST(Y1). 对于任何j，1ji-1, 2in ，FIRST(Yj)都含有 (即Y1， ，Yi-1 )，则:FIRST() = (FIRST(Y1)- )(FIRST(Yi-1)- )FIRST(Yi). 当所有Yi （1in），则FIRST() = FIRST(Y1)FIRST(Yn).,例5.5 若文法GS为：,SAB SbC A Ab B BaD CAD Cb DaS Dc,文法GS的每个非终结符的FIRST集： FIRST(S)=FIRST(A) FIRST(B)=a, b, FIRST(A) =b, FIRST(B) =a, FIRST(C) = (FIRST(A) - ) FIRST(D) b FIRST(D)=a, c FIRST(C) = a,b,c,例5.5 若文法GS为：,SAB SbC A Ab B BaD CAD Cb DaS Dc,文法GS的每个产生式右部符号串的FIRST集： FIRST(AB)=FIRST(A) FIRST(B)=a, b, FIRST(bC) =b FIRST() = FIRST(b) =b FIRST(aD)=a FIRST(AD)=(FIRST(A) -)FIRST(D)=a,b,c FIRST(aS) = a FIRST(c) =c,关系图法：求文法符号FIRST(X),文法符号X对应图中一个结点，若XV，用X表示；若XVN，用FIRST(X)表示。 若 X是文法的一个产生式, 且 ，则FIRST(A) FIRST(X), XVN; 或FIRST(A) X, XVT. 凡是从FIRST(A)结点有路径可到达的终结符结点的终结符都属于FIRST(A). A ，则 FIRST(A)= FIRST(A),例5.5 若文法GS为：（关系图法）,SAB SbC A Ab B BaD CAD Cb DaS Dc,FIRST(S),FIRST(A),FIRST(B),b,a,FIRST(C),FIRST(D),c,FIRST集： FIRST(S)= a, b, FIRST(A) =b, FIRST(B) =a, FIRST(C) = a,b,c FIRST(D)=a, c,3计算FOLLOW集,(1) 定义法： 对于文法的开始符号S,置#于FOLLOW(S) 中； 若 B是一个产生式, 则把FIRST()- 加至FOLLOW(B)中；如 ，则把FOLLOW（A）加至FOLLOW(B)中；这是因为当有形如：D 1A1， B 的产生式，A, B, D VN，1, 1, , V*, 在推导过程中可能出现如下的句型序列：S 1A1 =>1B1=>1B1 有：FOLLOW(A)FOLLOW(B) 反复使用(b)步骤，直到每个非终结符号的FOLLOW集合不再增大为止。,例5.5 若文法GS为：,SAB SbC A Ab B BaD CAD Cb DaS Dc,文法GS的每个非终结符的FOLLOW集： FOLLOW(S)=# FOLLOW(D) FOLLOW (A) =FIRST(B)-FOLLOW(S) FIRST(D) FOLLOW (B) = FOLLOW(S) FOLLOW (C) = FOLLOW(S) FOLLOW (D) = FOLLOW(B)FOLLOW(C) FOLLOW(S)=#; FOLLOW (A) =a,#,cFOLLOW(B)=#; FOLLOW(C)=#FOLLOW(D)=#,(2) 关系图法： S是开始符号，FOLLOW(X) #. 若 BX是文法的一个产生式, 且 ，则FOLLOW(B)FIRST(X), XVN; 或FOLLOW(B)X, XVT. 若 B是文法的一个产生式, 且 ，则FOLLOW(B) FOLLOW(A). 对图中每个FIRST(A)结点，若 X是文法的一个产生式, 且 ，则FIRST(A) FIRST(X), XVN; 或FIRST(A) X, XVT. 凡从FOLLOW(A)结点有路径可到达的终结符或#的结点，其标记的终结符或#都属于FOLLOW (A).,例5.5 若文法GS为：（关系图法）,SAB SbC A Ab B BaD CAD Cb DaS Dc,FOLLOW(A),FIRST(B),FOLLOW(S),a,c,FOLLOW集： FOLLOW(S)=# FOLLOW (A)=a, c,# FOLLOW (B)=# FOLLOW (C)=# FOLLOW (D)=#,FOLLOW(B),FOLLOW(C),FOLLOW(D),FIRST(D),