编译原理与实践（中英双语版）课件 Chapter 8 Intermediate Code

Chapter8

IntermediateCode

Intermediatecodegenerationisinthemediatepartofcompiler,itisabridgewhichtranslatesourceprogramintointermediaterepresentationandthentranslateintotargetcode.ThepositionofintermediatecodegenerationincompilerisshowninFigure8.1..

23Therearetwoadvantagesofusingintermediatecode,Thefirstoneisthatwecanattachdifferenttargetcodemachinestosamefrontpartafterthepartofintermediatecodegeneration;;Thesecondoneisthatamachine-independentcodeoptimizercanbeappliedtotheintermediatedrepresentation..

4Intermediatecodesaremachineindependentcodes,buttheyareclosetomachineinstructions.Thegivenprograminasourcelanguageisconvertedtoanequivalentprograminanintermediatelanguagebytheintermediatecodegenerator..

5Intermediatelanguagecanbemanydifferentlanguages,andthedesignerofthecompilerdecidesthisintermediatelanguage.Postfixnotation,four-addresscode(Quadraples),three-addresscode,portablecodeandassemblycodecanbeusedasanintermediatelanguage.Inthischapter,wewillintroducethemindetail.68.1PostfixNotation

Ifwecanrepresentthesourceprogrambypostfixnotation,itwillbeeasytobetranslatedintotargetcode,becausethetargetinstructionorderissamewiththeoperatororderinpostfixnotation..

78.1.1Thedefinitionofpostfixnotation

thepostfixnotationfortheexpressiona+b*cisabc*+.theexpressionareasfollows:

1Theorderofoperandsforexpressioninpostfixnotationissamewithitsoriginalorder.2Operatorfollowsitsoperand,andtherearenoparenthesesinpostfixnotation.3Theoperatorappearsintheorderbythecalculationorder.8Forexample,thepostfixnotationforexpressiona*(b+c/d)isabcd/+*,thetranslationprocedureisjustfollowingthestepsabove..firstly,accordingtostep1wegettheorderofoperandsoftheexpression:abcd,secondly,bythestep2,thefirstoperatorinoperatororderis/,becauseitjustfollowsitsoperandscd,inaddition,asthestep3,operator/iscalculatedfirst,sotheoperatorfollowoperandsis/.Thesecondoperatorinoperatororderis+,itduestothatthereisparenthesesintheoriginalexpression,operator+shouldbecalculatedearlierthanoperator*.Thelastoneis*,because*iscalculatedlastly..

9Theotherexample,thepostfixnotationforexpressiona*b+(c-d)/eisab*cd-e/+.Fromexamples,weknowitisabitdifficulttotranslateanexpressionintoitspostfixnotation.SoscientistE.W.DIJKSTRAfromHolandcreatedamethodtosolvetheproblem..

108.1.2E.W.DIJKSTRAMethod

TherearetwostacksinE.W.DIJKSTRAmethod,onestackstoragesoperands,theotheroneisforoperators,theprocedureofitisshownbyFigure8.2,andthestepofE.W.DIJKSTRAmethodisasfollows:.

11

12Actually,scanningtheexpressionisfromlefttoright.Atthebeginningofscanning,wepushidentifier#tothebottomofoperatorstack,similarly,weaddidentifier#totheendofexpressiontolabelthatitisterminalofexpression.Whenthetwoidentifier#meet,itmeanstheendofscanning.Thestepsofscanningare:

1Ifitisoperand,gototheoperandstack

:

132Ifitisoperator,itshouldbecomparedwiththeoperatoronthetopofoperatorstack.Whenthepriorityofoperatoronthetopstackisbiggerthanthescanningoperator,orequaltoit,theoperatoronthetopofoperatorstackwouldbepoppedandgototheleftside.Ontheotherhandwhenthepriorityofoperatoronthetopstackislessthanthescanningoperator,scanningoperatorshouldbepushedintooperatorstack.143Ifitisleftparenthesis,justpushitintooperatorstack,andthencomparetheoperatorswithinparentheses..Ifitisrightparenthesis,popalltheoperatorswithinparentheses,whatismore,parentheseswouldbedisappearedandwouldnotberepresentedaspostfixnotation..4

Returntostep1tilltwoidentifier#meet.

15Example8.1

Thereisanexpressionofa+b*c,itspostfixnotationisabc*+.FromthetranslatingprocedureshownbyFigure8.3,wecanseethatoperatororderis*+,itisalsothepoporderoftheoperatorstackandcalculatingorder.

1617188.1.3Extendedpostfixnotation

IftheexpressionEisintheformofE1:=E2,thenthepostfixnotationforEis:=,whereandarethepostfixnotationforE1andE2,respectively.Example8.2

Thereisanexpressiona:=b,accordingtothedefinitionabove,itspostfixnotationisab:=.19Example8.3Forexpressiona：=5*(b+8),thepostfixnotationofitis:a5b8+*:=IfThereisaprogramwhichformis：

IFuTHENS1

ELSE……BEGINS2……END20uinthisprogramisaconditionwhichhastworesults,oneistrue,theotheroneisfalse,S1,S2aretwopartsofprogram,l1isthestartnumberofS2,l2istheendnumberofS2..Thepostfixnotationoftheprogramisasfollows:BZmeansifthevalueuisnottrue,thenturntol1,BRmeansjustgotol2.Nowwewillgiveanexampletoexplainthetranslation..

21Example8.4

S:=0;IFi<10THENS：=S+i

ELSE BEGINi:=i+1END；

Thepostfixnotationofexample8.4isasfollows,thevalueofinthisprogramis7,thevalueofis9.S0：=i10<7BZSSi+:=9BR(7)ii1+:=(9)228.2Four-AddressCode

Theotherrepresentationofintermediatecodeisfour-addresscode,anditsdefinitionis:op,y,z,xApplyoperatoroptoyandz,andstoretheresultinx.wherex,yandzarenames,constantsorcompiler-generatedtemporaries;opisanyoperator..

23Example8.5

Theexpression:a+(-b*c+d)*emightbetranslatedintothefollowingfour-addresscodesequence

（1）（-，b，，T1）（2）（*，T1，c，T2）（3）（+，T2，d，T3）（4）（*，T3，e，T4）（5）（+，a，T4，T5）Wecandividefour-addresscodeintodifferenttypesaccordingtotheiroperators.

24BinaryOperator:

op,y,z,resultWhereopisabinaryarithmeticorlogicaloperator.Thisbinaryoperatorisappliedtoyandz,andtheresultoftheoperationisstoredinresult.Forexample:a+b*c,itsfouraddresscodeis:

（*，b，c，T1）（+，a，T1，T2）25UnaryOperator:

op,y,,resultWhereopisaunaryarithmeticorlogicaloperator.Thisunaryoperatorisappliedtoy,andtheresultoftheoperationisstoredinresult.Forexample,expressionS:=0,itsfouraddresscodeis::

（：=，0，，S）26UnconditionalJumps:

op,L,Wewilljumptothethree-addresscodewiththelabelL,andtheexecutioncontinuesfromthatstatement.HereopisBR.Forexample::

（BR，9，，)27ConditionalJumps:

op,L,,xHereopisBZ,wewilljumptothethree-addresscodewiththelabelLiftheresultofxisnottrue,andtheexecutioncontinuesfromthatstatement.Iftheresultistrue,theexecutioncontinuesfromthestatementfollowingthisconditionaljumpstatement..

（BZ，7，，T1）28Thefouraddresscodeforexample8.4:（1）（：=，0，，S）（2）（—，i，10，T1）（3）（BZ，7，，T1）（4）（+，S，i，T2）（5）（：=，T2，，S）（6）（BR，9，，）（7）（+，i，l，T3）（8）（：=，T3，，i）Thestorageforfour-addresscodeissimilarwithpostfixnotation,namely,theyarealluseE.W.DIJKSTRAmethodtorealizetheoperation..

298.3Three-AddressCode

Thedifferencebetweenthree-addresscodeandfour-addresscodeisthedifferentmemorytheyoccupy.Whenweproducetargetcode,allthedatawillbeassignedrun-timememory.Thememorylocationwillbeplacedinthesymbol-tableforthedata.Comparedwiththree-addresscode,symboltableforfour-addresscodeinterposeanextrafieldtostoretheresultpartinfour-addresscode.Whenweusethecalculationresult,weshouldonlylookforthefourthpartinfour-addresscode,however,inthree-addresscode,weshoulddefineatemporaryvaluewhichreferencestotheresultpart.Thisproblemmakesthree-addresscodemoredifficulttobedesignedinanoptimizingcompiler..308.5PortableCode

Portablecodeisakindofintermediatecode,itcanbewrittenbymanyprogramlanguages.Thissection,wewillexplainportablecodewrittenbyPASCALsubprogram..

Portablecodeincludestwosections,oneisPROCEDUREBLOCKwhichformsintermediatecode,theotheroneisPROCEDUREGENwhichgeneratesintermediatecode,andthenstoresittoCODEbyPROCEDUREINTERPRET

31WewillintroducethePROCEDUREGENindetail.ThereisaPASCALsourceprogramwhichisshownbelow..

PROGRAMmain；PROCEDURE1；PROCEDURE2；BEGINREAD（i）；WHILEi>1DOBEGINIFi>10THENCALL1ELSE BEGINCALL2END；END；END32Theportablecodeofthesourceprogramisasfollows.33Fromaboveportablecode,thestructureofportablecodeincludesthreeparts,thefirstoneisoperand,suchasINT,

STO,OPR,LOD,JPCandCAL,thesecond

partisthelevelvalue,actuallyitis0,thethird

partisvalue,suchasrelativeaddress,thenumberofunits,procedureenteraddress,valueofconstantorsomespecialoperators..34INTmeansdataspaceinstack.Arepresentsunitnumberinstackforprocedures,forexample,5inline11.CALmeansthatitcallsprocedure.Ainitistheaddressofprocedure.LITispushingconstantintothetopofstack.Ainitisthevalueofconstant.LODispushingvariableintothetopofstack.Ainitistherelativeaddressofvariable.35STOmeanstopopthetopofstacktounit.Ainitistherelativeaddressofit.JMPmeanstogotoanaddressdirectly.JPCistomovetheaddresswhilethevalueonthetopofstackisfalse,otherwiseitmovesforward.OPRisoperator.WhenA=2,itrepresentst