COS 126: Fall 1996 Evaluating Expressions

Due: Wed. 12/4, 11:59pm (2 weeks)

Lecture 19 describes a simple expression language and a compiler that translates arithmetic expressions to TOY instructions. For this assignment, you'll extend this simple language and turn the compiler into an interpreter, in eval.c, that evaluates arithmetic expressions instead of compiling them. You'll also use binary search trees to implement a general-purpose symbol-table module, in table.c, and you'll learn about void pointers.

Most of the work in this assignment involves modifying existing code; you'll write very little new code. Of course, the modifications can be done only after you understand the existing code. Don't wait until the last moment to do this assignment!

The Language

The grammar for the extended expression language is

pgm			expr
			identifier = expr	§
expr			expr + expr
			expr - expr
			expr * expr
			expr / expr	§
			( expr )
			identifier
			$	§
			constant

Compare this grammar with the one on page 19-3; the new productions are tagged with § symbols. Also, an "identifier" has 1 or more lowercase letters, and a "constant" is 1 or more digits with optional embedded decimal points. (We'll ignore the extraneous characters in constants with more than one decimal point, like "4.53.2".) The identifier "$" refers the value most recently computed. All arithmetic is floating-point arithmetic.

eval.c reads expressions, one per line. For each expression, eval.c "compiles" it into an abstract syntax tree, evaluates the expression by traversing its tree in postorder, and prints the resulting value. This value is remembered as the value of the special identifier "$". The assignment operator, "=", assigns values to identifiers, which, along with "$", may be referenced in subsequent expressions. Here's an example:

% /u/cs126/bin/lcc eval.c table.o
/u/cs126/lib/table.o:
% a.out
4.5*(9-2)
	31.500000
$/2
	15.750000
save=$+3
	18.750000
save=save + 4
	22.750000
save
	22.750000
a=save + b
	22.750000
b
	0.000000

Identifiers are initialized to 0.0, as illustrated by "b" in the example above. Values are printed using the printf format "\t%f\n".

/u/cs126/bin/eval is an executable version of the program, which you can run to explore its behavior with various inputs.

The Program

eval.c is very similar to /u/cs126/examples/compile.c, so start by making a copy of /u/cs126/examples/compile.c as your initial version of eval.c:

% cp /u/cs126/examples/compile.c eval.c

Here's a sketch of the changes you'll need to make to this initial version of eval.c:

• Extend the lexical analyzer (get) and perhaps the parser (pgm and expr) to accept multicharacter floating-point constants and identifiers and to accept "$" as an identifier. Use sscanf or atof (Deitel and Deitel, Sec. 8.4) to convert strings to floating-point values.
• Extend the parser to accept the new productions shown above; that is, extend pgm to accept assignments and extend expr to accept "/" and "$".
• Add new fields to tree structures for nodes representing identifiers and constants, and extend the code in expr that handles them. These changes are needed because a node for an identifier must somehow refer to the identifier's floating-point value, and a constant node must refer to the floating-point value of the constant.
• Replace the codegen function with a recursive function that evaluates the expression given by an abstract syntax tree, instead of generating TOY instructions. Be careful about division by zero.

Consider doing the last two steps first; that is, get eval.c working with only single-character identifiers and constants, then add assignments and divisions, and finally add the code to handle multicharacter identifiers and constants.

To report errors, use error and the other error-reporting functions listed in /u/cs126/include/misc.h.

You will need to maintain a symbol table so that you can associate values with identifiers. Use the interface in /u/cs126/examples/table.h for your symbol-table module. As detailed below, you must also implement table.c, but you can get your eval.c working by loading your eval.c with the object code in /u/cs126/lib/table.o, which is an implementation of the symbol-table interface. As suggested above, build your program with the command

% /u/cs126/bin/lcc -n eval.c table.o

Be sure to specify #include "table.h" in your eval.c.

The Symbol-Table Module

There are two functions in the symbol-table interface

extern void *lookup(struct node *tree, char *key)

looks up key in the table rooted at tree and returns the void pointer value associated with key. If key is not in the table, lookup returns NULL.

extern void install(struct node **tree, char *key, void *value)

adds the key and an associated void pointer value to the table rooted at *tree, changing *tree if necessary (which is why a pointer to a pointer to a struct node is passed to install). key must not already be in the table. install makes a copy of key (e.g., with strsave).

The symbol-table module maintains keys and their associated values, but it doesn't depend on the details of those associated values. Indeed, lookup and install just pass these values around; they never need to look at them. The interface specifies that associated values are pointers to void, which are also called generic pointers, because they can hold pointers of any type. Thus, the code in eval.c can, for example, call install with an identifier as the key and, as the value, a pointer to a dynamically allocated structure that holds the floating-point value of the identifier. When lookup is called with the same identifier as the key, it returns the appropriate pointer. For more information about generic pointers, see lecture 14 and pp. 280-281, 470 in Deitel and Deitel.

Also, eval.c doesn't need to know anything about the innards of a struct node, because it deals only with the root of the table, which is just a pointer to a struct node. Thus, the definition of struct nodeits fieldscan be confined to just table.c.

These information hiding techniques are essential to writing reusable, general-purpose interfaces.

Once you have eval.c working, implement table.c. Use a binary search tree to represent a table. Most of the code for table.c is already written: Copy /u/cs126/examples/lookup2.c's search and insert functions and modify them as necessary to morph them into table.c's lookup and install functions.

Submitting Your Program

Turn in your code and your documentation with the command

/u/cs126/bin/submit 10 readme eval.c table.c

Extra Credit

Write your eval.c and table.c so that they use no global variables.