The AST should only represent the syntax tree of your language. The objects making up the AST would generally not have any further functionality. Nice things like evaluating the AST or prettyprinting it can be implemented outside.
I generally use the Visitor Pattern for these external methods – given that I implement an accept_visitor method for each AST object, I can easily define various visitors that do the actually interesting stuff. One of these visitors could be an Evaluator, and that object would then hold the environment.
Here's an example in Scala, using pattern matching instead of the visitor pattern:
sealed abstract class Ast
case class Literal(value: Int) extends Ast
case class Var(name: String) extends Ast
case class Set(name: String, value: Ast) extends Ast
case class Add(left: Ast, right: Ast) extends Ast
case class Block(statements: Seq[Ast]) extends Ast
import scala.collection.mutable.HashMap
class Evaluator {
val env: HashMap[String, Int] = new HashMap()
def evaluate(ast: Ast): Int = ast match {
case Literal(value) => value
case Var(name) => env(name)
case Set(name, value) => { val v = evaluate(value); env(name) = v; v }
case Add(left, right) => evaluate(left) + evaluate(right)
case Block(statements) => statements.map(s => evaluate(s)).last
}
}
val ast = Block(Seq(
Set("x", Literal(40)),
Set("y", Literal(2)),
Add(Var("x"), Var("y"))
))
new Evaluator().evaluate(ast) //=> 42
Later, you might have nested scopes. The easiest solution to represent these nested scopes is to maintain a list of hash maps. If a variable is not found in the innermost hash map, we traverse the list of scopes until either the variable was found or we reach the end of the list. In such a case, care has to be taken when setting variables – new variables should be put in the innermost scope, whereas existing variables should be updated even when they are in an outer scope.
