《最新【考研计算机专业课】天津大学 编译原理讲义 自上而下3.2-3.4(共33张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】天津大学 编译原理讲义 自上而下3.2-3.4(共33张PPT课件).pptx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、语法分析的任务是分析一个文法语法分析的任务是分析一个文法(wnf)的句子结构。对于一个文法的句子结构。对于一个文法(wnf)，当给你一串，当给你一串(终结符号终结符号)时，怎么知道它是不是该文法时，怎么知道它是不是该文法(wnf)的的一个句子呢？所谓一个句子呢？所谓语法分析器语法分析器就是这样的一个程序，它将按文法的就是这样的一个程序，它将按文法的产生式，识别输入符号串是否为一个句子。产生式，识别输入符号串是否为一个句子。语法分析的方法语法分析的方法(fngf)可粗略的分成两类，一类是自下而上分析法，另可粗略的分成两类，一类是自下而上分析法，另一类是自上而下分析法。一类是自上而下分析法。自下而
2、上分析法自下而上分析法就是从输入串开始，逐步就是从输入串开始，逐步(zhb)进进“归约归约”，直至归到，直至归到文法的开始符号。文法的开始符号。自上而下分析法自上而下分析法就是从文法的开始符号出发，反复使用文法的产生就是从文法的开始符号出发，反复使用文法的产生式，寻找式，寻找“匹配匹配”于输入串的于输入串的推导推导。第一页，共三十三页。3.2 自上而下自上而下(z shn r xi)分析分析自上而下分析方法自上而下分析方法: 是从文法的根符号开始，自顶向下的进行句型推导是从文法的根符号开始，自顶向下的进行句型推导(tudo)(tudo)，推导，推导(tudo)(tudo)的每一步都谋求的每一步
3、都谋求“匹配匹配”输入串的现行输入符输入串的现行输入符号。号。 设现行输入符号是设现行输入符号是“a”“a”，当前分析的句型是，当前分析的句型是xAy，AVN，x,yVT，设设A有两个候选式，即有两个候选式，即A1 1|2 2，若有，若有1 1aa和和2 2bb，且，且abab。此时，则确定侯选式。此时，则确定侯选式1 1和输入串和输入串“相匹配相匹配”。 若句型的每一步都和输入串的现行输入符号若句型的每一步都和输入串的现行输入符号“相匹配相匹配”，且句，且句型的所有符号都是终极符，则确定型的所有符号都是终极符，则确定(qudng)(qudng)所给输入串是给定所给输入串是给定文法的文法的句子
4、句子。 第二页，共三十三页。例例: : 文法文法(wnf)(wnf)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，采用采用(ciyng)(ciyng)自自上上向下的分析方法向下的分析方法: : (1) 根符号根符号S S有两个侯选式有两个侯选式“xAy”“xAy”和和“z”“z”，显然，显然(xinrn)(xinrn)，侯选式侯选式“xAy”“xAy”与输入串与输入串“x“x*y”y”相匹配相匹配，故作句型推导故作句型推导: : S SxAyxAy。Sx A y(2) 当前句型当前句型“x
5、Ay”中中A也有两个侯选式也有两个侯选式“*”和和“*”，首先选用首先选用“*”对句型进行推导，则得对句型进行推导，则得 Sx*y，但第，但第三个符号三个符号“*”与输入串第三个符号与输入串第三个符号“y”“y”不相匹配。不相匹配。 * *(3) 推导回溯到句型推导回溯到句型“xAy”，非终极符，非终极符A选第二个侯选选第二个侯选式式“*”进行推导，即进行推导，即: : S xAyx*y，推导的结果与，推导的结果与输入串全部相匹，且都是终极符，从而判定输入串输入串全部相匹，且都是终极符，从而判定输入串“x*y”是所给文法的句子。是所给文法的句子。 *第三页，共三十三页。自顶向下分析自顶向下分析
6、(fnx)(fnx)存在的问题存在的问题 2.回溯问题回溯问题: 对某个非终结符，当有多条规则时，需采用逐个对某个非终结符，当有多条规则时，需采用逐个(zhg)选选择的方法，若不能匹配需要回溯。择的方法，若不能匹配需要回溯。3.当最终报告分析不成功时，我们难于知道输入当最终报告分析不成功时，我们难于知道输入(shr)串中出错的确切位置。串中出错的确切位置。总之总之: 由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法试探法，因此，效率很低，代价极高。严重的低效使得这种分析方法只具有因此，效率很低，代价极高。严重的低效使得这种分析方
7、法只具有理论价值。理论价值。1.左递归问题左递归问题: 一个文法是含有左递归的，如果存在非终结符一个文法是含有左递归的，如果存在非终结符P ( P P)含有左递归的文法将使上述的自上而下的分析过程陷含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即，当试图用入无限循环。即，当试图用P去匹配输入串时，我们会发现，在去匹配输入串时，我们会发现，在没有吃进任何输入符的情况下，又得重新要求没有吃进任何输入符的情况下，又得重新要求P去进行新的匹配。去进行新的匹配。+第四页，共三十三页。1. 左递归的消除左递归的消除(xioch)(1) 直接直接(zhji)左递归左递归的消除的消除设文法设文法(
8、wnf)的产生式的产生式 PP|P| PPP P P P P| 消除左递归变为消除左递归变为E E + T | | T T T * F | | F F(E)|iF(E)|i 例例，设文法，设文法消除直接左消除直接左递归后变为递归后变为E T E E+TE| |TFT T*FT| |F(E)|iF(E)|i 第五页，共三十三页。其中，其中，j j 不以不以P打头，打头，i 非空。非空。 一般地，若文法的产生式为一般地，若文法的产生式为:PP1| | P2| | |Pn| |1| |2| | |m消除直接左递归后，为消除直接左递归后，为: P1 1P|P|2 2 P| P|m m P P P1 1
9、 P| P| 2 2 P| P|n n P| P| 思想思想(sxing): 把直接左递归改成直接右递归。把直接左递归改成直接右递归。第六页，共三十三页。(2) 但这并不意味着已经消除了整个但这并不意味着已经消除了整个(zhngg)文法的左递归性。文法的左递归性。例例，文法，文法G: S Q c | c Q R b | b RSa|aRSa|a G显然不具有直接左递归，显然不具有直接左递归，但但S、Q、R都是左递归的。都是左递归的。因为有如下推导因为有如下推导: S: SQcQcRbcRbcSabcSabc消除左递归算法消除左递归算法:前提前提: 要求不含回路，即不存在要求不含回路，即不存在P
10、P(PVN )。 +第七页，共三十三页。消除关于消除关于(guny)Ai规则的直接左递归；规则的直接左递归；把行如把行如AiAj的规则改成的规则改成Ai1|2|k 其中其中Aj1|2|k是关于是关于Aj的所有规则；的所有规则；for ( j=1；j=i-1；j+)for ( i=1；i=n；i+) 化简所得的文法（去掉无用化简所得的文法（去掉无用(w yn)(w yn)产生式）产生式） 首先首先(shuxin)(shuxin)给文法给文法VN中的符号一个排序中的符号一个排序: : A1,A2, ,An 第八页，共三十三页。例例，文法，文法(wnf)G: SQc| |c QRb| |b RSa|
11、aSa|a 设文法设文法(wnf)的非终极符若按的非终极符若按R、Q、S排序排序 执行执行(zhxng)算法得算法得iv 消除直接左递归得消除直接左递归得SabcS| |bcS| |cS SabcS| | SabcS| |bcS| |cS S a b c S| | Q S a b| | a b| |b RSa| |a 化简化简SabcS| |bcS| |cS SabcS| | iii SSabc| |abc| |bc| |c ii QSab| |ab| |b i RSa| |a 第九页，共三十三页。消除左递归算法与非终极消除左递归算法与非终极(zhngj)(zhngj)符排序方法无关。符排序方
12、法无关。 文法的非终极文法的非终极(zhngj)符若按符若按S、Q、R排序排序 执行执行(zhxng)算法得算法得iv 消除直接左递归得消除直接左递归得RbcaR| |caR| |aR RbcaR| | SQc| |c QRb| |b RbcaR| |caR| |aR RbcaR| | 例例，文法，文法G: SQc| |c QRb| |b RSa|aSa|a i SQc| |c ii QRb| |b iii RQca| |ca| |a Rbca|b|bca| |ca| |a 第十页，共三十三页。若文法若文法(wnf)(wnf)含有回路，上述消除左递归的算法无法解含有回路，上述消除左递归的算法无
13、法解决。决。 例例，如下，如下(rxi)文法文法: SQ| |c QR| |b RS|a|a SaS|bS|cS SS| i RS| |a ii QR| |b iii SQ| |c S| |a|b|b|civ 消除消除(xioch)直接左递归得直接左递归得SaS|bS|cS S S|S|a|a|b第十一页，共三十三页。2. 提取左公因子提取左公因子(ynz)(ynz)，消除回溯，消除回溯为了消除回溯就必须为了消除回溯就必须(bx)保证保证:(1) 对文法的任意非终结符，当要它去匹配输入串时，对文法的任意非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确的指派它的一个候能够根据它所面
14、临的输入符号准确的指派它的一个候选去执行任务，并且此候选的工作选去执行任务，并且此候选的工作(gngzu)结果应是确结果应是确信无疑的。信无疑的。(2) 若此候选获得成功匹配，那么，这种匹配决不是若此候选获得成功匹配，那么，这种匹配决不是虚假的；若此候选无法完成匹配任务，则任何其他候虚假的；若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。选也肯定无法完成。第十二页，共三十三页。不带回溯的文法具有如下不带回溯的文法具有如下(rxi)性质性质:首先对文法的所有非终结符的每个首先对文法的所有非终结符的每个候选候选定义一个定义一个集合集合FIRST()，终结首符集终结首符集。FIRST()=a
15、 |a ，a VT *我们可以考虑一下，如果非终结符我们可以考虑一下，如果非终结符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 2FIRST(2 2) 第十三页，共三十三页。实际实际(
16、shj)中，文法候选的终结首符集并不是两两不相交的。中，文法候选的终结首符集并不是两两不相交的。例例，Sif B then S1 else S2| | if B then S1提取公共左因子提取公共左因子A1| |2| | |n改写成改写成:AAAAA1| |2| | |n第十四页，共三十三页。 3.3 递归下降递归下降(xijing)(xijing)分析器分析器 在不含在不含左递归左递归且每个非终结符的所有且每个非终结符的所有候选终结首符集都两两候选终结首符集都两两不相交不相交的条件下，我们就可能构造一个不带回溯的自上而的条件下，我们就可能构造一个不带回溯的自上而下分析程序，这个分析程序是由
17、一组下分析程序，这个分析程序是由一组递归过程递归过程组成的，每组成的，每个过程对应文法个过程对应文法(wnf)的一个非终结符。这样的一个分析程的一个非终结符。这样的一个分析程序称为序称为递归下降分析器递归下降分析器。EE+T|T TT*F|F F(E)| i 例例，消除左递归消除左递归提取左公因子提取左公因子ETE E+TE| TFT T*FT| F(E)|i 第十五页，共三十三页。程序结构示意图程序结构示意图:第十六页，共三十三页。递归下降递归下降(xijing)分析器分析器void E(void)T( )；E( )；void E(void)T( )；E( )；if (sym=+) adva
18、nce( )；sym存放当前读来的输入符号；存放当前读来的输入符号；advance()advance()将读输入符指针下将读输入符指针下移一个字符位置，且读出指针所指的字符，存入移一个字符位置，且读出指针所指的字符，存入symsym；error()error()为出错为出错(ch cu)(ch cu)诊断处理程序。诊断处理程序。 第十七页，共三十三页。 3.4 LL(1)LL(1)分析器分析器 一种一种(y zhn)(y zhn)规范的自顶向下分析方法，称为规范的自顶向下分析方法，称为LL(1)LL(1)分析器分析器。 分析器由三部分分析器由三部分(b fen)(b fen)组成组成: : L
19、L(1)(1)分析表分析表，语法符号栈语法符号栈，总控程序总控程序。 例例，ETE E+TE| | TFTFT T T* FTFT| F(E)|iF(E)|i 第十八页，共三十三页。(1). LL(1)分析分析(fnx)表表 i + * ( ) #EETE ETE E E+TE EETTFTFT TFTFT T T TT T*F FT T T TT TFFiFi F(E)F(E) (2). 语法符号栈语法符号栈STACK栈，用于存放文法符号。分析栈，用于存放文法符号。分析开始开始时，栈底存时，栈底存放句子放句子左界符左界符“#”和文法的和文法的根符号根符号； 第十九页，共三十三页。总控程序总控
20、程序(chngx)(chngx)根据根据STACK栈顶符号栈顶符号“X”和和输入串的当前值输入串的当前值a查查LL(1)分析表，且进行自上而下分析，分析过程如下分析表，且进行自上而下分析，分析过程如下: : (3). 总控程序总控程序(chngx)a. 若若X=a=“#”，分析成功，即，分析成功，即STACK 栈顶符号为栈顶符号为“#”，当，当前输入前输入(shr)(shr)符号为符号为“#”，此时成功。，此时成功。 b. 若若X=a“#”，则将，则将STACK栈顶符号栈顶符号X 逐出，且从输入串逐出，且从输入串中读入下一个符号存入中读入下一个符号存入a。 c. 若若XVN，则根据，则根据X和
21、和a 查查LL(1) 分析表分析表M X，aa，若表中，若表中为一产生式，则将为一产生式，则将X 从栈中逐出，后将从栈中逐出，后将X的产生式右部按的产生式右部按反序反序推进推进STACK 栈栈( (当候选式为当候选式为时，则意味不推什么东西进栈时，则意味不推什么东西进栈) )；若；若MA,a为空白，出错。为空白，出错。 为何是反序？为何是反序？ 第二十页，共三十三页。Begin #和文法的和文法的开始符开始符推进推进STACK栈；栈； 把第一个输入符号读进把第一个输入符号读进a； FLAG=TRUE； While FLAG Do Begin 把把STACK栈顶符号上托出去并放在栈顶符号上托出去
22、并放在X中；中； if X=a=# then 分析成功分析成功(chnggng)(FLAG=FALSE)； else if (X=a and XVT ) then 把下一个输入符号读进把下一个输入符号读进a； else if (XVN and MX，a=XX1 1X2 2Xk k) then 把把Xk k，Xk-1k-1，X1 1一一推进一一推进STACK栈；栈； else ERROR End of while；End第二十一页，共三十三页。例例，分析输入，分析输入(shr)串串 #i+i# 的过程。的过程。步骤步骤分析栈分析栈当前输入当前输入a剩余输入串剩余输入串所用产生式所用产生式1#Ei
23、+i#ETE2#ETi+i#TFT3#ETFi+i#FiX=i=a 匹配匹配(ppi)5#ET+i#T6#E+i#E+TE7#ET+i#X=+=a 匹配匹配(ppi)X=i=a 匹配匹配12#E#E13#分析成功分析成功X=a=#ETFi#Fi9#ET#T11#ETi#TFT8#ETii10# 4#ETii+i#第二十二页，共三十三页。LL(1)分析器的主控程序是一个固定程序，我们最关心的问题是，分析器的主控程序是一个固定程序，我们最关心的问题是， 对于一个文法对于一个文法G，如何构造，如何构造(guzo)它的它的LL(1)分析表分析表！首先定义首先定义(dngy)两个重要集合两个重要集合:(
24、1) FIRST()=a |a ，a VT *头符号集头符号集 FIRST()，V* (2)(2)若若成立，则规定成立，则规定 FIRST()。 *后继符号集合后继符号集合FOLLOW( (A) )，AVN (1) FOLLOW( (A) )=a|S Aa ，*(2)(2)若若S A 成立，则句子的右界符成立，则句子的右界符#FOLLOW( (A) )。 *AVNaVT，S是根符号是根符号第二十三页，共三十三页。(1). 求求FIRST( (X) )的算法的算法(sun f)(sun f)a. a. 若若XVT，FIRST(X)=X。 b.b. 若若XVN，且有产生式且有产生式Xa ，aVT
25、，则，则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(1ik，1ji-1)1ji-1)，都有，都有FIRST( (Yj j) )，则则FIRST( (Yi) ) FIRST(X)。特别，若。特别，若Y1 1Y2 2 Yk k则则FIRST(X)。 *d.d.第二十四页，共三十三页。例例，已知文法，已知文法(wnf)的产生式为：的产生式为：XY1 Y2
26、Y3 Y4 Y5Y1a|Y2b|Y3c|Y4d|Y5e| 求求FIRST(X):*由由Y1Y2Y3Y4Y5得到得到 FIRST(X)=FIRST(X)； =aa，b b，c c，d d，e e，由由XY1 Y2 Y3 Y4 Y5得到得到(d do) FIRST(X)=FIRST(X)FIRST(Yi)； =aa，b b，c c，d d，eeFIRST(X)=第二十五页，共三十三页。ETE E+TE| | TFT T*FT| | F(E)|)|i 例例，文法，文法:解解: : 头符号头符号(fho)(fho)集集FIRST(E)=+， FIRST(F) =( ， i FIRST(T)=*， FI
27、RST(T) =( ， i FIRST(F) FIRST(T)FIRST(T) FIRST(E)FIRST(E) =( ， i 第二十六页，共三十三页。(2). 求求FOLLOW( (A) )的算法的算法(sun f)(sun f)( (AVN) )置初值，置初值， 对任一对任一AVN ，置，置FOLLOW( (A)=)=；对文法的根符号对文法的根符号S，“# #”FOLLOW( (S) )。a.a.若有若有AB，则，则FIRST()() FOLLOW( (B) )。 b.b.若有产生式若有产生式ABB 或或 ABB，且有，且有，则，则FOLLOW( (A) ) FOLLOW( (B) )。
28、*c.c.第二十七页，共三十三页。解解: : 后继后继(huj)(huj)符号符号集集ETE E+TE| | TFT T*FT| | F(E)| |i 例例，文法，文法:FIRST(F) =( ， i FIRST(T)=*， FIRST(E)=+， FIRST(T) =( ， i FIRST(E) =( ， i 初始初始(ch sh)， FOLLOW(E) =#第二步，第二步，FOLLOW(T) =+FOLLOW(F) =*FOLLOW(E) =)，#第三步，第三步，FOLLOW(T) =+，)，#FOLLOW(E)=)，#FOLLOW(T)=+，)，#FOLLOW(F)=*，+，)，# 第二
29、十八页，共三十三页。(3). LL(1)LL(1)分析分析(fnx)(fnx)表构造算法表构造算法 设文法设文法(wnf)(wnf)G: : ( (VN,VT,P,S) ) i. 任给一产生任给一产生(chnshng)(chnshng)式式AP，AVN ，V*按按ii.、iii.填填LL(1)(1)分析表。分析表。 ii. 若若aVT 且且aFIRST()()，则将，则将A填在表填在表MA，a中。中。 iii. 若若FIRST()()，则对任何，则对任何bFOLLOW( (A) )，将，将A填在表填在表MA，b中。中。 iv. 若若MA，a为空时，则填为空时，则填ERROR。 上述方法构造的分
30、析表称为上述方法构造的分析表称为LL(1)(1)分析表分析表。 第二十九页，共三十三页。 i + * ( ) #E E T T F ETE E+TE| | TFT T*FT| | F(E)| |i 例例，文法，文法(wnf):FIRST(F) =( ， i FIRST(T)=*， FIRST(E)=+， FIRST(T) =( ， i FIRST(E) =( ， i FOLLOW(E) =)，#FOLLOW(E)=)，#FOLLOW(T) =+，)，#FOLLOW(T)=+，)，#FOLLOW(F)=*，+，)，#ETEETEE+TEEETFTTFTTTTT*FTFiF(E)第三十页，共三十三
31、页。若若LL( (1) )分析表无重复定义分析表无重复定义(dngy)(dngy)( (即任一即任一MA，a值唯一值唯一) )，则相应的文法为则相应的文法为LL( (1) )文法文法。 定理定理: 上下文无关文法上下文无关文法G是是LL(1)(1)文法的文法的充要条件充要条件是对每个是对每个AVN ，若有产生式，若有产生式A|，则有，则有 i. FIRST()()FIRST()= ()= ii. 若若，则，则 FIRST()()FOLLOW(A)(A)= *条件条件 i. 是显然的；条件是显然的；条件 ii. 中，若中，若，且终极符，且终极符 b(FIRST()()FOLLOW(A)(A)，则
32、，则LL(1)(1)分析表的分析表的MA，b中要填两个产生式中要填两个产生式: : “A”和和“A” 试证试证: PP|P|不是不是(b shi)(b shi)LL(1)LL(1)文法文法 ( (P VN ，,V*) )第三十一页，共三十三页。非非LL(1)(1)文法文法(wnf)(wnf)的的LL(1)(1)分析表分析表 S i C t S S| a SeS| Cb 例例，文法，文法(wnf)(wnf) 文法非终极符的头符号集合文法非终极符的头符号集合(jh)(jh)和后继符号集合和后继符号集合(jh)(jh)如下如下: : FIRST( (S ) )=i，a FOLLOW( (S ) )=
33、e，#FIRST( (S) )=e， FOLLOW( (S) )=e，#FIRST( (C) )=b FOLLOW( (C) )=t abeit#SSa SiC+SS S SeSS SC Cb 第三十二页，共三十三页。内容(nirng)总结语法分析的任务是分析一个文法的句子结构(jigu)。因为有如下推导: SQcRbcSabc。首先给文法VN中的符号一个排序: A1,A2,。设文法的非终极符若按R、Q、S排序。文法的非终极符若按S、Q、R排序。若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。头符号集 FIRST()，V*。AVNaVT，S是根符号。对文法的根符号S，“#”FOLLOW(S)。设文法G: (VN,VT,P,S)。Cb第三十三页，共三十三页。