6.2 Type Expressions and Type Constructors

One obvious way of representing a complex data type is to show how it is arrived at by means of a tree structure. For example, consider the following declarations and definition.

int a[100];

This can be represented by a tree as:

struct my {
  float f[20];
  int *pi;
} b[5];

This array of struct definition can be represented by a tree as:

Usually, a complex data type is constructed by the following methods or their combination:

Pointers: have a single component of type T, the type of construct is a pointer to T.

Arrays: have two components – type of array elements T (left child) and number of elements (right child).

Structures (Records): have one component (child) for each field in the structure, in the left-to-right order in which they appear in the structure.

Functions: have two components (children) – the type of the returned value and the list of types of arguments.

Unions: similar to structures.

It will be desirable to construct these type trees as Binary trees, but here we face a problem – in general a structure can have more than two fields and a function could have more than one argument. We must have a way of representing more than two children in a Binary tree. This can be done as follows. Suppose we have a function with 3 arguments:

int func1(float a, int *b, float *c);

We can represent this by a tree such as:

A function without arguments will be represented by a tree such as:

A type tree for a structure with more than two fields be similarly constructed.

For example:

represents a struct with four fields:

struct four {
  int   i;
  float f;
  int   *pi;
  float *pf;
}

Though the Node structure we have suggested previously can easily be used for representing a non-Binary tree, we are still interested in Binary type tree, as we already have in our Scanner functions for Binary tree manipulations like insert node, look-up node, traverse, etc.

In the Symbol Table, we should be able to refer to a type tree instead of a simple type. First, we define additional types:

#define   INT          274
#define   NUMBER       258
#define   STRING       259
#define   VAR          261
#define   IVAR         275
#define   SVAR         276
#define   FUNCTION     268
#define   PROCEDURE    269
#define   TREE         1000
#define   POINTER      TREE+1
#define   ARRAY        TREE+2
#define   STRUCT       TREE+3
#define   UNION        TREE+4
#define   FUNCDEF      TREE+5
#define   LIST         TREE+10

Note that all the structuring types have assigned values greater than TREE = 1000. Type TREE is simply used in code to decide if we have a complex type definition.

We now redefine the interpretation of various fields in the Node structure as follows:

typedef union{
  struct node_struct*N;
  char*S;
  long I;
  float F;
  void *P;
}util;

typedef struct node_struct{
struct node_struct *link[2]; //  left = link[0], right = link[1]
util u,v,w,x,y,z;
}Node;
#define L(n) ((n)–>link[0])     
#define R(n) ((n)–>link[1])     |
#define left(n)    L(n)         |  Basic Symbol Table
#define right(n)   R(n)         |
#define name(n)    ((n)–>w.S)   /
#define type(n)    ((n)–>v.I) ––+    Types:
                                |    if > TREE than a constructor
#define ttree(n)   ((n)–>z.N) <–+    tree at this pointer

Other fields in the Node are used for other purposes and not of concern here.