Symbol tables

Objects such as variables, functions and types are named. At their declaration, their names are defined as synonyms and this is called binding. This is visible to a block of code which is the scope of the object. Such declarations are local and if the scope were for larger, the scopes would be global. If there are nested scopes, the context closest to the usage as it appears in the syntax tree is used.  The scoping that is based on the syntax tree is called static or lexical binding. In dynamic binding, the declaration most recently encountered during execution defines the current use of the name.
A symbol table is a table that binds names to objects. We start with an empty table. We need to bind a name to an object. In case the name is already defined in the symbol table, the new name takes precedence. We should be able to lookup a name in the symbol table to find the object it is bound to. We need to be able to enter a new scope and exit a scope, reverting the table to what it was prior to entry.
Symbol tables are implemented using a persistent or functional data structure. In this method, a copy is made of the data structure whenever an operation updates it, hence preserving the old structure. Only a portion of the data structure needs to be copied, the rest can be shared. There is another approach called the imperative approach in which when an update is made, the old binding of a name that is overwritten is recorded (pushed) on the stack. When a new scope is entered,  a marker is pushed on the stack. When the scope is exited, the bindings on the stack are used to revert to the earlier symbol table. Text from Mogensen.