编译原理与实践（中英双语版）课件 Chapter 5 Bottom-Up Parsing

Chapter5

Bottom-UpParsing

Shift-reduceparsingattemptstoconstructaparsetreeforaninputstringbeginningattheleaveswhichcanbeconsideredasbottomandworkinguptowardstheroot,knowastop.Wecanthinkofthisprocessasoneofreducingwhichreduceastringtothestartsymbol.Ateachreductionstep,aparticularsubstringmatchestherightsideofproductionandisreplacedbythesymbolontheleftoftheproduction.Aneasy-to-implementformofshift-reduceparsingisoperator-precedenceparsing.Amuchmoregeneralmethodofshift-reduceparsingisLR(0)andSLR(1)parsing.Thepositionofbottom-upsyntaxanalyzerincompilerisshownbyFig.5.1.235.1Operator-precedenceParsing

Ifagrammarhasthepropertythathastwoadjacentnonterminals,wecaneasilyconstructefficientshift-reduceparsersbyhand,theeasy-to-implementparsingtechniquecalledoperator-precedenceparsing.Thetechniqueisdescribedasamanipulationontokenswithoutanyreferencetoanygrammar.Oncewefinishbuildinganoperator-precedenceparserfromagrammar,wemayefficientlyignorethegrammar,usingthenonterminalsonthestackonlyasplaceholdersforattributesassociatedwiththenonterminals.45.1.1Relationbetweenpairsof

operatorprecedence

Therearethreerelationsbetweenpairsofoperatorprecedence,“a”and“b”belongstoVT,U,VandRbelongtoVN,thentheiroperatorprecedenceare51.ab,meanstherearerulesU∷=…ab…orU∷=…aVb…2.a

b,meanstherearerulesU∷=…aR…，R+b…orR+Vb3.ab,meanstherearerulesU∷=…Rb…，R+…aorR+…aV

Note:Theprecedencerelationsbetweenaandbaredifferentwitharithmeticrelations“lessthan”,“equalto”and“greaterthan”,thatis,a

bdoesnotequaltoba，abdoesnotequaltoba

.＞

·

＜.＞·

＜···6Example5.1

grammarG〔E〕：

E∷=E+T|TT∷=T*F|FF∷=(E)|iFromruleF∷=（E），wecanobtaintheprecedencerelationbetween“(“and“)”（）FromruleE∷=E+T，weknowafter“+”thereisTT*…，sotheprecedencerelationbetween“+”and“*”：

+*FromruleF∷=（E），andE+…+T，wecanobtaintheprecedencerelationbetween“+”and“)”：+）·.＞·

＜75.1.2ConstructingOperator-

precedenceRelation

Thissection,wewillgiveageneralmethodofconstructingoperatorprecedence,firstly,wewilldefinetwonewsets:FIRSTTERM(U)andLASTTERM(U).b∈FIRSTTERM(U)whenthereisrule:U∷=+b…orU∷=+Vb…b∈LASTTERM(U)whenthereisrule:U∷=+…borU∷=+…bVwhileb∈VT,V∈VN。8ThealgorithmofconstructingoperatorprecedenceisStep1constructingsetofFIRSTTERMandsetofLASTTERMforeachnonterminal.a,b∈VTandU,R∈VN。Step2IfthereisgrammarGlikeU∷=…ab…orU∷=…aVb…abIfthereisgrammarGlikeU∷=…aR…,and,b∈FIRSTTERM(R)abIfthereisgrammarGlikeU∷=…Rb…,and,a∈LASTTERM(R)ab··

＜.＞9Step3

constructingoperatorprecedencefromstring“#”andotherterminals,thereare#FIRSTTERM(U)LASTTERM(U###Accordingtothealgorithm,weconstructtheoperatorprecedenceofexample5.1·.＞·

＜1011So,theoperatorprecedencematrixofexample5.1isshownbytable5.1125.1.3Operator-precedenceGrammar

Operator-precedenceparsinghasthreedisadvantages,Itishardtohandletokensliketheminussign,whichhastwodifferentprecedence.Onecannotalwaysbesuretheparseracceptsexactlythedesiredlanguage.Onlyasmallclassofgrammarscanbeparsedusingoperator-precedencetechniques.Inanoperatorgrammar,noproductionrulecanhave.13

attherightsidetwoadjacentnon-terminalsattherightside.E∷=AB E∷=EOE E∷=E+E|A∷=a E∷=id E*E|B∷=b O∷=+|*|/ E/E|inotoperatorgrammarnotoperatorgrammar operatorgrammar14OperatorgrammaralsocanbecalledOG.Therearethreetypesdisjointprecedencerelationbetweenpairofterminals,thethreetypesdisjointprecedenceare,and,Butifapairofterminalsonlyhasonecertaintypeprecedencerelation,thiskindofOGisoperatorprecedencegrammar,namely,OPG.

Forexample,grammarE∷=E+E|E*E|E/E|iisnotoperator-precedencegrammar.BecausefromFig5.2,weknowtherearetwogrammartreefor(+，/),inadditiontherearetwoprecedencerelationsbetweenthem,namely,+/and+/·

＜.＞15Fig.5.2TwosyntaxtreeofstringE+E/E图5.2句型E+E/E的两棵语法树165.1.4LeftmostPhrase

Thesyntaxtreeforsentence#T+T*F+i#ingrammarG[E]ofexample5.1isshownbyFig.5.3.EE+TET+FTT*Fi

Fig.5.3syntaxtreeof#T+T*F+i#图5.3句型语法树17

WecanseethatthereareseveralphrasesfromFig.5.3T（FornonterminalE）

T*F（FornonterminalT）

T+T*F（FornonterminalE）

i（FornonterminaF）

T+T*F+i（FornonterminalE）18ThesimplephrasesareT，T*Fandi,thehandleisT,T*Fistheleftmostphrase.Sothedefinitionofleftmostphraseis:itisaphrasethatincludesatleastoneterminal,inaddition,itdoesnotincludeanyotherphrase.Forexample,thereissentence#F*i+i#,itssyntaxtreeisshownbyFig.5.4.Ithastwophrasesiandi,butF*iisnotphrase,becauseitincludestheotherphrasei.1920Next,wewillgiveageneralmethodtoobtaintheleftmostphraseofoperatorprecedence.thesentenceofaoperatorgrammar#V1a1V2a2…Viai…Vn

andVn+1#WhileViisnonterminal,aiisterminal，thatmeansthereisonlyonenonterminalbetweentwoadjacentterminals.Leftmostphrasehasthepropertyaiai+1，ai+1ai+2，aj-1aj，ajaj+1

··.＞·

＜21theleftmostphraseisVi+1ai+1…VjajVj+1Forexample,thesentenceofG[E]is#T+T*F+i#,therearethreenonterminals（V1=T，V2=T，V3=F）,andfourterminals（a1=+，a2=*，a3=+，a4=i）,whilea1，a2，a3havethepropertie,a1a2，a2a3So,T*F（namely,V2a2V3）istheleftmostphraseofthesentence#T+T*F+i#.·

＜.＞225.1.5TheAlgorithmandProgramof

OperatorPrecedenceParsing

Thissection,wewillintroduceabottom-upparsingalgorithm—operatorprecedenceparsingalgorithm.Inthealgorithm,everyplaceholderisleftmostphrase,namely,everyreductionistofindtheleftmostphrase.Step1.Constructoperatorprecedencerelationmatrix.Step2.Createasymbolstacktostorethereductionstringorleftmoststring,buildotherinputstacktostoreinputstring.Atbeginning,thereisonlyonesymbol“#”insymbolstack,andthereisthefirstterminalininputstack.23Step3.Fromthetopterminalxnmovetobottomofsymbolstack,andatthesametimecomparewithitsclosest..terminal,ifxn-1xngooncomparingxn-2andxn-1tillxi-1xi,nowwecanobtaintheleftmostphrase:NixiNi+1xi+1…NnxnNn+1（IfNiisempty，xiisthebeginningsymbol）.＞24Step4.IngrammarG,wechoosetherightofruleisNixiNi+1xi+1…NnxnNn+1toreduce(nonterminalneednotbesame),thatis,popleftmostphraseatthetopofsymbolstack,andpushitsleftoftheruleintothestack.Whenthereareonly#oronenonterminaland#insymbolstack,thereis#ininputstack,thatmeanstheanalysissucceed,theinputstringisthesentenceofthegrammar,exitfromtheprogram;ornot,returnto3.25Theprogramofoperatorprecedenceparsingisasfollows.setptopointtothefirstsymbolofw$;

repeatforever

if($isontopofthestackandppointsto$)thenreturn

else{ letabethetopmostterminalsymbolonthestackandletbbethesymbolpointedtobyp;

if(aborab)then{ /*SHIFT*/ pushbontothestack; advanceptothenextinputsymbol;}

elseif(ab)then

/*REDUCE*/

repeatpopstack

until(thetopofstackterminalisrelatedbytotheterminalmostrecentlypopped);

elseerror();}26Soforexample5.1grammarG〔E〕：

E∷=E+T|TT∷=T*F|FF∷=(E)|iStringi*（i+i）isrecognizedbyoperatorprecedencealgorithm,theanalysisprocessisshownbyTable5.22728Example5.2

ConsiderthefollowinggrammarS∷=(L)|aL∷=L,S|S

andthefollowingoperator-precedencerelations29Usingtheseprecedencerelationstoparsethesentence(a,(a,a)).305.2LR（0）Parser

Wehaveknownthattherearesomelimitationsingrammarwhenwereducebymethodofoperatorprecedence,forexample,theruleofU∷=εshouldnotbeappeared,andtherearetwoadjacentnonterminalsinoperatorprecedencegrammar.ForLR(0)parser,therearenosuchlimits,soitisefficientbottom-upsyntaxanalysistechniquethatcanbeusedtoparsealargeclassofcontext-freegrammars.“L”inLRparsingmeansleft-to-rightscanningoftheinput,the“R”initisforconstructingarightmostderivationinreverse,the“0”meansneednottocheckuplookaheadfortheinputsymbolsthatareusedinmakingparsingdecisions.315.2.1ViablePrefix

Inordertoexplainhowtoderivationfrombottomtoup,wewillfirstlydiscusstheconceptofcanonicalprefixbyanexample.ThereisgrammarG〔S〕：

S∷=aABeA∷=Abc|bB∷=dWelabelfourrulesinG[S]bynumbers,theyareS∷=aABe〔1〕

A∷=Abc

〔2〕

A∷=b〔3〕

B∷=d〔4〕32Sotherightsententialdeductionof“abbcde”isS

aABe

aAde

aAbcde

abbcde

〔1〕〔4〕〔2〕〔3〕

Thereductionoftheinputstring“abbcde”isshownbelow.So,theprefixofeveryderivation,wecallitviableprefix.

335.2.2ConstructingFAbyViablePrefixItisremarkablefactthatifitispossibletorecognizeaviableprefixknowingonlythegrammarsymbolonthestack,thereisfiniteautomationthatcandeterminewhatthehandleis..

Inaddition,wecandefinethatitemofgrammaristhestateoffiniteautomation.34Itemofgrammarisaproductionofgrammarwithadotatsomepositionoftherightside.Forexample,productionA∷=XYZyieldsthefouritemsA∷=·XYZA∷=X·YZA∷=XY·ZA∷=XYZ·35ThefirstitemaboveindicatesthatwehopetoseeastringderivablefromXYZnextontheinput.TheseconditemindicatesthatwehavejustseenontheinputastringderivablefromX,andwehopenextsteptoseeastringderivablefromYZ.TheproductionU∷=εgeneratesonlyoneitem,U∷=·.Afterdefiningtheitem,weknowthestatesinfiniteautomation,thenwecandesignfiniteautomation.Forexample,thereisaruleofgrammar:X::=aAc,ithasthreeitems,(h)X::=•aAc(i)X::=a•Ac(k)A::=•d36h,i,kareitems(states)offiniteautomation.Thedotinstateiisinnextpositionofstateh,sowecandrawanarcfromstatehtostatei,thearcislabeledbya.Inaddition,Aisnonterminal,andthereisitemkthatitsleftsideisA,wecandrawanarcfromitokandlabelthearcbyε..

37Example5.3GrammarG[S]：

S∷=E〔1〕

E∷=aA

〔2〕

E∷=bB

〔3〕

A∷=cA

〔4〕

A∷=d〔5〕

B∷=cB

〔6〕

B∷=d〔7〕38Fromtheitemdefinedabove,weknowthereare18items,anditsfiniteautomationisshownbyFig.5.51．S∷=·E2．S∷=E·3．E∷=·aA4．E∷=a·A5．E∷=aA·6．A∷=·cA7．A∷=c·A8．A∷=cA·9．A∷=·d10．A∷=d·11．E∷=·bB12．E∷=b·B13．E∷=bB·14．B∷=·cB15．B∷=c·B16．B∷=cB·17．B∷=·d18．B∷=d·3940Wedivideitemsintoseveraltypesaccordingtothedotpositioninitemandjudgebythesymbolafterthedotifitisnonterminalorterminal.(1)Shiftitem,theitemformlookslikeA::=α·aβ,meanspush“a”intostack,andstatechangesfrombeforedotstatetodotafterstate,whileα,β∈V*,a∈VT..(2)Waitingreductionitem,theitemformlookslikeA::=α·Bβ,itemafterdotiswaitingreduceitem,itmeansafterreduceBthatAcanbereduce,whileα,β∈V*,B∈VN..41(3)Reduceitem,theitemformisA::=α·,whileα∈V*，namely,itisreductionitemwhendotisontherightmost,itmeansthattherightsideofaproductionhasbeenanalyzed,thehandlehasbeenrecognized.(4)Acceptitem,theitemformlookslikeS∷=α·,whileα∈V+,Sisstartsymbol.Inexample5.3,state3andstate17isshiftitem,state4andstate15iswaitingreduceitem,state2andstate5isreduceitem,inaddition,state2isacceptitem.Theconnectionarcsonpathfromstartstatetooneofreducestateisviableprefixofthesentence,suchasbccBisviableprefix..42FromFig.5.4,weknowitisanonfiniteautomation.ThecentralideaintheLRmethodistoconstructadeterministicfiniteautomationfromthegrammar.So,weshouldgroupitemstogetherintosets,whichcanconstructdeterministicfiniteautomationfromit.Weuseclosureoperationtoconstructitemsets.435.2.3TheClosureofsetofitems

IfIisasetofitemsforagrammarG,thenclosure(I)isthesetofitemsconstructedfromIbythetworules:1Initially,everyiteminIisaddedtoclosure(I).2IfU∷=x·Vyisinclosure(I)andV∷=zisaproduction,thenaddtheitemV∷=·ztoI,ifitisnotalreadythere.Weapplythisruleuntilnomorenewitemscanbeaddedtoclosure(I).Forexample,thereisitemS∷=·E,anditisinclosureI0,thenE∷=aA|bB,sotheitemsE∷=·aAandE∷=·bBareinclosureI0too,thatis,I0={S∷=·E，E∷=·aA，E∷=·bB}44Intuitively,U∷=x·Vyinclosure(I)indicatesthat,atsomepointsintheparsing,wemightseeasubstringderivablefromVythatisasinput.IfV∷=zisaproduction,wealsoexpectwemightseeasubstringderivablefromz.Forthisreason,V∷=·zisincludedinclosure(I).AnusefulapplicationofclosureisfunctionGOTO(I,X),whileIisasetofitemsandXisasymbol.GOTO(I,X)isdefinedtobetheclosureofthesetofallitemsU∷=xX·yisinI.45Thealgorithmofclosure(I)is:Cis{closure({S’

.S})}repeatthefollowingsuntilnomoresetofLR(0)itemscanbeaddedtoC.foreachIinCandeachgrammarsymbolXifgoto(I,X)isnotemptyandnotinC

addgoto(I,X)toC46WithclosureandGOTOfunction,wecaneasilychangetheNFAtoDFA,Fig.5.6isanexampleofit.475.2.4LR(0)ParsingTable

LR(0)parserconsistsofaninputandoutputstack,adriverprogram,andaparsingtablethathastwoparts(ACTIONandGOTO).ThedrivingprogramissameforallLRparser,onlytheparsingtablechangesfromeachother.Inputstackstoresinputstringoftheforms0X1s1X2s2…Xmsm,whereeachXiisagrammarsymbol,andeachsiisasymbolcalledastate.Parsingtableincludestwoparts,aparsingactionfunctionACTIONandagotofunctionGOTO.ACTIONandGOTOfunctionscanrecognizeviableprefixfromallthedeterministicfiniteautomation..48TherearethreerowsinLR(0)parsingtable,thefirstonerepresentsthestates(Ii);thesecondoneisACTION,meanswhatACTIONshoulddonext;thethirdoneisGOTO,meanstojudgewhichstatewillbechosennext.WeshallexplainGOTOandACTIONasfollow.x,y∈V,a∈VT.ConstructC={I0，I1，…In},thecollectionofsetsofLR(0)itemsforgrammar.(1)IfU∷=x·ayisinIi,andGOTO（Ii，a）=Ij,thensetACTION[i，a]=“Sj”,Here“a”mustbeaterminal.(2)IfU∷=x·isinIi,thensetACTION[i，a]=“rj”orACTION[i，#]=“rj”,meansusingrulej:U∷=xtoreduce,because“#”and“a”representsanysymbol;.49(3)IfZ∷=x·isinIi,Zisstartsymbolofgrammar.thensetACTION[i，#]=“acc”，“acc”meansaccept.(4)TheGOTOtransitionsforstateiareconstructedforallnonterminalsU,ifGOTO(Ii，U)=Ij,thenGOTO[i,U]=“j”.(5)Allentriesisnotdefinedbyaboverulesaremade“error”.Note:

ifanyconflictingactionisgeneratedbytheaboverules,wesaythegrammarisnotLR(0),thealgorithmfailstoproduceaparserinthiscase.50Weknowhowtoconstructtheitemsfromgrammarandhowtoobtaintheclosureofitems,thenwhatwedonextistouseexample5.3toexplainhowtoconstructLR(0)parsingtablebythemethodabove.First,welookfortheitemwhichformisU∷=x·ayfromI0toI11,inexample5.3,therearerulesE∷=•aA,E∷=•bB,GOTO（I0，a）=I2,GOTO（I0，b）=I3,sothereareACTION﹝0，a﹞=“S2”,ACTION﹝0，b﹞=“S3”,thatiswhythereareS2andS3inthefirstandsecondrowinTable5.5,withthesimilarreason,thereareS5,S6,S8,S9indifferentrows.51Second,wejudgeifthereisitemformofU∷=x·,inexample5.3,formofitemI4isE∷=aA•,sothenumber2ruleofE∷=aAcanbeusedtoreduceandthereisr2inI4,similarly,I6I7I9I10I11haver5,r3,r7,r4andr6separately.Third,wecheckifthereareitemswhichformisZ∷=x·,inexample5.3,itemI1istheformofS∷=E•,soACTION﹝1，#﹞=“acc”,thereisaccinI1inTable5.5.Finally,welookfortheitemthatformisGOTO（Ii，U）=IjandU∈VN,inexample5.3,thereisGOTO（I0，E）=I1,sothereis1inrowEofI0.Similarly,withI2,I3,I4andI8,theyhave4,7,10and11inrowAandBdifferently.So,weobtaintheparsingtableofexample5.3anditisshownbyTable5.5.5253Withparsingtable,weareeasytoparsegrammar,butiftheparserrunsautomatically,thelimitationisthatwemusthaveadriverprogramtocontroltheinputandoutputstack,andtheirinformationtransformationwithparsingtable.Namely,everystepofdriverprogramwillcheckupthepresentstateofstack,inputsymbolandLR（0）parsingtable,runtheoperationofACTION﹝q，a﹞andGOTO.Wecanusethefollowingconfigurationtorepresenttheirrelation,itincludesthreeparts:statestack“q”,symbolstack“X”andinputstring“a”.

（q0q1…qi，#X1X2…Xi，akak+1…an#）54Thetopstateofstatestackisqi,topsymbolofsymbolstackisXi,thecurrentinputsymbolisak.WhatwewilldonextistocheckLR（0）parsingtableandruntheoperationbyACTION[qi，ak],thedetailisasfollows.Theinitialconfiguration

（q0，#，a1a2…an#）(1).IfACTION﹝qi，ak﹞=Sj，meanstheinputsymbolakwouldbepushedintosymbolstackX,thestatewillshiftfromstateqitoitsnextstateqj，theconfigurationbecomes

（q0q1…qiqj，#X1X2…Xiak，ak+1…an#）Thecurrentstatebecomesstateqj,currentinputsymbolisak+1.55(2).IfACTION﹝qi，ak﹞=rj，akisterminalor#,theparserexecutesareducemove,thetopofsymbolstackwillreducebyrulej,thelengthofsymbolstackandstatestackshoulddecreaselengthm,heremislengthofrightsideofrj.Forexample,rulejisU∷=x,thelengthofxism,inaddition,thereisGOTO﹝qi-m，U﹞=qt,sotheconfigurationbecomes

（q0q1…qi-mqt，#X1X2…Xi-mU，akak+1…an#）WhileakisnotinsymbolstackX,thecurrentinputsymbolstillisak,thecurrentstateisqt,itcomesfromGOTO﹝qi-m，U﹞=qt.563IfACTION﹝qi，ak﹞=acc,parsingiscompleted.4IfACTION（qi，ak）=ERROR,theparserhasdiscoveredanerror,driverprogramofparserwillstop.Weusethedriverprogramtojudgeifstring“acccd”canberecognizedbythegrammarofexample5.3,therecognitionsucceedsandtheresultisshownbytable5.6.57585.3SLR(1)Parser

Weoftenmeetaugmentedexpressiongrammarwhenweparse,suchasthegrammarG[U].G[U]:U∷=x·by

〔1〕

V∷=x·〔2〕

W∷=x·〔3〕

ThethreerulesbelongtooneitemI0={U∷=x·by，V∷=x·，W∷=x·}59Whenweparsethegrammar,therearetworulesV∷=x·andW∷=x·thattheybothcanbeusedtoreduce,namely,r2andr3.Inthiscase,wecannotparsethegrammarbyLR(0),becauseLR(0)parsetablecannotrecognizetworeducerulesinoneitemform.Whatweshoulddointhiscase?SLR(1)parsercansolvethisproblem.SLR(1)parserwillchecktheinputsymbol“a”tojudge（1）Ifa=b，thenACTION[0,a]=“S1”（2）Ifa∈FOLLOW（V），thenACTION[[1，a]=“r2”（3）Ifa∈FOLLOW（W），thenACTION[[1，a]=“r3”（4）Otherwise,ACTION[0,a]=“ERROR”60Note:FOLLOW（V），FOLLOW（W）and{b}shouldnotbeintersectedandhavenotsameelement.AnSLR(1)grammarcanbedefinedasfollows.I={U1∷=x·b1y1，U2∷=x·b2y2，…，Um∷=x·bmym，V1∷=x·，V2∷=x·，…，Vn∷=x·}Set{b1，b2，…，bm},FOLLOW（V1）,FOLLOW（V2）,…,andFOLLOW（Vn）shouldnotbeintersected.SLRmeanssimpleLR,itistheweakestgrammarandistheeasiesttobeimplement.ParsingtableconstructedbythismethodiscalledSLRtable,inaddition,LRparserusinganSLRparsingtableissaidtobeSLRparser.AgrammarforwhichanSLRparsercanbeconstructedisSLRgrammar.SLR(1)parserworkslikethatitscanstheinputstringfromleft-to-right,constructsarightmostderivationinreverse,checksup1inputsymbollookahead.61ThedifferentbetweenconstructingSLR(1)parsertableandLR(0)parsertableisatthesecondstep,thechangedstep2is:IfU∷=x·isinIi,andifa∈FOLLOW（U）,thensetACTION[i，a]=“rj”orACTION[i，#]=“rj”,meansusingrulej:U∷=xtoreduce,because“#”and“a”(representsanysymbol)areinFollow(U);WestillusethegrammarG[S]ofexample5.1toexplainhowtoconstructtheSLR(1)parser.G[S]：

S∷=E〔1〕

E∷=E+T〔2〕

E∷=E〔3〕

T∷=T*F〔4〕

T∷=F〔5〕

F∷=（E）〔6〕

F∷=i〔7〕62BeginningFromthefirstruleS∷=E，WeobtaintheitemI0：I0={S∷=·E，E∷=·E+T，E∷=·T，T∷=·T*F，T∷=·F，F∷=·（E），F∷=·i}