Wie bewertet ein Compiler einen geparsten Tokenbaum?

Question

Ich interessiere mich für Compiler, und schreibe ein einfaches in C++ einfach für die Erfahrung! Ich verstehe, wie ein Compiler Quellcode analysiert und dann eine Token-Struktur erstellt. Was ich nicht verstehe, ist, wie dieser Baum ausgewertet wird, und dann gegebenenfalls einen Wert zurückgibt. Zum Beispiel, wenn es eine Aussage (a + b) gibt, würde ich eine Funktion haben, um den + Token zu behandeln, der a und b übergeben würde? Würde es folgen, dass ich dasselbe mit Vergleichsoperationen machen würde, und dann auch wenn Aussagen?

Answer 1

Compiler werten den AST nicht aus, das tun (naive) Interpreter. Compiler generieren Code vom AST.

einen einfachen int-only AST auswerten könnte etwa so aussehen, unter der Annahme, dass ein AST-Knoten eines ENUM besteht darin, die Art von Knoten und eine Reihe von untergeordneten Knoten zu sagen:

int eval_expression(node) { 
    switch(node.type) { 
    case ADD: 
    return eval_expression(node.children[0]) + eval_expression(node.children[1]); 
    case IF: 
    if(eval_expression(node.children[0])) { 
     return eval_expression(node.children[1]); 
    } else { 
     return eval_expression(node.children[2]); 
    } 
    // and so on 
    } 
} 

auf Ihrer Sprache Je und Wie du den AST darstellst, sieht vielleicht viel anders aus, aber hoffentlich gibt dir das eine Idee.

Was für eine (sehr einfach) Compiler tun könnte, würde aussehen wie folgt aus:

void compile_expression(Node node, const char* target_register) { 
    switch(node.type) { 
    case ADD: 
    const char* temp_register = find_unused_register(); 
    compile_expression(node.children[0], target_register); 
    compile_expression(node.children[1], temp_register); 
    printf("ADD %s %s\n", target_register, temp_register); 
    free_register(temp_register); 
    case IF: 
    const char* condition_register = find_unused_register(); 
    compile_expression(node.children[0], condition_register); 
    const char* elseLabel = generate_label(); 
    const char* labelAfterIf = generate_label(); 

    // If the condition was zero, jump to the else case 
    printf("JZ %s %s\n", condition_register, elseLabel); 
    compile_expression(node.children[1], target_register); 
    printf("JUMP %s\n", labelAfterIf); 

    printf("%s:\n", elseLabel); 
    compile_expression(node.children[2], target_register); 

    printf("%s:\n", labelAfterIf); 
    free_register(temp_register); 
    // and so on 
    } 
} 

Der obige Code schreibt Assembler-Code direkt auf die Standardausgabe, die nicht ganz ist, was ein echter Compiler tun würde. Es ist auch voll von schlechten Engineering-Praktiken und geht von einem eher vereinfachten Assembly-Dialekt als Ziel aus. Hoffentlich kommt es aber auf die Idee.

---

Beachten Sie, dass die reale Welt Compiler nicht Baugruppe (oder Maschinencode) erzeugt direkt aus dem AST, noch werden Dolmetscher direkt den AST bewerten. Stattdessen werden beide zuerst eine Form von Zwischencode (wie Dreiadressencode) von dem AST erzeugen und dann weiter damit arbeiten.