K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 48
Текст из файла (страница 48)
The compiler must check each of those calls. Itmust ensure that each actual parameter is type compatible with the corresponding formal parameter. It must determine the type of any returned valuefor use in further inference.Type signaturea specification of the types of the formalparameters and return value(s) of a functionFunction prototypeThe C language includes a provision that lets theprogrammer declare functions that are notpresent. The programmer includes a skeletondeclaration, called a function prototype.To analyze and understand procedure calls, the compiler needs a type signature for each function. For example, the strlen function in c’s standardlibrary takes an operand of type char * and returns an int that contains itslength in bytes, excluding the terminating character.
In c, the programmercan record this fact with a function prototype that looks like:unsigned int strlen(const char *s);This prototype asserts that strlen takes an argument of type char *, whichit does not modify, as indicated by the const attribute. The function returnsa nonnegative integer. Writing this in a more abstract notation, we mightsay thatstrlen : const char * → unsigned intwhich we read as “strlen is a function that takes a constant-valued character string and returns an unsigned integer.” As a second example, the classicScheme function filter has the type signaturefilter: (α →boolean) × list of α → list of αThat is, filter is a function that takes two arguments.
The first should bea function that maps some type α into a boolean, written (α →boolean), andthe second should be a list whose elements are of the same type α. Givenarguments of those types, filter returns a list whose elements have type α.The function filter exhibits parametric polymorphism: its result type is afunction of its argument types.4.2 An Introduction to Type Systems 181To perform accurate type inference, the compiler needs a type signature forevery function. It can obtain that information in several ways. The compilercan eliminate separate compilation, requiring that the entire program be presented for compilation as a unit. The compiler can require the programmerto provide a type signature for each function; this usually takes the form ofmandatory function prototypes.
The compiler can defer type checking untileither link time or runtime, when all such information is available. Finally,the compiler writer can embed the compiler in a program-development system that gathers the requisite information and makes it available to thecompiler on demand. All of these approaches have been used in real systems.SECTION REVIEWA type system associates with each value in the program some textualname, a type, that represents a set of common properties held by allvalues of that type.
The definition of a programming language specifiesinteractions between objects of the same type, such as legal operationson values of a type, and between objects of different type, such as mixedtype arithmetic operations. A well-designed type system can increase theexpressiveness of a programming language, allowing safe use of featuressuch as overloading. It can expose subtle errors in a program long beforethey become puzzling runtime errors or wrong answers.
It can let thecompiler avoid runtime checks that waste time and space.A type system consists of a set of base types, rules for constructingnew types from existing ones, a method for determining equivalenceof two types, and rules for inferring the types of each expression ina program. The notions of base types, constructed types, and typeequivalence should be familiar to anyone who has programmed in ahigh-level language. Type inference plays a critical role in compilerimplementation.Review Questions1. For your favorite programming language, write down the base typesin its type system. What rules and constructs does the language allowto build aggregate types? Does it provide a mechanism for creating aprocedure that takes a variable number of arguments, such as printfin the C standard I/O library?2.
What kinds of information must the compiler have to ensure typesafety at procedure calls? Sketch a scheme based on the use of function prototypes. Sketch a scheme that can check the validity of thosefunction prototypes.182 CHAPTER 4 Context-Sensitive Analysis4.3 THE ATTRIBUTE-GRAMMAR FRAMEWORKAttributea value attached to one or more of the nodes in aparse treeOne formalism that has been proposed for performing context-sensitiveanalysis is the attribute grammar, or attributed context-free grammar. Anattribute grammar consists of a context-free grammar augmented by a setof rules that specify computations.
Each rule defines one value, or attribute,in terms of the values of other attributes. The rule associates the attributewith a specific grammar symbol; each instance of the grammar symbol thatoccurs in a parse tree has a corresponding instance of the attribute. The rulesare functional; they imply no specific evaluation order and they define eachattribute’s value uniquely.To make these notions concrete, consider a context-free grammar forsigned binary numbers.
Figure 4.4 defines the grammar SBN = (T,NT,S,P).SBN generates all signed binary numbers, such as -101, +11, -01, and+11111001100. It excludes unsigned binary numbers, such as 10.From SBN, we can build an attribute grammar that annotates Number withthe value of the signed binary number that it represents. To build an attributegrammar from a context-free grammar, we must decide what attributes eachnode needs, and we must elaborate the productions with rules that definevalues for these attributes. For our attributed version of SBN, the followingattributes are needed:SymbolAttributesNumberSignListBitvaluenegativeposition, valueposition, valueIn this case, no attributes are needed for the terminal symbols.Figure 4.5 shows the productions of SBN elaborated with attribution rules.Subscripts are added to grammar symbols whenever a specific symbolNumberSignP=ListBit→→|→|→|Sign List +−List Bit Bit0T= { +, -, 0, 1 }NT = { Number, Sign, List, Bit }S= { Number }1n FIGURE 4.4 An Attribute Grammar for Signed Binary Numbers.4.3 The Attribute-Grammar Framework 183ProductionAttribution Rules1Number → Sign ListList.position ← 0if Sign.negativethen Number.value← - List.valueelse Number.value ← List.value2Sign → +Sign.negative ← false3Sign → -Sign.negative ← true4List → BitBit.position ← List.positionList.value ← Bit.value5List0 → List1 BitList1 .position ← List0 .position + 1Bit.position ← List0 .positionList0 .value ← List1 .value + Bit.value6Bit → 07Bit → 1Bit.value ← 0Bit.value ← 2Bit.positionn FIGURE 4.5 Attribute Grammar for Signed Binary Numbers.appears multiple times in a single production.
This practice disambiguatesreferences to that symbol in the rules. Thus, the two occurrences ofList in production 5 have subscripts, both in the production and in thecorresponding rules.The rules add attributes to the parse tree nodes by their names. An attributementioned in a rule must be instantiated for every occurrence of that kind ofnode.Each rule specifies the value of one attribute in terms of literal constantsand the attributes of other symbols in the production. A rule can pass information from the production’s left-hand side to its right-hand side; a rulecan also pass information in the other direction. The rules for production4 pass information in both directions. The first rule sets Bit.position toList.position, while the second rule sets List.value to Bit.value.
Simpler attribute grammars can solve this particular problem; we have chosenthis one to demonstrate particular features of attribute grammars.Given a string in the SBN grammar, the attribution rules set Number.valueto the decimal value of the binary input string. For example, the string -101causes the attribution shown in Figure 4.6a. (The names for value, number,and position are truncated in the figure.) Notice that Number.value hasthe value -5.To evaluate an attributed parse tree for some sentence in L(S B N ), theattributes specified in the various rules are instantiated for each node in184 CHAPTER 4 Context-Sensitive Analysisthe parse tree.
This creates, for example, an attribute instance for bothvalue and position in each List node. Each rule implicitly defines a setof dependences; the attribute being defined depends on each argument to therule. Taken over the entire parse tree, these dependences form an attributedependence graph. Edges in the graph follow the flow of values in theevaluation of a rule; an edge from nodei .field j to nodek .fieldl indicates thatthe rule defining nodek .fieldl uses the value of nodei .field j as one of itsinputs. Figure 4.6b shows the attribute-dependence graph induced by theparse tree for the string -101.Synthesized attributean attribute defined wholly in terms of theattributes of the node, its children, and constantsInherited attributean attribute defined wholly in terms of thenode’s own attributes and those of its siblings orits parent in the parse tree (plus constants)The rule node.field←1 can be treated as eithersynthesized or inherited.The bidirectional flow of values that we noted earlier (in, for example, production 4) shows up in the dependence graph, where arrows indicate bothflow upward toward the root (Number) and flow downward toward theleaves.
The List nodes show this effect most clearly. We distinguish betweenattributes based on the direction of value flow. Synthesized attributes aredefined by bottom-up information flow; a rule that defines an attribute forthe production’s left-hand side creates a synthesized attribute.
A synthesizedattribute can draw values from the node itself, its descendants in the parsetree, and constants. Inherited attributes are defined by top-down and lateralinformation flow; a rule that defines an attribute for the production’s righthand side creates an inherited attribute. Since the attribution rule can nameany symbol used in the corresponding production, an inherited attribute candraw values from the node itself, its parent and its siblings in the parse tree,Numberval:-5Numberval:-5pos:0Signneg:truepos:0pos:1pos:2pos:1Bit val:1List val:4List val:4pos:1pos:2Bit val:0List val:4Bit val:1pos:1Bit val:0pos:2pos:21pos:0List val:4Bit val:4Bit val:4-pos:0List val:5Signneg:trueList val:501(a) Parse Tree for-101n FIGURE 4.6 Attributed Tree for the Signed Binary Number −101.-10(b) Dependence Graph for-10114.3 The Attribute-Grammar Framework 185and constants.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
