K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 43
Текст из файла (страница 43)
It then presents the most widely used technique, ad hoc syntaxdirected translation, and compares the strengths and weaknesses of thesetwo tools. The advanced topics section includes brief descriptions of situations that present harder problems in type inference, along with a finalexample of ad hoc syntax-directed translation.OverviewConsider a single name used in the program being compiled; let’s call it x.Before the compiler can emit executable target-machine code for computations involving x, it must have answers to many questions.nnWhat kind of value is stored in x? Modern programming languages usea plethora of data types, including numbers, characters, boolean values,pointers to other objects, sets (such as {red, yellow, green}), andothers. Most languages include compound objects that aggregateindividual values; these include arrays, structures, sets, and strings.How big is x? Because the compiler must manipulate x, it needs toknow the length of x’s representation on the target machine.
If x is anumber, it might be one word (an integer or floating-point number), two4.1 Introduction 163nnnwords (a double-precision floating-point number or a complex number),or four words (a quad-precision floating-point number or a doubleprecision complex number). For arrays and strings, the number ofelements might be fixed at compile time or it might be determined atruntime.If x is a procedure, what arguments does it take? What kind of value, ifany, does it return? Before the compiler can generate code to invoke aprocedure, it must know how many arguments the code for the calledprocedure expects, where it expects to find those arguments, and whatkind of value it expects in each argument. If the procedure returns avalue, where will the calling routine find that value, and what kind ofdata will it be? (The compiler must ensure that the calling procedureuses the value in a consistent and safe manner.
If the calling procedureassumes that the return value is a pointer that it can dereference, and thecalled procedure returns an arbitrary character string, the results maynot be predictable, safe, or consistent.)How long must x’s value be preserved? The compiler must ensure thatx’s value remains accessible for any part of the computation that canlegally reference it. If x is a local variable in Pascal, the compiler caneasily overestimate x’s interesting lifetime by preserving its value forthe duration of the procedure that declares x.
If x is a global variablethat can be referenced anywhere, or if it is an element of a structureexplicitly allocated by the program, the compiler may have a hardertime determining its lifetime. The compiler can always preserve x’svalue for the entire computation; however, more precise informationabout x’s lifetime might let the compiler reuse its space for other valueswith nonconflicting lifetimes.Who is responsible for allocating space for x (and initializing it)? Isspace allocated for x implicitly, or does the program explicitly allocatespace for it? If the allocation is explicit, then the compiler must assumethat x’s address cannot be known until the program runs.
If, on the otherhand, the compiler allocates space for x in one of the runtime datastructures that it manages, then it knows more about x’s address. Thisknowledge may let it generate more efficient code.The compiler must derive the answers to these questions, and more, fromthe source program and the rules of the source language.
In an Algol-likelanguage, such as Pascal or c, most of these questions can be answered byexamining the declarations for x. If the language has no declarations, as inapl, the compiler must either derive this kind of information by analyzingthe program, or it must generate code that can handle any case that mightarise.164 CHAPTER 4 Context-Sensitive AnalysisMany, if not all, of these questions reach beyond the context-free syntax ofthe source language. For example, the parse trees for x ← y and x ← z differonly in the text of the name on the right-hand side of the assignment. If x andy are integers while z is a character string, the compiler may need to emitdifferent code for x ← y than for x ← z.
To distinguish between these cases,the compiler must delve into the program’s meaning. Scanning and parsingdeal solely with the program’s form; the analysis of meaning is the realm ofcontext-sensitive analysis.To see this difference between syntax and meaning more clearly, considerthe structure of a program in most Algol-like languages. These languagesrequire that every variable be declared before it is used and that each use ofa variable be consistent with its declaration. The compiler writer can structure the syntax to ensure that all declarations occur before any executablestatement. A production such asProcedureBody → Declarations ExecutablesTo solve this particular problem, the compilertypically creates a table of names.
It inserts aname on declaration; it looks up the name ateach reference. A lookup failure indicates amissing declaration.This ad hoc solution bolts onto the parser, butuses mechanisms well outside the scope ofcontext-free languages.where the nonterminals have the obvious meanings, ensures that all declarations occur before any executable statements. This syntactic constraintdoes nothing to check the deeper rule—that the program actually declareseach variable before its first use in an executable statement.
Neither does itprovide an obvious way to handle the rule in c++ that requires declarationbefore use for some categories of variables, but lets the programmer intermixdeclarations and executable statements.Enforcing the “declare before use” rule requires a deeper level of knowledgethan can be encoded in the context-free grammar.
The context-free grammardeals with syntactic categories rather than specific words. Thus, the grammarcan specify the positions in an expression where a variable name may occur.The parser can recognize that the grammar allows a variable name to occur,and it can tell that one has occurred.
However, the grammar has no way tomatch one instance of a variable name with another; that would require thegrammar to specify a much deeper level of analysis—an analysis that canaccount for context and that can examine and manipulate information at adeeper level than context-free syntax.4.2 AN INTRODUCTION TO TYPE SYSTEMSTypean abstract category that specifies propertiesheld in common by all its membersCommon types include integer, list, and character.Most programming languages associate a collection of properties witheach data value.
We call this collection of properties the value’s type.The type specifies a set of properties held in common by all values ofthat type. Types can be specified by membership; for example, an integer might be any whole number i in the range −231 ≤ i < 231 , or red4.2 An Introduction to Type Systems 165might be a value in an enumerated type colors, defined as the set{red, orange, yellow, green, blue, brown, black, white}. Types canbe specified by rules; for example, the declaration of a structure in c definesa type.
In this case, the type includes any object with the declared fields inthe declared order; the individual fields have types that specify the allowable ranges of values and their interpretation. (We represent the type of astructure as the product of the types of its constituent fields, in order.) Sometypes are predefined by a programming language; others are constructed bythe programmer. The set of types in a programming language, along withthe rules that use types to specify program behavior, are collectively calleda type system.4.2.1 The Purpose of Type SystemsProgramming-language designers introduce type systems so that they canspecify program behavior at a more precise level than is possible in acontext-free grammar.
The type system creates a second vocabulary fordescribing both the form and behavior of valid programs. Analyzing aprogram from the perspective of its type system yields information thatcannot be obtained using the techniques of scanning and parsing. In a compiler, this information is typically used for three distinct purposes: safety,expressiveness, and runtime efficiency.Ensuring Runtime SafetyA well-designed type system helps the compiler detect and avoid runtimeerrors. The type system should ensure that programs are well behaved—that is, the compiler and runtime system can identify all ill-formed programsbefore they execute an operation that causes a runtime error.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
