A.W. Appel - Modern Compiler Implementation in C (798423), страница 2
Текст из файла (страница 2)
However,the student trying to finish a compiler project in one semester does not have41.2. TOOLS AND SOFTWAREthis luxury. Therefore, I present in this book the outline of a project where theabstractions and interfaces are carefully thought out, and are as elegant andgeneral as I am able to make them.Some of the interfaces, such as Abstract Syntax, IR Trees, and Assem, takethe form of data structures: for example, the Parsing Actions phase builds anAbstract Syntax data structure and passes it to the Semantic Analysis phase.Other interfaces are abstract data types; the Translate interface is a set offunctions that the Semantic Analysis phase can call, and the Tokens interfacetakes the form of a function that the Parser calls to get the next token of theinput program.DESCRIPTION OF THE PHASESEach chapter of Part I of this book describes one compiler phase, as shown inTable 1.2This modularization is typical of many real compilers.
But some compilers combine Parse, Semantic Analysis, Translate, and Canonicalize intoone phase; others put Instruction Selection much later than I have done, andcombine it with Code Emission. Simple compilers omit the Control FlowAnalysis, Data Flow Analysis, and Register Allocation phases.I have designed the compiler in this book to be as simple as possible, butno simpler. In particular, in those places where corners are cut to simplify theimplementation, the structure of the compiler allows for the addition of moreoptimization or fancier semantics without violence to the existing interfaces.1.2TOOLS AND SOFTWARETwo of the most useful abstractions used in modern compilers are context-freegrammars, for parsing, and regular expressions, for lexical analysis.
To makebest use of these abstractions it is helpful to have special tools, such as Yacc(which converts a grammar into a parsing program) and Lex (which convertsa declarative specification into a lexical analysis program).The programming projects in this book can be compiled using any ANSIstandard C compiler, along with Lex (or the more modern Flex) and Yacc(or the more modern Bison).
Some of these tools are freely available on theInternet; for information see the Wide-World Web pagehttp://www.cs.princeton.edu/˜appel/modern/5CHAPTER ONE. INTRODUCTIONChapterPhase2Lex3Parse4SemanticActions5SemanticAnalysis67FrameLayoutTranslate8Canonicalize9InstructionSelectionControlFlowAnalysisDataflowAnalysis101011RegisterAllocation12CodeEmissionTABLE 1.2.DescriptionBreak the source file into individual words, or tokens.Analyze the phrase structure of the program.Build a piece of abstract syntax tree corresponding to each phrase.Determine what each phrase means, relate uses of variables totheir definitions, check types of expressions, request translationof each phrase.Place variables, function-parameters, etc.
into activation records(stack frames) in a machine-dependent way.Produce intermediate representation trees (IR trees), a notationthat is not tied to any particular source language or target-machinearchitecture.Hoist side effects out of expressions, and clean up conditionalbranches, for the convenience of the next phases.Group the IR-tree nodes into clumps that correspond to the actionsof target-machine instructions.Analyze the sequence of instructions into a control flow graphthat shows all the possible flows of control the program mightfollow when it executes.Gather information about the flow of information through variables of the program; for example, liveness analysis calculatesthe places where each program variable holds a still-needed value(is live).Choose a register to hold each of the variables and temporaryvalues used by the program; variables not live at the same timecan share the same register.Replace the temporary names in each machine instruction withmachine registers.Description of compiler phases.Source code for some modules of the Tiger compiler, support code for someof the programming exercises, example Tiger programs, and other useful filesare also available from the same Web address.Skeleton source code for the programming assignments is available fromthis Web page; the programming exercises in this book refer to this directory as$TIGER/ when referring to specific subdirectories and files contained therein.61.3.
DATA STRUCTURES FOR TREE LANGUAGESStmStmStmExpExpExpExp→ Stm ; Stm(CompoundStm)→ id := Exp(AssignStm)→ print ( ExpList ) (PrintStm)→ id(IdExp)→ num(NumExp)→ Exp Binop Exp(OpExp)→ ( Stm , Exp )(EseqExp)GRAMMAR 1.3.1.3ExpListExpListBinopBinopBinopBinop→ Exp , ExpList (PairExpList)→ Exp(LastExpList)→+(Plus)→−(Minus)→×(Times)→/(Div)A straight-line programming language.DATA STRUCTURES FOR TREE LANGUAGESMany of the important data structures used in a compiler are intermediaterepresentations of the program being compiled. Often these representationstake the form of trees, with several node types, each of which has differentattributes. Such trees can occur at many of the phase-interfaces shown inFigure 1.1.Tree representations can be described with grammars, just like programming languages.
To introduce the concepts, I will show a simple programminglanguage with statements and expressions, but no loops or if-statements (thisis called a language of straight-line programs).The syntax for this language is given in Grammar 1.3.The informal semantics of the language is as follows.
Each Stm is a statement, each Exp is an expression. s1 ; s2 executes statement s1 , then statements2 . i:=e evaluates the expression e, then “stores” the result in variable i.print(e1 , e2 , . . . , en ) displays the values of all the expressions, evaluatedleft to right, separated by spaces, terminated by a newline.An identifier expression, such as i, yields the current contents of the variablei.
A number evaluates to the named integer. An operator expression e1 op e2evaluates e1 , then e2 , then applies the given binary operator. And an expressionsequence s, e behaves like the C-language “comma” operator, evaluating thestatement s for side effects before evaluating (and returning the result of) theexpression e.For example, executing this programa := 5+3; b := (print(a, a-1), 10*a); print(b)prints7CHAPTER ONE. INTRODUCTION.CompoundStmAssignStmaOpExpNumExpPlusCompoundStmAssignStmb5PrintStmNumExpLastExpListEseqExp3IdExpPrintStmOpExpbPairExpListNumExp TimesIdExpLastExpListaOpExpIdExpa10IdExpaMinus NumExp1a := 5 + 3 ; b := ( print ( a , a - 1 ) , 10 * a ) ; print ( b )FIGURE 1.4.Tree representation of a straight-line program.8 780How should this program be represented inside a compiler? One representation is source code, the characters that the programmer writes.
But that isnot so easy to manipulate. More convenient is a tree data structure, with onenode for each statement (Stm) and expression (Exp). Figure 1.4 shows a treerepresentation of the program; the nodes are labeled by the production labelsof Grammar 1.3, and each node has as many children as the correspondinggrammar production has right-hand-side symbols.We can translate the grammar directly into data structure definitions, asshown in Figure 1.5. Each grammar symbol corresponds to a typedef in thedata structures:81.3.
DATA STRUCTURES FOR TREE LANGUAGESGrammarStmExpExpListidnumtypedefA stmA expA expListstringintFor each grammar rule, there is one constructor that belongs to the unionfor its left-hand-side symbol. The constructor names are indicated on theright-hand side of Grammar 1.3.Each grammar rule has right-hand-side components that must be represented in the data structures. The CompoundStm has two Stm’s on the righthand side; the AssignStm has an identifier and an expression; and so on. Eachgrammar symbol’s struct contains a union to carry these values, and akind field to indicate which variant of the union is valid.For each variant (CompoundStm, AssignStm, etc.) we make a constructorfunction to malloc and initialize the data structure.
In Figure 1.5 only theprototypes of these functions are given; the definition of A_CompoundStmwould look like this:A_stm A_CompoundStm(A_stm stm1, A_stm stm2) {A_stm s = malloc(sizeof(*s));s->stm1=stm1; s->stm2=stm2;return s;}For Binop we do something simpler. Although we could make a Binopstruct – with union variants for Plus, Minus, Times, Div – this is overkillbecause none of the variants would carry any data.
Instead we make an enumtype A_binop.Programming style. We will follow several conventions for representing treedata structures in C:1. Trees are described by a grammar.2. A tree is described by one or more typedefs, corresponding to a symbol inthe grammar.3. Each typedef defines a pointer to a corresponding struct. The structname, which ends in an underscore, is never used anywhere except in thedeclaration of the typedef.4. Each struct contains a kind field, which is an enum showing differentvariants, one for each grammar rule; and a u field, which is a union.9CHAPTER ONE. INTRODUCTIONtypedeftypedeftypedeftypedefchar *string;struct A_stm_ *A_stm;struct A_exp_ *A_exp;struct A_expList_ *A_expList;struct A_stm_ {enum {A_compoundStm, A_assignStm, A_printStm} kind;union {struct {A_stm stm1, stm2;} compound;struct {string id; A_exp exp;} assign;struct {A_expList exps;} print;} u;};A_stm A_CompoundStm(A_stm stm1, A_stm stm2);A_stm A_AssignStm(String id, A_exp exp);A_stm A_PrintStm(A_expList exps);struct A_exp_ {enum {A_idExp, A_numExp, A_opExp, A_eseqExp} kind;union {String id;int num;struct {A_exp left; A_binop oper; A_exp right;} op;struct {A_stm stm; A_exp exp;} eseq;} u;};A_exp A_IdExp(String id);A_exp A_NumExp(int num);A_exp A_OpExp(A_exp left, A_binop oper, A_exp right);A_exp A_EseqExp(A_stm stm, A_exp exp);typdef enum {A_plus,A_minus,A_times,A_div} A_binop;struct A_expList_ {enum {A_pairExpList, A_lastExpList} kind;union {struct {A_exp head; A_expList tail;} pair;A_exp last;} u;}PROGRAM 1.5.Representation of straight-line programs.5.
If there is more than one nontrivial (value-carrying) symbol in the righthand side of a rule (example: the rule CompoundStm), the union will havea component that is itself a struct comprising these values (example: thecompound element of the A_stm_ union).6. If there is only one nontrivial symbol in the right-hand side of a rule, theunion will have a component that is the value (example: the num field of theA_exp union).7. Every class will have a constructor function that initializes all the fields. Themalloc function shall never be called directly, except in these constructor101.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
