AST翻譯？

Question

我有一個AST（抽象語法樹），現在我想通過給它2個或更多數字來測試我的編譯器，並期望輸出數學運算的結果（如計算器）。

我的問題是，構建解釋器的最佳方法是什麼？ AST節點的訪問是遞歸的，所以我不知道有多少封裝計算存在，直到我到達樹的末尾。但是，由於這是通過迭代完成迭代的，所以我怎樣才能使所有的操作到最後？

謝謝

Answer 1

Intepreters是很容易的代碼，一旦你有一個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; 

    ... 
    } 
} 

什麼是惱人做的是「GOTO」，因爲這改變的解釋的關注點。要實現goto或函數調用，必須在樹中搜索標籤或函數聲明，然後繼續執行。 [人們可以通過預掃描樹並在查找表中收集所有標籤位置/函數聲明來加快速度。這是構建編譯器的第一步。]即使這還不夠，你必須調整我們在函數調用中隱藏的遞歸堆棧，這樣做並不容易。如果將此代碼轉換爲具有明確管理的遞歸堆棧的迭代循環，修復堆棧會更容易。