AST 통역사?

Question

나는 AST (추상 구문 트리)를 가지고 있고, 이제는 2 개 이상의 숫자를 제공하고 계산기와 같은 수학 연산 결과를 사용하여 컴파일러를 테스트하려고합니다.

제 질문은 통역사를 만드는 가장 좋은 방법은 무엇입니까? 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; 

    ... 
    } 
} 

:

은 당신이 AST가 일단

Answer 1

통역사는, 코드에 아주 쉽게 감사드립니다. goto 또는 함수 호출을 구현하려면 트리에서 레이블이나 함수 선언을 검색하고 거기에서 실행을 계속해야합니다. [트리를 미리 스캔하고 조회 테이블에서 모든 레이블 위치/함수 선언을 수집하여 속도를 향상시킬 수 있습니다. 이것이 컴파일러를 만들기위한 첫 걸음입니다.] 이것조차도 충분하지 않습니다. 재귀 스택을 조정해야합니다. 재귀 스택은 함수 호출에 숨겨져 있으므로 쉽게 수행 할 수 없습니다. 이 코드를 명시 적으로 관리되는 재귀 스택이있는 반복 루프로 변환하면 스택을 수정하는 것이 훨씬 쉽습니다.