CSc 453 — Compilers and Systems Software11 : Semantic Analysis IIIChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergSeptember 27, 20091Basic and Structured Types2 Basic Types• Which basic types does the language have? In Pascal boolean, real, integer, char are basic types.• Integers: may come in different sizes and signed/unsigned.• Reals: may come in different sizes. Some languages allow programmer control over precision.• Some languages have fix-point numbers, complex numbers, rational numbers,. . . .• Does the language automatically convert from one type to another? Can I add a complex number andan integer?3 Basic Types. . .Enumeration typesTYPE E1 = (white,blue,yellow,green,red);TYPE E2 = (apple=4,pear=9,kumquat=99);• Pascal, Ada, Modula-2, C have some variant of enumeration types.Subrange typesTYPE S1 = [0..10];TYPE S2 = [’a’..’z’];TYPE S3 = [blue..green];• Subranges can be used to force additional runtime checks. Some languages use them as array indextypes.14 Structured Types: Arrays• Are they static or dynamic? I.e. do I create them at compile-time (C) or run-time (Java)?• Do I check for out-of-bounds errors (Java) or not (C)?• Are they 0-based (C) or 1-based (Icon)?• Can the user define both the lower and upper bounds (Pascal)?• Must the index type be integer (C,Java) or any enumerable type (Pascal)?5 Structured Types: Arrays. . .TYPE A1 = ARRAY 100 OF CHAR;TYPE A2 = ARRAY [5..99] OF INTEGER;TYPE A3 = ARRAY CHAR OF INTEGER;TYPE A4 = ARRAY OF INTEGER;VAR a3 : A3;VAR a4 : A4;BEGINa3[’X’] := 55;a4 := NEW ARRAY 99 OF INTEGER;END6• Most languages lay out arrays in row-major order. FORTRAN uses column-major.A[1,1] A[1,2]A[2,1] A[2,2]A[3,1] A[3,2]A[4,1] A[4,2]0 A[1,1]1 A[1,2]2 A[2,1]3 A[2,2]4 A[3,1]5 A[3,2]6 A[4,1]7 A[4,2]0 A[1,1]1 A[2,1]2 A[3,1]3 A[4,1]4 A[1,2]5 A[2,2]6 A[3,2]7 A[4,2]Matrix Row Major Column Major7 Array Indexing – 1 Dimensions• How do we compute the address (L-value) of the n:th element of a 1-dimensional array?• Aelszis A’s element-size, Aaddris its base address.VAR A : ARRAY [l .. h] OF T;L-VAL(A[i]) ≡ Aaddr+ (i − l) ∗ Aelsz≡ Aaddr+ (l ∗ Aelsz) + i ∗ AelszC ≡ Aaddr+ (l ∗ Aelsz)L-VAL(A[i]) ≡ C + i ∗ Aelsz• Note that C can be computed at compile-time.28 Array Indexing – 2 DimensionsVAR A :ARRAY [l1..h1][l2..h2] OF T;w1≡ h1− l1+ 1w2≡ h2− l2+ 1L-VAL(A[i1, i2]) ≡ Aaddr+ ((i1− l1) ∗ w2+ i2+ l2) ∗ Aelsz≡ Aaddr+ (i1∗ w2+ i2) ∗ Aelsz−(l1∗ w2− l2) ∗ AelszC ≡ Aaddr− (l1∗ w2− l2) ∗ AelszL-VAL(A[i1, i2]) ≡ (i1∗ w2+ i2) ∗ Aelsz+ C• C can be computed at compile-time.9 Array Indexing – n DimensionsVAR A : ARRAY [l1..h1] ... [ln..hn] OF T;wk≡ hk− lk+ 1C ≡Aaddr− ((· · · (l1∗ w2+ l2) ∗ w3+ l3) · · · ) ∗ wn+ ln) ∗ AelszL-VAL(A[i1, i2, ..., in]) ≡((· · · (i1∗ w2+ i2) ∗ w3+ i3) · · · ) ∗ wn+ in) ∗ Aelsz+ C10 Record Types• Pascal, C, Modula-2, Ada and other languages havevariant records (C’s union type):TYPE R1 = RECORD tag : (red,blue,green);CASE tag OFred : r : REAL; |blue : i : INTEGER; |ELSE c : CHAR;END;END;Depending on the tag value R1 has a real, integer, or char field.• The size of a variant part is the max of the sizes of its constituent fields.311 Record Types. . .• Oberon has extensible record types:TYPE R3 = RECORDa : INTEGER;END;TYPE R4 = (R3) RECORDb : REAL;END;R4 has both the a and the b field.• Extensible records are similar to classes in other languages.12 Pointer Types• In order to build recursive structures, most languages allow some way of declaringrecursive types.These are necessary in order to construct linked structures such as lists and trees:TYPE P = POINTER TO R;TYPE R = RECORDdata : INTEGER;next : P;END;• Note that P is declared before its use. Languages such as Pascal and C don’t allow forward declarations,but make an exception for pointers.13 Procedure Types• C, Modula-2, and other languages supportprocedure types. You can treat the address of a procedurelike any other object:TYPE P = PROCEDURE(x:INTEGER; VAR Y:CHAR):REAL;VAR z : P; VAR c : CHAR; VAR r : REAL;PROCEDURE M (x:INTEGER; VAR Y:CHAR):REAL; BEGIN· · · END;BEGINz := M; /* z holds the address of M. */r := z(44,c);END.• Languages differen in whether they allow procedures whose address is taken to be nested or not.(Why?)14 Class Types• Java’s classes are just record types. Some languages (Object Pascal, Oberon, MODULA-3) defineclasses just like records:4TYPE C1 = CLASSx : INTEGER;void M() { · · · };void N() { · · · };END;TYPE C2 = CLASS EXTENDS C1r : REAL; // Add another field.void M() { · · · }; // Overrides C1.Mvoid Q() { · · · }; // Add another method.END;15Type Constructors16 Type Expressions (TE)• To reason about types we build up an algebra of TEs:T E = int, string, real, · · · , type error, void= subrange(from, to)= array(idx, eltype)= record((f1× t1) × · · · × (fn× tn))= pointer(type)= d1× · · · × dn→ r• The fi:s are field names and ti:s are field types (TEs).• d1× · · · × dnis thedomain and r is the range of a function type. diand r are TEs.17TYPE T = RECORDA : INTEGER;B : POINTER TO ARRAY [1..10] OF CHAR;ENDrecord(A × int,B × pointer(array(subrange(1,10),char))))A int Barraysubrangepointerchar110record××Type ExpressionType Graph518TYPE P = PROCEDURE (A:INTEGER; B:T) : REAL;int × T → realA intarraysubrangechar110pointerintrealBrecord××→×19Typechecking20 Static/Dynamic Typechecking• Semantic checking can be done both at compile-time (static checking) and run-time (dynamic checking).• Some translators also do some checking atlink-time and load-time. Java, for example, verifies thecorrectness of class-files at class load time.• A language has aSound Type System if no dynamic typechecking necessary.• In aStrongly Typed Language there are no type errors at run time.21 Static/Dynamic Typechecking. . .VAR V : REAL;VAR S = [1 .. 10];BEGINV := V + 3.14; // Static checkS := READ; // Dynamic checkEND22Type Equivalence623 Equivalence Types• Equivalence types are used to create type aliases:TYPE Flag = (red,white,blue);TYPE Q = Flag;VAR x : Flag;VAR y : Q;BEGINx := y; /* Legal? */ END;• But, when are two types equivalent? I.e. when can we compare two variables of “different” types?• Some languages usestructural type equivalence, others name equivalence, others a mixture of