Symbol Table

Description:

A symbol table is a stack of scopes. The purpose of this program is to replicate the idea of how a compiler keeps track of symbols within a program (variables, types, functions, etc); thus, giving a better understand of how scopes work in programming. The use of the Catch Framework was used in this program to run test cases against the program.

For instance, say we have two scopes currently available: global and main. Global encapsulates the main scope but does not have access to any of the variables within main. For example, if the main scope contains the variable userVar of type int then userVar can not be access by the global scope.

Commands within symtable.h class:

• size: returns the number of symbols in the symbol table. [O(1)]
• numscopes: returns the number of open scopes. [O(1)]
• enterScope: enters new scope and opens the scope in the symbol table (visualized as "pushing" a new scope to the stack). [O(1)]
• exitScope: exit the current open scope which discards all symbols in the scope (visualized as "popping" from the symbol table that returns to the previously opened scope). [O(1)]
• curScope: returns a copy of the current open scope. [O(N)]
• insert: inserts a (key, symbol) pair within the current open scope. If the key exists then the symbol is replaced. [O(lgN)]
• lookup: searches symbol table for (key, symbol) pair that the user requested by searching through the current scope outward to the global scope.
• dump: output contents of symbol table from current to global.

Data Structure: Map, Deque
Leveraged Knowledge: use of map and deque data structures, the idea of scopes within a program by the use of a stack by the use of the compiler, Catch Framework.

Download Code Here