Symbol table using vectors

Question

I've been racking my brain trying to figure out the logic with implementing my symbol table & now I'm waving the white flag and asking for some help. I'm creating a symbol table using vectors but I'm having trouble putting the symbol table entry (a string for now, a struct later) in the right scope. My code has an int scopenum that increments every time a block is opened { and decrements every time a block is closed }. However this line causes a problem: { a { b } { q } } because it puts q in scope 2 when it should be in scope 3. My code pushes a new row onto the vector but it doesn't use it in the insert. How can I modify my code to correctly account for opening & closing scopes?

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int stacknum=-1;
vector< vector<string> > v;

void display(){
    for(int i=0; i<v.size(); i++){
        cout << "Scope " << i+1 << ": " << endl;
        for(int j=0; j<v[i].size(); j++)
            cout << v[i][j] << endl;
        cout << endl;
    }
}

void insert(string s){
    v[stacknum].push_back(s);
}

int main(){
    string data;
    ifstream file;
    file.open("input");

    if(!file.is_open()) {
        cout << "Input file not found";
        return 1; }

    while(file >> data){
        if(data=="{"){
            stacknum++;
            vector<string> row;
            v.push_back(row);
            continue;
        }

        if(data=="}"){
            stacknum--;
            continue;
        }

        insert(data);
    }
    file.close();

    display();

    return 0;
}

Answer 1

You can't track the current scope with just a index; you need a stack. Alternatively (and probably more usefully) you need to record the parent scope for each scope, which you can do with a second vector or by including an extra data member in the scope object.

In either case, when you enter a new scope, you create a new scope object (a vector of symbols, with associated parent scope index) at the end of the vector of scope objects, and make that object's index the "current scope index". When you leave a scope, the current scope index is set to the current scope's parent.

The parent pointers are useful when you are searching for a symbol; you need to search all of the parents of the current scope until you find the symbol.

Depending on the scoping rules you are trying to model, that might not be adequate. It doesn't accurately model C's scoping rules, for example, because in C, the scope of a declared variable starts at the declaration, not at the beginning of the enclosing block. However it may be good enough for building an AST, as long as you do all symbol lookups in order as you parse the input left to right.