Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 45
Описание файла
Файл "Cooper_Engineering_a_Compiler(Second Edition)" внутри архива находится в следующих папках: Rice, Купер и Торчсон - перевод. PDF-файл из архива "Rice", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 45 страницы из PDF
Recently, more implementations—both operating system and programming language—have begun to support larger charactersets expressed in the Unicode standard format, which requires 16 bits. Mostlanguages assume that the character set is ordered, so that standard comparison operators, such as <, =, and >, work intuitively, enforcing lexicographicordering. Conversion between a character and an integer appears in somelanguages.
Few other operations make sense on character data.172 CHAPTER 4 Context-Sensitive AnalysisBooleansMost programming languages include a boolean type that takes on two values: true and false. Standard operations provided for booleans includeand, or, xor, and not. Boolean values, or boolean-valued expressions, areoften used to determine the flow of control. c considers boolean values as asubrange of the unsigned integers, restricted to the values zero (false) andone (true).Compound and Constructed TypesWhile the base types of a programming language usually provide an adequate abstraction of the actual kinds of data handled directly by the hardware, they are often inadequate to represent the information domain neededby programs. Programs routinely deal with more complex data structures,such as graphs, trees, tables, arrays, records, lists, and stacks.
These structures consist of one or more objects, each with its own type. The ability toconstruct new types for these compound or aggregate objects is an essentialfeature of many programming languages. It lets the programmer organizeinformation in novel, program-specific ways. Tying these organizations tothe type system improves the compiler’s ability to detect ill-formed programs. It also lets the language express higher-level operations, such as awhole-structure assignment.Take, for example, Lisp, which provides extensive support for programmingwith lists. Lisp’s list is a constructed type.
A list is either the designated valuenil or (cons first rest) where first is an object, rest is a list, andcons is a constructor that creates a list from its two arguments. A Lisp implementation can check each call to cons to ensure that its second argument is,in fact, a list.ArraysArrays are among the most widely used aggregate objects. An array groupstogether multiple objects of the same type and gives each a distinct name—albeit an implicit, computed name rather than an explicit, programmerdesignated, name. The c declaration int a[100][200]; sets aside space for100 × 200 = 20,000 integers and ensures that they can be addressed usingthe name a. The references a[1][17] and a[2][30] access distinct andindependent memory locations. The essential property of an array is thatthe program can compute names for each of its elements by using numbers(or some other ordered, discrete type) as subscripts.Support for operations on arrays varies widely.
fortran 90, pl/i, and aplall support assignment of whole or partial arrays. These languages support element-by-element application of arithmetic operations to arrays. For4.2 An Introduction to Type Systems 17310 × 10 arrays x, y, and z, indexed from 1 to 10, the statement x = y + z wouldoverwrite each x[i,j] with y[i,j] + z[i,j] for all 1 ≤ i, j ≤ 10.
apl takesthe notion of array operations further than most languages; it includes operators for inner product, outer product, and several kinds of reductions. Forexample, the sum reduction of y, written x ← +/y, assigns x the scalar sumof the elements of y.An array can be viewed as a constructed type because we construct an arrayby specifying the type of its elements. Thus, a 10 × 10 array of integers hastype two-dimensional array of integers. Some languages include the array’sdimensions in its type; thus a 10 × 10 array of integers has a different typethan a 12 × 12 array of integers.
This lets the compiler catch array operationsin which dimensions are incompatible as a type error. Most languages allowarrays of any base type; some languages allow arrays of constructed typesas well.StringsSome programming languages treat strings as a constructed type. pl/i, forexample, has both bit strings and character strings.
The properties, attributes,and operations defined on both of these types are similar; they are propertiesof a string. The range of values allowed in any position differs between a bitstring and a character string. Thus, viewing them as string of bit and string ofcharacter is appropriate. (Most languages that support strings limit the builtin support to a single string type—the character string.) Other languages,such as c, support character strings by handling them as arrays of characters.A true string type differs from an array type in several important ways. Operations that make sense on strings, such as concatenation, translation, andcomputing the length, may not have analogs for arrays. Conceptually, stringcomparison should work from lexicographic order, so that "a" < "boo" and"fee" < "fie". The standard comparison operators can be overloaded andused in the natural way.
Implementing comparison for an array of characterssuggests an equivalent comparison for an array of numbers or an array ofstructures, where the analogy to strings may not hold. Similarly, the actuallength of a string may differ from its allocated size, while most uses of anarray use all the allocated elements.Enumerated TypesMany languages allow the programmer to create a type that contains a specific set of constant values. An enumerated type, introduced in Pascal, letsthe programmer use self-documenting names for small sets of constants.Classic examples include days of the week and months. In c syntax, thesemight be174 CHAPTER 4 Context-Sensitive Analysisenum WeekDay {Monday, Tuesday, Wednesday,Thursday, Friday, Saturday, Sunday};enum Month {January, February, March, April,May, June, July, August, September,October, November, December};The compiler maps each element of an enumerated type to a distinct value.The elements of an enumerated type are ordered, so comparisons betweenelements of the same type make sense.
In the examples, Monday < Tuesdayand June < July. Operations that compare different enumerated typesmake no sense—for example, Tuesday > September should produce a typeerror, Pascal ensures that each enumerated type behaves as if it were a subrange of the integers. For example, the programmer can declare an arrayindexed by the elements of an enumerated type.Structures and VariantsStructures, or records, group together multiple objects of arbitrary type.
Theelements, or members, of the structure are typically given explicit names.For example, a programmer implementing a parse tree in c might need nodeswith both one and two children.struct Node1 {struct Node2 {structNode2 *left;Node2 *right;unsigned Operator;structNode1 *left;unsigned Operator;intstructValueint}Value}The type of a structure is the ordered product of the types of the individual elements that it contains. Thus, we might describe the type ofa Node1 as (Node1 *) × unsigned × int, while a Node2 would be(Node2 *) × (Node2 *) × unsigned × int. These new types should havethe same essential properties that a base type has.
In c, autoincrementinga pointer to a Node1 or casting a pointer into a Node1 * has the desiredeffect—the behavior is analogous to what happens for a base type.Many programming languages allow the creation of a type that is the unionof other types. For example, some variable x can have the type integer orboolean or WeekDay. In Pascal, this is accomplished with variant records—a record is the Pascal term for a structure.
In c, this is accomplished with aunion. The type of a union is the alternation of its component types; thusour variable x has type integer ∪ boolean ∪ WeekDay. Unions can also4.2 An Introduction to Type Systems 175AN ALTERNATIVE VIEW OF STRUCTURESThe classical view of structures treats each kind of structure as a distincttype. This approach to structure types follows the treatment of other aggregates, such as arrays and strings. It seems natural.