next up previous contents
Next: 7 Activation Records Up: 6 Semantic Analysis Previous: 6.2 Types and Type   Contents

6.3 Case Study: The Calculator Interpreter

The AST used in the calculator example is given in Scala as follows:

sealed abstract class Expr
case class BinOpExp ( op: String, left: Expr, right: Expr ) extends Expr
case class UnOpExp ( op: String, operand: Expr ) extends Expr
case class CallExp ( name: String, arguments: List[Expr] ) extends Expr
case class IfExp ( condition: Expr, then_expr: Expr, else_expr: Expr ) extends Expr
case class IntConst ( value: Int ) extends Expr
case class RealConst ( value: Float ) extends Expr
case class StringConst ( value: String ) extends Expr
case class Var ( name: String ) extends Expr
The calculator parser that constructs these ASTs is given at http://lambda.uta.edu/cse5317/calc/src/edu/uta/calc/calc.cup. Most nonterminals and some terminals have a type:
terminal String         ID;
terminal Integer        INT;
terminal Float          REALN;
terminal String         STRINGT;
non terminal Expr	exp;
non terminal List	expl, ids;
non terminal		item, prog;
For example, each production for the nonterminal exp constructs a value of type Expr when is reduced. For example, the following line in the calculator parser:
    |   exp:e1 PLUS exp:e2     {: RESULT = new BinOpExp("plus",e1,e2); :}
constructs a new Expr for exp when the rule is reduced. This Expr, which is assigned to the variable RESULT, is a binary operation "plus" with two children, e1 and e2.

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 interpreter 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 http://lambda.uta.edu/cse5317/calc/src/edu/uta/calc/SymbolTable.scala. It is a dictionary of type List[List[(String,EnvDecl)]] that maps a name to an EnvDecl. It's a list of lists because it is a stack of bindings that implements variable scoping, where each symbol table is a List[(String,EnvDecl)] (a list of bindings from names to EnvDecl). That way, begin_scope pushes an empty list to the stack, while end_scope pops the top list. The class EnvDecl is:

sealed abstract class EnvDecl
case class VarDec ( value: Double ) extends EnvDecl
case class FunDec ( body: Expr, params: List[String] ) extends EnvDecl
The binding VarDec binds a variable name to its actual value (a double floating point number). The binding FunDec binds a function name to its declaration, which consists of the function body (code) and the formal parameters.

The interpreter code is given in http://lambda.uta.edu/cse5317/calc/src/edu/uta/calc/Eval.scala. 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.


next up previous contents
Next: 7 Activation Records Up: 6 Semantic Analysis Previous: 6.2 Types and Type   Contents
2015-01-20