如何使用分析树？

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这样的中间程序集，这个程序会经过另一个编译阶段来定位精确的体系结构。

希望这会给你一些关于遍历树来生成实际指令是多么的简单的感觉，以及为什么你更喜欢这种树形表示来覆盖文本。