Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 43

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.

In truth, thetype system cannot catch all ill-formed programs; the set of ill-formed programs is not computable. Some runtime errors, such as dereferencing anout-of-bounds pointer, have obvious (and often catastrophic) effects. Others, such as mistakenly interpreting an integer as a floating-point number,can have subtle and cumulative effects. The compiler should eliminate asmany runtime errors as it can using type-checking techniques.To accomplish this, the compiler must first infer a type for each expression.These inferred types expose situations in which a value is incorrectly interpreted, such as using a floating-point number in place of a boolean value.Second, the compiler must check the types of the operands of each operatoragainst the rules that define what the language allows.

In some cases, theserules might require the compiler to convert values from one representationto another. In other circumstances, they may forbid such a conversion andsimply declare that the program is ill formed and, therefore, not executable.Type inferencethe process of determining a type for each nameand each expression in the code166 CHAPTER 4 Context-Sensitive Analysis+integerintegerrealdoublecomplexintegerrealdoublecomplexrealrealrealdoublecomplexdoublecomplexdoubledoubledoublecomplexcomplexillegalcomplexillegaln FIGURE 4.1 Result Types for Addition in FORTRAN 77.Implicit conversionMany languages specify rules that allow anoperator to combine values of different type andrequire that the compiler insert conversions asneeded.The alternative is to require the programmer towrite an explicit conversion or cast.In many languages, the compiler can infer a type for every expression.

fortran 77 has a particularly simple type system with just a handful of types.Figure 4.1 shows all the cases that can arise for the + operator. Given anexpression a + b and the types of a and b, the table specifies the type of a + b.For an integer a and a double-precision b, a + b produces a double-precisionresult. If, instead, a were complex, a + b would be illegal. The compilershould detect this situation and report it before the program executes—asimple example of type safety.For some languages, the compiler cannot infer types for all expressions.

apl,for example, lacks declarations, allows a variable’s type to change at anyassignment, and lets the user enter arbitrary code at input prompts. While thismakes apl powerful and expressive, it ensures that the implementation mustdo some amount of runtime type inference and checking. The alternative, ofcourse, is to assume that the program behaves well and ignore such checking.In general, this leads to bad behavior when a program goes awry.

In apl,many of the advanced features rely heavily on the availability of type anddimension information.Safety is a strong reason for using typed languages. A language implementation that guarantees to catch most type-related errors before they execute cansimplify the design and implementation of programs. A language in whichevery expression can be assigned an unambiguous type is called a stronglytyped language. If every expression can be typed at compile time, the language is statically typed; if some expressions can only be typed at runtime,the language is dynamically typed. Two alternatives exist: an untyped language, such as assembly code or bcpl, and a weakly typed language—onewith a poor type system.Improving ExpressivenessA well-constructed type system allows the language designer to specifybehavior more precisely than is possible with context-free rules.

This capability lets the language designer include features that would be impossible4.2 An Introduction to Type Systems 167to specify in a context-free grammar. An excellent example is operatoroverloading, which gives context-dependent meanings to an operator. Manyprogramming languages use + to signify several kinds of addition. The interpretation of + depends on the types of its operands. In typed languages,many operators are overloaded. The alternative, in an untyped language, isto provide lexically different operators for each case.For example, in bcpl, the only type is a “cell.” A cell can hold any bitpattern; the interpretation of that bit pattern is determined by the operatorapplied to the cell.

Because cells are essentially untyped, operators cannot beoverloaded. Thus, bcpl uses + for integer addition and #+ for floating-pointaddition. Given two cells a and b, both a + b and a #+ b are valid expressions,neither of which performs any conversion on its operands.In contrast, even the oldest typed languages use overloading to specify complex behavior. As described in the previous section, fortran has a singleaddition operator, +, and uses type information to determine how it shouldbe implemented.

ansi c uses function prototypes—declarations of the number and type of a function’s parameters and the type of its returned value—toconvert arguments to the appropriate types. Type information determines theeffect of autoincrementing a pointer in c; the amount of the increment isdetermined by the pointer’s type. Object-oriented languages use type information to select the appropriate implementation at each procedure call. Forexample, Java selects between a default constructor and a specialized one byexamining the constructor’s argument list.Generating Better CodeA well-designed type system provides the compiler with detailed information about every expression in the program—information that can often beused to produce more efficient translations.