第5章 自顶向下语法分析

语法分析技术概况不确定的自顶向下分析法递归下降分析法确定的预测分析法LL(1)语法分析方法简单优先分析法优先分析法算符优先分析法自底向上分析法LR(0)分析法LR分析法SLR(1)分析法LR(1)分析法LALR(1)分析法第五章自顶向下语法分析方法5.1自顶向下分析法的相关问题5.2LL(1)文法的定义和判别5.3文法等价变换5.4确定的自顶向下分析法（递归下降程序法和预测分析法）5.1相关问题1、什么是语法分析？2、什么是自顶向下分析法？3、在自顶向下的分析过程中，存在的问题是什么？4、什么是确定的自顶向下分析法？文法G1[S]:SpA[1]SqB[2]AcAd[3]Aa[4]输入串W=pccadd。自顶向下的推导过程为:SpApcAdpccAddpccadd相应的语法树为：pAcAdcAdaS5.1相关问题文法G1[S]:SpA[1]SqB[2]AcAd[3]Aa[4]自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)】S#pccadd#DerivationpA#pccadd#MatchA#ccadd#DerivationcAd#ccadd#MatchAd#cadd#DerivationcAdd#cadd#MatchAdd#add#Derivationadd#add#Matchdd#dd#Matchd#d#Match##Success5.1相关问题问：当一个非终结符号对应若干个规则时，选择哪个规则的右部对该非终结符号进行展开呢？例如：如果要被代换的最左非终结符号是U，且有n条规则：U::=A1|A2|…|An，那么如何确定用哪个规则的右部去替代U？5.1相关问题确定的自顶向下分析法：对每一个非终结符，都能够确定地选择规则来展开它。LL(1)文法文法G2[S]:SAp[1]SBq[2]Aa[3]AcA[4]Bb[5]BdB[6]输入串W=ccap。自顶向下的推导过程为:SApcApccApccap相应的语法树为：SApcAcAa5.1相关问题First集的定义设G=(VT，VN，S，P)是上下文无关文法,其中：(VT∪VN)*，则：First()={aVT|a...}∪(ifεthen{ε})可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。**5.2LL(1)文法的定义和判别文法G3[S]:SaA[1]Sd[2]AbAS[3]Aε[4]输入串W=abd。自顶向下的推导过程为:SaAabASabSabd相应的语法树为：SaAbASεdFollow集的定义设G=(VT，VN，S，P)是上下文无关文法，AVN，S是开始符号Follow(A)={aVT|S...Aa...}∪(ifS......Athen{#})当文法中存在推导形如：Aε时，如果当前的字符属于Follow(A)，则用空字符串取代A的出现。*++5.2LL(1)文法的定义和判别Select集的定义Select(A→)=First()，当εFirst()=First()∪Follow(A),当εFirst()定义：文法G是LL(1)文法的充要条件是,对于U的任意两个不同的规则有:Select(U→α)∩Select(U→)=Φ5.2LL(1)文法的定义和判别LL(1)文法的判别判别算法：1、计算能推出ε的非终结符2、构造First集3、构造Follow集4、构造Select集并作判别5.2LL(1)文法的定义和判别文法G[E]：ETE’E’+TE’|TFT’T’*FT’|Fi|(E)EE’TT’FNYYNN计算First(X)集对每一文法符号X计算First(X)若XVT,First(X)={X}若XVN则First(X)={a|Xa…P,aVT}若XVN,且有产生式Xε,则εFirst(X)若XVN,有产生式XY1Y2…Yn，且Y1,Y2,…,YiVN当Y1,Y2,…,Yi-1ε，则First(Y1)-{ε},First(Y2)-{ε},…First(Yi-1)-{ε},First(Yi)都包含在First(X)中。当Yiε(i=1,2,…n),将{ε}并入First(X)中。**文法G[E]：ETE’E’+TE’|TFT’T’*FT’|Fi|(E)First(E)First(T)First(E’)First(T’)First(F)*+i(计算First()集若符号串=X1X2…Xn，当X1,X2,…Xi-1，Xi不能，则First()=(First(Xj)-{})First(Xi)若所有Xi都能，则First()=First(Xj)i=1jj-1i=1***计算Follow(X)集1:对所有XVN，令Follow(X):={}；对开始符S,令Follow(S)={#}；2:若有产生式A→xBy，如果First(y)则：Follow(B)=First(y)否则Follow(B)=(First(y)－{})Follow(A)3:重复2和3，直至对所有XVN，Follow(X)收敛为止。文法G[E]：ETE’E’+TE’|TFT’T’*FT’|Fi|(E)Follow(E)Follow(T)Follow(E’)Follow(T’)Follow(F)#First(E’))+First(T’)*计算Select集Select(A→)=First()，当First()不含ε=First()-{ε}Follow(A)，当First()含ε结论：如果相同左部产生式的Select交集都是空集，则该文法是LL(1)文法。文法G[E]：ETE’E’+TE’|TFT’T’*FT’|Fi|(E)Select(ETE’)=first(TE’)={i,(}Select(E’+TE’)=first(+TE’)={+}Select(E’)=follow(E’)={),#}Select(TFT’)=first(FT’)={i,(}Select(T’*FT’)=first(*FT’)={*}Select(T’)=follow(T’)={+,),#}Select(Fi)=first(i)={i}Select(F(E))=first((E))={(}文法G[E]：ETE’E’+TE’|TFT’T’*FT’|Fi|(E)Select(E’+TE’)∩Select(E’)=Select(T’*FT’)∩Select(T’)=Select(Fi)∩Select(F(E))=因此，该文法是LL(1)文法。5.3文法等价变换LL(1)文法不含公共左因子某个非终极符A有如下的两个产生式：A→，A→(即有左公共前缀)LL(1)文法不含左递归某个非终极符A有直接左递归产生式：A→A|......消除左公共因子变换步骤：1:产生式形如：A1|2|…|n|表示不以开头的字符串。2:引进非终极符A’，使产生式替换为：AA|A1|2|…|nStm→id:=ExpStm→id(ExpL)ExpL→ExpExpL→Exp,ExpLStm→idStmStm→:=ExpStm→(ExpL)ExpL→ExpExpLExpL→,ExpExpLExpL→消除左公共因子的例子1消除左公共因子(简接)的例子2AadABcBaABbBAadAaAcAbBcBaABbBAa(d|Ac)AbBcBaABbBAaAAdAAcAbBcBaABbB替换提因子引进A’消除左递归一个文法含有下列形式的产生式时（1）AAAVN,V*（2）ABBAA,BVN,,V*其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有AA…，则称文法为左递归的。+对直接左递归形如：AA|消除直接左递归为：AAAA|消除间接左递归：在没有形如A=A的推导和没有空规则的条件下，算法如下：1:将所有非终结符排列为A1,A2,…,An;2:for(i=1;i=n;i++)for（j=1；j=i-1;j++）｛将规则Ai→Ajy改写；//若Aj→x1|x2|…|xk，//则Ai→x1y|x2y|…|xky｝消除规则中的直接左递归;3:化简文法（消除无用规则）。例：[1]A→B1|a[2]B→C2|b[3]C→A3|cAB1C21A3212:ij1没有直接左递归，无须改写1:非终结符排序：A,B,C3:消除无用规则。新文法中的产生式是[1][2][4][5]消除[3]中的直接左递归，引入新非终结符C：[4]C→(b13|a3|c)C[5]C→213C|2把[2]代入[3]得：[3]C→C213|b13|a3|c31把[1]代入[3]得：[3]C→(B1|a)3|c21无须替换，没有直接左递归，无需改写5.4自顶向下分析—递归下降法递归下降法(Recursive-DescentParsing)对每个非终结符按其产生式右部设计相应的语法分析子程序。终结符产生匹配命令[match(…)]非终结符则产生调用命令文法递归则相应的子程序也递归，所以称为递归子程序方法或递归下降法。对应每个非终结符，编一个独立的子程序。对应每个非终结符语法分析从读入第一个单词开始，沿语法描述图箭头所指出的方向进行分析：当遇到非终结符时，则调用相应的子程序。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。（１）选择形式根据规则U→x1|x2|…|xn，有:P(U)≡P(x1|x2|…|xn)≡switch(SYM){caseSELECT(U→x1):P(x1);break;caseSELECT(U→x2):P(x2);break;…caseSELECT(U→xn):P(xn);break;default:ERROR();(２)序列形式。根据y=y1y2…ym，有:P(y)≡P(y1y2…ym)≡{P(y1);P(y2);…;P(ym);}(３)若每个终结符yi，有P(yi)≡match(yi)≡CHECK(yi);GetSym();而CHECK(yi)≡if(SYM!=yi)ERROR();(４)对每个非终结符U，P(U)是调用语句U()．例5构造文法G[E]的递归子程序．G[E]:E→eBaAP(E)≡{match(e);A→a|bAcBB();B→dEd|aCmatch(a);C→e|dCA();}P(A)≡if(SYM==a)P(a);elseif(SYM==b)P(bAcB);elseERROR();≡if(SYM==b)P(bAcB);elsematch(a);≡if(SYM==b){/*match(b)*/GetSym();A();match(c);B();}elsematch(a);P(B)≡switch(SYM){cased:GetSym();E();match(d);break;casea:GetSym();C();break;default:ERROR();}P(C)≡if(SYM==d){GetSym();C();}elsematch(e);(5)重复形式。P({E})≡while(SYMINFIRST(E))P(E);P(E{E})≡do{P(E);}while(SYMINFIRST(E));(6)取舍形式。P([E])≡if(SYMINFIRST(E))P(E);例6PL