A starting point for symbol tables

To make things simple, one could avoid linked lists and use only records and arrays instatead. For instance let us consider the following types in mool-3.h

#define INT "int"

// Maximum effective size of strings
#define MAX_STRING_LENGTH 255

// Maximum effective number of classes
#define MAX_CLASS_NUMBER 16

// Maximum effective number of attributes per class
#define MAX_ATTRIBUTE_NUMBER 16

// Maximum effective number of methods per class
#define MAX_METHOD_NUMBER 64

// Maximum effective number of parameters per method
#define MAX_PARAMETER_NUMBER 16

// Maximum effective number of variables per body
#define MAX_VARIABLE_NUMBER 64


// A parsed variable will be known by its name and type
// By convention the type field will refer to the class
// rank in the class table. Negative values will be used
// for primitive types. Currently we have only one such
// type which is int and we will use -1 for it. 
typedef struct {
  char name[MAX_STRING_LENGTH+1];
  int type;
} Variable;

// This structure is meant to store information
// local to the body of a method or the main body 
// of a program. In our case, this information 
// consists of local Variables together with
// the number of them.
typedef struct {
  Variable varTab[MAX_VARIABLE_NUMBER];
  int      varNumb;
} Locals;


// This structure is meant to store the information
// related to a method.
typedef struct {
  char name[MAX_STRING_LENGTH+1];
  Variable paramTab[MAX_PARAMETER_NUMBER];
  int paramNumb;
  Locals body;
  int class;
} Method;

// This structure is meant to store the information
// related to a class.
typedef struct {
  char name[MAX_STRING_LENGTH+1];
  Variable attribTab[MAX_ATTRIBUTE_NUMBER];
  int attribNumb;
  Method methTab[MAX_METHOD_NUMBER];
  int methNumb;
} Class;

Here's the version mool-3.y of the mool.y YACC program.

• The symbol table for the whole program consists of
  • the table classTab for the classes
  • and the table mainBody for the variables declared in the MainBody.
• The global variables classNumber pc, pa, pm keep track of where we are in the parsing: how many classes yet, which class now, which attribute and which method respectively.

Observe that

• we report errors on the error canal
• when a construct (like an attribute declaration) is invalid, we just skip it and continue parsing
• types are encoded by integers:
  • -1 for int
  • ranks in classTab for classes.
• Certain actions should become function calls:
  • we should put the definitions of these functions in a separate C file
  • we should declare these functions together with the global variables in the header file mool.h

%{
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mool.h"


// The symbol table for classes
Class classTab[MAX_CLASS_NUMBER];

// The current number of known classes
int classNumber=0;

// The index in classTab of the class
// currently being parsed 
int pc =-1;

// The index in classTab[pc] of the attribute
// currently being parsed 
int pa =-1;

// The index in classTab[pc] of the method
// currently being parsed 
int pm =-1;

// The symbol table of the main body
Locals mainBody;

int i;
int j;
int c;
int na;

int yywrap()
{
  return 1;
}

%}

%union{
        int  ival;
        char sval[MAX_STRING_LENGTH+1];
      };


%token <ival> TOK_NUM
%token <sval> TOK_CLASS TOK_INT TOK_iD TOK_ID TOK_LP TOK_LB TOK_RP TOK_RB TOK_SM TOK_ERROR

%type <sval> kind

%%
program         :            {printf("Parsing program ... \n"); } 
                  classDecs  
                             {printf("Program parsed.\n");
			     // Reporting on the symbol tables:
      			      for(i=0;i<classNumber;i++) {
				printf("Class[%d] is %s\n", i, classTab[i].name);
				na = classTab[i].attribNumb;
                                for (j=0;j<na;j++) {
				      printf("      Attribute %d : %s of type %d\n",
                                             j,  
				      	     (classTab[i].attribTab)[j].name,
                                             (classTab[i].attribTab)[j].type);
				}
			      }
			     }
                ;


classDecs       : classDec  classDecs   
                | /* empty word */
                ;

classDec        : TOK_CLASS 
                  TOK_ID
                              { 
                                if (classNumber < MAX_CLASS_NUMBER) 
				  {
				    pc++;
				    pa = -1;
				    pm =-1;
				    strcpy(classTab[pc].name, $2);
				    printf("   Parsing class %s ...\n", 
                                           classTab[pc].name); 
				    classNumber++;
                                  }
			      }
                  TOK_LB 
                  attributes 
                  TOK_RB 
                            {
                                if (classNumber < MAX_CLASS_NUMBER) 
                                  {
				    printf("   Class parsed.\n"); 
				  }
			    }
                ;
attributes      :  attribute 
                   attributes
                | /* empty word */
                ;

attribute       :             
                   kind
                   TOK_iD 
                              { 
				if (classTab[pc].attribNumb < MAX_ATTRIBUTE_NUMBER)
				  { 
				    // Determining the type of the attribute
				    c = -2;
				    if (strcmp($1,INT) == 0) {
				      c = - 1;
				    } else {
					  for (i=0;i<classNumber;i++) {
					    if (strcmp($1,classTab[i].name) == 0) {
					      c = i;
					      break;
					    }
					  }
				    } 
				    // Feeding the symbol table if type ok
				    if (c > -2) {
				      pa++;
				      strcpy((classTab[pc].attribTab)[pa].name, $2);
				      (classTab[pc].attribTab)[pa].type = c;
				      (classTab[pc].attribNumb)++;
				    } else {
				      fprintf(stderr,"\nUnknown type:\n%s\n", $1);
                                    }
				    // One could also check if the attribute
				    // was not already defined ...
				  }	
			      }
				  
                   TOK_SM 
                             
                 ;

kind             : TOK_ID { strcpy($$, $1);}
                 | TOK_INT { strcpy($$, $1); }
                 ;


%%

Consider the MOOL program:

class Pair {
	int left;
	int right;
}

class ThreeByTwo {
        Pair left;
        Pair middle;
        Pair right;
}

class MeliMelo {
        int a;
        Pair b;
	int c;
        ThreeByTwo d;
}

The parsing of this file with mool-3.y:

[moreno@iguanodon yacc]$ ./bin/mool < test/p3.mool 
Parsing program ... 
   Parsing class Pair ...
   Class parsed.
   Parsing class ThreeByTwo ...
   Class parsed.
   Parsing class MeliMelo ...
   Class parsed.
Program parsed.
Class[0] is Pair
      Attribute 0 : left of type -1
      Attribute 1 : right of type -1
Class[1] is ThreeByTwo
      Attribute 0 : left of type 0
      Attribute 1 : middle of type 0
      Attribute 2 : right of type 0
Class[2] is MeliMelo
      Attribute 0 : a of type -1
      Attribute 1 : b of type 0
      Attribute 2 : c of type -1
      Attribute 3 : d of type 1