編譯原理英文版課件：Chapter8 Code Generation

1、8. Code Generation Overview of Code GenerationGenerate executable code for a target machine that is a faithful representation of the semantics of the source codeDepends on the characteristics of the source language detailed information about the target architecturethe structure of the runtime enviro

2、nmentand the operating system running on the target machineCode generation is typically broken into several stepsIntermediate code generationGenerate some form of assembly code instead of actual executable codeOptimization: to improve the speed and reduce the size of the target codeOverview of Code

3、Generationlexical analysissyntax analysissemantic analysisintermediate code generationtarget code generationintermediate code optimizationtarget code optimizationAlthough a source program can be translated directly into the target language, some benefits of using a machine-independent intermediate c

4、ode are:Retargeting is facilitated: a compiler for a different machine can be created by attaching a back end for the new machineA machine-independent code optimizer can be applied to the intermediate codeOverview of Code GenerationOverview of Code GenerationWe will talk about general techniques of

5、code generation rather than present a detailed description for a particular target machineContents8.1 Intermediate Code and Data Structure for code GenerationMore8.2 Basic Code Generation TechniquesMore8.4 Code Generation of Control Statements and Logical ExpressionMore8.1 Intermediate Code and Data

6、 Structures for Code GenerationIntermediate CodeIntermediate Representation(or IR)A data structure that represents the source program during translationFor example: abstract syntax treeSuch an intermediate representation that resembles target code is called intermediate codeIntermediate CodeThe need

7、 for intermediate codeAbstract syntax tree does not resemble target codeparticularly in its representation of control flow constructsIntermediate code is the representation of the syntax tree in sequential form that more closely resembles target codeIntermediate CodeAdvantage of intermediate codeIt

8、is particularly useful when the goal of the compiler is to produce extremely efficient code;It can also be useful in making a compiler more easily retargetableTwo popular forms of intermediate code: Three -Address code P-code8.1.1 Three-Address CodeThe most basic instruction of three-address code de

9、signed to represent the evaluation of arithmetic expressions has the general form: x=y op zx,y,z are names, constants or compiler-generated temporary namesop stands for any arithmetic or logical operator, such as + ,and“Three-address code” comes from this form of instruction, in general each of x,y

10、and z represents an address in memoryExampleComputation of an expression is represented in three-address code2*a+(b-3) the correspondingthree-address code ist1 = 2*at2 = b-3t3 = t1+t2where t1,t2,t3 are names for temporaries, they correspond to the interior nodes of the syntax tree and represent thei

11、r computed values+*-2ab3Other instructions of three-address codeThree-address code for each construction of a standard programming languageAssignment statement has the form“x=y op z”, where op is a binary operationAssignment statement has the form “x=op y”, where op is a unary operationCopy statemen

12、t has the form “x=y” where the value of y is assigned to xOther instructions of three-address codeThe unconditional jump “goto L”Conditional jumps, such as “if B goto L” , “if_false B goto L” and “if A rop B goto L”Statement “Label L” represents the position of the jump address“read x” “write x”Stat

13、ement “halt” serves to mark the end of the codeExampleSample TINY programread x;If 0 x then fact:=1;repeat fact:=fact*x; x:=x-1;until x=0;write factendThree-address code for itread xt1=0 id==exp1.tacode=exp2.tacode+ id.strval| “=”| exp - = exp.taco

14、de=aexp.tacodeaexp1 - aexp2+ =newtemp()aexp1.tacode=aexp2.code +factor.tacode+ | ”=” ||”+”|aexp - = aexp.tacode=factor.tacodefactor - (exp)= factor.tacode=exp.tacodefactor - =num.strval factor.t

15、acode=“ ”factor - =id.strval factor.tacode=“ ”tacode attribute of expression (x=x+3)+4name=xname=xname=3name=t1;tacode=“t1=x+3”name=t1;tacode=“t1=x+3 x=t1”name=t1;tacode=“t1=x+3 x=t1”name=4name=t2;tacode=“t1=x+3 x=t1 t2=t1+4”expaexpfactor( exp )id = expaexp + factoraexp + factorfactorid

16、 (x)num (3)num (4)aexp(x)name=t1;tacode=“t1=x+3”Back8.4 Code Generation of Control Statements and Logical ExpressionsA program consists of declarations and statementsDeclarations do not generate intermediate codes, for each declared name, we create a symbol-table entryCode generation for assignment

17、and simple arithmetic expressions (8.2)Code generation for control statements and logical expressions (8.4)8.4.1 Code Generation for If and While StatementsForms of the if- and while-statements:if-stmt if ( e x p ) stmt | if ( exp ) stmt else stmtwhile-stmt while ( e x p ) stmtThe chief problem is t

18、o translate the structured control features into an “unstructured” equivalent involving jumpsCompilers arrange to generate code for such statements in a standard order that allows the efficient use of a subset of the possible jumps that target architecture might permit.The typical code arrangement f

19、or an if-statement is shown as follows: if-stmt-if (exp) stmt | if (exp) stmt else stmtThe typical code arrangement for a while-statementwhile-stmt- while (exp) stmtThree-Address Code for Control StatementFor the statement:if ( E ) S1 e l s e S2The following code pattern is generated:if_false t1 got

20、o L1goto L2label L1label L2Three-Address Code for Control Statementwhile-statement of the formwhile ( E ) Sthree-address code pattern to be generated:label L1if_false t1 goto L2goto L1label L2NoteThere needs only two kinds of jumpsUnconditional jumps (goto L)Jumps when the condition is false (if_fal

21、segoto L)The true case is always a “fall-through” case that needs no jump.This reduces the number of jumps that the compiler needs to generate8.4.3 Code Generation of Logical ExpressionsCode Generation of Logical ExpressionsLogical expressions (or Boolean Expressions) have two primary purposeThey ar

22、e used to compute logical valuesThey are used as test in control statements, such as if-then or while-doComponent of Logical expressionsThey are composed of the Boolean operators (and,or,not) applied to elements that are Boolean variables or relational expressionsRelational expressions are of the fo

23、rm “E1 relop E2”, where E1 and E2 are arithmetic expressions，relop is a comparison operator such as , , =Component of Logical expressionsBoolean expressions generated by the following grammarE-E or E | E and E | not E | (E) | id relop id | true | false or and and are left-associative, and or has the

24、 lowest precedence, then and , then notCode generation for Boolean ExpressionsCode for Boolean Expressions can be generated in a manner similar to arithmetic expressionsFor example, the translation for “a or b and not c” is the three-address sequencet1= not ct2=b and t1t3=a or t2Code generation for

25、Boolean ExpressionsShort circuitA logic operation is short circuit if it may fail to evaluate its second argument.For exampleA and B: if A is computed to be false then A and B can be determined to be false without evaluating BA or B: if A is known to be true, then A or B can be determined to be true without evaluating BShort circuitShort-circuit Boolean operators are similar to if-statements, except that they return values, and often they are defined using if-exp