语法分析自上而下分析 (2)幻灯片.ppt
语法分析自上而下分析第1页，共34页，编辑于2022年，星期二4.1语法分析器的功能功能定义：按照文法产生式，识别输入符号串是否为一个句子。技术路线：是否能从文法的开始符号出发推导出这个输入串。或者，建立一颗与输入串相匹配的语法分析树。策略：自上而下分析法，自下而上分析法。第2页，共34页，编辑于2022年，星期二图4.1语法分析器在编译程序中的地位接收词法分析器输出的记号串，检查是否合乎语法。报告语法错误，并恢复语法错误，从而可以继续分析。输出是分析树的某种形式。分析时其它任务：将各种记号的信息收入符号表、类型检查和其它语义检查、中间代码的生成，这些放在“前端的其它部分”完成。第3页，共34页，编辑于2022年，星期二4.2自上而下分析面临的问题例4.1假定有文法(1)SxAy(2)A*|*对输入串x*y，构造语法树。构造过程：(1)把S作为根(2)用S的产生式构造子树(3)让输入串指示器IP指向输入串的第一个符号。第4页，共34页，编辑于2022年，星期二(4)调整输入串指示器IP与叶结点进行匹配。(5)如果为非终结符，用A的下一个产生式构建子树。(6)如果匹配成功则结束；否则，回溯到步骤(4)。SxAySxAy*SxAy*第5页，共34页，编辑于2022年，星期二自上而下分析法的缺点：是文法的左递归性问题。一个文法是含有左递归的自上而下的分析过程陷入无限循环。如PP。由于有回溯，就会产生一大堆麻烦事情。在上述的自上而下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的。这种虚假现象，我们需要更复杂的回溯技术。一般说，要消除虚假匹配是很困难的。当最终报告分析不成功时，我们不知道输入串中出错的确切位置。第6页，共34页，编辑于2022年，星期二4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析条件第7页，共34页，编辑于2022年，星期二4.3.1左递归的消除一个简单例子：已知文法：PP|是一个左递归文法，它的等价的非左递归文法为：PPPP|例2.2一般转换规则有：PP1|P2|Pm|1|2|n改写成P1P|2P|nPP1P|2P|mP|其中：i都不以P开头,I不等于第8页，共34页，编辑于2022年，星期二一个反例：文法：SQc|c；QRb|b；RSa|a虽然不是直接左递归，但S、Q、R都是左递归。消除左递归算法：算法的思想是：首先构造直接左递归；再利用一般转换规则，消除直接左递归化简文法。下面算法在不含PP，也不含在右部产生式时可以消除左递归。第9页，共34页，编辑于2022年，星期二消除一个文法的左递归算法：(1)把文法G的所有非终结符按任一种顺利排列成P1Pn；按此顺序执行；(2)FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pj+1Pj的规则改写成Pj+11|1|k|。其中Pj1|1|k是关于Pj的所有规则；消除关于Pi规则的直接左递归性。END化简由（）所得的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生规则。第10页，共34页，编辑于2022年，星期二例子4.3：对4.3文法，它的非终结符排序为R,Q,S。把R代入Q，Q代入S得到：SSabc|abc|bc|c消除左递归后得到：SabcS|bcS|cSSabcS|QSab|ab|b(化简消去)RSa|a（化简后消去）对不同的排列，会有不同形式的无左递归文法，但它们等价。第11页，共34页，编辑于2022年，星期二4.3.2消除回溯、提左因子消除回溯的思路：对输入符号a，指派一个A的候选式1与a匹配，而再没有其他候选式i的字符与a匹配。通过提取公共左因子，判断首字符集的差异。首字符集定义：对G的所有非终结符的每个候选，它的首字符集为FIRST()=a|a，aVT，若*，则规定FIRST()。第12页，共34页，编辑于2022年，星期二提取公共左因子算法：A1|2|n|1|2|m(其中每个不以开头)那么可以把这些规则改写成：AA|1|2|mA1|2|n例4.4上述算法的不足：当非终结符A面临输入符号a,且a不属于A的任意候选首符集,但A的某个候选首符集包含时，就一定可以使A自动匹配。这是一种错误。第13页，共34页，编辑于2022年，星期二4.3.3LL(1)分析条件定义FOLLOW(A)集合：假定S是文法G的开始符号，对于G的任何非终结符A，我们定义FOLLOW(A)=a|S*Aa,aVT若S*A，则规定FOLLOW(A)。LL(1)文法的充分必要条件：文法不含左递归。若1|2|n，则FIRST(i)FIRST(j)=(ij)对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(A)FOLLOW(A)=第14页，共34页，编辑于2022年，星期二LL(1)匹配算法：对输入符号a，A的所有产生式为：1|2|n(1)若aFIRST(i)，则指派I去执行匹配任务。(2)若a不属于任何一个候选首符集，则：FIRST(i)且aFOLLOW(A)，则让A(i)与(a)自动匹配；否则，a的出现是一种语法错误。例4.4第15页，共34页，编辑于2022年，星期二4.4递归下降分析程序构造递归下降分析器：这个分析程序由一组递归过程组成的，每个过程对应文法的一个非终结符。ETEE+TE|TFTT*FT|F(E)|i第16页，共34页，编辑于2022年，星期二PROCEDUREEPROCEDURETBEGINBEGINT;EF;TENDENDPROCEDUREEPROCEDURETIFSYM=THENIFSYM=THENBEGINBEGINADVANCE;ADVANCE;T;EF;TENDEND第17页，共34页，编辑于2022年，星期二PROCEDUREFIFSYM=iTHENADVANCEELSEIFSYM=(THENBEGINADVANCE;E;IFSYM=)THENADVANCEELSEERRORENDELSEERROR;第18页，共34页，编辑于2022年，星期二扩展巴科斯范式(BackusNaurForm)：用花括号表示闭包运算*。用n0表示可任意重复次至n次，000=。用方括号表示0，即表示的出现可有可无,等价于|。第19页，共34页，编辑于2022年，星期二例4.5：文法ET|E+TTF|T*FFi|(E)可表示成ET+TFF*FF(E)|I第20页，共34页，编辑于2022年，星期二4.5预测分析程序4.5.1预测分析程序工作过程4.5.2预测分析表的构造第21页，共34页，编辑于2022年，星期二预测分析器思想：.a总控程序预测分析表MX.#输出输入串栈第22页，共34页，编辑于2022年，星期二表4.1 文法4.2的LL(1)分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)第23页，共34页，编辑于2022年，星期二预测分析程序的总控程序：其具体工作过程是首先把文法开始符号和#压入栈，然后总控程序在任何时候都是按STACK栈顶符号X和当前输入符号a行事的，如图所示。对于任何（X,a）,总控程序每次都执行下述三种可能的动作之一：若X=a,则宣布分析成功，停止分析过程。若X=a,则把X从STACK栈顶逐出，让a（指示器）指向下一个输入符号。若X是一个非终结符，则查看分析表M。若MA,a中存放着关于X的一个产生式，则X出栈，把X产生式右部符号串按反序压栈，如果MA,a中存放出错标志，则调用诊断程序。第24页，共34页，编辑于2022年，星期二预测分析程序的总控程序描述是：BEGIN首先把然后把文法开始符号推进STACK栈；把第一个输入符号读进a；FLAG:=TRUE;WHILEFLAGDOBEGIN把STACK栈顶符号上托出并放在X中；IFXVTTHENIFX=aTHEN把下一输入符号读进aELSEERRORELSEIFX=#THENIFX=aTHENFLAG:=FALSEELSEERROR第25页，共34页，编辑于2022年，星期二ELSEIFMA,a=XX1X2XkTHEN把Xk,Xk-1,X1一一推进STACK栈/*若X1X2Xk=，不推任何字进栈*/ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕*/END第26页，共34页，编辑于2022年，星期二例例4.6：输入串为i1*i2+i3,利用分析表进行预测分析的步骤步骤符号栈输入串所用产生式0#Ei1*i2+i3#1#ETi1*i2+i3#ETE2#ETFi1*i2+i3#TFT3#ETii1*i2+i3#Fi4#ET*i2+i3#5#ETF*i2+i3#T*FT15#E#T16#E第27页，共34页，编辑于2022年，星期二4.5.2预测分析表的构造FIRST(X)集的构造算法：若XVT，则FIRST(X)X。若XVn，且有产生式Xa,则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。若XY是一个产生式，且YVn，则把FIRST(Y)中所有非-元素都加到FIRST(X)中；若XY1Yi-1是一个产生式且YVn，且对任何的j(1ji-1),FIRST(Yj)都含有（即Y1Yi-1*）则把FIRST(Yj)中的所有非-元素都加到FIRST(X)中；特别地,若FIRST(Yj)都含有,把加入FIRST(X)中重复以上操作，直到FIRST(X)不再增大为止。上述算法可以推广到FIRST()，=X1Xk第28页，共34页，编辑于2022年，星期二非终结符B的FOLLOW(B)构造算法：对于文法的开始符号S,置于FOLLOW(B)中;若AB是一个产生式,则把FIRST()-加至FOLLOW(B)中；若AB是一个产生式,或AB是一个产生式而（即FIRST()）,则 把FOLLOW(A)加 至FOLLOW(B)中。第29页，共34页，编辑于2022年，星期二构造分析表M的算法：(1)对文法G的每个产生式A执行第步和第步；(2)对每个终结符aFIRST(),把A加至MA,a中；(3)若FIRST()，则对任何bfollow(A)把()加至MA,b中；(4)把所有无定义的MA,a标上“出错标志”例4.7、4.8第30页，共34页，编辑于2022年，星期二4.6LL(1)分析中的错误处理错误类型：栈顶的终结符与当前的输入符号不匹配。非终结符A处于栈顶,面临的输入符号为a，但分析表M中的MA,a为空。错误处理方法：跳过输入串中的一些符号直至遇到“同步符号”为止。第31页，共34页，编辑于2022年，星期二同步符号集合的选择方法：把FLLOWO(A)加入A的同步活动集。把FIRST(A)加入到A的同步活动集。直接弹出站顶元素，并发送信息告知插入下一个终结符后，继续分析。第32页，共34页，编辑于2022年，星期二例4.9：i+*()#EETEETESynchSynchEE+TEE E TTFTSynchTFTSynchSynchTT T*FTT T FFisynchsynchF(E)synchsynch表4.2加入同步符号的LL(1)分析表第33页，共34页，编辑于2022年，星期二分析栈输入串附注EE#ET#ETFE）i*+ii*+ii*+ii*+i错，跳过）iFIRST(E)表4.3对）id*+i的语法分析与错误处理第34页，共34页，编辑于2022年，星期二
