如何使用分析樹？

Question

我目前正在學習解析器。我一直在觀看視頻並試圖編寫代碼，但我開始很難理解。我想也許理解的動機解析器可以幫助理解它們如何工作以及如何構建它們。

因此解析器的目標是獲取一串令牌並創建一個解析樹。我可以理解什麼是解析樹是，但我只是看不到它是如何使用。最終，編譯器使用分析樹來創建機器代碼，但是它究竟是如何做到的？有人可以給我看一個例子嗎？

還有什麼解析（和解析樹）用於？

Answer 1

想象一下，你想爲數學表達式做一種語言。用戶可以輸入

(3 + 4) * 36

，編譯器將創建爲輸入，看起來像

 * 
    /\ 
    + 36 
/\ 
    3 4 

一個簡單的編譯器可以生成機器碼通過的遞歸遍歷來評估這個數學表達式解析樹樹，散發孩子的指示，然後自己。又名後序遍歷。在這種情況下發出指令的次序將是：

1. 說明把號3的堆棧上
2. 說明把編號4的堆棧上
3. 說明彈出頂部2元件斷堆棧，添加它們並將結果放入堆棧
4. 在堆棧上放置數字36的指令
5. 有關彈出堆棧頂端2個元素，將它們相乘並將結果放入堆棧的說明。

此代碼完全按照這種方式編譯樹。當您運行程序時，它會打印評估表達式所需的MIPS彙編指令。

#include <stdio.h> 

enum TYPE { 
    ADD, 
    MULTIPLY, 
    NUMBER 
}; 

struct tree { 
    enum TYPE type; 
    int number_val; 
    struct tree* left; 
    struct tree* right; 
}; 

void emit(struct tree* node); 

void emitNumber(struct tree* node) { 
    // load the 32-bit number into a register 
    printf("lui $t0, %d\n", (node->number_val) & 0xFFFF0000); 
    printf("ori $t0, $t0, %d\n", (node->number_val) & 0x0000FFFF); 

    // put the number on the stack 
    puts("addi $sp, $sp, -4");   
    puts("sw $t0, 0($sp)"); 
} 

void emitAdd(struct tree* node) { 
    emit(node->left); 
    emit(node->right); 

    // pop the left and right args off the stack and put them in registers 
    puts("lw $t0, 0($sp)"); 
    puts("addi $sp, $sp, +4"); 
    puts("lw $t1, 0($sp)"); 
    puts("addi $sp, $sp, +4"); 

    // add them and put the result on the stack  
    puts("add $t2, $t0, $t1"); 
    puts("addi $sp, $sp, -4"); 
    puts("sw $t2, 0($sp)"); 
} 

void emitMult(struct tree* node) { 
    emit(node->left); 
    emit(node->right); 

    // pop the left and right args off the stack and put them in registers 
    puts("lw $t0, 0($sp)"); 
    puts("addi $sp, $sp, +4"); 
    puts("lw $t1, 0($sp)"); 
    puts("addi $sp, $sp, +4"); 

    // multiply them and put the result on the stack  
    puts("mul $t2, $t0, $t1"); 
    puts("addi $sp, $sp, -4"); 
    puts("sw $t2, 0($sp)"); 
} 

void emit(struct tree* node) { 
    if (node == NULL) { 
     return; 
    } 

    switch (node->type) { 
     case NUMBER: 
      emitNumber(node); 
      break; 
     case ADD: 
      emitAdd(node); 
      break; 
     case MULTIPLY: 
      emitMult(node); 
      break; 
    } 
} 

int main() { 
    // create an example tree 
    struct tree three = { NUMBER, 3, NULL, NULL }; 
    struct tree four = { NUMBER, 4, NULL, NULL }; 
    struct tree thirtysix = { NUMBER, 36, NULL, NULL }; 
    struct tree add = { ADD, 0, &three, &four }; 
    struct tree mult = { MULTIPLY, 0, &add, &thirtysix }; 

    emit(&mult); 

    // put the calculated result in register $t0 
    puts("lw $t0, 0($sp)"); 
} 

您可以在MIPS模擬器上測試輸出，如MARS或SPIM。最後，註冊$t0保存結果252這就是答案！

要爲完整的語言編譯器，需要在樹中有更多類型的節點，並且需要更多的函數。您還需要考慮如何在函數調用期間保存/恢復堆棧中的變量。您還希望編譯器能夠跨體系結構工作。有幾個解決方案...你可以發出運行在虛擬機上的字節碼，比如Python，Java或者C＃。或者你可以編譯成像Clang那樣的LLVM這樣的中間程序集，這個程序會經過另一個編譯階段來定位精確的體系結構。

希望這會給你一些關於遍歷樹來生成實際指令是多麼的簡單的感覺，以及爲什麼你更喜歡這種樹形表示來覆蓋文本。