Help in understanding the implementation/application of scope trees

Question

I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope trees are meant to be used.

In my toy language, I’m using the Visitor pattern to traverse the syntax tree as a simple interpreter. I assign a pointer to a given symbol table to a member of the syntax node to make the various symbols available at “run time”. The symbol tables are hash tables on a stack, and I resolve symbols defined in a parent scope by inspecting the stack.

But the literature I’ve read (specifically Language Implementation Patterns by Terence Parr) talks about a scope tree as a distinct tree structure, like the syntax tree, and traversing the scope tree. Does a scope tree stand separately and alongside the syntax tree, and if so how does one track the current position in the scope tree while traversing the syntax tree? Is it simply a global pointer to a scope node/symbol table that’s adjusted whenever a scope-affecting node is encountered in the syntax tree? Or, Is it okay for the scope tree’s tree structure to be implicitly defined by piggy-backing the syntax tree as I have done? I feel I am polluting the syntax nodes definitions by adding a symbol table member.

Answer 1

My opinion on this is that the scope tree is a derived entity from the syntax tree, therefore as you perform your semantic analysis by walking the syntax tree you create a temporary scope tree on the fly and by doing that, the current position is automatically tracked.

The point is that both the scope tree and the syntax tree have to be married together somehow. As this would allow you to track the position of the symbols in unison. So as you traverse a method called a() on the syntax tree you statically know where to start in the symbol tree.

Note: you do not require a scope tree, you could use a stack but the advantage of the tree is that the storage of the scope is persistent. Therefore for simple validations a stack could be used to determine whether or not a variable is out of scope but for mode advanced analysis problems a scope-tree which behaves like a multidimensional stack would be required.

i.e.:

int a()
{
    int b;
    int c;
    {
       int b;
       int c;
    }
}

int b()
{
     int a;
}

So whenever you go into a function such as a you can create a function node and every time you see a declaration you can create a symbol and add it to the function's scope (push) and when you see a declaration you can resolve it by traversing up the tree.

Language implementation patterns by Terence Parr has a complete example of this and a very useful book.