intérprete AST?

Question

Tengo un AST (árbol sintáctico abstracto) y ahora quiero probar mi compilador dándole 2 o más números y espero una salida con el resultado de las operaciones matemáticas (como una calculadora).

Mi pregunta es, ¿cuál es la mejor manera de construir el intérprete? La visita de los nodos AST es recursiva, por lo que no sé cuántos cálculos encapsulados existen hasta que llegue al final del árbol. Pero dado que esto se hace iteración por iteración, ¿cómo puedo hacer todas las operaciones al final?

Gracias

Answer 1

interpretes son bastante fáciles de código, una vez que tenga un AST:

int interpret(tree t) 
{ /* left to right, top down scan of tree */ 
    switch (t->nodetype) { 
    case NodeTypeInt: 
     return t->value; 
    case NodeTypeVariable: 
     return t->symbtable_entry->value 
    case NodeTypeAdd: 
     { int leftvalue= interpret(t->leftchild); 
      int rightvalue= interpret(t->rightchild); 
      return leftvalue+rightvalue; 
     } 
    case NodeTypeMultiply: 
     { int leftvalue= interpret(t->leftchild); 
      int rightvalue= interpret(t->rightchild); 
      return leftvalue*rightvalue; 
     } 
    ... 
    case NodeTypeStatementSequence: // assuming a right-leaning tree 
     { interpret(t->leftchild); 
      interpret(t->rightchild); 
      return 0; 
     } 
    case NodeTypeAssignment: 
     { int right_value=interpret(t->rightchild); 
      assert: t->leftchild->Nodetype==NodeTypeVariable; 
      t->leftchild->symbtable_entry->value=right_value; 
      return right_value; 
     } 
    case NodeTypeCompareForEqual: 
     { int leftvalue= interpret(t->leftchild); 
      int rightvalue= interpret(t->rightchild); 
      return leftvalue==rightvalue; 
     } 
    case NodeTypeIfThenElse 
     { int condition=interpret(t->leftchild); 
      if (condition) interpret(t->secondchild); 
      else intepret(t->thirdchild); 
      return 0; 
    case NodeTypeWhile 
     { int condition; 
      while (condition=interpret(t->leftchild)) 
       interpret(t->rightchild); 
      return 0; 

    ... 
    } 
} 

Lo que es molesto que hacer es "goto", porque esto cambia el punto de atención del intérprete. Para implementar llamadas goto o función, uno tiene que buscar en el árbol la etiqueta o la declaración de la función, y continuar la ejecución allí. [Se puede acelerar esto mediante el preescaneo del árbol y la recopilación de todas las ubicaciones de las etiquetas/declaraciones de funciones en una tabla de búsqueda. Este es el primer paso para construir un compilador.] Incluso esto no es suficiente; tienes que ajustar la pila de recursión, que escondimos en las llamadas a funciones, por lo que no es fácil de hacer. Si uno convierte este código a un bucle iterativo con una pila de recursión administrada explícitamente, es mucho más fácil arreglar la pila.