第5章 语法分析-自顶向下分析

.,第5章语法分析自顶向下分析,本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理。确定的自顶向下分析思想FIRST、FOLLOW、SELECTLL(1)文法的判别预测分析方法,.第5章语法分析自顶向下分析(2),LL(1)分析法。要求理解递归下降分析、LL(1)文法的基本概念；LL(1)分析表的构造与分析方法。能够对一个给定的文法判断是否是LL(1)文法；能构造预测分析表；能用预测分析方法判断给定的输入符号串是否是该文法的句子；能对某些非LL(1)文法做等价变换：消除左递归提取左公共因子可能会变成LL(1)文法。这样可扩大自顶向下分析方法的应用。,教学目的及要求,.,5.1确定的自顶向下分析思想,要点：由根向下构造语法树；构造最左推导；推导出的终结符是否与当前输入符匹配？SaaabABaA,SABAaABbbBaaabSABSABaABAaAaaABAaAaaaABAaAaaaBAaaabBb,.,1.带回溯的自上而下分析,SABAaABbbBaaabbS(1)A.SAB(2)aA.AaA(3)aaA.AaA(4)aaaA.AaA(5)aaaB.A(6)aaabBb,aaabbS(1)A.SAB(2)aA.AaA(3)aaA.AaA(4)aaaA.AaA(5)aaaBA(6)aaabBBbB(7)aaabbBb,.,2.无回溯的自顶向下分析程序,特征根据下一个输入符号为当前要处理的非终结符选择产生式。要求文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导1向前看一个输入符号(lookahead)预测分析程序的实现技术(1)递归下降子程序(2)表驱动分析程序,.,3.语法分析的任务语法分析是编译过程的核心部分。检查由扫描器输出的单词序列是否符合该语言的文法句子。分析器的输入：单词序列分析器的输出、分析树出错处理：定位、继续编译分析方法：（1）自顶向下(预测分析)（2）自底向上(算符优先、LR分析器),.,.,例5-1若有文法GS：SpA|qBAcAd|aBdB|b若输入串W=pccadd，自顶向下的推导过程为：SpApcAdpccAddpccAdd所示文法的两个特点：(1)每个产生式的右部都由终结符开始。(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。因此分析过程是唯一确定的。,.,例5-2若有文法GS：SAp|BqAcA|aBdB|b若输入串W=ccap，自顶向下的推导过程为：SApcApccApccap所示文法有三个特点(1)产生式的右部不全是由终结符开始。(2)如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。(3)文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时，为了便于正确考察和选择需要求出相关产生式的首符号集FIRST()。,.,定义5-1设G=(V，T，P，S)是上下文无关文法FIRST()=a*a,aT,(VT)*若*则规定FRIST()，称FIRST()为的开始符号集或首符号集。求例5-2的首符号集如下：FIRST(Ap)=a,cFIRST(Bq)=b,d结论：产生式左部相同，而右部都以非终结符开始，只要他们右部的符号串可以推导出的首符号集不相交，仍然可以唯一确定所要选择的产生式。,.,5.2LL(1)文法的判别方法,利用自顶向下的语法分析技术，必须首先判断给定的文法是否为LL(1)文法。分别计算FIRST、FOLLOW、SELECT集合，进而判断给定的文法是否为LL(1)文法。分析前面的3个例子，找出关键问题，不同的问题采用不同的方法。,.,计算FIRST集,1.若XT，则FIRST(X)=X2.若XV，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。3.若XY是一个产生式且YV,则把FIRST(Y)中的所有非元素都加到FIRST(X)中；若XY1Y2YK是一个产生式，Y1,Y2,Y(i-1)都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1.Y(i-1)*)，则把FIRST(Yj)中的所有非元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj,j=1,2,K)均含有，则把加到FRIST(X)中。,.,例5-3若有文法GS：SaASdAbASA若输入串W=abd,则试图推导出abd串的推导过程为:,.,例5-3所示文法的特点当某一非终结符的产生式中含有空产生式时，它的非空产生式的右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可以构造确定的自顶向下分析，为此，需要定义一个文法符号的后跟符号的集合FOLLOW()。定义5-2FOLLOW(A)=aS*A且aT,aFRIST()，(VT)*，(VT)+若S*A，且*，则#FOLLOW(A)。,.,计算FOLLOW集,1.对于文法的开始符号S，置#于FOLLOW(S)中；2.若B是一个产生式，则把FIRST()#加至FOLLOW(B)中；3.若B是一个产生式，或B是一个产生式而*(即FIRST()，则把FOLLOW(A)加至FOLLOW(B)中。,.,定义5-3给定上下文无关文法的产生式AAV，(VT)*,若*，则SELECT(A)=FIRST()。如果*，则SELECT(A)=(FIRST()-)FOLLOW(A)。定义5-4一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式，A，A满足SELECT(A)SELECT(A)=其中、不同时能*。,.,LL(1)文法的判别一个文法G是LL(1)的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立：FIRST()FIRST()=，也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字。.假若*，那么，FIRST()FOLLOW(A)。也就是，若*，则所能推出的串的首符号不应在FOLLOW(A)中。,.,例：GE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fi,非终结符的FIRST集合如下：FIRST(E)=(，iFIRST(E)=+，FIRST(T)=(，iFIRST(T)=*，FIRST(F)=(，i,非终结符的FOLLOW集合为：FOLLOW(E)=)，#FOLLOW(E)=)，#FOLLOW(T)=，)，#FOLLOW(T)=，)，#FOLLOW(F)=*,，)，#,.,GE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa,E+TEFIRST(+TE)=+FOLLOW(E)=)，T*FTFIRST(*FT)=*FOLLOW(T)=+,)，F(E)aFIRST(E)=(FIRST(a)=a所以GE是LL(1)的,.,5.3非LL(1)文法与LL(1)文法的等价变换LL(1)文法的性质:LL(1)文法是无二义的LL(1)文法不含左递归非LL(1)文法的改造（1）提左公因子（2）消除左递归,.,1.提取左公共因子文法G的产生式A1存在左因子,这导致了对相同左部的产生式其右部的FIRST集相交，即SELECT(A1)SELECT(A)。影响分析：遇到时难以判断用哪一个产生式进行匹配若A1改写成:A(1)或引入新非终结符AAA1一般：A12n1m改写成:AA1mA12n若1，2n仍有公共左因子，可再次提取，直到无公共左因子为止。,.,例5-6GS：(1)SaSb(2)SaS(3)S提取(1)(2)的左公因子后得：SaSAAbS例5-7SiEtSiEtSeSaEb其中，i,t,e分别表示if,then和else,E和S分别表示表达式和语句。提取了公共左因子之后，文法变为SiEtSaSeSEb于是，对于输入i，可以展开S为iEtSS，直到iEtS分析完毕再去决定把S展为eS或。,.,隐式左公因子：产生式右部以非终结符开始，方法：用该非终结符的右部以终结符开始的产生式去替换它。例5-8GS:SaSdAcAaSb把A的产生式代入S中：SaSdaScbc提取左因子：SaSAbcAdcAaSbA的产生式是多余的，需删除。最终：SaSAbcAdc,.,例5-9GS：(1)SApBq(2)AaApd(3)BaBqe用(2)(3)右部替换(1)中的A，B(1)SaAppaBqqdpeq(2)AaApd(3)BaBqe替换(1)Sa(AppBqq)dpeqSaSdpeqSAppBqq继续，无休止。在有限步骤内不能改写成无公共左因子的文法。,说明：1、有些文法在有限步骤内不能改写成无公共左因子的文法。2、一个文法提取公共左因子后不一定为LL(1)文法。,.,2.消除左递归左递归的定义：一个文法G，若存在下列产生式时AA,其中:AV,(VT)*，(直接左递归)ABBAA,BV,、(VT)*,(间接左递归)则称G是左递归的。左递归文法不适于用来构造自顶向下分析，这种产生式更简单的代表是：SSab(1)FIRST(Sa)FIRST(b)。(2)由S产生的句子是bann0。例如:对于输入baaa#,从左到右扫描输入串。,.,用这样的产生式构造递归预测分析的过程，那么，一进入这种过程不匹配任何输入符号，直接执行递归调用，形成自己调用自己的死循环。,.,消除直接左递归1.简单左递归AA消除左递归改写为右递归：AAAA2.一般左递归AA1A2Am12n消除左递归改写为右递归：A1A2AnAA1A2AmA例如：EE+TTTT*FFF(E)id,消除左递归的结果为：ETEE+TETFTT*FTF(E)id,.,消除间接左递归要求无环路AA和无-产生式。1.把非终结符按某一顺序排序为A1,A2An。2.for(i=1;iaba当前输入串为：xay可以通过不确定的语法分析树进行分析！,.,若输入串为xay，则其分析过程如下：(1)首先建立根结点S。(2)文法关于S的产生式只有一个，也即由S生长的语法树如图(a)所示，它的第一个终结符x与输入串待分析的字符x匹配。此时，下一个待分析的字符为a，期待着与语法树中在x右侧且与x相邻的叶结点A匹配。(3)非终结符A有两个候选式，先选用第一个候选式生长的语法树如图(b)所示；这时语法树的第二个叶结点a恰与待分析的字符a匹配。,.,(4)输入串中下一个待分析的字符为y，它期待与第三个叶结点b匹配，但匹配时发现这两个字符是不同的，即匹配失败，这是因为生成A的子树时所选用的是其第一个候选式。(5)因不匹配而将A所生成的这棵子树注销，即把匹配指针回退到输入串的第二个字符a，也就是恢复与A匹配时的现场，即(3)之前。(6)此时A选用第二个候选式并生长语法树如图(c)所示，这时第二个叶结点a与输入串的第二个叶结点a匹配。,.,(7)此时输入串的下一个待分析字符指向y，而语法树的下一个未匹配的叶结点也为y，两者恰好匹配。因此，图(c)的语法树即为输入串xay的语法树。试探分析对应的语法树,.,2.由于相同左部产生式的右部存在能=*的产生式，且该终结符的FOLLOW集中含有其它产生式右部FIRST集的元素。SaASSbAbASA对输入串ab#的试探推导过程可以用不确定的语法树表示！,.,3.由于文法含有左递归SSaSb对输入串baa#的试探推导过程可以用不确定的语法树表示！显然，这种带回溯的自上而下分析是一个不断试探的过程；其分析效率极低，在实用的编译程序中很少使用。,.,典型例题及解答,例题1已知文法G(S)：SaHHaMddMAbAaMe1.判断G(S)是否为LL(1)文法，若是，构造相应的预测分析表。2.请给出对输入串aaabd#的预测分析过程，aaabd是否为合法句子。,.,SaHHaMddMAbAaMe,.,预测分析表,SaHHaMddMAbAaMe,.,对输入串aaabd#的预测分析过程如下：,.,例题2文法G(S)：SAabASBBab1.试对文法进行改写，并判断改写后的文法是否为LL(1)文法？2.对于一个文法若消除了左递归，提取了左公因子后是否一定为LL(1)文法？,.,第1种改