编译第五章终版.ppt

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.1

6、 确定的自顶向下分析思想,若有文法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,a

7、VT 若 * 则规定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(a

8、)=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，且Y1.Y(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）加至FOLLOW

11、（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()-)FOLLOW(A

12、),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(A bA

13、S)= 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 bA)

14、 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)文法。,预测分析表

15、的构造,对于文法的每个产生式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,#,所以是LL(1)文法,例2：GS: S aAS | b A bA |,first(S)=a,b first(A)=b, follow(S)=#

16、follow(A) =first(S)=a,b,所以不是LL(1)文法,预测分析表举例,文法： E TG G+TG| T FH H *FH| F (E)|i,first(E)=first(T)=first(F)=(,i first(G)=+, first(H)=*, follow(E)=#,) follow(G)=follow(E)=#,) follow(T)=first(G)- follow(G)=+,),# follow(H)=follow(T)=+,),# follow(F)=first(H)- follow(H)=*, +,),#,预测分析表,预测分析表的使用,匹配句子(i+i)*i#

17、的过程： ETG FH (E)H (TG)H (FHG)H (iHG)H (iG)H (i+TG)H (i+FHG)H (i+iHG)H (i+i)H (i+i)*FH (i+i)*iH (i+i)*i (i+i)*i,预测分析表举例,S AB|bC A |b B |aD C AD|b DaS|c,first(S) =(first(A) - ) first(B) b=,b,a first(A)=,b first(B)=,a first(C) = (first(A)- ) first(D) b=a,b,c first(D)=a,c,first(S)=,b,a first(A)=,b first(

18、B)=,a first(C)=a,b,c first(D)=a,c,S AB|bC A |b B |aD C AD|b DaS|c,follow(S)=# follow(D)=# follow(D)=follow(C) follow(B) =# follow(C)= follow(S) =# follow(B)= follow(S) =# follow(A)=first(B)- follow(S) first(D) =a,c,#,预测表构造：,所以不是LL(1)文法。,某些非LL(1)文法到LL(1)文法的等价变换,1、由LL(1)文法的定义：可知若文法中含有 直接或间接左递归； 含有左公共因

19、子则该文法 肯定不是LL(1)文法。 2、方法：进行等价变换 消除文法中的左递归， 提取左公共因子对文法， 在某些特殊情况下可能使其变为LL(1)文法。,含有左公因子,1提取左公共因子 若文法中含有形如：A | 的产生式，SELECT(A )SELECT(A) ，不满足LL(1)文法的充分必要条件。 现将产生式A |进行等价变换为：A ( | ) 引进新非终结符A，去掉(，)使产生式变换为： A A A | ,提取左公因子,写成一般形式为：A1| 2| n，提取左公共因子后变为：A(1| 2|n），再引进非终结符A，变为：AA A1|2|n 在i、 j、k (其中1i，j，kn)中仍含有左公共

20、因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。,举例1，变换后还不是LL(1)文法,若文法G1的产生式为：(1) SaSb (2) SaS (3) S 请提取文法中的左公因子。 对产生式(1)、(2)提取左公因子后得： S aS(b|)S进一步变换为文法G1：SaSAAbAS,first(S)=a, first(A)=b, follow(A) =follow(S) =# first(A)- =b,#,举例2，变换后为LL(1)文法,若文法G2：(1) Aad (2) ABc (3) BaA (4) BbB请提取文法中的隐式左公因子。 对右部以非终结符开

21、始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换，对文法G2分别用(3)、(4)的右部替换(2)中的B，可得： (1) Aad (2) AaAc (3) AbBc (4) BaA (5) BbB 提取产生式(1)、(2)的左公共因子得： Aa(d|Ac) AbBc BaA BbB 引进新非终结符A，去掉(，)后得G2为： (1) AaA (2) Ad (3) A Ac (4) AbBc (5) BaA (6) BbB,文法注意,经验证： 提取左公共因子后文法G1仍不是LL(1)文法。 文法G2变成LL(1)文法， 因此文法中不含左公共因子只是LL(1)文法的必要条件。 值得注意的

22、是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩(或化简)。,举例3，变换后产生无用产生式,文法G3：(1) SaSd (2) SAc (3) AaS (4) Ab 用产生式(3)、(4)中右部替换产生式(2)中右部的A，变为： (1) SaSd (2) SaSc (3) Sbc (4) AaS (5) Ab 对(1)、(2)提取左公共因子得：SaS(d|c)引入新非终结符A后变为： (1) SaSA(2) Sbc (3) Ad|c (4) AaS (5) Ab 显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产

23、生式，所以应删除。变为： (1) SaSA(2) Sbc (3) Ad|c,举例4，不能在有限步骤内提取完左公共因子,文法G4： (1) SAp|Bq (2) AaAp|d (3) BaBq|e 用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为： (1)SaApp|aBqq (2) Sdp|eq(3)AaAp|d (4) BaBq|e 对(1)提取左公共因子则得：Sa(App|Bqq)再引入新非终符S结果得等价文法为： (1) SaS (2) Sdp|eq (3) SApp|Bqq (4) AaAp|d (5) BaBq|e 同样分别用(4)、(5)产生式的右部替换(3)中右部

24、的A、B再提取左公共因子最后结果得： (1) SaS(2) Sdp|eq(3) SaS(4) Sdpp|eqq (5) SAppp|Bqqq (6) AaAp|d (7) BaBq|e 可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。,提取左公因子存在的问题, 不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法G4就是如此。 一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1

25、)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。,消除左递归,设一个文法含有下列形式的产生式。 直接左递归：1)AA AVN，V* 间接左递归： 2)AB BA A,BVN, ,V* 产生式的文法有A + A 则称文法中含有左递归。 一个文法是左递归时不能采用自顶向下分析法。,直接左递归存在问题：,文法G5含有直接左递归： SSa Sb 所能产生的语言L=ban|n0， 对输入串baaaa#是该语言的句子，但用自顶向下分析时可看出当输入符为b时，为与b匹配则应选用Sb来推导，但这样就推不出后边部分，而若用SSa推导则出现图5.6的情况，无法确定到什么时候才用Sb

26、替换。 另一方面，用递归子程序法时，在处理S的过程中，没有对当前输入符号匹配就又进入递归调用处理S的过程，这样就会造成死循环。,间接左递归存在问题,文法G6： (1) AaB (2) ABb (3) BAc (4) Bd 若有输入串为adbcbcbc#，分析过程的语法树见右图。 这时B若用产生式(4)替换，则推导到此终止，不能推出adbcbcbc#，而若选用(3)则有图5.7(b)。 而自左向右分析法在没有与当前输入符号匹配又进入A陷入死循环那么只能用带回溯的不确定分析方法。,消除左递归,含有左递归的文法绝对不是LL(1)文法，为了使某些含有左递归的文法经过等价变换消除左递归后可能变为LL(1

27、)文法，可采取下列变换公式： 1) 消除直接左递归，把直接左递归改写为右递归. 如对文法G5： SSa Sb 可改写为： SbS SaS| 改写后的文法和原文法产生的语言都为：ban|n0。,消除左递归,一般情况下，假定关于A的全部产生式是： AA1|A2|Am|1|2|n其中，i(1im)不等于,j(1jn)不以A开头，消除直接左递归后改写为： A1 A|2 A|n A A1 A|2 A|m A| 2) 消除间接左递归。对于间接左递归的消除需先将间接左递归变为直接左递归，然后再消除直接左递归。,消除左递归举例,以文法G6为例： (1) AaB (2) ABb (3) BAc (4) Bd 消

28、除文法中的左递归，并检验改写后的文法是否为LL(1)文法。 用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为：(1) BaBc (2) BBbc (3) Bd 消除左递归后得：B(aBc|d)B BbcB| 再把原来其余的产生式AaB，ABb加入，最终文法为：(1) AaB (2) ABb (3) B(aBc|d)B(4) BbcB| 可以检验改写后的文法不是LL(1)文法。,回溯,1)产生回溯的原因 进行推导时，若产生式存在多个候选式，选择哪个候选式进行推导存在不确定性。 2)消除回溯的基本原则 对文法的任何非终结符，若能根据当前读头下的符号，准确的选择一个候

29、选式进行推导，那么回溯就可以消除。 注:之所以会产生回溯是因为在推导匹配的过程中存在虚假匹配。,回溯的缺陷,1）如果文法存在左递归，语法分析会无限循环下去。 2）若产生式存在多个候选式，选择哪个进行推导完全是盲目的。 3）回溯会引起时间和空间的大量消耗。 4）如果被识别的语句是错的，算法无法指出错误的确切位置。,引起回溯的原因一,1.由于相同左部的产生式的右部FIRST集交集不为空而引起的回溯。 例如 文法：S xAy A ab | a 输入串为xay，其推导过程见图，第一步推导选用S xAy ，进一步推导选用A ab ，得到左图，但不能与输入串匹配，回退到a，选用另一个产生式A a进行试探，

30、见右图，匹配成功。,引起回溯的原因二,2.由于相同左部非终结符的右部存在能* 的产生式，且该非终结符的FOLLOW集中含有其他产生式右部FIRST集的元素。 例 GS: S aAS | b A bAS | 对输入串ab#进行推导，当面临a时， 用S aAS 推导，a匹配，输入串指针移到b，可用A向下推导，先选A bAS 进行推导，b得到匹配，输入符已结束，但语法树的末端节点并非全是终结符，出错，换用A ，成功。,引起回溯的原因三,3.由于文法有左递归而引起回溯 例：文法 S Sa Sb 若推导串为baa# 开始符号为b用Sb 推导，错 选用S Sa，语法树当前最左符号为非终结符，而当前符号为b

31、，用Sb 推导，错 选用S Sa，语法树当前最左符号为非终结符，而当前符号为b，用Sb 推导，成功。,确定的自顶向下分析方法-递归子程序法,递归子程序法是比较简单直观易于构造的一种语法分析方法。 要求文法满足LL(1)文法。 实现思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式能够按LL(1)形式可唯一地确定选择某个候选进行推导。 具体的实现方式，识别过程可参考和回顾PL/0编译程序语法分析方法在每个过程中如何识别及各个过程之间的调用关系。,确定的自顶向下分析方法-预测分析方法,预测分析方法是自顶向下分析的一种方法，一个预

32、测分析器是由三个部分组成。 预测分析程序(总控程序) 先进后出栈(stack) 预测分析表,5.5不确定的自顶向下分析思想,2、算法 1）若栈顶符号x是非终结符，查询语法表，找出一个以x作为左部的产生式，x出栈，并将其右部反序入栈，且输出带记下产生式编号推导。 2）若栈顶符号x是终结符，且读头下的符号也是x，则x出栈，读头指向下一个符号匹配。 3）若栈顶符号x是终结符，但读头下的符号不是x，则匹配失败。这说明可能前面推导时选错了候选式，退回到上次推导现场(包括栈顶符号、读头的指针和输出带上信息)回溯。,5.5不确定的自顶向下分析思想,4）回溯后选取另一候选式进行推导，若没有候选式可选，则进一步

33、回溯。若回溯到开始符号又已无候选式可选，则识别失败。 5）若栈内仅剩下“”，且读头也指向“”，则识别成功。,5.5不确定的自顶向下分析思想,1、基本构成 设下推栈的初始状态包含两个符号：#S，其中#为栈底，S为文法开始符号。整个分析过程在语法分析程序控制下进行。在语法分析中用到的文法产生式的表，称为语法表。,5.5不确定的自顶向下分析思想,例：文法产生式如下，请分析符号串x*y#的过程: 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :

34、文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不

35、确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5不确定的自顶向下分析思想,例 :文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *,5.5确定的自顶向下分析方法,图中符号说明如下： “#”句子括号即输入串的括号 “S”文法的开始符号 “X”存放当前栈顶符号的工作单元 a存放当前输入符号a的工作单元,预测分析程序的工作过程用示意图,5.5确定的自顶向下分析方法,以表达式文法为例构造预测分析表。 表达式文法为：EE+T|T TT*F|F Fi|(E) 构造步骤： (1) 判断文法是否为L

36、L(1)文法 由于文法中含有左递归，所以必须先消除左递归，使文法变为：ETE E+TE|TFT T*FT|Fi|(E),可推出的非终结符表为 各非终结符的FIRST集合为：FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)=(,i 各非终结符的FOLLOW集合为：FOLLOW(E)=),#FOLLOW(E)=)，#FOLLOW(T)=+，)，#FOLLOW(T)=+，)，#FOLLOW(F)=*，+，)，#,各产生式的SELECT集合为：SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E)=)，#SELECT(TFT)=(，iSELECT(T*FT)=*SELECT(T)=+，)，#SELECT(F(E)=(SELECT(Fi)i 由上可知有相同左部产生式的SELECT集合的交集为空，所以文法是LL(1)文法。,ETE E+TE| TFT T*FT| Fi|(E),5.5确定的自顶向下分析方法,5.5确定的自顶向下分析方法,(2) 构造预测分析表 对每个终结符或“#”号