slike bài giảng môn chương trình dịch chương 7 symbol tables
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (102.18 KB, 14 trang )
Type Checking
Dr. Nguyen Hua Phung
Faculty of CSE
HCMUT
Outline
• Type systems
– Type expressions
– Static and dynamic type checking
• Equivalence of type expressions
• Type conversions
CSE - HCMUT Type Checking 2
Type Expressions
• A basic type is a type expression.
– boolean, char, integer, float, void, subrange.
• A type name is a type expression.
• A type constructor applied to type expressions is
a type expression. Including:
– Arrays: array(I,T) where I: index type, T:element type
– Products: T
1
× T
2
– Records: record((name
1
× T
1
) × (name
2
× T
2
) ×…)
– Pointers: pointer(T)
– Functions: T
1
→ T
2
• A type variable is a type expression.
CSE - HCMUT Type Checking 3
Example
• typedef int siso; ⇒ siso
• int t[10]; ⇒ array(0 9,int)
• int foo(int a,float b) ⇒ (int × float) → int
• struct {int a;int b} ⇒ record((a × int) × (b × int))
• int *p ⇒ pointer(int)
• template <class T> struct vd {T a; T b[3];}
⇒ record((a × T) × (b × array(0 2,T)))
CSE - HCMUT Type Checking 4
Type Checking
• Static type checking
– is perfomed by the compiler
– applied to typed language
• Dynamic type checking
– is done when the target program runs
– target code needs to carry the type of an
element
CSE - HCMUT Type Checking 5
Equivalence of Type Expressions
• Name equivalence
• Structural equivalence
• Structural equivalence under naming
rec1 = record
a : integer;
b : real;
end;
rec2 = record
c : real;
d : integer;
end;
rec3 = record
c : integer;
d : real;
end;
rec4 = record
a : integer;
b : real;
end;
rec1 and rec4 are structural equivalence under naming
rec1 and rec3 are structural equivalence
CSE - HCMUT Type Checking 6
Static Type Checking for
Structural Equivalence
function sequiv(Type s,Type t):boolean
begin
if (s and t are the same basic type) then
return true;
else if (s = array(s1,s2) and t = array(t1,t2) then
return sequiv(s1,t1) and sequiv(s2,t2);
else if (s = s1 × s2 and t = t1 × t2) then
return sequiv(s1,t1) and sequiv(s2,t2);
else if (s = pointer(s1) and t = pointer(t1)) then
return sequiv(s1,t1);
else if (s = s1 → s2 and t = t1 → t2) then
return sequiv(s1,t1) ;
else
return false;
CSE - HCMUT Type Checking 7
Object-Oriented Approach
Type
CSE - HCMUT Type Checking 8
BasicType
NumericType
BooleanType
PointerType
ProductType
FunctionType
ArrayType
RangeType
array(I,T)
IntType FloatType
class ArrayType extends Type {
RangeType index;
Type element;
}
Object-Oriented Approach (cont’d)
abstract class Type {
abstract boolean isLeftCompatibleTo(Type t) ;
}
abstract class BasicType extends Type {
boolean isLeftCompatibleTo(Type t) {
if (this.getClass().equals(t.getClass()))
return true;
return false;
}
}
class FloatType extends NumericType {
boolean isLeftCompatibleTo(Type t) {
if (t instanceof NumericType)
return true;
return false;
}
}
CSE - HCMUT Type Checking 9
Object-Oriented Approach (cont’d)
class ArrayType {
RangeType
index;
Type
element;
boolean isLeftCompatibleTo(Type t) {
if (t instanceof ArrayType) {
ArrayType at=(ArrayType) t;
return
index.isLeftCompatibleTo(at.index) &&
element.isLeftCompatibleTo(at.element);
} else
return false;
}
}
CSE - HCMUT Type Checking 10
Static Type Checking for
Assignment Expression
Expr → Term = Expr
{ if (!Term.type.isLeftCompatibleTo(Expr.type))
throw new TypeMismatch(=);
}
Expr → Term
Term → INTLITERAL
Term → FLOATLITERAL
Term → id
Term → ( Expr )
{Expr.type = Term.type;}
{Term.type = new IntType();}
{Term.type = new FloatType();}
{sym = lookup(id.Lexeme);
Term.type = sym.type;}
{Term.type = Expr.type}
CSE - HCMUT Type Checking 11
Implicit Assignment
int foo(int a, float b) {
…
return a;
}
int goo() {
…
foo(x,y);
…
}
foo = a
a = x; b = y
CSE - HCMUT Type Checking 12
Implicit Assignment (cont’d)
==(int i
1
, int i
2
)
• ==
•a == b
==(boolean b
1
, boolean b
2
)
i
1
= a; i
2
= b
b
1
= a; b
2
= b
CSE - HCMUT Type Checking 13
Type Conversions
• Converts from one type to another.
• implicit if it is done automatically by the
compiler ⇒ type coercions
float x = 3;
• explicit if the programmer must write
something to cause the conversion.
CSE - HCMUT Type Checking 14
