Design Tradeoffs

Data Structure Tradeoffs

Resolution of Keywords

The µ-pascal language has 36 reserved words. We chose to use an array to store these words and simply do a linear search of each token scanned to determine whether or not it is a reserved word. While this is not the most efficient method of searching, it is easy to program, and with only 36 elements in the list, is certainly fast enough. A hash function makes little sense on a data set as small as this because calculating the hash would be expensive as performing a linear search. Another alternative would be to implement a binary tree to reduce the search time to O(log(n)). Again, because the data structure is more complicated than a simple array, the actual time savings would be insignificant to the overall runtime of the program.

Symbol Table Design

Our implementation of the symbol table as a singularly linked list forced our lookup of elements in the table to be O(n). Of course faster search algorithms exist. The symbol table would have to have an additional field representing the nesting level and be a simple list to use a hash table or other data structure that allows faster lookup time. However, this adds some complexity to the search to ensure the variable currently in scope is the variable being referenced. The linked list symbol table with a recursive linear search solves this problem. The actual time difference of faster search algorithms was not sufficient to justify the ease of not only writing the code, but also elegantly solve the problem of variable scope.