The interpreter will use a symbol table to recognize valid identifiers in TVI source code during the parsing phase. The parser needs to be able to quickly determine what are valid identifiers and what is garbage. However, even though the interpreter only supports a limited number of opcodes there are too many to recognize with a switch statement or nested if structure in the scanner. The solution is to use a hash table to record all the built in identifiers (opcodes and keywords) and user defined identifiers (goto labels and function names). This allows the parser to quickly determine valid identifiers and allows adding new opcodes and keywords to the TVI language without changing the logic of the parser or scanner.

Assignment one consists of four tasks

  1. Developing the domain model for the application
  2. Deloping class diagrams for the SymbolTable class
  3. Implementing a SymbolTable class.
  4. Updating the string class developed by the other group.

Before proceding any further with the interpreter it is important to understand the domain of the problem being solved. What are the major actors in the application? What actors interact and how do they interact?

A domain model is a UML diagram that can be used to both assists in answering those questions and communicating those answers to other developers. The first use is a matter of sketching diagrams on the back of napkins and other handy pieces of paper. The later is a formal diagram that shows the conceptual layout of all the major classes and objects in the application.

It is important to keep in mind that the concepts of class and object as expressed in a domain model do not correspond with C++ (or any other implementation language) classes or objects. The domain model is for modelling the conceptual view of the application and there may be conceptual objects in an application that are not realized by an actual class in the chosen implementation language. Consider; UML could be used to design TVI programs, a language that does not even have the concept of types never mind classes!

You are required to provide implementation level class diagrams for the symbol table class hierarchy. The diagrams should include at least two classes: the symbol table class itself, and a table entry class that will be the base class for all objects to be inserted into the symbol table.

While it is important to be as detailed as possible, do not be overly concerned with capturing every possible nuance of the symbol table and table entry classes at this point. The class diagrams will evolve over time as further requirements are identified.

back to the top

The symbol table class should be implemented as a hash table so inserts and searches can be done in constant time (average case with a non-full table and a good hash function). Besides the usual constructors and destructor (there is no copy constructor needed, in fact copies should not be made of a symbol table) the symbol table only needs to support three other methods

  1. int Add(TableEntry *item) : adds the item to the hash table.
  2. TableEntry* Find(const cs235::string& name) const : Searches for name in the hash table. If found returns a pointer to it's symbol table record, otherwise returns NULL
  3. void Print(ostream& out) : Prints the contents of the symbol table to the ostream. This will be used during debugging only.

Note : The symbol table manages pointers to table entry objects. DO NOT let some STL container class manage the memory for the symbol table objects (you can use STL containers, just store pointers to objects and not objects themselves in the containers)

The table entry class need only store the name of the object as a cs235::string. A minimal interface would be:

	class TableEntry
	{
		public:
			cs235::string Name(void) const;

			virtual EntryType Type(void) const = 0;
			virtual void Print(ostream& out) const = 0;
	};

where EntryType is an enumeration used to identify the type of object in the symbol table. The enumeration should contain one element for subclass of TableEntry. Each subclass must override the Type method and have it return the appropriate element of the enumeration. I.E

	enum EntryType { FooEntryType, BarEntryType };
	class Foo : public TableEntry
	{
		public
			virtual EntryType Type(void) const     { return FooEntryType; }
			virtual void Print(ostream& out) const { out << "this is a foo."; }
	};

	class Bar : public TableEntry
	{
		public:
			virtual EntryType Type(void) const     { return BarEntryType; }
			virtual void Print(ostream& out) const { out << "this is a bar."; }
	};

(Note : The type names used above are for example purposes only. Use whatever type names you feel are appropriate.)

back to the top

Each group must continue to use the string class developed by the other group during assignment one. However, each group can now provide the source code to their string class to the group using the class. Furthermore, each groups can now extend and fix the string class they are using. However, each group must continue to use the string class developed by the other group. Under no circumstances is a group allowed to use their own string class, or any part of their own string class (you can't paste the contents of your .C file into their .C file and call it an update.)

Any changes made to the string class must be thoroughly documented (and I mean thoroughly). Code that is remove should be commented out with an explanation why and NOT deleted from the file. Any additions should note the date, author, and reason for the addition.

Each group must submit

The domain and class diagrams can be hand drawn or you may use any suitable drawing program (ask Charles about XFig). Please follow the UML notation as closely as the tool you are using will allow (if you are drawing them by hand that is pretty close).

Each group must not submit

back to the top