编译原理第四章课件——张淑艳.ppt

编译原理,语法分析自上而下分析,词法分析器,语法分析器,语义分析与中间代码生成器,代码优化,表格管理,出错处理,目标代码生成器,语法分析自上而下分析,本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；用上下文无关文法来描述语法规则。,上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。,例，定义只含+，*的算术表达式的文法G=，其中，P由下列产生式组成：EiEE+EEE*EE(E),定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。例：对文法(1)E(E)(E+E)(i+E)(i+i),通常，用表示：从1出发，经过一步或若干步，可以推出n。,用表示：从1出发，经过0步或若干步，可以推出n。,所以：即或,定义：假定G是一个文法，S是它的开始符号。如果，则称是G的一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。,4.1语法分析器的功能,语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。,.,语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约,G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+iE*i+iE*E+iE+iE+EE,i,+,*,i,i,语法分析的方法：自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。,4.2自上而下分析面临的问题,自上而下就是从文法的开始符号出发，向下推导，推出句子。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。,例4.1假定有文法G1(S):(1)SxAy(2)A*|*分析输入串x*y(记为)。,当某个非终结符有多个产生式候选时，可能带来如下问题:1.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P含有左递归的文法将使自上而下的分析陷入无限循环。2.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。,确定的自顶向下分析思想,例2若有文法G2S：SpASqBAcAdAa若有输入串w=pccadd.,解：推导过程为：,其相应的语法树见右图：,这个文法的特点：1每个产生式的右部都由终结符号开始。2如果两个产生有相同的左部，那么它们的右部由不同的终结符开始。,显然对于这样的推导中完全可以根据当前的输入符号决定选择哪个产生式往下推导。因此分析过程是唯一的。,考察自顶向下的推导过程。,例3：,解：自顶向下的推导过程为：,其相应的语法树见右图：,这个文法的特点：1产生式的右部不全是由终结符号开始。2如果两个产生有相同的左部，它们的右部由不同的终结符或非终结符开始。3文法中无空产生式。,小结：,在上述推导过程中，对于产生式中相同左部含有非终结符打头的右部时，在推导中选用哪个产生式是不能直接知道的。,对输入串W=ccap为输入串时，其第一个符号为c，这时从S出发选择SAp，还是选择SBq。其根据是要知道A或B它们是否能推导以c打头的符号串，即它们的首符集是什么。若c是Ap的首符集的元素，且c不在Bq的首符集中，则选择SAp往下推导。反之，若c在Bq的首符集中，不在Ap的首符集中，则选择SBq往下推导。其它情况为不确定推导或出错。,因此，在推导前有必要求出每个文法符号的首符集。,这样在文法G3中，关于S的两个产生式虽然都以非终结符开始，但它们右部符号串可以推导出首符集合互不相交，因此可根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。因此是确定的自顶向下分析。,例4:,若有文法G4S:SaASdAbASA若有输入串W=abd。考察自顶向下的推导过程。,解：,相应语法树为右图：,当文法中有空产生式时,如例：,小结：,由此可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。为此可定义一个文法符号的后继符集合。,4.3LL(1)分析法,构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯,4.3.1左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP|其中不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：PPPP|,左递归变右递归,一般而言，假定P关于的全部产生式是PP1|P2|Pm|1|2|n其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P1P|2P|nPP1P|2P|mP|,左递归变右递归,例文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：ETEE+TE|TFTT*FT|F(E)|i,(4.2),PP1|P2|Pm|1|2|nP1P|2P|nPP1P|2P|mP|,例如文法G(S):SQc|cQRb|bRSa|a(4.3)虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc,如何消除它的左递归？,消除文法的左递归,如果一个文法满足以下条件：不含以为右部的产生式不含回路，则执行下述算法将消除所有左递归，但改写后的文法可能含有以为右部的产生式,消除左递归的算法:1.把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如PiPj的规则改写成Pi1|2|k;(其中Pj1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,例考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q的有关候选后，把Q的规则变为QSab|ab|b,例考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。Q的规则变为QSab|ab|b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成SSabc|abc|bc|c,例考虑文法G(S)SQc|cQRb|bRSa|aS变成SSabc|abc|bc|c消除S的直接左递归后：SabcS|bcS|cSSabcS|QSab|ab|bRSa|a,例考虑文法G(S)SQc|cQRb|bRSa|a消除S的直接左递归后：SabcS|bcS|cSSabcS|QSab|ab|bRSa|a关于Q和R的规则已是多余的，化简为：SabcS|bcS|cSSabcS|(4.4),注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：SQc|cQRb|bRbcaR|caR|aR(4.5)RbcaR|文法(4.4)和(4.5)的等价性是显然的。,4.3.2消除回溯、提左因子,为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A1|2|n,令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,特别是，若，则规定FIRST()。,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选i和jFIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。,提取公共左因子:假定关于A的规则是A1|2|n|1|2|m(其中，每个不以开头)那么，可以把这些规则改写成AA|1|2|mA1|2|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。代价：大量引进新的非终结符和产生式,使非终结符的首符集两两不相交的方法,在例4.1中，文法G1(S)：(1)SxAy(2)A*|*分析输入串x*y(记为)。消除文法G1(S)中的回溯(1)SxAy(2)A*B(3)B*|,（一）求FIRST(X)的算法对每一文法符号X(VNVT），求FIRST(X).(a)若XVT,则令FIRST(X)=X;(b)若XVN,且有产生式Xa.,(aVT)，则令aFIRST(X);(c)若XVN,有X，则令FIRST(X);(d)若XVN,y1,y2,.yi都VN,且有产生式Xy1y2.yn,注：三种集合均为终结符集,（二）求FIRST()的算法（=x1x2.xn):,1.若n=0,即=,则令FIRST()=;2.否则，对1in,求FIRST(xi)3.若n=1,则令FIRST()=FIRST(x1);4.若n2且对一切j=1,2,.,i-1都有FIRST(xj).则令FIRST(xi)-FIRST(),其中2in;若对一切j=1,2,n都有FIRST(xj),则令FIRST(),或：1.把FIRST(x1)中所有非元素加入到FIRST()中，即FIRST()=FIRST(x1)-;若FIRST(x1)包含有，则把FIRST(x2)的所有非元素加入到FIRST()中，即FIRST()=FIRST()(FIRST(x2)-);若FIRST(x1)和FIRST(x2)都包含有，则把FIRST(x3)的所有非元素加到FIRST()中；照此方法继续，一直到考察到xn。2.若FIRST(xi),i=1,2,n;即每个FIRST(xi)中都有。则将加到FIRST()中。特别地，若=，则FIRST()=.,例：有文法G（S）SBAABSAdBaABbSBc试写出其FIRST集,First(B)=a,First(B)=b,First(B)=c,First(S)=First(BA)=a,b,c,First(A)=First(BS)=a,b,c,First(A)=d,LL(1)分析条件,当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件就一定能进行有效的自上而下分析呢？答案是否定的。,ETEE+TE|TFTT*FT|F(E)|ii+i,4.3.3LL(1)分析条件,i+i,IP,E,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,F,T,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,i+i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E):ETEE+TE|TFTT*FT|F(E)|i,ST+,当非终结符T面临输入符号“+”时，“+”不属于T的任意候选首符集，但T的某个候选首符集包含时，就一定能使”+”自动匹配？只有当“+”是某个句型中跟在T后面的终结符时，才能允许自动匹配，否则“+”的出现是一种语法错误。,假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,特别是，若，则规定FOLLOW(A),4.3.3LL(1)分析条件,(这里#不是文法中的符号，而一个特别的表示输入串的结束符或称句子括号如#输入串#）表示：所有在句型中紧挨着A出现的终结符或#均是FOLLOW(A)的元素。,对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：1.对于文法的开始符号S，置于FOLLOW(S)中；2.若AB是一个产生式，则把FIRST()-加至FOLLOW(B)中；,3.若AB是一个产生式，或AB是一个产生式而(即FIRST()，则把FOLLOW(A)加至FOLLOW(B)中。,构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A1|2|n则FIRST(i)FIRST(j)(ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,对LL(1)文法的第三个条件可以理解为：当文法中含有形如：A和A的产生式时，其中AVN,V*,当和不同时推导出空串时，设*，*，则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符A的替代仍可唯一地确定候选。,定义：,定义选择符集合SELECT如下：对于给出上下文无关文法的产生式A,AVN,V*，则,LL(1)文法的判别,当一个文法是LL(1)文法时，则该文法一定能够采用确定的自顶向下的分析方法进行分析。,结论：LL(1)文法是无二义的。,LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定选择哪个产生式(规则)进行推导，类似也可以有LL(K)文法，也就是需向前查看K个符号才可确定选用哪个产生式。通常采用K=1，个别情况采用K=2。,给出例4文法的证明,例4的文法G4S为：SaASdAbASA由定义可得：SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=(-)FOLLOW(A)=a,d,#,所以SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#,=由定义知例4文法是LL(1)文法，所以可用确定的自顶向下分析。,证明下列文法是否为LL(1)文法,例5文法G5S为：SaASSbAbAA解：SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=(-)FOLLOW(A)=a,b所以SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b因此，例5文法不是LL(1)文法，因而也就不可能用确定的自顶向下分析。,LL(1)文法的判别,当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。在下面的讨论中假定所给文法是经过压缩的。,所谓文法是经过压缩的是指：文法中不得含有有害规则和多余规则.有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。含有、情况非终结符的产生式都为多余规则。,例,GS为：1)SBe2)BCe3)BAf4)AAe5)Ae6)CCf7)Df经对每个产生式进行分析可发现非终结符D为不可到达，C为不可终止,含D、C的产生式2)，6)，7)为多余规则应去掉。现举例说明判断LL(1)文法的步骤。,例7,若文法G7S为：SABSbCAAbBBaDCADCbDaSDc,判别步骤：1.求出能推出的非终结符2.计算FIRST集3.计算FOLLOW集4.计算SELECT集,求出能推出的非终结符,首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出。其值有三种情况：未定、是、否。,G7S：SABSbCAAbBBaDCADCbDaSDc,计算能推出的非终结符步骤如下,将数组X中对应每一非终结符的标记置初值为“未定”。扫描文法中的产生式。(a)删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出。(b)若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。,由中(a)、(b)得知例中对应非终结符D的标志改为否，对应非终结符A、B的标志改为是。,G7S：SABSbCAAbBBaDCADCbDaSDc,(a)删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出,(b)若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式,是,是,否,扫描产生式右部的每一符号。(a)若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改“是”，并删除该非终结符为左部的所有产生式。(b)若所扫描到的非终结符号在数组中对应的标志是“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”。重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。,G7S：SABCAD,3-(a)若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改“是”，并删除该非终结符为左部的所有产生式.在数组中A、B对应的标志都为是，删去后S的右部变为空，所以S对应标志置为是,3-(b)若所扫描到的非终结符号在数组中对应的标志是“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”。其中，A对应的标志为是，D对应的标志是否，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为否。,重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。,是,否,SABSbCAAbBBaDCADCbDaSDc,经过上述中(a)、(b)两步后文法中的产生式只剩下：SAB和CAD，也就是只剩下右部全是非终结符串的产生式。再由中的(a)步扫描到产生式SAB时，在数组中A、B对应的标志都为是，删去后S的右部变为空，所以S对应标志置为是。最后由中的(b)扫描到产生式CAD时，其中，A对应的标志为是，D对应的标志是否，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为否。,由关系图法求文法符号的FIRST集,由关系图法求文法符号的FIRST集，其方法为：(a)每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。(b)如果文法中有产生式AX，且则从对应A的结点到对应X的结点连一条箭弧。(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由判别步骤1确定是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。,计算FIRST集的关系图,由关系图法求得文法7非终结符的FIRST集结果如下：FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c,G7S：1.SAB2.SbC3.A4.Ab5.B6.BaD7.CAD8.Cb9.DaS10.Dc,1,1,2,4,6,7,7,8,9,10,a,FIRST(S),b,c,FIRST(B),FIRST(C),FIRST(A),FIRST(D),(a)每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。,(b)如果文法中有产生式AX，且推导出，则从对应A的结点到对应X的结点连一条箭弧。,(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由判别步骤1确定是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。,用关系图法求非终结符的FOLLOW集,a,FOLLOW(D),b,c,#,FOLLOW(S),FOLLOW(C),FOLLOW(A),FOLLOW(B),G7S：1.SAB2.SbC3.A4.Ab5.B6.BaD7.CAD8.Cb9.DaS10.Dc,FIRST(D),FIRST(B),(a)文法G中的每个符号和#对应图中的一个结点，对应终结符和#的结点用符号本身标记。对应非终结符的结点(如AVN)则用FOLLOW(A)或FIRST(A)标记。,(b)从开始符号S的FOLLOW(S)结点到#号的结点连一条箭弧。,(e)对每一FIRST(A)结点如果有产生式AX,且推出,则从FIRST(A)到FIRST(X)连一条箭弧,现在对例7文法用关系图法计算FOLLOW集，如图所示,则得FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#与根据定义计算结果相同。,(d)如果文法中有产生式AB,且，则从FOLLOW(B)结点到FOLLOW(A)结点连一条箭弧,每个产生式的SELECT集合计算为：SELECT(SAB)=FIRST(AB)FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=FIRST()FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=FIRST()FOLLOW(B)=#SELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c,4.计算SELECT集,SELECT(A)=FIRST()FOLLOW(A),FIRST()=(FIRST(Xj)FIRST(Xi),由以上计算结果可得相同左部产生式的SELECT交集为：SELECT(SAB)SELECT(SbC)=b,a,#b=bSELECT(A)SELECT(Ab)=a,c,#b=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)b,a,cbbSELECT(DaS)SELECT(Dc)=ac由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。,G7S：1.SAB2.SbC3.A4.Ab5.B,6.BaD7.CAD8.Cb9.DaS10.Dc,对于一个LL(1)文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A1|2|n1.若aFIRST(i)，则指派i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且aFOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。,4.4递归下降分析程序的构造,是进行语法分析的一种方法要求文法是LL(1)文法实现思想：识别程序由一组过程组成。每个过程对应于文法的一个非终结符号。过程的名字就是产生式左部的非终结符，过程体则是按产生式的右部符号顺序编写的，每匹配一个终结符，则再读入下一个输入符号；对于产生式右部的每个非终结符，则递归调用相应过程。,基本架构(1),对于每个非终结符号的产生式Uu1|u2|un处理的方法如下：U()ch保存当前符号sym;if(ch是u1符号串的第一个符号)处理u1elseif(ch是u2符号串的第一个符号)处理u2elseerror(),由于文法无回溯，可以保证选择是唯一的。当存在时，可以将error()替代为return;这样可以较晚发现错误。约定：进入这个过程时，已读入U的第一个符号到当前符号。离开这个过程时，下一个符号已经被读到当前符号。,基本架构(2),对于U的每个右部ui=x1x2xn的处理架构如下：处理x1的程序；处理x2的程序；处理xn的程序；如果右部为空，则不处理。,基本架构(3),对于右部中的每个符号xi如果xi为终结符号：if(x=当前输入符号串中的符号)NextCh()；else出错处理如果xi为非终结符号，直接调用相应的过程：xi()；,给出以下文法的递归子程序：,ETEE+TE|TFTT*FT|F(E)|i,/主程序PROGRAMMAIN;BEGINADVANCE;E;IFSYM=#THENACCEPTELSEERROREND;,PROCEDUREE;BEGINT;EEND;,PROCEDUREE;BEGINIFSYM=+THENBEGINADVANCE;T;EENDEND;,ETEE+TE|TFTT*FT|F(E)|i,ETEE+TE|TFTT*FT|F(E)|i,PROCEDURET;BEGINF;TEND;,PROCEDURET;BEGINIFSYM=*THENBEGINADVANCE;F;TENDEND;,PROCEDUREF;/F(E)|iBEGINIFSYM=iTHENADVANCEELSEIFSYM=(THENBEGINADVANCE;E;IFSYM=)THENADVANCEELSEERRORENDELSEERROREND;,ETEE+TE|TFTT*FT|F(E)|i,/提前报错，检测FRIST集PROCEDUREE;BEGINIFSYMINFRIST(T)THENBEGINT;IFSYMINFRIST(E)THENEELSEERROR;ENDELSEERROREND;,/提前报错，检测FOLLOW集PROCEDUREE;/E+TE|BEGINIFSYM=+THENBEGINADVANCE;T;EENDELSEIFSYMINFOLLOW(E)THEN空语句ELSEERROREND;,扩充的巴克斯范式,（1）用花括号表示闭包运算*。（2）用0n表示可任意重复0次至n次，00=0=（3）用方括号表示01，即表示的出现可有可无（等价于|）。引入上述元符号的文法称扩充的巴克斯范式。,例2：,文法G(E):ET|E+TTF|T*FFi|(E),为了处理方便，把上述文法变为：ET+TTF*FFi|(E)可以用语法图表示上述文法，如图4.3(p75),T:procedureT;beginF;whilechar=*dobeginREAD(char);Fendend,E:procedureE;beginT;whilechar=+dobeginREAD(char);Tendend,F:procedureF;beginifchar=(thenbeginREAD(char);E;ifchar)thenERRORelseREAD(char)endelseifchar=ithenREAD(char)elseERRORend,ET+TTF*FFi|(E),预测分析程序,一、预测分析程序工作原理预测分析程序或LL(1)分析法：总控程序分析表MA，a矩阵，AVN，aVT是终结符或，分析栈STACK用于存放文法符号,总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:1.若Xa，则宣布分析成功，停止分析。2.若Xa，则把X从STACK栈顶逐出，让a指向下一个输入符号。,匹配成功,3.若X是一个非终结符，则查看分析表M。若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。若MX，a中存放着“出错标志”，则调用出错诊察程序ERROR。,推导,预测分析程序的总控程序：BEGIN首先把然后把文法开始符号推进STACK栈；把第一个输入符号读进a；FLAG:=TRUE;WHILEFLAGDOBEGIN把STACK栈顶符号上托出去并放在X中；IFXVTTHENIFX=aTHEN把下一输入符号读进aELSEERROR,匹配成功,ELSEIFX=#THENIFX=aTHENFLAG:=FALSEELSEERRORELSEIFMX,a=XX1X2XkTHEN把Xk,Xk-1,X1一一推进STACK栈/*若X1X2Xk=，不推什么进栈*/ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕*/END,分析成功,推导,例4.6对于文法G(E)ETEE+TE|TFTT*FT|F(E)|i输入串为i1*i2+i3，利用分析表进行预测分析：,步骤符号栈输入串所用产生式0#Ei1*i2+i3#1#ETi1*i2+i3#ETE2#ETFi1*i2+i3#TFT3#ETii1*i2+i3#Fi,步骤符号栈输入串所用产生式3#ETii1*i2+i3#Fi4#ET*i2+i3#5#ETF*i2+i3#T*FT6#ETFi2+i3#7#ETii2+i3#Fi,步骤符号栈输入串所用产生7#ETii2+i3#Fi8#ET+i3#9#E+i3#T10#ET+i3#E+TE11#ETi3#,步骤符号栈输入串所用产生11#ETi3#12#ETFi3#TFT13#ETii3#Fi14#ET#15#E#T16#E,为了便于描述分析过程，我们定义：，代表栈X面临输入符号a采取第i条动作后，栈变为Y。例1分析i*i#,二、分析表MA，a的构造,构造FIRST()和FOLLOW(A)构造分析表MA，a,例4.6对于文法G(E)ETEE+TE|TFTT*FT|F(E)|i构造每个非终结符的FIRST和FOLLOW集合：,FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)=(,i,FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。1.对文法G的每个产生式A执行第2步和第3步；2.对每个终结符aFIRST()，把A加至MA，a中；3.若FIRST()，则对任何bFOLLOW(A)把A加至MA，b中。4.把所有无定义的MA，a标上“出错标志”。,如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。,G(S):SiCtS|iCtSeS|aCb提取左因子之后，改写成：G(S):SiCtSS|aSeS|Cb,最近匹配原则,递归下降分析程序构造,构造不带回溯的自上而下分析程序要消除文法的左递归性克服回溯,构造不带回溯的自上而下分析器分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号SYM，IP当前所指的输入符号ERROR，出错处理子程序,例:文法G(E):ETEE+TE|TFTT*FT|F(E)|i每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。,例:文法G(E):ETEE+TE|TFTT*FT|F(E)|i对应的递归下降子程序为:,PROCEDUREE；BEGINT；EEND；,PROCEDUREE；IFSYM=+THENBEGINADVANCE；T；EEND,PROCEDURET；BEGINF；TEND,PROCEDURET；IFSYM=*THENBEGINADVANCE；F；TEND；,例:文法G(E):ETEE+TE|TFTT*FT|F(E)|i对应的递归下降子程序为:,例:文法G(E):ETEE+TE|TFTT