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

Chapter9

CodeGeneration

Thephaseafterintermediaterepresentationincompileriscodegeneration.Theinputforcodegenerationistheintermediaterepresentationandtheoutputofitisequivalenttargetprogram,thepositionofcodegenerationincompilerisshownbyFigure9.1..2Asweknowthatthereareseveralchoicesfortheintermediatelanguage,

including:

postfixnotation,four-address

code,three-addresscodeandsyntaxtrees.

.

Inthischapterweassumethatthesourceprogramhasbeentranslatedintoareasonablyintermediaterepresentation,andthevalueofidentifierappearinginintermediaterepresentationcanbedirectlymanipulated..3Wealsoassumethatthenecessarytypecheckinghasbeentakenplaceandsemanticerrorshavealreadybeendetected.Targetprogramofcodegenerationconsistsofabsolutemachinelanguage,relocatablemachinelanguage,orassemblylanguage.Here,weuseassemblylanguageasthetargetlanguageforreadability..4

SourceprogramSymboltableLexical,syntax，semanticanalyzerandIntermediaterepresentationCodeGenerationFig.9.1Positionofcodegenerationincompiler图9.1代码生成阶段在编译器中的位置CodeoptimizationTargetcode59.1Structureoftargetprogram

Thereare

three

typesoftargetlanguagethatareabsolutemachine-language,relocatedmachine-languageandassemblylanguage.

.Usingabsolutemachine-languageastargetprogramhastheadvantagethatitcanbeplacedinafixedlocationinmemoryandimmediatelyexecuted，portablecodeisakindofabsolutecode..6Arelocatedmachine-languageprogramastargetprogramcangainagreatdealofflexibilityforsubprogramtobecompiledseparately,becauseasetofrelocatableobjectmodulescanbelinkedtogetherandbeloadedforexecutionbyalinkingloader.Assemblylanguageasoutputiseasiertomakecodegenerationprocessduetoitdoesn’tduplicatetheentiretaskofassembler.Inthischapter,weuseportablecodewrittenbyPASCALsubprogramtoexplainhowtoproduceabsolutecodewhichcomesfromtheoffsetofintermediatecode..

79.1.1Structureof“If”sentenceinprogram

Theformof“IF”sentenceinprogramisasfollows:IFi>10THEN…24ELSE BEGIN…25END；

820 LOD 0 321 LIT 0 1022 OPR 0 1223JPC025……2425Thetargetcodeofitis:9meansthatiftheresultofexpressioni>10isfalse,itwillgototheelsepartofinstruction25,ifnotitwillrunthethenpartofinstruction24.

Thealgorithmofgeneratingtargetcodeisshownbelow.10IFSYM=IFSYM/*checkupifthereisword“IF”*/THENBEGIN GETSYM； CONDITION(…) /*Targetcodeofconditionexpression*/

IFSYM=THENSYM /*checkupifthereisword“THEN”*/THENGETSYM ELSEERROR（18）；

BEGIN IFSYM=ELSESYM /*checkupifthereisword“ELSE”*/THEN BEGIN

119.1.2Structureof“While”sentenceinprogram

Theformof“while”sentenceinprogramisasfollows.WHILEc>1DOBEGIN….END12Itscorrespondtargetcodeis16 LOD 0 317 LIT 0 118 OPR 0 1219JPC02820….. 27JMP016281316istheinstructionlinenumberofwhile,whenitreachesline27,itwillreturntoline16asaloop..

28meansthatifthevalueoflogicexpressioni>1isfalse,thengotoline28.Weknowwhenprogramisrunningatline19thatwecannotlookaheadtoline28,sowehavetowaituntilreachingline28,thensaveandadd28toit.Thealgorithmofgeneratingtargetcodeisshownbelow..14IFSYM=WHILESYM /*Judgeifitis“while”sentence*/THEN BEGIN L1:=CX；/*L1storethelinenumberof“while”sentenceCX*/GETSYM； CONDITION(…) /*Targetcodeofconditionexpression*/L2：=CX； /*L2recordstheescapelinenumberof“while”,nowwaitsforbeingadded*/GEN(JPC,0,0);/*generatetheloopexitinstructionthatL2isemptynow*/IFSYM=DOSYM /*checkupifthereisword“DO”*/THENGETSYM ELSEERROR（18）；GEN(JMP,0,L1);/*generatejumpinstructionwithoutlimitationandreturntolineL1*/CODE[L2].A:=CX/*recordtheloopescapelinenumberandaddittoL2*/END; 159.1.3Structureof“PROCEDURE”sentenceinprogram

Weknowtheformofprocedureinprogramincludestwoparts,thefirstpartistheprocedure,thesecondoneisthecallinginstruction.Theformofprocedureprogramisshownbelow.PROGRAMmain；

PROCEDURE1；

PROCEDURE2；

CALL1CALL2END16TheformoftargetcodeprocedurecanbewrittenasLine7andline9aretheinstructionlineofprocedure1andprocedure2.Line24and25arethecallinginstructions..

7 …… 9 ……

24 CAL07 25CAL0917Thealgorithmofgeneratingthetargetcodeisshownbelow.BEGIN DX：=3； /*therelativeinputaddressofmainprograminstack*/TX：=0； /*theinputaddressofmainprograminsymboltable*/TABLE[0].ADR：=0；/*thefirstinstructionaddressinsymboltableofmain

program*/BLOCK（0，2，…）； /*enteringPROCEDURE1*/DX:=3;/*therelativeinputaddressofprocedure1instack*/TX:=2;/*theinputaddressofprocedure1insymboltable*/TABLE[2].ADR：=0；/*thelevelofprocedure1isrecordedinsymboltable,andwillbereplacedbythestartaddressofprocedure1later*/GEN(JMP,0,0);/*generatetheinstructionshifttoprocedure1,theaddresswillbeaddedlater*/CODE[TABLE[2].ADR:=7/*recordthestartaddressofprocedure1,andaddittoGEN(JMP,0,0);*/

18TABLE[2].SIZE:=3/*Thespaceneedbyprocedure1*/GEN(INT,0,3)/*Thestackspaceneedbyprocedure1*/BLOCK（0，4，…）； /*enteringPROCEDURE2*/DX：=3； /*therelativeinputaddressofprocedure2instack*/TX：=4； /*theinputaddressofprocedure2insymboltable*/TABLE[4].ADR：=0；/*thelevelofprocedure2isrecordedinsymboltable,andwillbereplacedbythestartaddressofprocedure2later*/GEN(JMP,0,0);/*generatetheinstructionshifttoprocedure2,theaddresswillbeaddedlater*/CODE[TABLE[4].ADR:=9/*recordthestartaddressofprocedure1,andaddittoGEN(JMP,0,0);*/TABLE[4].SIZE:=3/*Thespaceneedbyprocedure1*/GEN(INT,0,3)/*Thestackspaceneedbyprocedure1*/19IFSYM=CALLSYMTHEN/*generatethetargetcodeofprocedure1*/BEGINWITHTABLE[2]DOIFKIND=PROCEDURETHENGEN(CAL,0,7)/*generatethecallcodeforprocedure1*/GEN(OPR,0,0)/*generatethereturncode*/IFSYM=CALLSYMTHEN/*generatethetargetcodeofprocedure1*/BEGINWITHTABLE[4]DOIFKIND=PROCEDURETHENGEN(CAL,0,9)/*generatethecallcodeforprocedure2*/GEN(OPR,0,0)/*generatethereturncode*/209.2Anexample9.2.1Thealgorithmofgeneratingthetargetcode

BEGIN DX：=3； /*therelativeinputaddressofmainprograminstack*/TX：=0； /*theinputaddressofmainprograminsymboltable*/TABLE[0].ADR：=0； /*thefirstinstructionaddressinsymboltableofmainprogram*/GEN(JMP,0,0);/*generatethejumpinstruction*/BLOCK（0，2，…）； /*enteringPROCEDURE1*/DX:=3;/*therelativeinputaddressofprocedure1instack*/TX:=2;/*theinputaddressofprocedure1insymboltable*/TABLE[2].ADR：=0；/*thelevelofprocedure1isrecordedinsymboltable,andwillbereplacedbythestartaddressofprocedure1later*/GEN(JMP,0,0);/*generatetheinstructionshifttoprocedure1,theaddressaddedlater*/IFSYM=VARSYMTHEN/*recordidentifyinsymboltable*/…21CODE[TABLE[2].ADR:=7/*recordthestartaddressofprocedure1,andaddittoGEN(JMP,0,0);*/TABLE[2].SIZE:=3/*Thespaceneedbyprocedure1*/GEN(INT,0,3)/*Thestackspaceneedbyprocedure1*/BLOCK（0，4，…）； /*enteringPROCEDURE2*/DX：=3； /*therelativeinputaddressofprocedure2instack*/TX：=4； /*theinputaddressofprocedure2insymboltable*/TABLE[4].ADR：=0；/*thelevelofprocedure2isrecordedinsymboltable,andwillbereplacedbythestartaddressofprocedure1later*/

GEN(JMP,0,0);/*generatetheinstructionshifttoprocedure1,theaddressaddedlater*/IFSYM=CONSTSYMTHEN/*recordconstantinsymboltable*/…22CODE[TABLE[4].ADR:=9/*recordthestartaddressofprocedure1,andaddittoGEN(JMP,0,0);*/TABLE[4].SIZE:=3/*Thespaceneedbyprocedure1*/GEN(INT,0,3)/*Thestackspaceneedbyprocedure1*/IFSYM=WHILESYM /*Judgeifitis“while”sentence*/THEN BEGIN L1：=CX； /*L1storethelinenumberof“while”sentenceCX*/ GETSYM；

CONDITION（…）； /*Targetcodeofexpression*/

L2：=CX； /*L2recordstheescapelinenumberof“while”,nowwaitsforbeingadded*/GEN（JPC，0，0）； /*generatetheloopexitinstructionthatL2isemptynow*/23IFSYM=DOSYM/*checkupifthereisword“DO”*/THENGETSYM ELSEERROR（18）；IFSYM=IFSYM/*checkupifthereisword“IF”*/THENBEGIN GETSYM； CONDITION(…)/*Targetcodeofconditionexpression*/IFSYM=THENSYM /*checkupifthereisword“THEN”*/THENGETSYM24 ELSEERROR（18）；BEGINIFSYM=CALLSYMTHEN/*generatethetargetcodeofprocedure1*/BEGINWITHTABLE[2]DOIFKIND=PROCEDURETHENGEN(CAL,0,7)/*generatethecallcodeforprocedure1*/GEN(OPR,0,0)/*generatethereturncode*/IFSYM=ELSESYM /*checkupifthereisword“ELSE”*/THEN BEGIN 25GETSYM；

IFSYM=CALLSYMTHEN/*generatethetargetcodeofprocedure1*/BEGINWITHTABLE[4]DOIFKIND=PROCEDURETHENGEN(CAL,0,9)/*generatethecallcodeforprocedu