Interpreter AST?

Question

Mam AST (abstrakcyjne drzewo składniowe), a teraz chcę przetestować mój kompilator, podając mu 2 lub więcej liczb i oczekując wyniku z operacji matematycznych (takich jak kalkulator).

Moje pytanie brzmi, jaki jest najlepszy sposób na zbudowanie tłumacza? Odwiedzanie węzłów AST jest rekursywne, więc nie wiem, ile enkapsulowanych obliczeń istnieje, dopóki nie dojdę do końca drzewa. Ale ponieważ jest wykonywana iteracja przez iterację, jak mogę wykonać wszystkie operacje na końcu?

Dziękuję

Answer 1

tłumacze są dość łatwe do kodu, gdy masz 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; 

    ... 
    } 
} 

Co irytujące zrobić, to „goto”, bo to zmienia punkt uwaga tłumacza. Aby zaimplementować wywołania goto lub funkcji, należy przeszukać drzewo dla etykiety lub deklaracji funkcji i kontynuować tam wykonywanie. [Można przyspieszyć ten proces, wstępnie oczyszczając drzewo i zbierając wszystkie lokalizacje etykiet/deklaracje funkcji w tabeli odnośników. Jest to pierwszy krok do zbudowania kompilatora.] Nawet to nie wystarczy; musisz dostosować stos rekursji, który ukryliśmy w wywołaniach funkcji, więc nie jest to łatwe. Jeśli ktoś zamieni ten kod na iteracyjną pętlę z jawnie zarządzanym stosem rekursji, o wiele łatwiej będzie naprawić stos.