自顶向下的句法分析.ppt

第4章自顶向下的句法分析,自顶向下分析方法递归下降分析法LL(1)分析法自底向上分析方法算符优先分析法LR分析法,4.1句法分析器概述,句法分析是编译程序的核心部分。任务：识别由词法分析得出的单词序列是否是合法的句子。理论基础：上下文无关文法和下推自动机句法分析方法：自顶向下(top-down)的句法分析：反复使用不同产生式进行推导以谋求与输入符号串相匹配。自底向上(bottom-up)的句法分析：对输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入符号指词法分析所识别的单词。,确定的自顶向下分析思想例文法G1S:SpASqBAcAdAaBdBBbW=pccadd自顶向下的推导过程：SpApcAdpccAddpccadd,S,p,A,S,p,A,c,A,d,S,p,A,c,A,d,c,A,d,S,p,A,c,A,d,c,A,d,a,文法G1S:SpA|qBAcAd|aBdB|b文法的特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。,文法G2S:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程：SApcApccApccap,文法G2S:SAp|BqAa|cABb|dB文法的特点：每个产生式的右部不全是由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。,为了实现确定的(即无回溯的)自顶向下分析，则要求文法满足下述两个条件：(1)文法不含左递归直接左递归：AA间接左递归：AB，B+A左递归文法使自上而下分析工作陷入死循环。例如，如果有产生式EE+TEE+TE+T+TE+T+T+T,(2)无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推导出的终结符号串的首字符集合要两两不相交。例如，如果有文法GS：SxAyAaba输入串xay的分析就需要回溯。带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低。,消除左递归1.直接左递归方法是引入一个新的非终结符，把含有左递归的产生式改为右递归。设关于A的产生式为AA1A2Am12n其中，每个i都不为且每个j都不以A开头，则消除A的直接左递归就是将其改写为：,例如，含有直接左递归的表达式文法GE为：GE:EE+TTTT*FFF(E)i消去直接左递归后得到文法GE为：GE:ETEE+TETFTT*FTF(E)i,2.间接左递归将间接左递归变为直接左递归，然后消除直接左递归。如文法GA含有间接左递归：AaBAaBAaBABbABbABbBAcBaBcBaBcB|dBBdBBbcBbcB|Bd,消除文法中一切左递归的算法要求：无回路(即不存在A+A的推导)充分条件：文法不含形如AA的有害产生式，也不含A的空产生式。,(1)将所有非终结符排序：A1、A2、An；(2)for(i=1;i=n;i+)for(j=1;j1)在实际中极少使用。,1表驱动的LL(1)分析器基本思想：根据输入串的当前输入符号来唯一确定选用某条产生式来进行推导；当这个输入符号与推导的第一个符号相同时，再取输入串的下一个符号，继续确定下一个推导应选的规则；直到推导出被分析的输入串为止。LL(1)分析器：LL(1)分析表(也称预测分析表)先进后出分析栈控制程序(表驱动程序),LL(1)分析器,(1)输入串是待分析的符号串，它以界符“#”作为结束标志。(注：#VT但不是文法符号，是由分析程序自动添加的。)(2)分析栈中存放分析过程中的文法符号。分析开始时栈底先放入一个“#”，然后再压入文法的开始符号；当分析栈中仅剩“#”，输入串指针也指向串尾的“#”时，分析成功。,(3)分析表用一个矩阵M表示，它概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符相关联，而每一列与文法的一个终结符或界符“#”相关联。对MA,a来说，A为非终结符，而a为终结符或“#”。分析表元素MA,a中的内容为一条关于A的产生式，表明当A面临输入符号a时当前推导所应采用的候选式；当元素内容为空白(空白表示“出错标志”)时，则表明A不应该面临这个输入符号a，即输入串含有语法错误。,(4)控制程序根据分析栈顶符号X和当前输入符号a来决定分析器的动作：若X=a=“#”，则分析成功，分析器停止工作。若X=a“#”，即栈顶符号X与当前扫描的输入符号a匹配；则将X从栈顶弹出，输入指针指向下一个输入符号，继续对下一个字符进行分析。,若X为一非终结符A，则查MA,a：i若MA,a中为一个A的产生式，则将A自栈顶弹出，并将MA,a中的产生式右部符号串按逆序逐一压入栈中；如果MA,a中的产生式为A，则只将A自栈顶弹出。ii若MA,a中为空，则发现语法错误，调用出错处理程序进行处理。,控制程序描述如下：将“#”和文法开始符依次压入栈中；把第一个输入符号读入a；do把栈顶符号弹出并放入X中；if(XVT)if(X=a)将下一输入符号读入a;elseerror();elseif(MX,a=“XY1Y2Yk”)依次把Yk、Yk1、Y1压入栈中;输出“XY1Y2Yk”;elseerror();while(X!=“#”),例一文法的LL(1)分析表如表所示，试给出输入串aadl的分析过程。,输入串aadl的分析过程,2LL(1)分析表的构造定义FIRST集假定是文法GS的任一符号串(VTVN)*)，FIRST()a*a,aVT如果*，则规定FIRST()。FIRST()是的所有可能推导的开头终结符或可能的。,求能推导出的非终结符数组元素XA为0表示A不能推导出；XA为1表示A能推导出。(0)对所有AVN，XA0；(1)对所有AVN，若有A，则XA1；(2)change0；对每个XA为0的非终结符A，若有AB1B2Bn且XB1=XB2=XBn=1，则XA1，change1；(3)若change=1，则转(2)；否则，结束。,例如，文法GS：SAB，SbC，A，Ab，B，BaD，CAD，Cb，DaS，Dc(0)XS=XA=XB=XC=XD=0(1)XA=1，XB=1(21)XS=1，change=1(22)change=0,FIRST集构造方法设=X1X2Xn，其中Xi(VNVT),1in,为了求的首符集，分两步：首先求Xi的首符集，然后再求的首符集。1）求出文法中每个文法符号的首符集；(1)若xVT，则First(x)=x;(2)若XVN，且有产生式Xa，则将a加到First(X)中;若X,则也加入到First(X)；,(3)若XY1Y2Yk，其中Yj(VNVT),1jk,则按如下算法求First(X)j=0;FIRST(X)=;/初始化REPEATj=j+1;FIRST(X)=FIRST(X)(FIRST(Yj)-)UNTILFIRST(Yj)或j=kIF(j=k且FIRST(Yk)THENFIRST(X)=FIRST(X),2）求First()设=X1X2Xn，其中Xi(VNVT),1in,则按如下算法求First()i=0;FIRST()=;/初始化REPEATi=i+1;FIRST()=FIRST()(FIRST(Xi)-)UNTILFIRST(Xi)或i=nIF(i=n且FIRST(Xn)THENFIRST()=FIRST(),例如，文法GS：SAB，SbC，A，Ab，B，BaD，CAD，Cb，DaS，DcFIRST(A)=b,FIRST(B)=a,FIRST(D)=a,cFIRST(S)=(FIRST(A)-)FIRST(B)-)b=a,b,FIRST(C)=a,b,c,SAB，SbC，A，Ab，B，BaD，CAD，Cb，DaS，Dc,FIRST(AB)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=a,b,cFIRST(aS)=aFIRST(c)=c,定义FOLLOW集假定A是文法GS的任一非终结符(AVN)FOLLOW(A)=aS*Aa,aVT如果S*A，则规定#FOLLOW(A)。FOLLOW(A)是所有句型中出现在紧随A之后的终结符或“#”。,FOLLOW集构造方法：1)对文法开始符号S，将#加入到Follow(S)中；2)若BA是文法G的一个产生式，则将First()-加入到Follow(A)中;3)若BA是文法G的一个产生式，或BA是文法G的一个产生式，且*，则将Follow(B)加入到Follow(A)中；对任意aFollow(B)，有S*Ba，于是有S*BaAa或S*BaAa*Aa，所以aFollow(A)。,例如，文法GS：SAB，SbC，A，Ab，B，BaD，CAD，Cb，DaS，DcFOLLOW(S)=FOLLOW(D)#FOLLOW(A)=FIRST(B)-FOLLOW(S)FIRST(D)=aFOLLOW(S)a,cFOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FOLLOW(C),SAB，SbC，A，Ab，B，BaD，CAD，Cb，DaS，Dc,FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,构造预测分析表1、基本思想1）若A是一个产生式，aFirst(),那么当A是栈顶符号且将读入a时，选择取代A匹配成功的希望最大。故，MA,a元素为A。2）若A，而*；当A是栈顶符号且将读入a时，若aFollow(A)，则栈顶的A应被匹配；此时读头不前进，让A的跟随符与读头下的符号进行匹配，这样输入串匹配成功的可能最大。故MA,a元素为A。,2、构造算法1）假定A是一个产生式，aFirst(),那么当A是栈顶符号且将读入a时，A就应作为选用的侯选式，A应填入MA,a中。2）若A，而First()，对每个aFollow(A)，在MA,a元素中应填A。3）把所有无定义的MA,a都填上出错标志。,注：1）用此算法可以为任意文法G构造其分析表M。2）若是二义文法或没有消除左递归和提取左因子的文法，构造出的M包含有重定义项。即，它们的MA,a中填有一个以上的产生式。,定义LL(1)文法一个文法GS，若它的分析表M不含多重定义入口，则称它是一个LL(1)文法。定理一个上下文无关文法是LL(1)文法的充分必要条件是：对每一个非终结符A的任何两个不同产生式A，有下面的条件成立：(1)FIRST()FIRST()；(2)若*，则FIRST()FOLLOW(A)。,注意：1）可以使用这个定理直接根据FIRST集、FOLLOW集来判断文法是否是LL(1)。但判断之前，必须消除左递归和提取公共左因子，因为包含左递归和公共左因子的文法肯定不是LL(1)文法。2）LL(1)文法只是上下文无关文法的一个子集。,例：判断下面文法是不是LL(1)文法：SifEthenSelseS|ifEthenS|otherEb解：首先对文法进行改造，消除文法左递归和提取公共左因子；文法改写为：SifEthenSS|otherSelseS|Eb,SifEthenSS|otherSelseS|Eb,第2步求首字符集和跟随符集First(S)=if,other,First(S)=else,First(E)=bFollow(S)=Follow(S)=else,#Follow(E)=then第3步：根据定理判定文法是不是LL(1)文法。1)First(ifEthenSS)First(other)=First(elseS)First()=2)First(elseS)Follow(S)=else不为空集故此文法不是LL(1)文法。,例试构造表达式文法GE的LL(1)分析表，其中：GE:ETEE+TETFTT*FTF(E)i,ETEE+TETFTT*FTF(E)i,解答首先构造FIRST集，步骤如下：(1)FIRST(E)+,；FIRST(T)*,；FIRST(F)(,i；(2)FIRST(E)=FIRST(T)=FIRST(F)=(,i。(3)FIRST(TE)=(,i,FIRST(+TE)=+,FIRST(FT)=(