# Help in understanding the implementation/application of scope trees

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.

• Can you give some references as to what a scope tree is? – Ryan Jul 5 '15 at 20:39
• I have been working on these issues for a long time, and never heard of scope trees. So I think you should give references to the literature you have been using. Many people write papers about their own idea of how things should be presented. Few such ideas become mainstream, but it does not mean all the others are bad. Scope are usually enbedded into each other, so that there are naturally organized as a tree structure. But that is the best I can say. – babou Jul 5 '15 at 22:27
• I found some references to scope trees by A. Colin and others. It seems to be a structure used for worst-case time analysis of programs, and was apparently designed for that purpose. Hence, if that is what you are trying to do, you should say so, and explain where it fits in your project, why you are doing it. And if that is not what you are trying to do, why are you attempting to use scope-trees at all? – babou Jul 6 '15 at 8:23
• Indeed, a lot of what I've read only mention symbol tables. The text that talks about scope trees is Language Implementation Patterns by Terence Parr (Pragmatic Programmers). I'm really not trying to do anything special with scope-trees per se, just implement a toy language.I'm content with a stack of maps, but even then I'm not sure what the "proper" way is to make them available as I walk the ast. – Timothy Jul 6 '15 at 23:23
• I suggest editing the question to include this information. Comments exist only to help you improve your question, and can disappear at any time. People shouldn't have to read the comments to understand your question. Thank you! – D.W. Jul 7 '15 at 18:20

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.

• Scopes do usually form a tree structure, corresponding to the embedding of scopes, though I suspect one could design scoping rules with more bizarre properties. This structure is related to the syntactic tree in the case of static scoping, which is not universal, though the dominant choie. This relation may even be seen as what chracterizes static scoping. However, there seems to be a concept of scope-tree that was introduced with a specific purpose (worst case time analysis), of which I am not sure it is identical. What you describe used to be called "block structure" in old languages. – babou Jul 6 '15 at 11:05
• Can you give a link/reference to "Language implementation patterns by Terence Parr"? – Ryan Jul 6 '15 at 14:17
• you will have to buy a copy of the book as it is not available online: amazon.co.uk/… it is well worth the read if you are going to implement a language/compiler by hand and it is very readable and easy to follow, it is not yet another dragon book. – user1932405 Jul 6 '15 at 15:28
• @babou I found some links to the scope-tree for worst case time analysis and glanced over it quickly. It seems that they are still using the syntax tree as the "original" copy and deriving a scope-tree as in the picture above but doing some kind of crazy transformations and analysis of the tree content which I did not understand but the general idea of representing scope seems to be the same. – user1932405 Jul 6 '15 at 15:40
• So if I understand correctly, a scope tree is basically (imprecisely) a set of persistent symbol tables as the tables are usually transient when a stack is used. One could easily have the tables linked to create a tree and use a stack to track references to the current scope. The tree would be separate from the AST and its root and stack perhaps stored as a global or object-member variable. Symbol tables would not be attached directly to the AST nodes, rather the stack manipulated as the AST is traversed. Correct? – Timothy Jul 7 '15 at 0:26