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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top