【精品】【考研计算机专业课】天津大学 编译原理讲义 自上而下3.2-3.4精品ppt课件.ppt

《【精品】【考研计算机专业课】天津大学 编译原理讲义 自上而下3.2-3.4精品ppt课件.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】天津大学 编译原理讲义 自上而下3.2-3.4精品ppt课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】天津大学 编译原理讲义 自上而下3.2-3.43.2自上而下分析自上而下分析自上而下分析方法自上而下分析方法:是从文法的根符号开始，自顶向下的是从文法的根符号开始，自顶向下的进行句型推导，推导的每一步都谋求进行句型推导，推导的每一步都谋求“匹配匹配”输入串的现输入串的现行输入符号。行输入符号。设现行输入符号是设现行输入符号是“a”“a”，当前分析的句型是，当前分析的句型是xAy，AVN，x,yVT，设设A有两个候选式，即有两个候选式，即A1 1|2 2，若有，若有1 1aa和和2 2bb，且，且abab。此时，则确定侯选式。此时，则确定侯选式1 1和输入串和输入串“相匹配相

2、匹配”。若句型的每一步都和输入串的现行输入符号若句型的每一步都和输入串的现行输入符号“相匹配相匹配”，且句型的所有符号都是终极符，则确定所给输入串是给定且句型的所有符号都是终极符，则确定所给输入串是给定文法的文法的句子句子。例例:文法文法G=(S,A,x,y,z,G=(S,A,x,y,z,*,SxAy,Sz,A,SxAy,Sz,A*,A,A*,S),S)输入串为输入串为x x*y y，采用自采用自上上向下的分析方法向下的分析方法:(1)根符号根符号S S有两个侯选式有两个侯选式“xAy”“xAy”和和“z”“z”，显然，显然，侯选式侯选式“xAy”“xAy”与输入串与输入串“x“x*y”y”相

3、匹配相匹配，故作句故作句型推导型推导:S:SxAyxAy。SxAy(2)当前句型当前句型“xAy”中中A也有两个侯选式也有两个侯选式“*”和和“*”，首先选用，首先选用“*”对句型进行推导，则得对句型进行推导，则得 Sx*y，但第三个符号，但第三个符号“*”与输入串第三个符号与输入串第三个符号“y”“y”不相匹配。不相匹配。*(3)推导回溯到句型推导回溯到句型“xAy”，非终极符，非终极符A选第二选第二个侯选式个侯选式“*”进行推导，即进行推导，即:SxAyx*y，推，推导的结果与输入串全部相匹，且都是终极符，从导的结果与输入串全部相匹，且都是终极符，从而判定输入串而判定输入串“x*y”是所给

4、文法的句子。是所给文法的句子。*自顶向下分析存在的问题自顶向下分析存在的问题2.回溯问题回溯问题:对某个非终结符，当有多条规则时，需采用逐个选对某个非终结符，当有多条规则时，需采用逐个选择的方法，若不能匹配需要回溯。择的方法，若不能匹配需要回溯。3.当最终报告分析不成功时，我们难于知道输入串中出错的确切当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。位置。总之总之:由于带回溯的自上而下分析实际上采用了一种穷尽一切可由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的能的试探法试探法，因此，效率很低，代价极高。严重的低效使得这种，因此，效率很低，代价极高。严重的低效使得这种分析方法

5、只具有理论价值。分析方法只具有理论价值。1.左递归问题左递归问题:一个文法是含有左递归的，如果存在非终结符一个文法是含有左递归的，如果存在非终结符P(PP)含有左递归的文法将使上述的自上而下的分析过程陷入含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即，当试图用无限循环。即，当试图用P去匹配输入串时，我们会发现，在没去匹配输入串时，我们会发现，在没有吃进任何输入符的情况下，又得重新要求有吃进任何输入符的情况下，又得重新要求P去进行新的匹配。去进行新的匹配。+1.左递归的消除左递归的消除(1)直接左递归直接左递归的消除的消除设文法的产生式设文法的产生式PP|P|PPP P P PP|

6、消除左递归变为消除左递归变为EE+T|TTT*F|FF(E)|iF(E)|i例例，设文法，设文法消除直接左消除直接左递归后变为递归后变为ETEE+TE|TFTT*FT|F(E)|iF(E)|i消除关于消除关于Ai规则的直接左递归；规则的直接左递归；把行如把行如AiAj的规则改成的规则改成Ai1|2|k其中其中Aj1|2|k是关于是关于Aj的所有规则；的所有规则；for(j=1；j=i-1；j+)for(i=1；i=n；i+)化简所得的文法（去掉无用产生式）化简所得的文法（去掉无用产生式）首先给文法首先给文法VN中的符号一个排序中的符号一个排序:A1,A2,An例例，文法，文法G:SQc|cQR

7、b|bRSa|aSa|a设文法的非终极符若按设文法的非终极符若按R、Q、S排序排序执行算法得执行算法得iv消除直接左递归得消除直接左递归得SabcS|bcS|cSSabcS|SabcS|bcS|cSSabcS|QSab|ab|bRSa|a化简化简SabcS|bcS|cSSabcS|iiiSSabc|abc|bc|ciiQSab|ab|biRSa|a消除左递归算法与非终极符排序方法无关。消除左递归算法与非终极符排序方法无关。文法的非终极符若按文法的非终极符若按S、Q、R排序排序执行算法得执行算法得iv消除直接左递归得消除直接左递归得RbcaR|caR|aRRbcaR|SQc|cQRb|bRbca

8、R|caR|aRRbcaR|例例，文法，文法G:SQc|cQRb|bRSa|aSa|aiSQc|ciiQRb|biiiRQca|ca|aRbca|b|bca|ca|a若文法含有回路，上述消除左递归的算法无法解决。若文法含有回路，上述消除左递归的算法无法解决。例例，如下文法，如下文法:SQ|cQR|bRS|a|aSaS|bS|cSSS|iRS|aiiQR|biiiSQ|cS|a|b|b|civ消除直接左递归得消除直接左递归得SaS|bS|cS SS|S|a|a|b2.提取左公因子提取左公因子，消除回溯，消除回溯为了消除回溯就必须保证为了消除回溯就必须保证:(1)对文法的任意非终结符，当要它去匹配

9、输入串对文法的任意非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确的指派它的时，能够根据它所面临的输入符号准确的指派它的一个候选去执行任务，并且此候选的工作结果应是一个候选去执行任务，并且此候选的工作结果应是确信无疑的。确信无疑的。(2)若此候选获得成功匹配，那么，这种匹配决不若此候选获得成功匹配，那么，这种匹配决不是虚假的；若此候选无法完成匹配任务，则任何其是虚假的；若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。他候选也肯定无法完成。不带回溯的文法具有如下性质不带回溯的文法具有如下性质:首先对文法的所有非终结符的每个首先对文法的所有非终结符的每个候选候选定义一个定义一

10、个集合集合FIRST()，终结首符集终结首符集。FIRST()=a|a，aVT*我们可以考虑一下，如果非终结符我们可以考虑一下，如果非终结符A的所有候选首符集的所有候选首符集两两不相交，即两两不相交，即A的任何两个不同候选的任何两个不同候选A1 1和和A2 2FIRST(1 1)FIRST(2 2)=那么，当要求那么，当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第就能根据它所面临的第一个输入符号，准确的指派某一个候选前去执行任务。一个输入符号，准确的指派某一个候选前去执行任务。a a1 1,b,b1 1,c,c1 1FIRST(1 1)，a a2 2,b,b2 2,c,c2 2FI

11、RST(2 2)实际中，文法候选的终结首符集并不是两两不相交的。实际中，文法候选的终结首符集并不是两两不相交的。例例，SifBthenS1elseS2|ifBthenS1提取公共左因子提取公共左因子A1|2|n改写成改写成:AAAAA1|2|n3.3递归下降分析器递归下降分析器在不含在不含左递归左递归且每个非终结符的所有且每个非终结符的所有候选终结首符候选终结首符集都两两不相交集都两两不相交的条件下，我们就可能构造一个不的条件下，我们就可能构造一个不带回溯的自上而下分析程序，这个分析程序是由一带回溯的自上而下分析程序，这个分析程序是由一组组递归过程递归过程组成的，每个过程对应文法的一个非终组成

12、的，每个过程对应文法的一个非终结符。这样的一个分析程序称为结符。这样的一个分析程序称为递归下降分析器递归下降分析器。EE+T|TTT*F|FF(E)|i例例，消除左递归消除左递归提取左公因子提取左公因子ETEE+TE|TFTT*FT|F(E)|i程序结构示意图程序结构示意图:递归下降分析器递归下降分析器voidE(void)T()；E()；voidE(void)T()；E()；if(sym=+)advance()；sym存放当前读来的输入符号；存放当前读来的输入符号；advance()advance()将读输入符将读输入符指针下移一个字符位置，且读出指针所指的字符，存指针下移一个字符位置，且读

13、出指针所指的字符，存入入symsym；error()error()为出错诊断处理程序。为出错诊断处理程序。3.4LL(1)LL(1)分析器分析器一种规范的自顶向下分析方法，称为一种规范的自顶向下分析方法，称为LL(1)LL(1)分析器分析器。分析器由三部分组成分析器由三部分组成:LL(1)(1)分析表分析表，语法符号栈语法符号栈，总控程序总控程序。例例，ETEE+TE|TFTFTT T*FTFT|F(E)|iF(E)|i(1).LL(1)分析表分析表i+*()#EETEETEEE+TEEETTFTFTTFTFTTT TT T*FTFTT TT TFFiFiF(E)F(E)(2).语法符号栈语法

14、符号栈STACK栈，用于存放文法符号。分析栈，用于存放文法符号。分析开始开始时，栈底存时，栈底存放句子放句子左界符左界符“#”和文法的和文法的根符号根符号；总控程序根据总控程序根据STACK栈顶符号栈顶符号“X”和和输入串的当前值输入串的当前值a查查LL(1)分析表，且进行自上而下分析，分析过程如下分析表，且进行自上而下分析，分析过程如下:(3).总控程序总控程序a.若若X=a=“#”，分析成功，即，分析成功，即STACK栈顶符号为栈顶符号为“#”，当前输入符号为当前输入符号为“#”，此时成功。，此时成功。b.若若X=a“#”，则将，则将STACK栈顶符号栈顶符号X逐出，且从输入逐出，且从输入

15、串中读入下一个符号存入串中读入下一个符号存入a。c.若若XVN，则根据，则根据X和和a查查LL(1)分析表分析表M X，aa，若，若表中为一产生式，则将表中为一产生式，则将X从栈中逐出，后将从栈中逐出，后将X的产生式右的产生式右部按部按反序反序推进推进STACK栈栈(当候选式为当候选式为时，则意味不推时，则意味不推什么东西进栈什么东西进栈)；若；若MA,a为空白，出错。为空白，出错。为何是反序为何是反序？Begin#和文法的和文法的开始符开始符推进推进STACK栈；栈；把第一个输入符号读进把第一个输入符号读进a；FLAG=TRUE；WhileFLAGDoBegin把把STACK栈顶符号上托出去

16、并放在栈顶符号上托出去并放在X中；中；ifX=a=#then分析成功分析成功(FLAG=FALSE)；elseif(X=aandXVT)then把下一个输入符号读进把下一个输入符号读进a；elseif(XVNandMX，a=XX1 1X2 2Xk k)then把把Xk k，Xk-1k-1，X1 1一一推进一一推进STACK栈；栈；elseERROREndofwhile；End例例，分析输入串，分析输入串#i+i#的过程。的过程。步骤步骤分析栈分析栈当前输入当前输入a剩余输入串剩余输入串所用产生式所用产生式1#Ei+i#ETE2#ETi+i#TFT3#ETFi+i#FiX=i=a匹配匹配5#ET

17、+i#T6#E+i#E+TE7#ET+i#X=+=a匹配匹配X=i=a匹配匹配12#E#E13#分析成功分析成功X=a=#ETFi#Fi9#ET#T11#ETi#TFT8#ETii10#4#ETii+i#LL(1)分析器的主控程序是一个固定程序，我们最关心的分析器的主控程序是一个固定程序，我们最关心的问题是，问题是，对于一个文法对于一个文法G，如何构造它的，如何构造它的LL(1)分析表分析表！首先定义两个重要集合首先定义两个重要集合:(1)FIRST()=a|a，aVT*头符号集头符号集FIRST()，V*(2)(2)若若成立，则规定成立，则规定FIRST()。*后继符号集合后继符号集合FOL

18、LOW(A)，AVN (1)FOLLOW(A)=a|SAa，*(2)(2)若若S A成立，则句子的右界符成立，则句子的右界符#FOLLOW(A)。*AVNaVT，S是根符号是根符号(1).求求FIRST(X)的算法的算法a.a.若若XVT，FIRST(X)=X。b.b.若若XVN，且有产生式且有产生式Xa ，aVT，则，则a aFIRST(X)。当产生式为当产生式为X时，则时，则FIRST(X)。c.c.若若XY ，且，且YVN，则，则FIRST(Y)FIRST(X)；*若若XY1 1Y2 2 Yk k，且，且Y1 1，Y2 2，Yk kVN。对于任何的。对于任何的i i，j j，(1i(1i

19、k，1ji-1)1ji-1)，都有，都有FIRST(Yj j)，则则FIRST(Yi)FIRST(X)。特别，若。特别，若Y1 1Y2 2 Yk k则则FIRST(X)。*d.d.例例，已知文法的产生式为：，已知文法的产生式为：XY1Y2Y3Y4Y5Y1a|Y2b|Y3c|Y4d|Y5e|求求FIRST(X):*由由Y1Y2Y3Y4Y5得到得到FIRST(X)=FIRST(X)；=aa，b b，c c，d d，e e，由由XY1Y2Y3Y4Y5得到得到FIRST(X)=FIRST(X)FIRST(Yi)；=aa，b b，c c，d d，eeFIRST(X)=ETEE+TE|TFTT*FT|F(

20、E)|)|i例例，文法，文法:解解:头符号头符号集集FIRST(E)=+，FIRST(F)=(，iFIRST(T)=*，FIRST(T)=(，iFIRST(F)FIRST(T)FIRST(T)FIRST(E)FIRST(E)=(，i(2).求求FOLLOW(A)的算法的算法(AVN)置初值，置初值，对任一对任一AVN，置，置FOLLOW(A)=)=；对；对文法的根符号文法的根符号S，“#”FOLLOW(S)。a.a.若有若有AB，则，则FIRST()()FOLLOW(B)。b.b.若有产生式若有产生式ABB或或 ABB，且有，且有，则，则FOLLOW(A)FOLLOW(B)。*c.c.解解:后

21、继符号后继符号集集ETEE+TE|TFTT*FT|F(E)|i例例，文法，文法:FIRST(F)=(，iFIRST(T)=*，FIRST(E)=+，FIRST(T)=(，iFIRST(E)=(，i初始，初始，FOLLOW(E)=#第二步，第二步，FOLLOW(T)=+FOLLOW(F)=*FOLLOW(E)=)，#第三步，第三步，FOLLOW(T)=+，)，#FOLLOW(E)=)，#FOLLOW(T)=+，)，#FOLLOW(F)=*，+，)，#(3).LL(1)LL(1)分析表构造算法分析表构造算法 设文法设文法G:(VN,VT,P,S)i.任给一产生式任给一产生式AP，AVN，V*按按i

22、i.、iii.填填LL(1)(1)分析表。分析表。ii.若若aVT且且aFIRST()()，则将，则将A填在表填在表MA，a中。中。iii.若若FIRST()()，则对任何，则对任何bFOLLOW(A)，将，将A填在表填在表MA，b中。中。iv.若若MA，a为空时，则填为空时，则填ERROR。上述方法构造的分析表称为上述方法构造的分析表称为LL(1)(1)分析表分析表。i+*()#EETTFETEE+TE|TFTT*FT|F(E)|i例例，文法，文法:FIRST(F)=(，iFIRST(T)=*，FIRST(E)=+，FIRST(T)=(，iFIRST(E)=(，iFOLLOW(E)=)，#F

23、OLLOW(E)=)，#FOLLOW(T)=+，)，#FOLLOW(T)=+，)，#FOLLOW(F)=*，+，)，#ETEETEE+TEEETFTTFTTTTT*FTFiF(E)若若LL(1)分析表无重复定义分析表无重复定义(即任一即任一MA，a值唯一值唯一)，则相应的文法为则相应的文法为LL(1)文法文法。定理定理:上下文无关文法上下文无关文法G是是LL(1)(1)文法的文法的充要条件充要条件是是对每个对每个AVN，若有产生式，若有产生式A|，则有，则有i.FIRST()()FIRST()=()=ii.若若，则，则 FIRST()()FOLLOW(A)(A)=*条件条件 i.是显然的；条件

24、是显然的；条件 ii.中，若中，若，且终极符，且终极符b(FIRST()()FOLLOW(A)(A)，则，则LL(1)(1)分析表的分析表的MA，b中要填两个产生式中要填两个产生式:“A”和和“A”试证试证:PP|P|不是不是LL(1)LL(1)文法文法 (PVN，,V*)非非LL(1)(1)文法的文法的LL(1)(1)分析表分析表SiCtSS|aSeS|Cb例例，文法，文法文法非终极符的头符号集合和后继符号集合如下文法非终极符的头符号集合和后继符号集合如下:FIRST(S)=i，aFOLLOW(S)=e，#FIRST(S)=e，FOLLOW(S)=e，#FIRST(C)=bFOLLOW(C)=tabeit#SSaSiC+SSSSeSSSCCb