语法分析review.pptVIP免费

语法分析方法小结自上而下分析自下而上分析其他语法分析方法比较自上而下分析自上而下分析一般过程LL（1）文法预测分析程序递归下降分析实现表驱动分析实现自上而下分析一般过程Inthetop-downparsing,webeginwiththestartsymbolandateachstep,expandoneoftheremainingnonterminalsbyreplacingitwiththerightsideofoneitsproductions.Werepeatuntilonlyterminalsremain.Thetop-downparsecreatealeftmostderivationofthesentence.LL（1）文法Thefirst“L”meanswescantheinputfromlefttoright;thesecond“L”meanswecreatealeftmostderivation;andthe1meansoneinputsymboloflookahead.AgrammarGisLL(1)iffwheneverA–>u|varetwodistinctproductionsofG,thefollowingconditionshold:-fornoterminaladobothuandvderivestringsbeginningwitha(i.e.firstsetsaredisjoint)-atmostoneofuandvcanderivetheemptystring-ifv=>*thenudoesnotderiveanystringbeginningwithaterminalinFollow(A)Thefirstsetofasequenceofsymbolsu,writtenasFirst(u)isthesetofterminalswhichstartallthesequencesofsymbolsderivablefromu.Abitmoreformally,considerallstringsderivablefromubyaleftmostderivation.Ifu=>*v,wherevbeginswithsometerminal,thatterminalisinFirst(u).Ifu=>*,thenisinFirst(u).First集Follow集ThefollowsetofanonterminalAisthesetofterminalsymbolsthatcanappearimmediatelytotherightofAinavalidsententialform.Abitmoreformally,foreveryvalidsententialformS=>*uAv,wherevbeginswithsometerminal,thatterminalisinFollow(A).计算First集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=>*,addtothefirstset.计算Follow集Foreachnonterminalinthegrammar,dothefollowing:1.Place#inFollow(S)whereSisthestartsymboland#istheinput'srightendmarker.Theendmarkermightbeendoffile,itmightbenewline,itmightbeaspecialsymbol,whateveristheexpectedendofinputindicationforthisgrammar.Wewilltypicallyuse#astheendmar...