[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.
- Table * stack -
the stack of Tables.
- int capacity -
the capacity of the stack.
- int topLevel -
the level number of the top Table in the stack.
This variable must be initialized to -1.
- char * cacheId -
the identifier parameter for the most recent call to level().
This variable must be initialized to null, and must be set to null whenever
there is a possibility that the entry for this identifier has been removed.
- int cacheLevel -
the level where cacheId can be found.
Public Data Type Implementations
The SymbolTable module does not export any data types.
Private Function Specifications
Private Function Algorithms
- initializeStack
Specification
topLevel = 0
capacity = 4
allocate array for stack with capacity entries (use calloc())
if calloc returns null
terminate the program with a system error message
put a new Table at stack[topLevel]
- doubleStackCapacity
Specification
double capacity
reallocate array for stack with capacity entries (use realloc())
if realloc returns null
terminate the program with a system error message
Public Function Algorithms
- level
Client Specification
parameter: char * id
local variable: int currentLevel
cacheId = id
currentLevel = topLevel
while currentLevel >= 0
if id is a key in stack[currentLevel]
break
decrement currentLevel
cacheLevel = currentLevel
return currentLevel
- descriptorFor
Client Specification
parameter: char * id
if cacheId is null or cacheId is not the same as id
call level(id)
if cacheLevel < 0
terminate the program with a precondition violation error message
return the data from stack[cacheLevel] for key id
- addDescriptor
Client Specification
parameter: char * id
parameter: Descriptor dscr
if topLevel is -1
initialize the stack
if the stack[topLevel] has an entry whose key is id
terminate the program with a precondition violation error message
add dscr to stack[topLevel] with key id
- currentLevel
Client Specification
if topLevel is -1
initialize the stack
return topLevel
- enterScope
Client Specification
if topLevel is -1
initialize the stack
increment topLevel
if topLevel >= capacity
double capacity of stack
put a new Table at stack[topLevel]
- exitScope
Client Specification
if topLevel <= 0
terminate the program with a precondition violation error message
free stack[topLevel]
decrement topLevel
if topLevel < cacheLevel
cacheId = null
[an error occurred while processing this directive]