Passare il contesto attorno ai nodi AST

L'AST dovrebbe rappresentare solo l'albero di sintassi della tua lingua. Gli oggetti che compongono l'AST generalmente non avrebbero alcuna ulteriore funzionalità. Cose interessanti come la valutazione di AST o di prettyprinting possono essere implementate all'esterno.

Generalmente utilizzo il pattern Visitor per questi metodi esterni - dato che implemento un metodo accept_visitor per ogni oggetto AST, posso facilmente definire vari visitatori che fanno cose davvero interessanti. Uno di questi visitatori potrebbe essere un Evaluator e quell'oggetto manterrà l'ambiente.

Ecco un esempio in Scala, che utilizza la corrispondenza dei pattern al posto del pattern visitor:

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

In seguito, potresti avere ambiti nidificati. La soluzione più semplice per rappresentare questi ambiti nidificati è mantenere un elenco di mappe hash. Se una variabile non viene trovata nella mappa di hash più interna, attraversiamo l'elenco degli ambiti fino a quando non viene trovata la variabile o raggiungiamo la fine dell'elenco. In tal caso, è necessario prestare attenzione quando si impostano le variabili: le nuove variabili devono essere inserite nello scope più interno, mentre le variabili esistenti devono essere aggiornate anche quando si trovano in un ambito esterno.

Nella lingua Boo , che incoraggia il gioco con gli AST tramite le sue funzioni di metaprogrammazione, esiste una classe di nodi AST chiamata CompileUnit ciò si trova alla radice di un albero compilato. I suoi figli sono Module nodi, che rappresentano un singolo file sorgente e ogni Module contiene nodi dell'albero corrispondenti al codice AST del codice in quel file.

Potresti fare qualcosa di simile. Se i tuoi nodi AST hanno una proprietà Parent (che probabilmente fanno comunque), e posti i dati di contesto nella radice dell'albero, è banale ottenerlo dichiarando un metodo GetRoot sulla classe del nodo base che porta la catena Parent fino in cima.

Ovviamente, questo sostituisce la situazione attuale, in cui l'accesso al contesto è un'operazione O(1) , con una situazione in cui l'accesso consiste nel percorrere un elenco collegato e quindi è O(n) . È un classico compromesso di ingegneria del software: memoria o velocità?