《编译第五章终版》由会员分享，可在线阅读，更多相关《编译第五章终版（87页珍藏版）》请在金锄头文库上搜索。
1、第5章自顶向下语法分析方法,5.1 确定的自顶向下分析思想 5.2 LL(1)文法的判别 5.3 某些非LL(1)文法到LL(1)文法的等价变换 5.4 不确定的自顶向下分析思想 5.5 确定的自顶向下分析方法 5.6 典型例题及解答,引言,1、语法分析的地位 是编译程序的核心部分。 2、语法分析的任务 识别由词法分析得出的单词序列是否是给定文法的句子。 3、语法分析方法 自顶向下分析和自底向上分析 自顶向下分析包括确定分析和不确定分析 自底向上分析包括算符优先分析和LR分析,引言,4、语法分析的方式1）自上而下语法分析 反复使用不同产生式进行推导以谋求与输入符号串相匹配。2）自下而上语法分析
2、 对输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入符号指词法分析所识别的单词,引言,自顶向下分析法：也就是从文法的开始符号出发，企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。 自顶向下分析法又可分为确定的和不确定的两种。 确定的分析方法:需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器。 不确定的方法:即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。,自下而上分析法： 从输入串出发进行归约，最终归约为文法开始符。从叶结点出发，向上归结出以文法开始符为根
3、结点的语法分析树。,引言,回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。 有文法GS，若S * x，且x V*则称x是文法G S的句型。 有文法GS，若S * x，且xVT*，则称x是文法G S的句子。 例：GS： S0S1， S01 可有推导 S 0S100S11000S111 00001111 说明00001111是GS的句子。,引言,最左（最右）推导：在推导的任何一步 (其中、是句型)，都是对中的最左（右）非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。 句型的分析 句型分析就是识别一个符号串是否
4、为某文法的句型，是某个推导的构造过程。,举例：,文法：G=VN,VT,S,P P：SaAcBe Ab|Ab Bd 判断输入串abbcde是否为文法的句子。,（1）自顶向下 最左推导： s aAcBe aAbcBe abbcBe abbcde,文法：G=VN,VT,S,P P：SaAcBe Ab|Ab Bd 判断输入串abbcde是否为文法的句子。,（2）自底向上 abbcde abbcBe abAcBe aAcBe S,引言,句型分析的有关问题 如何选择使用哪个产生式进行推导？ 假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定用哪个右部去替换V呢？ 如
5、何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。,5.1 确定的自顶向下分析思想,例：若有文法G1S: S pA |qB A cAd|a B d B |b 识别输入串w= pccadd是否是G1S的句子 试探推导过程： S pA pcAd pccAdd pccadd,5.1 确定的自顶向下分析思想,G1S: S pA |qB A cAd|a B d B |b 这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。,5
6、.1 确定的自顶向下分析思想,若有文法G2S: S Ap |Bq A a|cA B b|dB 识别输入串w=ccap是否是G2S的句子，那么试探推出输入串的推导过程为 ： S Ap cAp ccAp ccap,5.1 确定的自顶向下分析思想,G2S: S Ap |Bq A a|cA B b|dB 文法的特点是： 产生式的右部不全是由终结符开始。 如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。 文法中无空产生式。,FIRST集的定义 :,设G=(VT,VN,P，S)是上下文无关文法 FIRST ( ) =a| * a,aVT, , V* FIRST ( ) =a| * a
7、,aVT 若 * 则规定FRIST ( ) FIRST ( ) 为的开始符号或首符号集。 在文法G2中， FIRST ( Ap) a,c FIRST ( Bq) b,d,返回分析前两个确定的文法 选择哪个产生式可以看其first集,结论： 因此当文法含有形如 产生式时，其中A VN ，、 V*，若和 都不能同时推导出空，则当 FIRST()FIRST() =时，对于非终结符A的替换可唯一的确定候选。,FIRST()集的构造：,对每一个文法符号x(VNV),构造first(x)时，只要连续使用下列规则，直至每个first集不再增大为止。 1.若xV,则FIRST(x)=x;如X=a,则first
8、(a)=a; 2.若XVN,且有产生式Xa，则把a加入到FIRST(X)中;若X是一条产生式,则把也加到FIRST(X)中.如xaB,则afirst(x); 3.若XY是一个产生式且YVN,则把FIRST(Y)-加到FIRST(X)中;如XYb,Yc,则cfirst(X) 若XY1Y2YK 是一个产生式,Y1,Y2,Y(i-1)VN，且Y1Y(i-1) * ,则把FIRST(Yj)-加到FIRST(X)中;特别是,若FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中. 如XAB,Aa|,Bb,则a,bfirst(X) 如XAB,Aa|,Bb|,则a,b,first(X),
9、FIRST()集举例,文法： E TG G+TG| T FH H *FH| F (E)|i,first(E)=first(T)=first(F)=(,i first(G)=+, first(H)=*,5.1 确定的自顶向下分析思想,若有文法G3S: S aA|d A bAS| 识别输入串w=abd是否是G3S的句子 推导过程为： S aA abAS abS abd,5.1 确定的自顶向下分析思想,文法的特点是： 文法中含有空产生式。 由此可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符后边可能出现的终结符集也不相交，则仍可
10、构造确定的自顶向下分析。,FOLLOW集的定义 :,设G=(VT,VN,P，S)是上下文无关文法,A VN,S是开始符号。 FOLLOW（A）=aS * A 且a FRIST（）， V*， V+ FOLLOW(A)= =aS * Aa,aVT 若S * A ,且 * ，即S * A则#FOLLOW(A) 这里我们用#作为输入串的结束符,FOLLOW()集的构造：,1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若 B 是一个产生式,则把FIRST()加至FOLLOW(B)中; 3.若 B是一个产生式,或B是一个产生式而 * (即FIRST()），则把FOLLOW（A）加至FOLL
11、OW（B）中,5.1 确定的自顶向下分析思想,若有文法G3S: S aA|d A bAS| 识别输入串w=abd是否是G3S的句子 推导过程为： S aA abAS abS abd,结论：,因此当文法含有形如: 产生式时， 其中A VN ，、 V*， 若和 不能同时推导出空，假定不能推导出空， 推导出空，则当 (FIRST()(FIRST()FOLLOW(A)=时， 对于非终结符A的替换仍可唯一的确定候选。,定义SELECT集,给定上下文无关文法的产生式 ， A VN ，、 V*， 若* 不成立，则SELECT()=FIRST() 若* 成立，则 SELECT()=(FIRST()-)FOLL
12、OW(A),LL(1)文法的定义,一个上下文无关文法G是LL(1)的充要条件是，对每一个非终结符的产生式12|n ，满足： SELECT（i） SELECT(j)=即 first(i）first(j)=,当ij;i,j=1,2n 若i*，first(j）follow(A)=,j=1,n 且ji.,第一个L表示自顶向下分析是从左向右扫描输入串 第二个L表示分析过程中将用最左推导 1表示只需向右看一个符号便可以选择哪一个规则进行推导。,LL(1)的含义,5.1 确定的自顶向下分析思想,例：G3S: S aA|d A bAS| SELECT(S aA)=a SELECT(S d)=d SELECT(
13、A bAS)= b SELECT(A )= (first-)follow(A) =follow(A) =first(S)followS=a,d,# 因此SELECT(SaA) SELECT(Sd)= SELECT(A bAS) SELECT(A )= 根据定义可知文法G3S是LL(1)文法。,5.1 确定的自顶向下分析思想,GS: S aAS | b A bA | SELECT(S aAS)=a SELECT(S b)=b SELECT(A bA)= b SELECT(A )= followA=first(S)=a,b 因此SELECT(S aAS) SELECT(S b)= SELECT(A
14、 bA) SELECT(A ) 根据定义可知文法G S不是LL(1)文法。,W=ab SaAS abAS abS S aAS aS ab,产生式的选择,假设要用非终结符A进行匹配，输入符号为a时，A的所有产生式为12|n ， （1）若afirst(i),则指派i去执行匹配任务。 （2）若a不属于任一个候选首符集，若 first(i),即i*，且a follow(A),则让A与自动匹配。 否则，a的出现是一种语法错误。,LL(1)文法的判别,根据其定义，即充分必要条件。 采用预测分析表法，判断某一文法是不是LL(1)文法，画其分析表，在MA,a中如果有多于一个的产生式，则不是LL(1)文法。,预测分析表的构造,对于文法的每个产生式A，AVN,(VNVT)* (1)对每一个a first(),将A记为MA,a中； (2)若first(),则对任何bfollow(A),把A记为MA,b中； (3)凡无定义的MA,a均标上错误标志。,例1：G3S: S aA|d A bAS|,first(S)=a,d first(A)=b, follow(S) =# follow(A) =a,d,# follow(A)=first(S)- follow(S)=a,d,#,
