CSc 453Compilers and Systems Software11 : Semantic Analysis IIIDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergBasic and Structured TypesBasic TypesWhich basic types does the language have? In Pascalboolean, real, integer, char are basic types.Integers: may come in different sizes and signed/unsigned.Reals: may come in different sizes. Some languages allowprogrammer control over precision.Some languages have fix-point numbers, complex numbers,rational numbers,. . . .Does the language automatically convert from one type toanother? Can I add a complex number and an integer?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 enumerationtypes.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 index types.Structured Types: ArraysAre they static or dynamic? I.e. do I create them atcompile-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 enumerabletype (Pascal)?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;ENDMost languages lay out arrays in row-major order. FORTRANuses 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 MajorArray Indexing – 1 DimensionsHow do we compute the address (L-value) of the n:th elementof 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 ∗ AelszNote that C can be computed at compile-time.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+ CC can be computed at compile-time.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+ CRecord TypesPascal, C, Modula-2, Ada and other languages have variantrecords(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 charfield.The size of a variant part is the max of the sizes of itsconstituent fields.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.Pointer TypesIn order to build recursive structures, most languages allowsome way of declaringrecursive types. These are necessary inorder 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 asPascal and C don’t allow forward declarations, but make anexception for pointers.Procedure TypesC, Modula-2, and other languages support procedure types.You can treat the address of a procedure like 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 whoseaddress is taken to be nested or not. (Why?)Class TypesJava’s classes are just record types. Some languages (ObjectPascal, Oberon, MODULA-3) define classes just like records:TYPE 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;Type ConstructorsType Expressions (TE)To reason about types we build up an algebra of TEs:TE = int, string, real, · · · , typeerror, void= subrange(from, to)= array(idx, eltype)= record((f1× t1) × · · · × (fn× tn))= pointer(type)= d1× · · · × dn→ rThe fi:s are field names and ti:s are field types (TEs).d1× · · · × dnis the domain and r is the range of a functiontype. diand r are TEs.TYPE 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 Expression Type GraphTYPE P = PROCEDURE (A:INTEGER; B:T) : REAL;int × T → realA intarraysubrangechar110pointerintrealBrecord××→×TypecheckingStatic/Dynamic TypecheckingSemantic checking can be done both at compile-time (staticchecking) and run-time (dynamic checking).Some translators also do some checking at link-time andload-time. Java, for example, verifies the correctness ofclass-files at class load time.A language has a Sound Type System if no dynamictypechecking necessary.In a Strongly Typed Language there are no type errors at runtime.Static/Dynamic Typechecking. . .VAR V : REAL;VAR S = [1 .. 10];BEGINV := V + 3.14; // Static checkS := READ; // Dynamic checkENDType EquivalenceEquivalence TypesEquivalence 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 wecompare two variables of “different” types?Some languages use structural type equivalence, others nameequivalence, others a mixture of the two.Structural EquivalencePROCEDURE Equiv(s, t) : BOOLEANIF basic(s) & basic(t) & s = t THENRETURN TRUEELSIF s = array(i1, t1) & t = array(i2, t2) THENRETURN Equiv(i1, i2) & Equiv(t1, t2)ELSIF s = l1× r1& t = l2× r2THENRETURN Equiv(l1, l2) & Equiv(r1,