6.3 Case Study: The Calculator Interpreter

In Section 4.3, we described Gen used in constructing ASTs for the calculator example. We are now ready to go back to the calculator parser calc.gen to see how ASTs are constructed. Most nonterminals and some terminals have a type:

terminal String         ID;
terminal Integer        INT;
terminal Float          REALN;
terminal String         STRINGT;
non terminal Ast        exp, string, name;
non terminal Arguments  expl, names;
non terminal            item, prog;

For example, each production for the nonterminal exp constructs a value of type Ast when is reduced. For example, the following line in the calculator parser:

    |   exp:e1 PLUS exp:e2  {: RESULT = #<plus_exp(`e1,`e2)>; :}

constructs a new Ast for exp when the rule is reduced. This Ast, which is assigned to the variable RESULT, is a tree node with label plus_exp and two children, e1 and e2, which correspond to the Asts of the plus operands.

Recall that our calculator is an interpreter, rather than a compiler. The symbol table of an interpreter must bind each program variable to both its type and its value. For example, when the interpret encounters the variable x in a program, it must assert the type of x (eg, an integer) so it can tell if x is used correctly in the program. It also needs the value of x because it needs to evaluate x. A compiler would only need the type of x. Fortunately, our calculator has only one type: double floating points. So there is no need for type information since everything is expected to be (or be able to be converted to) a floating point. The calculator symbol table is an instance of the class SymbolTable given in SymbolTable.java. It is a hash table with items of type SymbolCell:

class SymbolCell {
    String     name;
    Ast        binding; 
    SymbolCell next;
    SymbolCell ( String n, Ast v, SymbolCell r ) { name=n; binding=v; next=r; }
}

The binding is the actual value of the symbol, not its type. If we had multiple types, we should have had another attribute type of type Ast in Symbol. The binding plays two roles: if the name is a variable name, then the binding is the actual value (a double floating point number) represented by a Real AST node. If the name is a function definition, then the binding is the AST of the actual definition. To implement variable scoping, a scope stack is used as it is described in the previous section. The special marker -1 in the scope stack indicates a new scope. All the other entries are locations in the symbol table.

The interpreter code is given in Eval.gen. Function eval evaluates the AST e using the symbol table st and returns a double floating point number. When a variable is encountered, its value is retrieved from the symbol table. A function call can be either a primitive operation, such as an integer addition, or a call to a defined function. In either case, the function arguments must be evaluated before the operation/call is performed. The function call is performed by creating a new scope, binding the functions' formal parameters to the evaluated call arguments, and evaluating the function body using the new scope. After the call, the function scope is popped out.