[an error occurred while processing this directive]

SymbolTable Module Implementation Specifications


Client Specifications

Implementation Data Model

Basic implementation model
The SymbolTable module implements a single symbol table using a stack of Tables implemented with a dynamic array named stack. This array is declared as a static global variable in the file SymbolTable.C, along with a variable named topLevel to keep track of the current scoping level.

The topLevel variable is returned by calls to currentLevel(), and also serves as the index for the top of the stack. When enterScope() is called, a new Table is pushed onto the stack. When exitScope() is called, the top Table is popped from the stack.

When a Descriptor is added to the SymbolTable by a call to addDescriptor(), the Descriptor is added to the top Table in the stack.

The level() function checks all tables in Tables in the stack for the target identifier, working from top to bottom. When it locates the identifier, it returns its level.

The descriptorFor() function selects a Table as described in the next subsection. The Descriptor for the identifier is then retrieved from the selected Table.

Caching
To improve efficiency of descriptorFor(), level() caches its identifier argument in a variable named cacheId and the level where it found the identifier in a variable named cacheLevel. When descriptorFor() is called, it checks cacheId to see if it the same as its identifier argument. If it is not the same, then level() is called to set cacheId and cacheLevel. Then cacheLevel is used as an index in the stack array to select a Table.

The cache variables cacheId and cacheLevel can be invalid. This occurs before level() has been called the first time and may occur after a call to exitScope(). This condition is signified by a null value for cacheId. It can be rectified by calling level().

Dynamic stack allocation
The client specifications for this module do not mention any limit on the number of levels, so an unbounded implementation is needed for the stack. With an array implementation, this requires dynamic allocation and reallocation. To support this, a variable named capacity is used to keep track of the current capacity of the stack. The private function doubleStackCapacity() is called to double the capacity of the stack whenever a new level is added that exceeds the current capacity.

The private function initializeStack() is provided for the initial stack allocation. This function also creates the level 0 Table and pushes it onto the stack.

Since there is no public function for initialization, topLevel is initialized to -1 to indicate that the stack is not yet initialized. Public functions addDescriptor(), currentLevel(), and enterScope() must check topLevel and initialize the stack if it is -1.

Error handling
Two kinds of error conditions arise in this module that lead to program termination: precondition violations for public functions, and system errors. The precondition violations can occur in addDescriptor() due to the presence of an entry in the top-level Table with the same key as the identifier argument, in descriptorFor() when there is no entry whose key is the identifier argument, and in exitScope() when attemting to exit the level 0 scope. All three of these conditions should lead to program termination with an error message that describes the nature of the problem to the client of this module. The precondition in the private function doubleStackCapacity() is not checked.

System errors can arise from dynamic memory allocation in initializeStack() and reallocation in doubleStackCapacity(). The returned values from C library functions calloc() and realloc() should be checked for null values that indicate memory allocation failure. A null returned value should lead to program termination with an error message that indicates the nature of the problem.

Private Importing Information

The SymbolTable module code file requires standard library functions from stdio.h, stlib.h, and string.h. In addition, it requires the following includes.

#include "Descriptor.h"
#include "Table.h"
#include "SymbolTable.h"

Private Data Type Implementations

There is no private data type defined for a symbol table since this module implements a single symbol table. This symbol table contains the following data variables, each declared as a static variable that is global in the file SymbolTable.C.

Public Data Type Implementations

The SymbolTable module does not export any data types.

Private Function Specifications

Private Function Algorithms

Public Function Algorithms

[an error occurred while processing this directive]