4.7 Symbol Table and Parser

We already had a preliminary discussion about Symbol Tables in Chapter 3 (Section 3.2). A Symbol Table exists throughout the compilation steps, but it has a rather limited role in the Parser. Basically, it accesses the Symbol Table to ensure that an operand exists. There are certain identifiers of which the Parser should be aware of, such as keywords, built-in functions and pre-defined constants and variables. They are often stored in the symbol table before the compilation process begins, so that Scanner and Parser are able to trap them. Also, user-defined declarations of variable and functions should be entered in the Symbol Table by the Parser for later processing by the semantic phase – like type checking, argument counts of the functions etc. We shall present here the additional functions needed to implement some of these facilities.

4.7.1 Pre-defined Entities

The simplest operation is insertion of pre-defined entities like keywords, built-in functions and predefined constants and variables. This is done through init() function given below.

/* install constants and built-ins in table */
void init(void){
     int i;
     Symbol *s;
     for(i = 0;  keywords[i].name; i++)
                 install(keywords[i].name, keywords[i].kval, 0.0);
     for(i = 0;  consts[i].name; i++)
                 install(consts[i].name, VAR, consts[i].cval);
     for(i = 0;  builtins[i].name; i++) {
                 s = install(builtins[i].name, BLTIN, 0.0);
                 ptr(s) = builtins[i].func;
     }
}

This init() function is invoked by the Parser at its beginning. The specification of keywords etc. is made available as arrays of structures as shown below:

struct{           /* Keywords */
       char   *name;
       int    kval;
} keywords[] = {
       “if”,      IF,
       “else”,    ELSE,
       “while”,   WHILE,
       “for”,     FOR,
       “int”,     IVAR,
       “float”,   VAR,
       “string”,  SVAR,
       0,         0,
};

The pre-defined constants are stored as

struct{           /* Constants */
       char     *name;
       double   cval;
} consts[] = {
       “PI”,     3.14159265358979323846,
       “E”,      2.71828182845904523536,
       “DEG”,   57.29577951308232087680, /* deg/radian */
       0,        0
};

The built-in functions are, for example,

static struct{      /* Built-ins */
        char *name;
        double(*func)(double);
} builtins[] = {
        “sin”, sin,
        “cos”, cos,
        0,     0
};

We have decided to include the built-in functions in the parser initialization, in anticipation of our presentation of a full compiler for a miniC language in Chapter 12. In the case of C, a large number of various function libraries are available and the C parser is made aware of the functions defined therein via the #include’d Header files.

Insertion of variable declarations, like int:a,b, involves semantic action of detecting and inserting the type of the variable and is explained in Chapter 5 (Section 5.4.7). The relevant portion of the grammar is:

%token  <sym> NUMBER STRING PRINT VAR BLTIN UNDEF WHILE FOR IF ELSE
%token  <sym> FUNCTION PROCEDURE RETURN FUNC PROC READ INT IVAR SVAR
%type   <sym> dtype
%type   <sym> dlist
decl:   dtype ‘:’ dlist ;
dtype:  IVAR | VAR | SVAR ;
dlist:  VAR                { type($1) = type($0); }
      | dlist ‘,’ VAR      { type($3) = type($0); }
      ;

Inserting the details of user-defined functions (and procedures) is slightly involved, as not only the return type of the function, but number and types of the formal arguments are to be handled. We postpone discussion about it till Chapter 12.

We tested the Scanner, with the above functions included, but without invoking the parser and we obtained the following result for inputs:

int : a

(275) 275
(275) 58
(263) 261
(263) 10

float:f

(261) 261
(261) 58
(263) 261
(263) 10

string:s

(276)	276
(276) 58
(263) 261
(263) 10

A dump of the Symbol Table gave something like this:

[DEG](261){42652ee1}
[E](261){402df854}
[PI](261){40490fdb}
[a](263){0}
[cos](262){8048ab8}
[else](267){0}
[f](263){0}
[float](261){0}
[for](265){0}
[if](266){0}
[int](275){0}
[s](263){0}
[sin](262){8048b98}
[string](276){0}
[while](264){0}

Notice that the variables a, f and s are shown with type as UNDEF and not their expected types IVAR (275), VAR (261) and SVAR (276), respectively. This has happened because we had suppressed the semantic phase and the inherited attributes transmission did not take place. Compare these results with those in Chapter 5 (Section 5.5).