Semantic Analysis
*****************

The main task of the semantic analysis, is to relate the occurrences of an entity, and to check they are used consistently.  The most important aspect is type checking.

Symbol Tables
=============

It is extremely easy to type check something like 1 + 2 or even 1 + "two", since it is easy to know the type of a literal.  But what can you do with a + b, where a and b are variables?  You need to remember what was the type of a and b the last time you met them, i.e., you have to keep a database on the entities the user can define (types, variables, functions and so on).

Such databases are called symbol tables.

These databases are constantly changing.  For instance in the following code:

     let var i := 0
         function id (i : string) : string = i
     in
       i := i + 1;
       id ("i")
     end

there are three symbol table, or, if you prefer, the symbol table goes through three different states.

Types
=====

There are basically two equalities for types:

intensional equality
     Two types are considered equal if they are the same individual, i.e., rigorously the same type instance.  This is the case in Ada, Pascal, Tiger etc.

extensional equality
     Two types are considered equal iff their structures match.  This is the case in C, C++ etc.

The following types

     type int1_list = { hd: int, tl : int1_list }
     type int2_list = { hd: int, tl : int2_list }

are intensionally different, but extensionally equal.  While you may assign an object of type int1_list to a variable of type int2_list in C, it would raise a type violation in Tiger, Pascal etc.

Note that the creation of a type is not to be confused with the aliasing:

     type int1_list = { hd: int, tl : int1_list }
     type int2_list = int1_list
     var  list1 = int1_list { hd = 1, tl = nil }
     var  list2 = list1

is valid in Tiger.