How to build symbol tables for different lexical levels?

Question

I'm in the middle of building a compiler for a C-like language. I'm somewhat done with the lexer and parser. Right now, I'm trying to do semantic analysis and am trying to build symbol tables. Now, according to the specifications, duplicate declarations are not allowed in the same lexical level. This necessitates building a different symbol table for each lexical level, right? How do I go about doing this? As of now, the one symbol table I have is in the form of a binary tree where each node looks like this:

struct tree_el
{
    char *identifier;
    char *type;
    struct tree_el *right, *left;
}

How do I point a particular node to the "root" node of another tree?

Any help will be great! Thanks much.

Answer 1

Typically this is done with a stack-like structure: each "lexical level" is opened on the stack when started, and additional levels are pushed on as they're encountered.

For example:

int i,j,k;

while (i) {
   int q, r, s;

   ...
}

As you were parsing this, you'd first definitions for i j and k and you'd add those. Then you'd hit the while statement, and "push" definitions for q r and s. When the while statement scope exited, you'd "pop" off q r and s, etc.

Answer 2

You need a separate tree of symbols for each lexical scope, that contains just the symbols directly defined within that scope. When looking up a symbol, look first in the deepest containing scope, then then parent scope, and so on until you reach file scope.