Interprete AST?

Question

Ho un AST (abstract syntax tree) e ora voglio testare il mio compilatore dandogli 2 o più numeri e aspetto un output con il risultato di operazioni matematiche (come una calcolatrice).

La mia domanda è, qual è il modo migliore per costruire l'interprete? La visita dei nodi AST è ricorsiva, quindi non so quanti calcoli incapsulati esistono fino a quando non arrivo alla fine dell'albero. Ma dal momento che questa operazione viene eseguita per iterazione, come posso fare tutte le operazioni alla fine?

Grazie

Answer 1

interpreti del sono abbastanza facile da codice, una volta che si dispone di 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; 

    ... 
    } 
} 

Cosa è fastidioso da fare è "goto", perché questo cambia il punto di attenzione dell'interprete. Per implementare goto o chiamate di funzione, è necessario cercare l'albero per l'etichetta o la dichiarazione di funzione e continuare l'esecuzione lì. [Si può accelerare la prescrizione dell'albero e raccogliere tutte le posizioni delle etichette/dichiarazioni di funzioni in una tabella di ricerca. Questo è il primo passo verso la costruzione di un compilatore.] Anche questo non è abbastanza; devi regolare lo stack di ricorsione, che abbiamo nascosto nelle chiamate alle funzioni, quindi non è facile da fare. Se si converte questo codice in un ciclo iterativo con uno stack di ricorsione gestito in modo esplicito, è molto più semplice correggere lo stack.