AST-Interpreter?

Question

Ich habe eine AST (abstrakte Syntaxbaum) und jetzt will ich mein Compiler testen, indem sie zwei oder mehr Zahlen geben und einen Ausgang mit dem Ergebnis der mathematischen Operationen erwarten (wie ein Taschenrechner).

Meine Frage ist, was ist der beste Weg, um den Interpreter zu bauen? Der Besuch der AST-Knoten ist rekursiv, daher weiß ich nicht, wie viele gekapselte Berechnungen existieren, bis ich das Ende des Baumes erreicht habe. Aber da dies Iteration für Iteration ist, wie kann ich alle Operationen am Ende machen?

Danke

Answer 1

Intepreters zu Code recht einfach sind, wenn Sie eine AST haben:

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; 

    ... 
    } 
} 

Was „goto“ zu tun ärgerlich ist, weil dies den Punkt der Aufmerksamkeit des Interpreters ändert. Um Goto- oder Funktionsaufrufe zu implementieren, muss man in der Baumstruktur nach dem Label oder der Funktionsdeklaration suchen und die Ausführung dort fortsetzen. [Man kann dies beschleunigen, indem der Baum vorgescannt wird und alle Labelpositionen/Funktionsdeklarationen in einer Nachschlagetabelle gesammelt werden. Dies ist der erste Schritt zum Aufbau eines Compilers.] Auch das ist nicht genug; Sie müssen den Rekursionsstapel anpassen, den wir in Funktionsaufrufen versteckt haben, so dass es nicht einfach ist. Wenn man diesen Code in eine iterative Schleife mit einem explizit verwalteten Rekursionsstapel umwandelt, ist es viel einfacher, den Stapel zu reparieren.