1

I have various objects inside my AST, such as IfBlock, FunctionBlock, LogicExpression, etc. All of those objects share a context, which is basically a hashmap with some variables. It's a very simple language, created for learning purposes. I use this hashmap to make it possible that a FunctionBlock is able to modify a variable later used in an LogicExpression.

Right now, i'm just injecting the hashmap into all objects, via constructor. Is this the proper way? Isn't there a more elegant way to share such global context between objects?

2 Answers 2

3

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.

1

In the Boo language, which encourages playing around with ASTs via its metaprogramming facilities, there's an AST node class called CompileUnit that lies at the root of a compile tree. Its children are Module nodes, which represent a single source file, and each Module contains tree nodes corresponding to the AST of the code in that file.

You could do something similar. If your AST nodes have a Parent property (which they probably do anyway), and you place the context data at the root of the tree, it's trivial to get at it by declaring a GetRoot method on the base node class that walks the Parent chain all the way up.

Of course, this replaces your current situation, where access to the context is an O(1) operation, with a situation where access involves walking a linked list and thus is O(n). It's a classic software engineering tradeoff: memory or speed?

2
  • What if on each addChild() i inject the pointer to the context? By having the pointer, i don't need to worry about speed.
    – vinnylinux
    Apr 23, 2015 at 19:16
  • 1
    @vinnylinux: Then each object is larger, in the amount of the size of one pointer. As I said, it's one of the classic tradeoffs. There's no one "the right answer" to this; it depends on factors such as how many AST objects you're creating, how deep the parse tree will go, and how frequently you're going to access the global context. Apr 23, 2015 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.