第五章 LL1文法及其分析程序

.,1,第5章自顶向下语法分析方法,主要内容：自上而下的语法分析预测分析程序递归下降子程序表驱动的预测分析程序LL(1)分析程序的生成LL(1)文法FIRST和FOLLOW集定义和计算非LL(1)文法的改造,.,2,5.1确定的自顶向下语法分析思想,1.语法分析概念2.自上而下的语法分析的一般过程3.自上而下的语法分析面临的问题4.开始符号集5.后跟符号集6.select集7.LL(1)文法,.,3,1。语法分析,在语言的编译实现中，把句子分析的过程称为语法分析，即完成这个任务的程序称为语法分析程序或称为识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,.,4,（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型的过程，或者说是某个推导的构造过程。,.,5,语法树推导的几何表示,句型aabbaa的可能推导序列和语法树,例:GS:SaASASbAASSSaAba,SaASSbAaaba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,.,6,分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,.,7,两种方法反映了语法树的两种构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,.,8,2。自上而下分析方法,对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，反复使用不同地产生式谋求匹配输入串的过程。,.,9,自上而下的语法分析的一般过程,例：文法G：ScAdAabAa识别输入串w=cabd是否为该文法的句子,SSScAdcAdab推导过程：ScAdcAdcabd,.,10,自上而下的语法分析的一般过程(1)ScAd(2)Aab(3)Aa识别输入串w=cad是否为,该文法的句子1.ScAd2.后选择(2)扩展A，得到推导ScAdcabd这时w的第二个符号可以与叶子结点a得以匹配，但第三个符号d却不能与下一叶子结点b匹配怎么办？-查看A有无另一个选择，有！回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）构造推导ScAdcad,识别输入串w=caa的过程：1.ScAd2.选择(2)扩展A，得到推导ScAdcabd3.回溯回到推导ScAd4.选择(3)扩展A，得到推导ScAdcad5.A没有选择了！回溯到推导ScAd6.再回溯S有无另一个选择？没有！宣告分析失败。（请思考若有(4)ScB(5)Baa会怎样?）,.,11,自上而下分析的进一步讨论,自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。自上而下分析对文法的要求文法不能含有左递归规则。自上而下分析又可分为确定的和不确定的两种不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法确定的分析方法需对文法有一定的限制,.,12,3。自上而下的语法分析面临的问题-实现考虑,回溯文法的左递归性SSa,.,13,自上而下分析对文法的要求,例文法G0S:(1)SSa(2)Sb分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)来推导SSa语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaaSaaa问题试图用S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求S去进行新的匹配.无法确定什么时候使用（2）产生式最适当，只能采用带回溯的不确定方法解决。原因文法含有左递归。,.,14,回溯的原因,例GS:SxAyAaba若当前输入串为xay，首先构造的推导SxAy匹配进一步推导对A可选择Aab替换，得SxAyxabyxayxaby匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa进行试探，SxAyxay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。,.,15,在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？-什么信息用于Parser做正确选择?(输入串,文法特点),.,16,可预测的试探推导过程,例文法GS:SpA|qBAcAd|aBdB|c识别输入串w=pccadd是否是G1S的句子可预测的试探推导过程：SpApcAdpccAddpccadd试探成功。,.,17,4。开始符号集-FIRST集,设G=(VT,VN,P，S)是上下文无关文法FIRST（）=a|=*a,aVT,、V*若=*则规定FRIST（）,.,18,FOLLOW（A）=aS=*A且aFRIST（），V*，V+若S=*uA,且=*，则#FOLLOW(A),5。后跟符号集-FOLLOW集,.,19,6。SELECT集,给定上下文无关文法的产生式AVN,V*若*，则SELECT()=FIRST()若=*,则SELECT()=(FIRST()-)FOLLOW(A),.,20,7。LL（1）文法一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立：SELECT()SELECT()=其中和不能同时=*,.,21,书中例子,.,22,5.2LL（1）文法的判别判别步骤：1）。求出能推出的非终结符,.,23,2）。计算FIRST集,1.若XV,则FIRST(X)=X2.若XVN,且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2YK是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1ji-1,FIRST(Yj)都含有(即Y1.Y(i-1)=*),则把FIRST(Yj)中的所有非元素和FIRST(Yi)中的所有元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,K)均含有,则把加到FRIST(X)中.,.,24,3）。计算FOLLOW集,1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若B是一个产生式,则把FIRST()-加至FOLLOW(B)中;3.若B是一个产生式,或B是一个产生式而=*(即FIRST()），则把FOLLOW（A）加至FOLLOW（B）中,.,25,GE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa,各非终结符的FIRST集合如下：FIRST(E)=(,aFIRST(E)=+,FIRST(T)=(,aFIRST(T)=*,FIRST(F)=(,a,各非终结符的FOLLOW集合为：FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，#FOLLOW(F)=*,，),#,.,26,4）。计算SELECT集,计算产生式的SELECT集,.,27,GE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa,E+TE|FIRST(+TE)=+FOLLOW(E)=)，T*FT|FIRST(*FT)=*FOLLOW(T)=+,)，F(E)|aFIRST(E)=(FIRST(a)=a所以GE是LL（1）的,.,28,5）。判断文法是否LL（1）文法,若文法所有具有相同左部产生式的SELECT集两两不相交，则文法是LL(1)文法。,.,29,LL(1)文法的性质：LL(1)文法是无二义的LL(1)文法不含左递归,.,30,5.3某些非LL(1)文法的改造,1。提取左公共因子提左公因子：将产生式|变换为：BB|,.,31,一般形式：,1|2|n提取左公共因子后：AAA1|2|n,.,32,2。消除左递归,左递归关于非终结符P的规则直接左递归：PP|、V*且、不以P开头一般左递归：P=*P例：SAaASb,.,33,消除文法中左递归规则,1）消除直接左递归：形如：PP|非，不以P打头改写为：PQQQ|其中Q为新增加的非终结符,.,34,消除文法中左递归规则举例,例:EE+T|TTT*F|FF(E)|aGE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa,.,35,消除一般左递归对文法要求:1.无回路(A(=+(A)2.无空产生式,2）消除一般左递归的方法：（1）.以某种顺序将文法非终结符排列A1,A2An（2）fori:=1tondobeginforj:=1toi-1do用Aj-1|2|k替代形如Ai-Ajr的规则,其中Aj-1|2|k是关于Aj的全部产生式;消除Ai规则的直接左递归;end;（3）化简由（2）得到的文法:去掉无用产生式,.,36,例P90,.,37,消除左递归和提左公因子并不一定都能将非LL(1)文法改造为LL(1)的,SifCtS|ifCtSeSCb提左因子SifCtSAAeS|,First集Follow集Sif#,eAe,#,eCbtSelect(AeS)Select(A)=e#,e改造后文法不是LL(1)文法,.,38,5.5确定的自顶向下分析方法,特征根据下一个(几个）输入符号为当前要处理的非终结符选择产生式要求文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导1向前看一个输入符号（lookahead),.,39,无回溯的自顶向下分析程序,预测分析程序的实现技术1.递归（下降）子程序2.表驱动分析程序,.,40,例：递归下降子程序ParseFunction(),BNF（Backus-NaurForm）描述programfunction_listfunction_listfunctionfunction_list|functionFUNCidentifier(parameter_list)statementvoidParseFunction()MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();,.,41,例：递归下降子程序ParseFunction()（续）,voidMatchToken(intexpected)if(lookahead!=expected)printf(syntaxerrorn);exit(0);else/ifmatch,consumetokenandmoveonlookahead=yylex();/读入一个单词,.,42,预测分析程序的实现表驱动预测分析程序模型,Input,#,总控程序,预测分析表,stack,.,43,预测分析表构造算法,1.对文法G的每个产生式执行第二步和第三步；2.对每个终结符aFIRST()，把加至A,a中，3.若FIRST()，则对任何bFOLLOW(A)把加至A,b中，4.把所有无定义的A,a标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的,.,44,例：表驱动予测分析程序GE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa用预测分析表表示状态转换。,.,45,GE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa预测分析表,.,46,表驱动预测分析程序分析算法,首先把#然后把文法开始符号推入栈；把第一个输入符号读进b;FLAG：=TRUE；WHILEFLAGDOBEGIN把栈顶符号上托出去并放在中；IFXVtTHENIFX=bTHEN把下一个输入符号读进bELSEERRORELSEIFX=#THENIFb=#THENFLAG:=FALSEELSEERRORELSEIFX,b=XX1X2.XKTHEN把XK，XK-1,.,X1一一推进栈ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕*,.,47,分析输入串#a+a#的步骤,栈内容栈顶符号当前输入余留串MX,b1#EEa+a#ETE2#ETTa+a#TFT3#ETFFa+a#Fa4#ETaaa+a#5#ETT+a#T6#EE+a#E+TE7#ET+a#8#ETTa#TFT9#ETFFa#Fa10#ETaaa#11#ETT#T12#EE#E13#,.,48,LL(1)分析中的一种错误处理办法,发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶，面临的输入符为a，但分析表M的MA,a为空“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。同步符号的选择1把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续2把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析,.,49,review-parsing,Thesyntaxanalysisphaseofacompilerverifiesthatthesequenceoftokensreturnedfromthescannerrepresentvalidsentencesinthegrammaroftheprogramminglanguage.Therearetwomajorparsingapproaches:top-downandbottom-up.Intop-downparsing,youstartwiththestartsymbolandapplytheproductionsuntilyouarriveatthedesiredstring.Inbottom-upparsing,youstartwiththestringandreduceittothestartsymbolbyapplyingtheproductionsbackwards.,.,50,Inthetop-downparsing,webeginwiththestartsymbolandateachstep,expandoneoftheremainingnonterminalsbyreplacingitwiththerightsideofoneitsproductions.Werepeatuntilonlyterminalsremain.Thetop-downparseprintsaleftmostderivationofthesentence.,Abottom-upparseworksinreverse.Webeginwiththesentenceofterminalsandeachstepappliesaproductioninreverse,replacingasubstringthatmatchestherightsidewiththenonterminalontheleft.Wecontinueuntilwehavesubstitutedourwaybacktothestartsymbol.Ifyoureadfromthebottomtotop,thebottom-upparseprintsoutarightmostderivationofthesentence.,.,51,lookaheadsymbol.Thelookaheadsymbolisthenextsymbolcomingupintheinput.backtracking.Basedontheinformationtheparsercurrentlyhasabouttheinput,adecisionismadetogowithoneparticularproduction.Ifthischoiceleadstoadeadend,theparserwouldhavetobacktracktothatdecisionpoint,movingbackwardsthroughtheinput,andstartagainmakingadifferentchoiceandsoonuntiliteitherfoundtheproductionthatwastheappropriateoneorranoutofchoices.,.,52,predictiveparserandLL(1)grammar,Predictiveparserisanon-backtrackingtop-downparser.Apredictiveparserischaracterizedbyitsabilitytochoosetheproductiontoapplysolelyonthebasisofthenextinputsymbolandthecurrentnonterminalbeingprocessed.Toenablethis,thegrammarmusttakeaparticularform.WecallsuchagrammarLL(1).Thefirst“L”meanswescantheinputfromlefttoright;thesecond“L”meanswecreatealeftmostderivation;andthe1meansoneinputsymboloflookahead.,.,53,recursive-descent,Thefirsttechniqueforimplementingapredictiveparseriscalledrecursive-descent.Arecursivedescentparserconsistsofseveralsmallfunctions(procedures),oneforeachnonterminalinthegrammar.Asweparseasentence,wecallthefunctions(procedures)thatcorrespondtotheleftsidenonterminaloftheproductionsweareapplying.Iftheseproductionsarerecursive,weendupcallingthefunctionsrecursively.,.,54,Table-drivenLL(1)parsing,Inarecursive-descentparser,theproductioninformationisembeddedintheindividualparsefunctionsforeachnonterminalandtherun-timeexecutionstackiskeepingtrackofourprogressthroughtheparse.Thereisanothermethodforimplementingapredictiveparserthatusesatabletostorethatproductionalongwithanexplicitstacktokeeptrackofwhereweareintheparse.,.,55,Howatable-drivenpredictiveparserworks,Wepushthestartsymbolonthestackandreadthefirstinputtoken.Astheparserworksthroughtheinput,therearethefollowingpossibilitiesforthetopstacksymbolXandtheinputtokennonterminala:1.IfX=aanda=endofinput(#):parserhaltsandparsecompletedsuccessfully2.IfX=aanda!=#:successfulmatch,popXandadvancetonextinputtoken.Thisiscalledamatchaction.3.IfX!=aandXisanonterminal,popXandconsulttableatX,atoseewhichproductionapplies,pushrightsideofproductiononstack.Thisiscalledapredictaction.4.Ifnoneoftheprecedingcasesappliesorthetableentryfromstep3isblank,therehasbeenaparseerror,.,56,Thefirstsetofasequenceofsymbolsu,writtenasFirst(u)isthesetofterminalswhichstartallthesequencesofsymbolsderivablefromu.Abitmoreformally,considerallstringsderivablefromubyaleftmostderivation.Ifu=*v,wherevbeginswithsometerminal,thatterminalisinFirst(u).Ifu=*,thenisinFirst(u).,.,57,ThefollowsetofanonterminalAisthesetofterminalsymbolsthatcanappearimmediatelytotherightofAinavalidsententialform.Abitmoreformally,foreveryvalidsententialformS=*uAv,wherevbeginswithsometerminal,thatterminalisinFollow(A).,.,58,Calculatingfirstset,TocalculateFirst(u)whereuhastheformX1X2.Xn,dothefollowing:1.IfX1isaterminal,thenaddX1toFirst(u),otherwiseaddFirst(X1)-toFirst(u).2.IfX1isanullablenonterminal,i.e.,X1=*,addFirst(X2)-toFirst(u).Furthermore,ifX2canalsogoto,thenaddFirst(X3)-andsoon,throughallXnuntilthefirstnonnullableone.3.IfX1X2.Xn=*,addtothefirstset.,.,59,Calculatingfollowsets.Foreachnonterminalinthegrammar,dothefollowing:,1.Place#inFollow(S)whereSisthestartsymboland#istheinputsrightendmarker.Theendmarkermightbeendoffile,itmightbenewline,itmightbeaspecialsymbol,whateveristheexpectedendofinputindicationforthisgrammar.Wewilltypicallyuse#astheendmarker.2.ForeveryproductionAuBvwhereuandvareanystringofgrammarsymbolsandBisanonterminal,everythinginFirst(v)exceptisplacedinFollow(B).3.ForeveryproductionAuB,oraproductionAuBvwhereFirst(v)contains(i.e.visnullable),theneverythinginFollow(A)