Implementing a symbol table with a hash table and a stack

Question

I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different levels of "blocks", which are usually { } curly brackets in languages such as C.

My thought was, what's wrong with using stacks instead?

For example, here's some code:

int x = 5;
float y = 3;
{
 // stuff
 int x = 100; 
}

Would I not be able to start off, hashing x, pushing it onto a stack struct as

struct symbol_def{
 char * type;
 val_type value;
}

I don't know how to do a dynamic type for the value (if the value is even needed in there).

When the second x comes in:

int x = 100;

Then we just again hash x, push onto the stack.

At any given moment, the top of the stacks are the current scope's visibility.

The issue might come with popping however. How do we pop off the right things? That one I'm not entirely sure about, and could be a fatal flaw of this design.

In theory, this would be a lot of O(1) jobs (hash table lookup, pushing, popping, peeking).

Let me know your thoughts. Maybe I'm missing something here, or maybe this is how it's really done already.

Answer 1

A stack of hashtables would be a perfectly fine representation.

A hashtable of stacks wouldn't be a good choice, but a stack of hashtables would work.

When you leave a scope (e.g., the } symbol), you need to pop off all of the symbol names defined in that scope. That's easy with a stack of hashtables, but a bit more annoying with a hashtable of stacks.

A natural way to represent a stack is as a linked list, so this might turn out to be equivalent to the solution you've already been presented.