Introduction:
This project builds on Projects 1, 2, and 3 and has two main purposes: (a) to give you more experience constructing classes and (b) to introduce you to the vector class. This program will consist of two classes: (a) the Expression class and (b) the SymbolTable class. You can use the Expression class unchanged from Project 3; the SymbolTable class is new and you will read more about this in the paragraphs below.
An overview:
The interaction between the program and the user is similar to what was expected in Project 3. Your program prompts the user for a filename and processes the file specified by the user. This process is repeated this until the user types "quit". The big difference between Project 4 and earlier projects is that your program is no longer expected to process arithmetic expressions; it is expected to process assignment statements. In particular, each file processed by your program contains one or more assignment statements. Each assignment statement has the form:
variable_name = expression;
A variable_name is defined as a sequence of one or more letters (upper or lower case). The notion of an expression is similar to what we used in earlier projects in that the only operators allowed are + and *. The big difference is that operands are not necessarily integer constants; they can be variable names as well. Here are some examples of valid assignment statements:
As in Projects 2 and 3, objects in an assignment statement may be arbitrarily spaced. That is, consecutive objects may be separated by 0 or more blanks. Each assignment statement may span several lines; the end of an assignment statement is indicated by a semi-colon. Variable names can be arbitrarily long, just as integer constants can be arbitrarily large.
Evaluating an assignment statement:
Your program should evaluate assignment statements by first evaluating the righthand side of the assignment operator and then assigning the resulting value to the variable on the lefthand side of the assignment operator. For example, consider:
x = 8 + 9 * 2 + 3;
The righthand side of this assignment statement evaluates to 29 and this is assigned to the variable x. Things are not always as simple because expressions can contain variable names as well. An expression with variable names is evaluated by using, for each variable name, the value that was most recently assigned to it. For example, suppose the first two assignment statements in a user specified file are as follows:
Then the expression 8 + x * 3 (that is on the righthand side of the second assignment statement) evaluates to 95 because the value 29 is used for x. Recall that the value 29 is assigned to x by the previous assignment statement. This way of evaluating expressions implies that your program stores variable names and their values in a ``table'' that it can lookup when necessary. The SymbolTable class described below is used for this purpose.
The SymbolTable class:
An object belonging to the SymbolTable class is meant to store variable names and their values. Thus the private data members of the SymbolTable class consist of two vector objects: (a) a vector of string objects for the names and (b) a vector of BigInt objects for the values. You may choose to have other private data members as well. Given the purpose of the SymbolTable class, it is clear that the following public member functions are needed:
SymbolTable (int size);
int search ( const string & variableName, BigInt & val);
This function returns 1 if varName is found in the symbolTable object; returns 0 otherwise. If varName is found, then its value is returned via the reference parameter val.
void insert (const string & variableName, const BigInt & val);
To understand how this function works, consider an example of a call to this function:
store.insert("Mass", 1001);
In the above example, store is an object belonging to the symbolTable class and the user is attempting to insert the variable name Mass with value 1001 into store. The function insert looks for the variable name Mass in the object store. If Mass is found, then insert updates its old value to 1001. If Mass is not found, then the function inserts Mass and the value 1001 in the appropriate slots in store. Here is what I mean by ``appropriate slots'': the search function described above can be implemented efficiently if the variable names are maintained in sorted order. This means that the new variable name Mass has to be inserted in the object store so as to maintain the variable names in sorted order.
Errors and error messages:
As in Project 3, the input file may contain all kinds of errors that your program is expected to handle gracefully. Here are some examples of ill-formed assignment statements:
In the first line above, the object on the lefthand side of the assignment statement is not a variable name at all. In the second line, we have an expression and not an assignment statement. For both these lines, your program should produce a message such as
Expecting a variable name, found something else instead
In the third line, the assignment operator is missing. While looking for the assignment operator, your program will stumble on the second occurance of sum. So for this input your program should be able to produce an error message such as:
Expecting an assignement operator, found something else instead
Of course, it is also possible for there to be errors in the expression occuring on the righthand side of the assignment operator. As before, these errors ought to be detected by the functions getOperand and getOperator.
The errors mentioned above are all syntax errors; they occur because the input does not have the right form. There is one new, semantic error that your program has to be able to detect and deal with. For example, suppose that the input file contains the assignment statement:
y = x + 10;
Further suppose that throughout the file, x has never occured on the lefthand side of an assignment statement. This means that x has never been assigned a value by assignments statements in the current file. So even though the assignment statement is syntactically valid, we have an ``undefined variable'' error. Your program should be able to detect and produce meaningful error messages for such errors. I leave the details to you. But, I do want you to note that the scope of a variable is the file in which it is assigned a value. In other words, assignment statements in different files are completely independent of each other.
After your program detects an error (and produces an error message) it should skip to the next semi-colon in the file. This means that your program essentially discards the current assignment statement and starts fresh with the next assignment statement.
Output:
For each error-free assignment statement, your program should produce a single line of output (to the screen) informing the user of the name of the variable that was assigned a value and the value itself. For each assignment statement with an error, your program should produce an appropriate error message.
Organization of your program:
Functions such as getOperand, getOperator, printOperatorError, and printOperandError, that were part of Project 3 should be reused in Project 4. Note that getOperand is now more complicated because it is responsible for extracting two kinds of operands from the input: BigInt constants and variable names. The main function in your program should be changed to process not just as expression, but an assignment statement. As in Project 3, the Expression class is used by the main function to maintain and update expressions. The Expression class and the way it is used remain unchanged from Project 3. For this project, I have left more details unspecified than usual in the hope that you will get a glimpse of some of the design aspects of developing software.
What to turn in:
Turn in a single 3.5'' Macintosh formatted disk with a five files called project4.cpp, expression.cc, expression.h, symbolTable.h, and symbolTable.cc. The grader will only examine files with these names; files with other names will be ignored. You should also make sure that there is nothing else on your diskette; points will be deducted for any other files on your diskette.
If your program is on a PC formatted diskette, there is no need to reformat it for a Macintosh since Power Macintosh computers in MLH ITC can read PC formatted diskettes also. However, if you are a PC user you should make sure that your program compiles and executes within the CodeWarrior environment as well. All programs, independent of their origins, have to compile and execute within the CodeWarrior environment.
Clearly label your diskette by writing your name, section number, and the project number on it. In addition turn in a printout of your program. Place the printout and the diskette in a folder and label the folder clearly. This will substantially ease the grader's task and will make it easier to keep track of projects.
A final word:
Instructions and advice from earlier project handouts, related to making your program more readable, still apply. Please don't wait till the last week to start thinking about the project. As always, the TAs and I will be glad to help. Have a pleasant spring break!