《《语法分析》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《语法分析》PPT课件.ppt（44页珍藏版）》请在三一办公上搜索。
1、第四章 语法分析和语法分析程序,对象：单词流形式的源程序任务：根据语法规则，分析源程序的语法结构，同时进行语法检查输出：语法树假定：先不考虑语义问题常见分析方法：自顶向下()和自底向上():递归下降法,预测分析法(LL分析法):优先分析法,LR分析法,4.1 自顶向下的语法分析,:对已给的输入串w,试图自上而下地建立一棵语法树;或者说,从S出发,为w构造一个最左推导.若成功,则wL(G),否则拒绝.一般说来,在为w寻求最左推导的每一步,都涉及使用何产生式进行替换的问题.最简单的方法是,逐一试探.遗憾的是,逐一试探也不能完全解决问题.例如,在含有左递归的文法中,就会出现不能终止的替换现象.,例:
2、ET|EAT TF|TMF F(E)|i A+|-M*|/(4.1)设w=i+i*i,每个产生式从左至右试验.从E出发:ETF(E)i TMFFMF(E)MF iMF i*F i/F TMFMF TMFMFMF.,自顶向下分析方法的特点,1.若G有左递归,则分析不能正常进行.因此,分析必须先消除文法的左递归;2.分析过程是反复进行试探的过程,因此,难免会出现大量的回溯.特别是当wL(G)时,只有在穷举完所有的试探后才能拒绝w.由于回溯,就需将从出错点到迄今为止已做过的大量工作废弃,显然会大大降低分析的效率.特别是在语法分析阶段还往往要进行同步的语义分析和处理,这些工作也就白做了.因此,消除回溯
3、是分析的另一目标.3.当拒绝w时,只能知道w不是句子,不知出何错及出在何处,消除文法的左递归,设文法是已简化的.若文法含直接左递归式:AA|(V+),引入新的非终结符A,令其产生*,则有:A AA A|由于不以A打头,A非左递归.对P105的文法(4.1),可改写为ETE EATE|TFT TMFT|F(E)|i A+|-M*|/,一般地,设文法中全部A-产生式为AA1|A2|An|1|m,其中,i不以A打头,则消除直接左递归后的产生式为 A1A|mA 及A 1A|nA上述方法可消除直接左递归,但对于间接左递归的文法来说,需将原文法进行变换后才适用.例如,S Ab|c ASa,可将其变换为S
4、Sab|c,再使用上述方法,得S cSS abS,回溯的消除及LL(1)文法,为解决回溯问题,我们从句子的最左推导开始讨论.设G=(VN,VT,P,S)为一CFG,w=a1a2an是VT上的符号串,现需判明w是否是L(G)中的句子.为此,从S开始进行最左推导.设经若干步推导后我们得到,注意,i=1时,w1=,A=S由假设可知,到目前为止,w的前缀w1已匹配,现在需对A进行推导.,对于当前输入符号ai,若只有一个 j(称为候选式)使得从j出发可以推导出一个以ai打头的符号串:,而其它的k(kj),k 都推导不出以ai打头的符号串,则选定产生式Aj就是唯一可行的推导,即wL(G)选Aj正确;wL(
5、G)选任何产生式均不能匹配显然,若P中产生式能满足上述要求,则回溯可消除,为得到w的剩余部分aiai+1an.由最左推导的定义,考虑A的所有产生式:,消除回溯的条件,由前面的讨论可知，要实现无回溯的分析,文法必须满足一定的条件。为导出这些条件,我们定义候选式的终结首符集FIRST()=a|*a,aVT,V*并约定*时,FIRST()若对于A-产生式的每个候选式i(i=1,2,m)都推不出,且 FIRST(i)互不相交,则当正扫描的当前输入符号为aiFIRST(j)时,唯一可用于推导的产生式只能是Aj.例如,文法G1S:SAAAaAb|*,A-产生式有两个候选式,且FIRST(aAb)=aFIR
6、ST(*)=*,两集不相交,设输入串为aa*bb*,其最左推导为 SAA(a)aAbA(a)aaAbbA(*)aa*bbA(*)aa*bb*(#)注:上面第每步推导右侧括号内为当前扫描的输入符号,#为结束符.我们得到了一个无回溯的条件:FIRST(i)FIRST(j)=,消除回溯的条件,然而还存在另外一种情况,可能存在某个候选式i,i*,即FIRST(i)(这样的是唯一的(?!),此时,为匹配当前扫描的符号a就可能有两种选择,一是存在某j,使j推导出以a打头的符号串,另一种选择是让A推导出i,并让跟随在A后的符号串推导出以a打头的符号串.若这两种选择都可行,则回溯不可避免.因此,就必须要求当i
7、*时,跟在A后的符号串不能推导出其它j 所能推导出的首终结符符号串.为此,我们定义可紧跟在A后的所有终结符之集FOLLOW(A)=a|S#*Aa,aVT#,V*其中,当A为一句型的尾符号时,#FOLLOW(A).现在,我们可把无回溯的另一条件描述为:若i*,则FOLLOW(A)与其它的j互不相交:FOLLOW(A)FIRST(j)=.,消除回溯的条件,例 SaA|b AcAS|FIRST(cAS)=c FOLLOW(A)=FIRST(S)#=a,b,#两个集合不相交,故可进行无回溯的分析.设输入串w=aca#,其推导过程如下:S#aA#当前输入符a属于FIRST(aA),用SaA推导 acAS
8、#当前输入符c属于FIRST(cAS),用AcAS推导 acS#当前输入符a属于FOLLOW(A),用A推导.acaA#当前输入符a属于FIRST(aA),用SaA推导 aca#当前输入符#属于FOLLOW(A),用A推导,成功。最后,我们将消除回溯的条件归纳为,对G中每个AVT,A-产生式中任何两个候选式i,j,均满足:(1)FIRST(i)FIRST(j)=(ij 1i,jm)(2)i,j中,至多有一个能推导出;(3)若j*,则FIRST(i)FOLLOW(A)=(i=1,2,m ij)注:条件(2)可省略.即(1)(2)我们把满足上述条件的文法称为LL(1)文法,递归下降分析法,递归下降
9、分析法(recursive descent method)的原理是,对于文法的每个非终结符,根据其各候选式的结构,为其建立一个递归的子程序(函数),用于识别该非终结符所表示的语法范畴.例如,产生式E+TE,相应的子程序(函数)为expr_prime()if(match(PLUS)advance();term();expr_prime();,程序中,函数match()的功能是,以其实参与当前正扫描的符号进行匹配,若成功则返回1,否则返回0;advance()是读下一单词函数,将所读单词赋给变量lookahead;term()函数是与非终结符T相对应的子程序.对于文法的每个非终结符,都建立了子程序
10、后,这组子程序组成了所需的自顶向下语法分析程序.注意,由于文法的递归性,子程序一定有递归.因此,只能使用允许递归的程序设计语言编写.由于程序有递归,通常,上述方法也称为递归子程序法,什么是LL(1)文法,一个上下文无关文法若满足下列条件(1)文法不含有左递归;(2)文法的每个非终结符A的各个产生式的first集和Follow集不相交，即满足first(A)follow(A)则称此文法为LL(1)文法。第一个L表示它从左到右扫描输入串，第二个L表示采用最左推导，1表示分析时每次直接推导只需向前察看一个字符。,LL（1）分析方法,预测分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序
11、(表驱动程序)及一分析栈组成,输入是待分析的符号串（单词流），以#结尾。分析表是一二维数组，M:VN(VT#)(PERR),MA,a的值按下述规则确定:对于每个产生式A1|2|m,(1)若aFIRST(i),则置MA,a=“Ai”;(2)FIRST(i),aFOLLOW(A),置MA.a=“Ai”,(3)除上述两种情况外,其它元素均填“ERR”.分析表元素的含义:指明当前应用何产生式进行推导,或指明输入串出现错误,一、分析器的工作原理,分析器对输入串的分析在控制程序的控制下进行，步骤如下：,2.设在分析的某时刻的分析格局为,此时,根据当前栈顶符号Xm的不同情况,分别作如下处理:(1)XmVT,
12、且Xm=ai,则匹配,将Xm 顶出栈,输入指针+;否则(Xmai),出错;(2)XmVN 查表MXm,ai,若MXm,ai=“ERR”,则出错;若MXm,ai=“Xm Y1Y2Yk”,则将Xm 出栈,Y1Y2Yk 按逆序压入栈,得到格局,1.初始化.首先将#及开始符S压入栈,各指针置初值.此时,格局为,(3)若Xm=ai=#,则表明输入串已完全得到匹配,分析成功,结束.,预测分析法实例,考虑文法(4.1).各个 FIRST集与FOLLOW集如右表所示,文法(4.1)相应的LL(1)分析表见右,注:在分析表中我们有意省略了左侧的非终结符(why?).在实际的表存储时,还可用产生式编号表示,对i+
13、i*i进行预测分析的过程,二、构造FIRST集的算法,对于G中的每个文法符号X,为求FIRST(X),反复应用如下规则,直到集合不再增大:(1)if(XVT)FIRST(X)=X;(2)if(XVN)if(XaP aVT)aFIRST(X);if(XP)FIRST(X);(3)if(XY1Y2YkP)if(Y1VN)FIRST(Y1)-FIRST(X);for(1 j k-1)if(YjVNFIRST(Yj)FIRST(Yj)-FIRST(X);if(for(1 j k):FIRST(Yj)FIRST(X);V*,=X1X2Xn,求FIRST()类似于求XY1Y2Yk,略.,构造FOLLOW集
14、的算法,FOLLOW:VNVT#,反复使用如下规则,直到不再增大:1.#FOLLOW(S);2.if(ABP)FIRST()-FOLLOW(B);3.if(ABP)(AB FIRST()FOLLOW(A)FOLLOW(B);算法的证明:对于1.,由定义直接得到;对于2.,由于A是有用符号,则必存在含A的句型:S*A B Ba(a FIRST();对于3.,类似地,S*A B,显然,FIRST()FOLLOW(A),并且,FIRST()FOLLOW(B).证毕/,构造FIRST集和FOLLOW集的例子,我们以文法(4.1)为例,计算相应的FIRST集和FOLLOW集.1.求所有VN符的FIRST
15、集.利用规则(2),有 FIRST(M)=*,/,FIRST(A)=+,-FIRST(F)=(,i;再利用规则(3),有FIRST(T)=FIRST(M)=*,/,FIRST(T)=FIRST(F)=(,i,FIRST(E)=FIRST(A)=+,-,FIRST(E)=FIRST(T)=(,i2.求FOLLOW集(1)由规则(1),#FOLLOW(E),再由产生式F(E),)FOLLOW(E),从而,FOLLOW(E)=),#(2)由规则(3)及产生式ETE可知FOLLOW(E)FOLLOW(E),即有 FOLLOW(E)=),#,(3)由规则(2)及产生式EATE有 FIRST(E)-FOL
16、LOW(T);再由规则(3)及ETE和E*有 FOLLOW(E)FOLLOW(T)即FOLLOW(T)=+,-),#=+,-,),#(4)由规则(3)有TFT有FOLLOW(T)FOLLOW(T),即FOLLOW(T)=+,-,),#(5)由规则(2)及TMFT,有 FIRST(T)-FOLLOW(F),再由规则(3)及TMFT和T*,有FOLLOW(T)FOLLOW(F),从而,FOLLOW(F)=*,/+,-,),#=+,-,*,/,),#(6)由规则(2)及EATE,T MFT,有 FIRST(T)FOLLOW(A),FIRST(F)FOLLOW(M),故有 FOLLOW(A)=(,i,
17、FOLLOW(M)=(,i.最终所得的FIRST集和FOLLOW集结果,见P119,求FIRST,FOLLOW集例子(续),三、预测分析表的构造,对已给的LL(1)文法,在得到各文法符号的FIRST集和FOLLOW集之后,就可容易地构造出预测分析表(也称LL(1)分析表).在实际的表存储结构中,矩阵中每个元素并非真正存储的是产生式,而是其右部的逆序(也可以是产生式序号),这样便于分析时使用,并节省了内存空间.造表的算法 在AVN所在行,aVT所在列,MA,a的填写方法如下:(1)if(AP and aFIRST()MA,a=A;(2)if(*(FIRST()and aFOLLOW(A)MA,a
18、=A;(3)Otherwise,MA,a=ERR.文法(4.1)的LL(1)分析表见P119表4-2,4.1.5 某些非LL(1)文法的改造,对于LL(1)文法而言,我们总能构造出相应的预测分析表,且表中决不会含有多重定义的元素.然而对于非LL(1)文法,它们不满足LL(1)文法的条件,尽管仍可为其建立预测分析表,但表中必然会出现多重定义的元素(why?)例如,文法GS:SabB ASC|BAA|BAbA CB|FIRST(S)=aFIRST(A)=a,b,FIRST(B)=a,b FIRST(C)=a,b,cFOLLOW(S)=FOLLOW(A)=FOLLOW(B)=FOLLOW(C)=a,
19、b,c,#,由造表规则,有 MA,a=ASC,A,同理,MB,b=ABAA,A.可见非LL(1)文法所造之表中,必有冲突元素.事实上,是否有冲突元素也是判别一文法是否是LL(1)文法的方法之一.对于某些非LL(1)文法而言,通过消除左递归,反复提取左因子等方法,有时是可以将其改造成LL(1)文法的.,某些非LL(1)文法的改造(续),提取左因子当文法中含有形如 A1|2|m 的产生式时,可将其改写为:AAA1|2|m 若诸候选式1,2,m 中的一部分仍含有左因子,则再进行提取工作,如此等等.这样,就可能得到一个LL(1)文法.例如,EE+T|TT(E)|a(E)|a经改造后可得文法ETEE+T
20、E|TaT|(E)T(E)|这是一个LL(1)文法.应当指出,并非所有的文法都能改造为LL(1)文法.例如,文法GS:SAU|BRAaAU|bBaBR|bUcRd 文法中S的两个候选式AU及BR的FIRST集相交,G是非LL(1)的.为提取左因子,先将S产生式中的A,B用其右部替换,得:SaAUU|bU|aBRR|bR,经提取左因子,得S aS|bS”SAUU|BRR S”U|R A 显然它仍不是LL(1)文法,关于LL(1)的一些结论,能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性,主要有:(1)任何LL(1)文法都是无二义性的;(2)左递归文法是非LL(1)的
21、;(3)存在一种算法,它能判定任意文法是否为LL(1)的;(4)存在一种算法,它能判定任意两个LL(1)文法是否等价;(5)CFL是否是LL(1)语言是不可判定的;(6)非LL(1)语言是存在的.若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.,4.2 自底向上的语法分析,自底向上()的语法分析是从给定的符号串出发,试图逐步将它们归约为文法的开始符号.的语法分析采用的是最左(规范)归约本节中介绍两种分析方法,即优先分析法和LR分析法;分析也需要一个分析栈用于存放分析过程中所得的文法符号,开始时,先将#入栈,然后逐步地将输入符号移进栈,当句柄在栈顶形成时,
22、则进行归约,否则移进下一符号.在分析的每一步,分析动作都是由当前栈里的内容和扫描到的符号确定的.分析动作有:移进,归约,报错,接受.,文法:SAB|c AbA|a BaSb|c,输入为bbaacb,自底向上语法分析的例子,关于自底向上分析,分析过程是最左归约的(规范的);注意,在分析过程中,一旦句柄在栈顶形成,则立即归约;有时栈顶出现了某产生式的右部,但它不一定是句柄(如前例中第七步,栈顶的a不是句柄);从分析过程可容易地建立一棵语法树,可用作语法分析的输出.建立树的方法见P125.,算符优先分析法,算符优先分析是一种自底向上的分析方法算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之
23、间的关系来寻找可归约串。将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄。,算符优先分析,算符文法定义:一个上下无关文法G,如果它的任一个产生式的右部都不含有两个相邻的非终结符，即不含有P.QR.(P,Q,R属于非终结符),则G是一个算符文法 相邻：若S ab或S aQb，则称a，b相邻,算符优先关系：其中A,B属于VN，a,b属于VTa b：当且仅当G中有P.ab.或P.aBb.则称a,b同等规约（同一句柄里的符号）a b：当且仅当G中有P.aA.的产生式,且A b.或A Bb.则称a后于b规约（寻找句柄的头）a b：当且仅当G 中有P.Ab.的产生式,且A=.a或A=.aB
24、则称a先于b规约（寻找句柄的尾）,算符优先文法的定义,以上三种关系也可由下列语法树来说明：(a)中为或为B，这样a,b在同一句柄中同时归约所以优先级相同。(b)中为或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。(c)为或为A，a、b不在同一句柄中，a先归约，所以a的优先性大于b。,例：EE+E|E*E|(E)|i 证明不是OPG文法。因为：EE+E，EE*E 则有+*又因为：EE*E,EE+E 则有+*所以不是算符优先文法。,3.算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有,中的一种成立,则G为一算符优先文法。,算符优先关系表的构造,用表格
25、(矩阵)形式来表示各终结符号的优先关系，这种表称为优先表(矩阵)。在优先表中，空白部分是一种错误关系相同的终结符之间的优先关系不一定是如果有a b,不一定有b a(不具传递性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。a,b之间未必有优先关系(,)构造关系表前我们先介绍FIRSTVT和LASTVT,FIRSTVT集和LASTVT集,定义：设文法GS(VN，VT，P，S)不含产生式，且任何产生式右部都不含有两个相继（并列）的非终结符，AVN，则FIRSTVT(A)=a|Aa或AQa，aVT，Q VNLASTVT(A)=a|Aa或AaQ，aVT，Q VN,FIRSTVT
26、集和LASTVT集,FIRSTVT集和LASTVT集可采用以下算法求得：（1）求FIRSTVT(A)集的算法令FIRSTVT(A)若文法中有形如Aa或AQa的规则，则aFIRSTVT(A)；若文法中有形如AQ的规则，则FIRSTVT(Q)FIRSTVT(A)。（2）求LASTVT(A)集的算法令LASTVT(A)若文法中有形如Aa或AaQ的规则，则aLASTVT(A)；若文法中有形如AQ的规则，则FIRSTVT(Q)LASTVT(A)。,1、构造每个非终结符的FIRSTVT和LASTVT集。2、1）若产生式右部有.aA.的形式,则对于每个bFIRSTVT(A)都有a b(优先集)2）若产生式右
27、部有.Ab的形式,则对于每个aLASTVT(A)集,都有a b 3）若产生是形如：Aab 或 AaBb形式，则有a b3、1)#FIRSTVT(S)2)LASTVT(S)#3)#,算符优先关系表的构造,E T|E+T T F|T*F F i|(E),算符优先分析算法,通过比较终结符间的优先关系来实现根据优先分析的原理,语法分析程序的任务是：不断移进输入符号，识别句柄并进行归约。分析的方法：根据优先性“高于”来识别句柄的头，根据优先性“低于”来识别句柄的尾。各种优先关系已经存于优先关系表中。,1.不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号
28、串,是当前句型的最左素短语.2.素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。3.最左素短语：是指位于句型最左边的那个素短语。,E T|E+TT F|T*FF i|(E),短语有：i,T*F,T*F+i素短语有：i,T*F最左素短语是：T*F,例：下述文法的一个句型：T*F+i 其短语、素短语、最左素短语分别是？,一个算符文法G的某个句型的最左素短语可描述：设句型的一般形式为(NiVN,ai VT#N1a1 N2a2 Nnan#它的最左素短语是满足下列条件的最左子串：Niai Ni+1ai+1 Njaj Nj+1其中：ai-1 ai,ai ai+1 aj-1 aj，aj
29、 aj+1,该定理说明了最左素短语与周围符号之间的关系,例:文法GE-E+T|TT-T*F|FF-(E)|i句型T+T*F+i的语法树如图：,根据语法树可知：句型#T+T*F+i#的短语有：T 相对非终结符E的短语T*F 相对非终结符T的短语T+T*F 相对非终结符E的短语i 相对非终结符P、F、T的短语T+T*F+i 相对非终结符E的短语,根据素短语的定义可知：i和T*F为素短语。其中：T+T*F(含T*F素短语)、T+T*F+i(含T*F素短语)和 T(不含终结符)也不是素短语T*F为最左素短语。,3.算符优先分析过程：(根据最左素短语的定义)句型的一般形式:#N1a1N2a2.NnanN
30、n+1#(ai为终结符,Ni为可有可无的非终结符)从左向右扫描各符号,依次查看算符优先矩阵,直至找到满足ai ai+1的终结符为止,一直移进.再从ai开始往左扫描,直至找到满足关系aj-1 aj的终结符为止,进行归约。此时,形如:Njaj Nj+1aj+1.NiaiNi+1的子串即为最左素短语，应被归约。分析过程的结束：分析栈中为#S，输入串为#,把#入栈,读一符号i,因为#+,所以归约:F-i因#*,所以归约:F-i因+#,所以归约:F-i因*#,所以归约:T-F*F因+#,所以归约:E-T+F分析成功,求i+i*i的算符优先分析过程,栈 输入缓冲区#i+i*i#i+i*i#F+i*i#F+
31、i*i#F+i*i#F+F*i#F+F*i#F+F*i#F+F*F#F+T#E#,算符优先分析的算法(续),关于算符优先分析的若干结论,按算符优先分析所确定的归约子串恰好是当前句型的最左素短语(证明略);算符优先分析是自底向上的,但并不是规范归约,因此,每步所得句型不是规范句型;由于分析过程中只考虑两个相邻VT符之间的关系,VN符无关紧要,所以归约所得的VN符可任意命名;分析所得的语法树不是真正意义上的语法树,而是其分枝构架,它省略了单产生式的归约过程;分析算法可容易地形式化:引入一分析栈,先将#压入栈,分析时总是用栈顶符与当前扫描符进行比较,遇时回头查找最左素短语,归约之;若两个符号无关系,则报错.若栈顶为开始符S,扫描符为#,成功.,
