COMPILER CONSTRUCTION
Principles and Practice
Kenneth C,Louden
6,Semantic Analysis
PART TWO
Contents
Part One
6.1 Attributes and Attribute Grammars
6.2 Algorithms for Attribute Computation
Part Two
6.3 The Symbol Table
6.4 Data Types and Type Checking
6.5 A Semantic Analyzer for the TINY Language
6.3 The Symbol Table
Symbol table,major inherited attribute and major
data structure in a compiler
Principal operations,
– Insert,store the information provided by name
declarations when processing these declarations
– Lookup,retrieve the information associated to a name
when that name is used in the associated code.
– Delete,remove the information provided by a
declaration when that declaration no longer applies.
Information stored:
– Include data type information,information on region of
applicability (scope),and information on eventual
location in memory.
6.3.1 The Structure of The
Symbol Table
Typical dictionary data structure
Linear list
– Provide easy and direct implementations of the three
basic operations;
– Operation time is linear in the size of the list;
– Good for a compiler implementation in which speed is
not a major concern such as a prototype or experimental
compiler or an interpreter for a very small program.
Various search tree structures
– (binary search trees,AVL trees,B trees)
– Don't provide best case efficiency;
– The delete operation is very complexity;
– Less useful.
Hash tables
– All three operation can be performed in almost
constant time
– Most frequently in practice,best choice
Main idea
– An array of entries (called buckets),indexed by an
integer range
– A hash function turns the search key into an integer
hash value in the index range
– And the item corresponding to the search key is
stored in the bucket at this index
– The efficiency greatly depends on the design of the
hash function
Main problem
– Collision resolution,two keys are mapped to the
same index by the hash function
The methods to deal with the collision
Open addressing
– Inserting the collided new items in successive buckets
– Will cause a significant degradation in performance and
make delete operation difficult
Separate chaining
– Each bucket is a linear list; collisions are resolved by
inserting the new item into the bucket list
Perhaps it is the best scheme for compiler
construction
6.3.2 Declarations
Basic kinds of declarations
Constant declarations (Value bindings)
– Associate values to names,is single assignment.
– const int SIZE = 199 ;
Type declarations
– Bind names to newly constructed types and may also
create aliases for existing named types
– Type names are usually used in conjunction with a
type equivalence algorithm to perform type checking
of a program
Struct Entry
{char * name;
int count;
struct Entry *next ;};
Variable declarations
– Bind names to data types,
Integer a,b[100]
– An attribute of variables related to scope
that is also implicitly or explicitly bound is the
allocation of memory for the declared variable
and the duration during execution of the allocation
(lifetime or extent of the declaration)
int count(void)
{static int counter = 0;
return ++counter;}
int count(void)
{extern int counter = 0;
return ++counter;}
Procedure/function declarations
– Include explicit and implicit declarations
Definition and Declaration
The strategies:
– Use one symbol table to hold the names from
all the different kinds of declarations.
– Use a different symbol table for each kind of
declaration.
6.3.3 Scope Rules and Block
Structure
Two rules:
Declaration before use
– Without this rule one-pass compilation is impossible
The most closely nested rule for block structure
– Block,any construct that can contain declarations,such
as procedure/function declarations,
– A language is block structured:
(1) If it permits the nesting of blocks inside other blocks;
(2) If the scope of declarations in a block are limited to
that block and other block contained in that block,
T he m ost c los e ly n e ste d r u le,
G iven se ve ra l dif fe r e nt d e c lar a ti ons for th e sa me na me,the d e c la ra ti on tha t
a ppli e s to a re fe r e nc e is the one in the most c losel y ne st e d block to the
re fe re nc e,
I nt i,j ;
I nt f (int si z e )
{ c ha r i,te mp;
…
{double j;
…
}
{c ha r * j;
…
}
}
F ig 6.14
F or e a c h n a me,the li nke d li sts in e a c h buc ke t be h a ve a s a stac k for
the dif fe r e nt dec l a ra ti ons of that na me,
I n d i c e s b u c k e t s l i s t s o f i t e m s
( a ) A f t e r p r o c e s s i n g t h e d e c l a r a t i o n s o f t h e b o d y o f f
1
2
3
4
5
i (c h a r) i (in t)
S ize (in t) j (in t)
tem p (c h a r)
F (f u n c ti o n )
I ndic e s buc k e ts li sts o f items
(b) A fte r pr o c e ss ing the de c lar a ti ons of the sec ond ne st e d
c ompound st a teme nt wit hin t he bod y of f
I (c h a r) i (in t) 1
J(c h a r * ) siz e (in t) 2
3
tem p (c h a r) 4
F (f u n c ti o n ) 5
j (in t)
I n d i c e s b u c k e t s l i s t s o f i t e m s
( c ) A f t e r e x i t i n g t h e b o d y o f f ( a n d d e l e t i n g i t s d e c l a r a t i o n s )
I n fa c t it is ne c e ssa r y to ke e p the de c lar a ti ons in the table (a t lea s t
not to de - a ll oc a t e their memor y ),so the d e lete ope ra ti on is sim pl y t o
mar k them a s no l on g e r a c ti ve,
I (in t) 1
j(i n t) 2
3
4
F (f u n c ti o n ) 5
The other solutions to the implementation of
nested scopes:
– Build a new symbol table for each scope and to link
the tables from inner to outer scopes together,
– Lookup operation will automatically continue the
search with an enclosing table if it fails to find a name
in the current table.
– Leaving a scope simply requires resetting the access
pointer to the next outermost scope.
I(char) j(int)
Size(int) j(int)
temp(char)
F(function)
j(char *)
Additional processing and attribute computation may
also be necessary during the construction of the symbol
table depending on the language and the details of the
compiler operations.
For example in the following Pascal code:
Program Ex;
Var i,j,integer;
Function f(size:integer):integer;
Var i,temp:char;
Procedure g
Var j,real;
Begin
…
end;
Procedure h;
Var j:^char;
Begin
…
End
Begin
…
end
begin (*main program*)
…
end
Identify each scope by a name and to prefix each name
declared within a scope by its accumulated nested scope
names,Thus,all occurrence of the name j would be
distinguished as
Ex.j Ex.f.g.j and Ex.f.h.j
or assign a nesting level or nesting depth to each scope and
record in each symbol table entry the nesting level of each
name.
Static scope,
– The standard scope rule that follows the textual structure of the
program
Dynamic scope,
– Requires the application of nested scopes follow the execution path,
rather than the textual layout of the program.
Example:
#include <stdio.h>
int I = 1;
void f(void)
{printf(“%d\n”,i);
}
void main(void)
{int I=2;
f();
return 0;
}
Static,1
Dynamic,2
6.3.4 Interaction of Same-Level
Declarations
Interaction among declarations at the same
nesting level can vary with the kind of declaration
and with the language being translated
One typical requirement:
– No reuse of the same name in declarations at the
same level
Typedef int i;
Int i;
– The above declaration will cause an error.
Solution:
– Lookup before each insert and determine by some
mechanism.
Int i = 1;
Void f(void)
{ int i = 2,j = i+1
… }
j should be initialized to the value 2 or 3?
Solution:
– By the most closely nested rule,the local declaration is
used,j should be 3.
– Sequential declaration,each declaration is added to
the symbol table as it is processed.
Collateral declaration,
– Declarations not be added immediately to the existing symbol table,
but accumulated in a new table (or temporary structure),
– and then added to the existing table after all declarations have been
processed
Recursive declaration,
– Declaration may refer to themselves or each other,(particularly
necessary for procedure/function declarations)
Int gcd(int n,int m)
{if (m = = 0) return n;
else return gcd(m,n%m)
}
– The compiler should add the function name gcd to the symbol
table before processing the body of the function.
Void f(viod)
{ … g() … }
Void g(viod)
{ … f() … }
It needs a scope modifier,adds a function prototype
declaration to extent the scope of the name g to include f,
Just as follows.
Void g(void); /* function prototype declaration */
Void f(void)
{ … g() … }
Void g(void)
{ … f() … }
Other solutions to mutual recursion
– (The compiler should add the procedure/function name to the
symbol table before processing the body of the procedure/function.)
– Provide forward declaration to extend procedure/function scope;
– The scope rule must be extended to the entire block of the
declarations.
6.3.5 An Extended Example of An
Attribute Grammar Using a Symbol
Table
An example:
– S?exp
– Exp?(exp) | exp + exp | id | num | let dec-list in exp
– Dec-list?dec-list,decl | decl
– Decl? id = exp
Assume the ambiguities have been dealt with at
parser time and the syntax tree has been
constructed
– Exp? let dec-list in exp
The declarations inside a let expression represent a
kind of constant declaration,Such as
– let x = 2+1,y=3+4 in x+y
Scope rules:
1,No redeclaration of the same name within the same let
expression,
such as let x = 2,x= 3 in x+1 (illegal)
2,Any name not declared in some surrounding let expression
caused an error,
such as let x = 2 in x+y
3,The scope of each declaration in a let expression extends
over the body of the let according to the most closely
nested rule for block structure,
Such as let x = 2 in (let x = 3 in x),the value is 3
4,Each declaration uses the previous declarations to resolve
names within its own expression,
Such as let x = 2,y = x+1 in (let x = x+y,y = x+y in y)
the first y is 3,second x is 5,second y is 8
Attribute equations that use a symbol table to keep
track of the declarations in let expressions
and that express the scope rules and interactions
just described are as follows.
(Only use the symbol table to determine whether
an expression is erroneous or not)
Three attributes:
– Err,Synthesize attribute,represent whether the
expression is erroneous;
– Symbol,Inherited attribute,represent the symbol table;
– Nestlevel,Inherited attribute,nonnegative integer,
represent the current nesting level of the let blocks.
Functions:
– Insert(s,n,l),
Returns a new symbol table containing all the
information from symbol table s and in addition
associating the name n with the nesting level l,without
changing s
– Isin(s,n),
Return a Boolean value depending on whether n is in
symbol table s or not.
– Lookup(s,n),
Return an integer value giving the nesting level of the
most recent declaration of n,if it exists,or –1,if n is
not in the symbol table s.
I nit ial s y mbol table that ha s no e ntrie s is e mpt y t a ble,
Gr a mm a r Rule S e mantic Rul e s
S? e x p e x p.s y mt a b = e mpt y table
E x p,n e s t l e v e l = 0
S,e r r = e x p,e r r
Ex p1? e x p2+ e x p3 e x p2.s y mt a b= e x p1.s y mt a b
E x p 3,s y m t a b = e x p 1,s y m t a b
E x p 2,n e s t l e v e l = e x p 1,n e s t l e v e l
E x p 3,n e s t l e v e l = e x p 1,n e s t l e v e l
E x p 1,e r r = e x p 2,e r r o r e x p 3,e r r
Ex p1? (e x p2) Ex p2.s y mt a b= e x p1.s y mt a b
Ex p2.ne s tl e ve l=e x p1.ne stl e ve l
E x p 1,e r r = e x p 2,e r r
Ex p? id e x p.e rr = not i sin(e x p.s y mt a b,id.n a me)
Ex p? num e x p.e rr = f a lse
Ex p1? let de c - li st i n e x p 2 de c - li st.i ntab= e x p1.s y mt a b
De c - li st,ne stl e ve l=e x p1.ne stl e ve l + 1
E x p 2,s y m t a b = d e c - li st.out tab
E x p 2,n e s t l e v e l = d e c - li st.nestl e ve l
E x p 1,e r r = ( d e c - li st.out tab= e rr t a b) or e x p2.e rr
De c - li st1? d ec - li st2,dec l de c - li st2.i ntab= de c - li st1.i ntab
D e c - li st2,ne stl e ve l=de c - li st1.nestl e ve l
D e c l,i n t a b = d e c - li st2.ou tt a b
d e c l,n e s t l e v e l = d e c - li st2.nestl e ve l
d e c l - li st1.ou tt a b= de c l.out tab
de c - li st? de c l de c l.i nta b = de c - li st.i ntab
d e c l,n e s t l e v e l = d e c - li st.nestl e ve l
d e c - li st.out tab= de c l.out t ab
de c l? id = e x p e x p.s y mt a b = de c l.i ntab
e x p,n e s t l e v e l = d e c l,n e s t l e v e l
d e c l,o u t t a b =
i f ( d e c l,i n t a b = e r r t a b ) o r e x p,e r r
t h e n e r r t a b
e l s e i f ( l o o k u p ( d e c l,i n t a b,i d,n a m e ) =
d e c l,n e s t l e v e l )
t h e n e r r t a b
e lse inse rt( de c l.i ntab,id.na me,d e c l,ne stl e ve l)
6.4 Data Types and Type
Checking
Type inference and type checking is one of the
principal tasks of a compiler,which are closely
related,performed together and referred to simply
as type checking
Data type information can be:
1,Static,such as in C,Pascal,Primarily,
– Used as the principal mechanism for checking the
correctness of a program prior to execution
– Determine the size of memory needed for the allocation
and the way that the memory can be accessed
– Simplify the runtime environment
2,Dynamic,such as in LISP
3,A mixture of the two
Data type forms,
– A set of values with certain operations on those values
These sets can be described by a type expression:
– A type name,integer
– A structured expression,array [1..10] of real
Type information can be explicit and implicit
– For instance var x,array[1..10] or real (explicit)
– Const greeting =,Hello” (implicitly array [1..6] of
char)
Type information is maintained in the symbol
table and retrieved by the type checker
6.4.1 Type Expressions and
Type Constructors
Simple types,
– Such as int,double,Boolean,char.
– The values exhibit no explicit internal structure,and the
typical representation is also simple and predefined.
Void,has no value,represent the empty set
New simply type defined such as subrange types
(Type digit = 0..9)
and enumerated types (typedef enum {red,green,
blue} color),
– can be treated as integers or using a smaller amount of
memory,
Structured type
1,Array,
Two type parameter,
Index type (often limited to so-called ordinal types,types for
which every value has an immediate predecessor and an
immediate successor)
and component type
Produce,a new array type,array [Color] of char
– Array[color] of char;
– Create an array type whose index type is color and whose
component type is char.
An array represents values that are sequences of values of
the component type,indexed by values of the index type
Arrays are commonly allocated contiguous storage from
smaller to larger indexes,to allow for the use of automatic
offset calculations during execution
The amount of memory needed is n * size (n is the
number of values in the index type and size is the amount
of memory needed for a value of the component type)
Multidimensioned arrays:
– Array[0..9] of array[color] of integer
– Array[0..9,color] of integer;
– The sequence of values can be organized in different ways in
memory depending on whether the indexing is done first on the
first index,and then on the second index,or vice versa.
Open-indexed array,whose index range is unspecified,
especially useful in the declaration of array parameters to
functions
2,Re c or d
A re c o rd or struc ture t y pe c onst ruc tor take s a li st of na mes a nd a ssocia ted
t y pe s and c onst ruc ts a n e w t y pe,
S truc t
{ double r ;
int i ;}
Dif fe r e nt t y p e s ma y be c ombi ne d a nd the na mes a re us e d to a c c e ss the
dif fe r e nt compone nts,
C a rte sian pr oduc t t y pe c onst ruc tors,i nt*re a l
The standa rd im pleme nta ti on method is to a ll oc a te memor y se qu e nti a ll y,wi th
a block of memor y f o r e a c h c omponent t y pe,
4b y tes 2b y tes
r i
3,Union
C or re spond t o the se t uni on ope ra ti on
Union
{double r ;
int i ;}
D isj oint union,ea c h va lue is vi e we d a s e it he r a re a l or a n int e g e r,
Alloca te me mor y in pa ra ll e l for e a c h c omponent,
r 4 b y tes
i 2 b y tes
Ex,x,r = 2.0;
pr int f(,% d,,x,i);
W il l not c a use a c ompi lation er ror,but wil l not print t he va lue 2,
The insecurity in union type has been addressed by many
different language design.
In pascal,for instance
Record case isReal,boolean of
True,(r,real);
False,(I,integer);
End
Whenever a union component is assigned,the discriminant
must be simultaneously assigned with a value that can be
checked for legality.
A different approach is taken by functional languages such
as the language ML:
IsReal of real | IsInteger of int
Value constructor IsReal and IsInteger must be used
whenever a value of this type is used.
4,Pointer
Values that are references to values of another type
A value of a pointer type is a memory address whose
location holds a value of its base type.
^integer in Pascal;
int* in C.
Allocated space based on the address size of the
target machine
It is most useful in describing recursive types.
5,Function
An array can be viewed as a function from its
index set to its component set.
Many languages have a more general ability to
describe function types.
Var f,procedure (integer),integer;
in Modula-2
Int (*f) (int);
in C
The allocated space depends on the address size of
the target machine,According to the language and
the organization of the runtime environment,
it should allocate for a code pointer alone or a
code pointer and an environment pointer.
6,Class
Similar to a record declaration,except it
includes the definition of operations (methods or
member functions)
Beyond type system such as inheritance and
dynamic binding,must be maintained by
separate data structures
6.4.2 Type Names,Type
Declarations and Recursive Types
Type declarations (type definition),mechanism for a
programmer to assign names to type expressions,
– Such as,typedef,=,associated directly with a struct or union
constructor
typedef struct
{double r;
int I;
} RealIntRec; (C)
type RealIntRec = real * int (ML)
struct RealIntRec
{double r;
int I;
} (C)
Type declarations cause the declared type names to
be entered into the symbol table just as variable
declarations,
Usually the type names can’t be reused as variable
names (except allowed by the scope nesting rules),
but the name associated to struct or union
declarations can be reused as typedef names.
Struct RealIntRec
{double r;
int I;
};
Typedef struct RealIntRec RealIntRec; (legal)
Recursive data types are extremely important include lists,trees,and
many other structures.
Permit the direct use of recursion in type declarations such as ML.
Datatype intBST = Nil | Node of int*intBST*intBST
The union of the value Nil with the Cartesian product of the integers
with two copies of intBST itself
– (one for the left subtree and one for the right subtree)
The equivalent C declaration (in slightly altered form) is
Struct intBST
{int isNull;
int val;
struct intBST left,right;
};
The declaration will generate an error message in C.
Allow recursion only indirectly through pointers,Such as C.
Struc intBST
{int val;
struct intBST *left,*right;
}
typedef struct intBST * intBST;
or
typedef struct intBST * intBST;
Struc intBST
{int val;
intBST left,right;
}
6.4.3 Type Equivalence
T y p e e quivale n c e,t wo t y pe e x pr e ssi on s r e pr e s e nt the sa me t y p e
F unc ti on t y p e E qua l(t1,t 2,T y pe Ex p),B oole a n
T y p e re p re se ntation,use a s y ntax tre e re pr e se ntati on to ex pr e ss t y pe e x pr e s sions,
F or e x a mpl e,t he t y p e e x pr e ssi on
R e c or d
X,point e r to r e a l;
Y,ar ra y [ 10] of int ;
End
This t y pe e x pr e ssi on c a n be r e pr e se nted b y the s y n tax tre e
r ecor d
V ar ( y )
V ar ( x)
A r r ay ( 10) poi nt er
i nt r eal
A sim ple gr a mm a r for t y pe e x pr e ssi ons,
V a r - d e c ls → va r - de c ls; v a r - de c l | va r - de c l
V a r - d e c l → id,t y p e - e x p
T y p e - e x p → sim ple - t y pe |struc ture d - t y pe
S im ple - t y p e → in t | b ool|r e al | c h ar | void
S truc ture d - t y pe → a r r ay [ n u m ] of t y p e - e x p |
Re c or d va r - de c ls e n d |
Uni on va r - de c ls e n d |
P oin te r t o t y p e - e x p |
Pr oc (t y p e - e x ps) t y p e - e x p
T y p e - e x ps → t y pe - e x ps,t y pe - e x p | t y pe - e x p
Another t yp e e xp r e ssi o n,
P roc ( bool,uni on a,re a l; b,cha r e nd,int ),void
C a n be r e pr e se nted b y th e f oll owing s y ntax tre e,
T h e f irst t yp e of e q u ival e n c e i s str u c tural e q u ival e n c e
( I n the a bsen c e o f na mes for t y p e s)
I f a nd onl y if the y ha v e s y n tax tre e s that a re identi c a l i n st ruc ture
uni on i nt B ool
V ar ( b) V ar ( q)
char r eal
pr oc
v oi d
T he pseud ocod e f or a t yp e E qu al f uncti on
F unc ti on t y p e Equa l(t1,t 2,T y pe Ex p),B oole a n,
V a r te mp,boolea n;
P 1,p2,T y pe Ex p;
B e g in
I f t1 and t2 a r e of simpl e t y pe then re turn t1= t2;
Else if t1.ki nd = a rr a y a n d t2.ki nd = a rr a y th e n
R e turn t1.si z e = t2.si z e a nd t y pe Equ a l(t1.c hil d1,t2.child1)
Else if t1.ki nd = r e c o rd a nd t2.kond = r e c o rd
Or t1.ki nd = union and t2,kond = union then
B e g in
P 1,=t1.c hil d1;
P 2,=t2.c hil d1;
T e mp,= true ;
W hil e temp a nd p1 ! = nil a nd P 2! = nil do
I f p1.na me ! = p2.na me th e n
T e mp,= f a lse
Else if not t y pe Equ a l(p1,c hil d1,p2.c hil d1)
The n temp,=f a lse
Else be g in
P 1:=p1.sibl ing ;
P 2:=p2.si bli ng ;
End;
R e turn temp a nd p1 = nil a nd p2 = nil ;
End
Else if t1.ki nd = point e r a nd t2.ki nd = point e r the n
R e turn t y pe Equ a l(t1.c hil d1,t2.child1)
Else if t1.ki nd = proc a nd t2.ki nd = proc then
B e g in
P 1,=t1.c hil d1;
P 2,= t2.c hil d1;
T e mp,= true ;
W hil e temp a nd p1 ! = nil a nd p2 ! = nil do
I f not t y p e Equa l(p1,c hil d1,p2.c hil d1)
The n temp,=f a lse
Else be g in
P 1:=p1.sibl ing ;
P 2:=p2.sibl ing ;
End;
R e turn temp a nd p1 = nil a nd p2 = nil
a nd t y p e Equa l(t1.c hil d2,t 2.c hil d2);
End
Else r e turn f a ls e
End;
A gr a m m ar f or t yp e e x p r e ssi on s w ith typ e d e c l ar at ion s,
V a r - d e c ls → va r - de c ls; v a r - de c l | va r - de c l
V a r - d e c l → id,sim pe - t y pe - e x p
T y p e - de c ls → t y pe - de c ls; t y pe - d e c l | t y pe - d e c l
T y p e - de c l → id,t y pe - e x p
T y p e - e x p → sim ple - t y pe - e x p | struc tur e d - t y pe
S im ple - T y pe - e x p → sim ple - t y p e | id
S im ple - t y p e → in t | b ool|r e al | c h ar | void
S truc ture d - t y pe → a r r ay [ n u m ] of simpl e - t y p e - e x p |
Re c or d va r - de c ls e n d |
Uni on va r - de c ls e n d |
P oin te r t o sim ple - t y pe - e x p|
Pr oc (t y p e - e x ps) sim ple - ty p e - e x p
T y p e - e x ps → t y pe - e x ps,si mpl e - t y pe - e x p | sim ple - t y p e - e x p
Name equivalence,
Two type expressions are equivalent if and only if
they are either the same simple type or are the
same type name.
For example:
T1=int;
T2=int;
The types of t1 and t2 are not equivalence and not
equivalence to int.
Function typeEqual(t1,t2:typeexp):Boolean:
Var temp,boolean;
P1,p2,typeExp;
Begin
If t1 and t2 are of simple type then
Return t1 = t2
Else if t1 and t2 are type names then
Return t1 = t2
Else return false;
End;
It is possible to retain structural equivalence in the
presence of type name.
By adding the following case to the above mentioned code
Else if t1 and t2 are type name then
Return typeEqual(getTypeExp(t1),getTypeExp(t2)).
Care must be taken in implementing structural equivalence
when recursive type references are possible,since the
algorithm just described can result in an infinite loop.
For example:
T1 = record
X,int;
T,pointer to t2;
End;
T2 =record
X:int;
T:pointer to t1;
End;
Modify typeEqual(t1,t2) to include the assumption that
they are already potentially equal.
Declaration equivalence:
(Pascal and struct and union in C)
Every type name is equivalent to some base type name,
which is either a predefined type or is given by a type
expression resulting from the application of a type
constructor.
For example:
T1=int;
T2=int;
Both t1 and t2 are equivalent to int.
For example:
T1=array [10] of int;
T2=array [10] of int;
T3=t1;
T1 and t3 are equivalence,but neither is equivalence to t2
Pascal uses declaration equivalence while C
uses declaration equivalence for structures and
unions and structural equivalence for pointers
and arrays
Occasionally,a language will offer a choice of
structural,declarations,or name equivalence,
where different type declarations are used for
different forms of equivalence.
6.4.4 Type Inference and Type
Checking
T y p e c he c ke r is ba se d on a r e pr e s e ntation o f t y p e s a nd a t y pe Equ a l
ope ra ti ons,
C onsi de r a sim ple g r a m mar a s follows,
pr ogra m? va r - de c ls; stm ts
va r - de c ls? va r - d e c ls; va r - de c l | v a r - d e c l
va r - de c l? id,t y pe - e x p
t y pe - e x p? int | bool | a rr a y [ num ] of t y pe - e x p
stm t s? stm ts; stm t| stm t
stm t? if e x p then st mt | id,= e x p
1,D e c lar a ti ons,c a us e the t y p e of a n identifie r to be e nter e d int o the s y mbol
table
2,S tate ments,subst ruc ture s will ne e d to be c he c ke d for t y p e c or re c tness
3,E x pr e ssi on,va ria ble na me ha ve their t y pe s de t e r mi ne d b y a look up in t he
s y mbol table,the othe r e x pr e ssi on a re f or med b y ope ra tors,
Note,How a bout t he be h a vior of t y pe c h e c k e r in pr e se nc e of e rr or s,
Gr a mm a r Rule S e mantic Rul e s
V a r - d e c l? id,t y pe - e x p inser t(id.na me,t y p e - e x p.t y p e )
T y p e - e x p? int t y pe - e x p.t y p e,=inte g e r
T y p e - e x p? bool t y p e - e x p.t y p e,=boole a n
T y p e - e x p1? a rr a y [ num] of t y pe - e x p2 t y p e - e x p1.t y pe,=
Make t y p e node (a r ra y,
num.s iz e,t y pe - e x p2.t y pe )
S tm t? if e x p then stm t if not t y pe qu a l(e x p.t y pe,boole a n)
T h e n t y p e - e rr o r( stm t)
S tm t? id,= e x p if not t y pe qua l(lookup(id.na me),e x p.t y pe )
T h e n t y p e - e rr o r( stm t)
Ex p1? e x p2+ e x p3 if not t y pe qua l(e x p2.t y pe,int e g e r)
a n d t y p e q u a l ( e x p 3,t y p e,i n t e g e r )
T h e n t y p e - e rr o r( e x p1)
E x p 1,t y p e,= i n t e g e r
Ex p1? e x p2 or e x p3 if not t y pe q ua l(e x p2.t y pe,boole a n)
a n d t y p e q u a l ( e x p 3,t y p e,b o o l e a n )
T h e n t y p e - e rr o r( e x p1)
E x p 1,t y p e,= b o o l e a n
Ex p? num e x p,t y p e,= i n t e g e r
Ex p? true e x p,t y pe,= bool e a n
Ex p? fa lse e x p,t y pe,=bool e a n
Ex p? id e x p,t y pe,=lookup( id.n a me)
6.4.5 Additional Topics in Type
Checking
1,Overloading
– Procedure max(x,y,integer),integer;
– Procedure max(x,y,real),integer.
Solutions:
– Augment the lookup procedure of the symbol
table with type parameters,allowing the
symbol table to find the right match;
– For the symbol table to maintain sets of
possible types for names and to return the set
to the type checker for disambiguation
2,Type conversion and coercion
– For example:
2.1 + 3
Solutions:
– operations must be applied to convert the
values at runtime to the appropriate
representations before applying the operator;
– supply the conversion operation
automatically,based on the types of the sub-
expressions (coercion)
3,Polymorphic typing
Procedure swap( var x,y:anytype);
Var x,y,integer;
a,b,char;
…
swap(x,y);
swap(a,b);
swap(a,x);
The type checking will involve sophisticated
pattern matching techniques.
6.5 A Semantic Analyzer for
the TINY Language
End of Part Two
THANKS
Principles and Practice
Kenneth C,Louden
6,Semantic Analysis
PART TWO
Contents
Part One
6.1 Attributes and Attribute Grammars
6.2 Algorithms for Attribute Computation
Part Two
6.3 The Symbol Table
6.4 Data Types and Type Checking
6.5 A Semantic Analyzer for the TINY Language
6.3 The Symbol Table
Symbol table,major inherited attribute and major
data structure in a compiler
Principal operations,
– Insert,store the information provided by name
declarations when processing these declarations
– Lookup,retrieve the information associated to a name
when that name is used in the associated code.
– Delete,remove the information provided by a
declaration when that declaration no longer applies.
Information stored:
– Include data type information,information on region of
applicability (scope),and information on eventual
location in memory.
6.3.1 The Structure of The
Symbol Table
Typical dictionary data structure
Linear list
– Provide easy and direct implementations of the three
basic operations;
– Operation time is linear in the size of the list;
– Good for a compiler implementation in which speed is
not a major concern such as a prototype or experimental
compiler or an interpreter for a very small program.
Various search tree structures
– (binary search trees,AVL trees,B trees)
– Don't provide best case efficiency;
– The delete operation is very complexity;
– Less useful.
Hash tables
– All three operation can be performed in almost
constant time
– Most frequently in practice,best choice
Main idea
– An array of entries (called buckets),indexed by an
integer range
– A hash function turns the search key into an integer
hash value in the index range
– And the item corresponding to the search key is
stored in the bucket at this index
– The efficiency greatly depends on the design of the
hash function
Main problem
– Collision resolution,two keys are mapped to the
same index by the hash function
The methods to deal with the collision
Open addressing
– Inserting the collided new items in successive buckets
– Will cause a significant degradation in performance and
make delete operation difficult
Separate chaining
– Each bucket is a linear list; collisions are resolved by
inserting the new item into the bucket list
Perhaps it is the best scheme for compiler
construction
6.3.2 Declarations
Basic kinds of declarations
Constant declarations (Value bindings)
– Associate values to names,is single assignment.
– const int SIZE = 199 ;
Type declarations
– Bind names to newly constructed types and may also
create aliases for existing named types
– Type names are usually used in conjunction with a
type equivalence algorithm to perform type checking
of a program
Struct Entry
{char * name;
int count;
struct Entry *next ;};
Variable declarations
– Bind names to data types,
Integer a,b[100]
– An attribute of variables related to scope
that is also implicitly or explicitly bound is the
allocation of memory for the declared variable
and the duration during execution of the allocation
(lifetime or extent of the declaration)
int count(void)
{static int counter = 0;
return ++counter;}
int count(void)
{extern int counter = 0;
return ++counter;}
Procedure/function declarations
– Include explicit and implicit declarations
Definition and Declaration
The strategies:
– Use one symbol table to hold the names from
all the different kinds of declarations.
– Use a different symbol table for each kind of
declaration.
6.3.3 Scope Rules and Block
Structure
Two rules:
Declaration before use
– Without this rule one-pass compilation is impossible
The most closely nested rule for block structure
– Block,any construct that can contain declarations,such
as procedure/function declarations,
– A language is block structured:
(1) If it permits the nesting of blocks inside other blocks;
(2) If the scope of declarations in a block are limited to
that block and other block contained in that block,
T he m ost c los e ly n e ste d r u le,
G iven se ve ra l dif fe r e nt d e c lar a ti ons for th e sa me na me,the d e c la ra ti on tha t
a ppli e s to a re fe r e nc e is the one in the most c losel y ne st e d block to the
re fe re nc e,
I nt i,j ;
I nt f (int si z e )
{ c ha r i,te mp;
…
{double j;
…
}
{c ha r * j;
…
}
}
F ig 6.14
F or e a c h n a me,the li nke d li sts in e a c h buc ke t be h a ve a s a stac k for
the dif fe r e nt dec l a ra ti ons of that na me,
I n d i c e s b u c k e t s l i s t s o f i t e m s
( a ) A f t e r p r o c e s s i n g t h e d e c l a r a t i o n s o f t h e b o d y o f f
1
2
3
4
5
i (c h a r) i (in t)
S ize (in t) j (in t)
tem p (c h a r)
F (f u n c ti o n )
I ndic e s buc k e ts li sts o f items
(b) A fte r pr o c e ss ing the de c lar a ti ons of the sec ond ne st e d
c ompound st a teme nt wit hin t he bod y of f
I (c h a r) i (in t) 1
J(c h a r * ) siz e (in t) 2
3
tem p (c h a r) 4
F (f u n c ti o n ) 5
j (in t)
I n d i c e s b u c k e t s l i s t s o f i t e m s
( c ) A f t e r e x i t i n g t h e b o d y o f f ( a n d d e l e t i n g i t s d e c l a r a t i o n s )
I n fa c t it is ne c e ssa r y to ke e p the de c lar a ti ons in the table (a t lea s t
not to de - a ll oc a t e their memor y ),so the d e lete ope ra ti on is sim pl y t o
mar k them a s no l on g e r a c ti ve,
I (in t) 1
j(i n t) 2
3
4
F (f u n c ti o n ) 5
The other solutions to the implementation of
nested scopes:
– Build a new symbol table for each scope and to link
the tables from inner to outer scopes together,
– Lookup operation will automatically continue the
search with an enclosing table if it fails to find a name
in the current table.
– Leaving a scope simply requires resetting the access
pointer to the next outermost scope.
I(char) j(int)
Size(int) j(int)
temp(char)
F(function)
j(char *)
Additional processing and attribute computation may
also be necessary during the construction of the symbol
table depending on the language and the details of the
compiler operations.
For example in the following Pascal code:
Program Ex;
Var i,j,integer;
Function f(size:integer):integer;
Var i,temp:char;
Procedure g
Var j,real;
Begin
…
end;
Procedure h;
Var j:^char;
Begin
…
End
Begin
…
end
begin (*main program*)
…
end
Identify each scope by a name and to prefix each name
declared within a scope by its accumulated nested scope
names,Thus,all occurrence of the name j would be
distinguished as
Ex.j Ex.f.g.j and Ex.f.h.j
or assign a nesting level or nesting depth to each scope and
record in each symbol table entry the nesting level of each
name.
Static scope,
– The standard scope rule that follows the textual structure of the
program
Dynamic scope,
– Requires the application of nested scopes follow the execution path,
rather than the textual layout of the program.
Example:
#include <stdio.h>
int I = 1;
void f(void)
{printf(“%d\n”,i);
}
void main(void)
{int I=2;
f();
return 0;
}
Static,1
Dynamic,2
6.3.4 Interaction of Same-Level
Declarations
Interaction among declarations at the same
nesting level can vary with the kind of declaration
and with the language being translated
One typical requirement:
– No reuse of the same name in declarations at the
same level
Typedef int i;
Int i;
– The above declaration will cause an error.
Solution:
– Lookup before each insert and determine by some
mechanism.
Int i = 1;
Void f(void)
{ int i = 2,j = i+1
… }
j should be initialized to the value 2 or 3?
Solution:
– By the most closely nested rule,the local declaration is
used,j should be 3.
– Sequential declaration,each declaration is added to
the symbol table as it is processed.
Collateral declaration,
– Declarations not be added immediately to the existing symbol table,
but accumulated in a new table (or temporary structure),
– and then added to the existing table after all declarations have been
processed
Recursive declaration,
– Declaration may refer to themselves or each other,(particularly
necessary for procedure/function declarations)
Int gcd(int n,int m)
{if (m = = 0) return n;
else return gcd(m,n%m)
}
– The compiler should add the function name gcd to the symbol
table before processing the body of the function.
Void f(viod)
{ … g() … }
Void g(viod)
{ … f() … }
It needs a scope modifier,adds a function prototype
declaration to extent the scope of the name g to include f,
Just as follows.
Void g(void); /* function prototype declaration */
Void f(void)
{ … g() … }
Void g(void)
{ … f() … }
Other solutions to mutual recursion
– (The compiler should add the procedure/function name to the
symbol table before processing the body of the procedure/function.)
– Provide forward declaration to extend procedure/function scope;
– The scope rule must be extended to the entire block of the
declarations.
6.3.5 An Extended Example of An
Attribute Grammar Using a Symbol
Table
An example:
– S?exp
– Exp?(exp) | exp + exp | id | num | let dec-list in exp
– Dec-list?dec-list,decl | decl
– Decl? id = exp
Assume the ambiguities have been dealt with at
parser time and the syntax tree has been
constructed
– Exp? let dec-list in exp
The declarations inside a let expression represent a
kind of constant declaration,Such as
– let x = 2+1,y=3+4 in x+y
Scope rules:
1,No redeclaration of the same name within the same let
expression,
such as let x = 2,x= 3 in x+1 (illegal)
2,Any name not declared in some surrounding let expression
caused an error,
such as let x = 2 in x+y
3,The scope of each declaration in a let expression extends
over the body of the let according to the most closely
nested rule for block structure,
Such as let x = 2 in (let x = 3 in x),the value is 3
4,Each declaration uses the previous declarations to resolve
names within its own expression,
Such as let x = 2,y = x+1 in (let x = x+y,y = x+y in y)
the first y is 3,second x is 5,second y is 8
Attribute equations that use a symbol table to keep
track of the declarations in let expressions
and that express the scope rules and interactions
just described are as follows.
(Only use the symbol table to determine whether
an expression is erroneous or not)
Three attributes:
– Err,Synthesize attribute,represent whether the
expression is erroneous;
– Symbol,Inherited attribute,represent the symbol table;
– Nestlevel,Inherited attribute,nonnegative integer,
represent the current nesting level of the let blocks.
Functions:
– Insert(s,n,l),
Returns a new symbol table containing all the
information from symbol table s and in addition
associating the name n with the nesting level l,without
changing s
– Isin(s,n),
Return a Boolean value depending on whether n is in
symbol table s or not.
– Lookup(s,n),
Return an integer value giving the nesting level of the
most recent declaration of n,if it exists,or –1,if n is
not in the symbol table s.
I nit ial s y mbol table that ha s no e ntrie s is e mpt y t a ble,
Gr a mm a r Rule S e mantic Rul e s
S? e x p e x p.s y mt a b = e mpt y table
E x p,n e s t l e v e l = 0
S,e r r = e x p,e r r
Ex p1? e x p2+ e x p3 e x p2.s y mt a b= e x p1.s y mt a b
E x p 3,s y m t a b = e x p 1,s y m t a b
E x p 2,n e s t l e v e l = e x p 1,n e s t l e v e l
E x p 3,n e s t l e v e l = e x p 1,n e s t l e v e l
E x p 1,e r r = e x p 2,e r r o r e x p 3,e r r
Ex p1? (e x p2) Ex p2.s y mt a b= e x p1.s y mt a b
Ex p2.ne s tl e ve l=e x p1.ne stl e ve l
E x p 1,e r r = e x p 2,e r r
Ex p? id e x p.e rr = not i sin(e x p.s y mt a b,id.n a me)
Ex p? num e x p.e rr = f a lse
Ex p1? let de c - li st i n e x p 2 de c - li st.i ntab= e x p1.s y mt a b
De c - li st,ne stl e ve l=e x p1.ne stl e ve l + 1
E x p 2,s y m t a b = d e c - li st.out tab
E x p 2,n e s t l e v e l = d e c - li st.nestl e ve l
E x p 1,e r r = ( d e c - li st.out tab= e rr t a b) or e x p2.e rr
De c - li st1? d ec - li st2,dec l de c - li st2.i ntab= de c - li st1.i ntab
D e c - li st2,ne stl e ve l=de c - li st1.nestl e ve l
D e c l,i n t a b = d e c - li st2.ou tt a b
d e c l,n e s t l e v e l = d e c - li st2.nestl e ve l
d e c l - li st1.ou tt a b= de c l.out tab
de c - li st? de c l de c l.i nta b = de c - li st.i ntab
d e c l,n e s t l e v e l = d e c - li st.nestl e ve l
d e c - li st.out tab= de c l.out t ab
de c l? id = e x p e x p.s y mt a b = de c l.i ntab
e x p,n e s t l e v e l = d e c l,n e s t l e v e l
d e c l,o u t t a b =
i f ( d e c l,i n t a b = e r r t a b ) o r e x p,e r r
t h e n e r r t a b
e l s e i f ( l o o k u p ( d e c l,i n t a b,i d,n a m e ) =
d e c l,n e s t l e v e l )
t h e n e r r t a b
e lse inse rt( de c l.i ntab,id.na me,d e c l,ne stl e ve l)
6.4 Data Types and Type
Checking
Type inference and type checking is one of the
principal tasks of a compiler,which are closely
related,performed together and referred to simply
as type checking
Data type information can be:
1,Static,such as in C,Pascal,Primarily,
– Used as the principal mechanism for checking the
correctness of a program prior to execution
– Determine the size of memory needed for the allocation
and the way that the memory can be accessed
– Simplify the runtime environment
2,Dynamic,such as in LISP
3,A mixture of the two
Data type forms,
– A set of values with certain operations on those values
These sets can be described by a type expression:
– A type name,integer
– A structured expression,array [1..10] of real
Type information can be explicit and implicit
– For instance var x,array[1..10] or real (explicit)
– Const greeting =,Hello” (implicitly array [1..6] of
char)
Type information is maintained in the symbol
table and retrieved by the type checker
6.4.1 Type Expressions and
Type Constructors
Simple types,
– Such as int,double,Boolean,char.
– The values exhibit no explicit internal structure,and the
typical representation is also simple and predefined.
Void,has no value,represent the empty set
New simply type defined such as subrange types
(Type digit = 0..9)
and enumerated types (typedef enum {red,green,
blue} color),
– can be treated as integers or using a smaller amount of
memory,
Structured type
1,Array,
Two type parameter,
Index type (often limited to so-called ordinal types,types for
which every value has an immediate predecessor and an
immediate successor)
and component type
Produce,a new array type,array [Color] of char
– Array[color] of char;
– Create an array type whose index type is color and whose
component type is char.
An array represents values that are sequences of values of
the component type,indexed by values of the index type
Arrays are commonly allocated contiguous storage from
smaller to larger indexes,to allow for the use of automatic
offset calculations during execution
The amount of memory needed is n * size (n is the
number of values in the index type and size is the amount
of memory needed for a value of the component type)
Multidimensioned arrays:
– Array[0..9] of array[color] of integer
– Array[0..9,color] of integer;
– The sequence of values can be organized in different ways in
memory depending on whether the indexing is done first on the
first index,and then on the second index,or vice versa.
Open-indexed array,whose index range is unspecified,
especially useful in the declaration of array parameters to
functions
2,Re c or d
A re c o rd or struc ture t y pe c onst ruc tor take s a li st of na mes a nd a ssocia ted
t y pe s and c onst ruc ts a n e w t y pe,
S truc t
{ double r ;
int i ;}
Dif fe r e nt t y p e s ma y be c ombi ne d a nd the na mes a re us e d to a c c e ss the
dif fe r e nt compone nts,
C a rte sian pr oduc t t y pe c onst ruc tors,i nt*re a l
The standa rd im pleme nta ti on method is to a ll oc a te memor y se qu e nti a ll y,wi th
a block of memor y f o r e a c h c omponent t y pe,
4b y tes 2b y tes
r i
3,Union
C or re spond t o the se t uni on ope ra ti on
Union
{double r ;
int i ;}
D isj oint union,ea c h va lue is vi e we d a s e it he r a re a l or a n int e g e r,
Alloca te me mor y in pa ra ll e l for e a c h c omponent,
r 4 b y tes
i 2 b y tes
Ex,x,r = 2.0;
pr int f(,% d,,x,i);
W il l not c a use a c ompi lation er ror,but wil l not print t he va lue 2,
The insecurity in union type has been addressed by many
different language design.
In pascal,for instance
Record case isReal,boolean of
True,(r,real);
False,(I,integer);
End
Whenever a union component is assigned,the discriminant
must be simultaneously assigned with a value that can be
checked for legality.
A different approach is taken by functional languages such
as the language ML:
IsReal of real | IsInteger of int
Value constructor IsReal and IsInteger must be used
whenever a value of this type is used.
4,Pointer
Values that are references to values of another type
A value of a pointer type is a memory address whose
location holds a value of its base type.
^integer in Pascal;
int* in C.
Allocated space based on the address size of the
target machine
It is most useful in describing recursive types.
5,Function
An array can be viewed as a function from its
index set to its component set.
Many languages have a more general ability to
describe function types.
Var f,procedure (integer),integer;
in Modula-2
Int (*f) (int);
in C
The allocated space depends on the address size of
the target machine,According to the language and
the organization of the runtime environment,
it should allocate for a code pointer alone or a
code pointer and an environment pointer.
6,Class
Similar to a record declaration,except it
includes the definition of operations (methods or
member functions)
Beyond type system such as inheritance and
dynamic binding,must be maintained by
separate data structures
6.4.2 Type Names,Type
Declarations and Recursive Types
Type declarations (type definition),mechanism for a
programmer to assign names to type expressions,
– Such as,typedef,=,associated directly with a struct or union
constructor
typedef struct
{double r;
int I;
} RealIntRec; (C)
type RealIntRec = real * int (ML)
struct RealIntRec
{double r;
int I;
} (C)
Type declarations cause the declared type names to
be entered into the symbol table just as variable
declarations,
Usually the type names can’t be reused as variable
names (except allowed by the scope nesting rules),
but the name associated to struct or union
declarations can be reused as typedef names.
Struct RealIntRec
{double r;
int I;
};
Typedef struct RealIntRec RealIntRec; (legal)
Recursive data types are extremely important include lists,trees,and
many other structures.
Permit the direct use of recursion in type declarations such as ML.
Datatype intBST = Nil | Node of int*intBST*intBST
The union of the value Nil with the Cartesian product of the integers
with two copies of intBST itself
– (one for the left subtree and one for the right subtree)
The equivalent C declaration (in slightly altered form) is
Struct intBST
{int isNull;
int val;
struct intBST left,right;
};
The declaration will generate an error message in C.
Allow recursion only indirectly through pointers,Such as C.
Struc intBST
{int val;
struct intBST *left,*right;
}
typedef struct intBST * intBST;
or
typedef struct intBST * intBST;
Struc intBST
{int val;
intBST left,right;
}
6.4.3 Type Equivalence
T y p e e quivale n c e,t wo t y pe e x pr e ssi on s r e pr e s e nt the sa me t y p e
F unc ti on t y p e E qua l(t1,t 2,T y pe Ex p),B oole a n
T y p e re p re se ntation,use a s y ntax tre e re pr e se ntati on to ex pr e ss t y pe e x pr e s sions,
F or e x a mpl e,t he t y p e e x pr e ssi on
R e c or d
X,point e r to r e a l;
Y,ar ra y [ 10] of int ;
End
This t y pe e x pr e ssi on c a n be r e pr e se nted b y the s y n tax tre e
r ecor d
V ar ( y )
V ar ( x)
A r r ay ( 10) poi nt er
i nt r eal
A sim ple gr a mm a r for t y pe e x pr e ssi ons,
V a r - d e c ls → va r - de c ls; v a r - de c l | va r - de c l
V a r - d e c l → id,t y p e - e x p
T y p e - e x p → sim ple - t y pe |struc ture d - t y pe
S im ple - t y p e → in t | b ool|r e al | c h ar | void
S truc ture d - t y pe → a r r ay [ n u m ] of t y p e - e x p |
Re c or d va r - de c ls e n d |
Uni on va r - de c ls e n d |
P oin te r t o t y p e - e x p |
Pr oc (t y p e - e x ps) t y p e - e x p
T y p e - e x ps → t y pe - e x ps,t y pe - e x p | t y pe - e x p
Another t yp e e xp r e ssi o n,
P roc ( bool,uni on a,re a l; b,cha r e nd,int ),void
C a n be r e pr e se nted b y th e f oll owing s y ntax tre e,
T h e f irst t yp e of e q u ival e n c e i s str u c tural e q u ival e n c e
( I n the a bsen c e o f na mes for t y p e s)
I f a nd onl y if the y ha v e s y n tax tre e s that a re identi c a l i n st ruc ture
uni on i nt B ool
V ar ( b) V ar ( q)
char r eal
pr oc
v oi d
T he pseud ocod e f or a t yp e E qu al f uncti on
F unc ti on t y p e Equa l(t1,t 2,T y pe Ex p),B oole a n,
V a r te mp,boolea n;
P 1,p2,T y pe Ex p;
B e g in
I f t1 and t2 a r e of simpl e t y pe then re turn t1= t2;
Else if t1.ki nd = a rr a y a n d t2.ki nd = a rr a y th e n
R e turn t1.si z e = t2.si z e a nd t y pe Equ a l(t1.c hil d1,t2.child1)
Else if t1.ki nd = r e c o rd a nd t2.kond = r e c o rd
Or t1.ki nd = union and t2,kond = union then
B e g in
P 1,=t1.c hil d1;
P 2,=t2.c hil d1;
T e mp,= true ;
W hil e temp a nd p1 ! = nil a nd P 2! = nil do
I f p1.na me ! = p2.na me th e n
T e mp,= f a lse
Else if not t y pe Equ a l(p1,c hil d1,p2.c hil d1)
The n temp,=f a lse
Else be g in
P 1:=p1.sibl ing ;
P 2:=p2.si bli ng ;
End;
R e turn temp a nd p1 = nil a nd p2 = nil ;
End
Else if t1.ki nd = point e r a nd t2.ki nd = point e r the n
R e turn t y pe Equ a l(t1.c hil d1,t2.child1)
Else if t1.ki nd = proc a nd t2.ki nd = proc then
B e g in
P 1,=t1.c hil d1;
P 2,= t2.c hil d1;
T e mp,= true ;
W hil e temp a nd p1 ! = nil a nd p2 ! = nil do
I f not t y p e Equa l(p1,c hil d1,p2.c hil d1)
The n temp,=f a lse
Else be g in
P 1:=p1.sibl ing ;
P 2:=p2.sibl ing ;
End;
R e turn temp a nd p1 = nil a nd p2 = nil
a nd t y p e Equa l(t1.c hil d2,t 2.c hil d2);
End
Else r e turn f a ls e
End;
A gr a m m ar f or t yp e e x p r e ssi on s w ith typ e d e c l ar at ion s,
V a r - d e c ls → va r - de c ls; v a r - de c l | va r - de c l
V a r - d e c l → id,sim pe - t y pe - e x p
T y p e - de c ls → t y pe - de c ls; t y pe - d e c l | t y pe - d e c l
T y p e - de c l → id,t y pe - e x p
T y p e - e x p → sim ple - t y pe - e x p | struc tur e d - t y pe
S im ple - T y pe - e x p → sim ple - t y p e | id
S im ple - t y p e → in t | b ool|r e al | c h ar | void
S truc ture d - t y pe → a r r ay [ n u m ] of simpl e - t y p e - e x p |
Re c or d va r - de c ls e n d |
Uni on va r - de c ls e n d |
P oin te r t o sim ple - t y pe - e x p|
Pr oc (t y p e - e x ps) sim ple - ty p e - e x p
T y p e - e x ps → t y pe - e x ps,si mpl e - t y pe - e x p | sim ple - t y p e - e x p
Name equivalence,
Two type expressions are equivalent if and only if
they are either the same simple type or are the
same type name.
For example:
T1=int;
T2=int;
The types of t1 and t2 are not equivalence and not
equivalence to int.
Function typeEqual(t1,t2:typeexp):Boolean:
Var temp,boolean;
P1,p2,typeExp;
Begin
If t1 and t2 are of simple type then
Return t1 = t2
Else if t1 and t2 are type names then
Return t1 = t2
Else return false;
End;
It is possible to retain structural equivalence in the
presence of type name.
By adding the following case to the above mentioned code
Else if t1 and t2 are type name then
Return typeEqual(getTypeExp(t1),getTypeExp(t2)).
Care must be taken in implementing structural equivalence
when recursive type references are possible,since the
algorithm just described can result in an infinite loop.
For example:
T1 = record
X,int;
T,pointer to t2;
End;
T2 =record
X:int;
T:pointer to t1;
End;
Modify typeEqual(t1,t2) to include the assumption that
they are already potentially equal.
Declaration equivalence:
(Pascal and struct and union in C)
Every type name is equivalent to some base type name,
which is either a predefined type or is given by a type
expression resulting from the application of a type
constructor.
For example:
T1=int;
T2=int;
Both t1 and t2 are equivalent to int.
For example:
T1=array [10] of int;
T2=array [10] of int;
T3=t1;
T1 and t3 are equivalence,but neither is equivalence to t2
Pascal uses declaration equivalence while C
uses declaration equivalence for structures and
unions and structural equivalence for pointers
and arrays
Occasionally,a language will offer a choice of
structural,declarations,or name equivalence,
where different type declarations are used for
different forms of equivalence.
6.4.4 Type Inference and Type
Checking
T y p e c he c ke r is ba se d on a r e pr e s e ntation o f t y p e s a nd a t y pe Equ a l
ope ra ti ons,
C onsi de r a sim ple g r a m mar a s follows,
pr ogra m? va r - de c ls; stm ts
va r - de c ls? va r - d e c ls; va r - de c l | v a r - d e c l
va r - de c l? id,t y pe - e x p
t y pe - e x p? int | bool | a rr a y [ num ] of t y pe - e x p
stm t s? stm ts; stm t| stm t
stm t? if e x p then st mt | id,= e x p
1,D e c lar a ti ons,c a us e the t y p e of a n identifie r to be e nter e d int o the s y mbol
table
2,S tate ments,subst ruc ture s will ne e d to be c he c ke d for t y p e c or re c tness
3,E x pr e ssi on,va ria ble na me ha ve their t y pe s de t e r mi ne d b y a look up in t he
s y mbol table,the othe r e x pr e ssi on a re f or med b y ope ra tors,
Note,How a bout t he be h a vior of t y pe c h e c k e r in pr e se nc e of e rr or s,
Gr a mm a r Rule S e mantic Rul e s
V a r - d e c l? id,t y pe - e x p inser t(id.na me,t y p e - e x p.t y p e )
T y p e - e x p? int t y pe - e x p.t y p e,=inte g e r
T y p e - e x p? bool t y p e - e x p.t y p e,=boole a n
T y p e - e x p1? a rr a y [ num] of t y pe - e x p2 t y p e - e x p1.t y pe,=
Make t y p e node (a r ra y,
num.s iz e,t y pe - e x p2.t y pe )
S tm t? if e x p then stm t if not t y pe qu a l(e x p.t y pe,boole a n)
T h e n t y p e - e rr o r( stm t)
S tm t? id,= e x p if not t y pe qua l(lookup(id.na me),e x p.t y pe )
T h e n t y p e - e rr o r( stm t)
Ex p1? e x p2+ e x p3 if not t y pe qua l(e x p2.t y pe,int e g e r)
a n d t y p e q u a l ( e x p 3,t y p e,i n t e g e r )
T h e n t y p e - e rr o r( e x p1)
E x p 1,t y p e,= i n t e g e r
Ex p1? e x p2 or e x p3 if not t y pe q ua l(e x p2.t y pe,boole a n)
a n d t y p e q u a l ( e x p 3,t y p e,b o o l e a n )
T h e n t y p e - e rr o r( e x p1)
E x p 1,t y p e,= b o o l e a n
Ex p? num e x p,t y p e,= i n t e g e r
Ex p? true e x p,t y pe,= bool e a n
Ex p? fa lse e x p,t y pe,=bool e a n
Ex p? id e x p,t y pe,=lookup( id.n a me)
6.4.5 Additional Topics in Type
Checking
1,Overloading
– Procedure max(x,y,integer),integer;
– Procedure max(x,y,real),integer.
Solutions:
– Augment the lookup procedure of the symbol
table with type parameters,allowing the
symbol table to find the right match;
– For the symbol table to maintain sets of
possible types for names and to return the set
to the type checker for disambiguation
2,Type conversion and coercion
– For example:
2.1 + 3
Solutions:
– operations must be applied to convert the
values at runtime to the appropriate
representations before applying the operator;
– supply the conversion operation
automatically,based on the types of the sub-
expressions (coercion)
3,Polymorphic typing
Procedure swap( var x,y:anytype);
Var x,y,integer;
a,b,char;
…
swap(x,y);
swap(a,b);
swap(a,x);
The type checking will involve sophisticated
pattern matching techniques.
6.5 A Semantic Analyzer for
the TINY Language
End of Part Two
THANKS
