c++ - 递归下降解析器

Question

《现代编译器设计》这本书是一本关于编译器的好书。在它的源代码中让我烦恼的是 AST 或抽象语法树。假设我们要编写一个带括号的表达式解析器，它解析如下内容: ((2+3)*4) * 2!这本书说我们有一个像这样的 AST:

        ((2+3)*4) * 2
          /   |     \
       (2+3)  *4    * 2
        /     | \
     (2+3)    *  4
     / | \
    2  + 3

那么我应该在内存中保存一棵树还是只使用递归调用？注意:如果我不将其存储在内存中，如何将其转换为机器码？

解析器代码:

int parse(Expression &expr)
{
  if(token.class=='D')
  { 
    expr.type='D';
    expr.value=token.val-'0';
    get_next_token();
    return 1;
  }
  if(token.class=='(') 
  {
    expr.type='P';
    get_next_token();
    parse(&expr->left);
    parse_operator(&expr->op);
    parse(&expr->right);
    if(token.class!=')')
      Error("missing )");
    get_next_token();
    return 1;
  }
  return 0;
}

语法是:

expr -> expr | (expr op expr)
digit   -> 0|1|2....|9
op  -> +|*

Answer 1

您可以将树存储在内存中，也可以直接生成所需的输出代码。存储中间形式通常是为了能够在生成输出之前对更高级别的代码进行一些处理。

以您为例，很容易发现您的表达式不包含变量，因此结果是一个固定数字。但是，一次只查看一个节点是不可能的。更明确地说，如果在查看“2*”之后生成机器代码来计算某些东西的双倍，当另一部分为例如“3”时，该代码有点浪费，因为您的程序将计算“3”然后计算每次加倍，而仅加载“6”将是等效的，但更短且更快。

如果您想生成机器代码，那么您首先需要知道要为哪种机器生成代码……最简单的模型使用基于堆栈的方法。在这种情况下，您不需要寄存器分配逻辑，并且无需中间表示即可轻松直接编译为机器代码。考虑这个只处理整数、四次运算、一元否定和变量的小例子......你会注意到根本没有使用任何数据结构:读取源代码字符并将机器指令写入输出......

#include <stdio.h>
#include <stdlib.h>

void error(const char *what) {
    fprintf(stderr, "ERROR: %s\n", what);
    exit(1);
}

void compileLiteral(const char *& s) {
    int v = 0;
    while (*s >= '0' && *s <= '9') {
        v = v*10 + *s++ - '0';
    }
    printf("    mov  eax, %i\n", v);
}

void compileSymbol(const char *& s) {
    printf("    mov  eax, dword ptr ");
    while ((*s >= 'a' && *s <= 'z') ||
           (*s >= 'A' && *s <= 'Z') ||
           (*s >= '0' && *s <= '9') ||
           (*s == '_')) {
        putchar(*s++);
    }
    printf("\n");
}

void compileExpression(const char *&);

void compileTerm(const char *& s) {
    if (*s >= '0' && *s <= '9') {
        // Number
        compileLiteral(s);
    } else if ((*s >= 'a' && *s <= 'z') ||
               (*s >= 'A' && *s <= 'Z') ||
               (*s == '_')) {
        // Variable
        compileSymbol(s);
    } else if (*s == '-') {
        // Unary negation
        s++;
        compileTerm(s);
        printf("    neg  eax\n");
    } else if (*s == '(') {
        // Parenthesized sub-expression
        s++;
        compileExpression(s);
        if (*s != ')')
            error("')' expected");
        s++;
    } else {
        error("Syntax error");
    }
}

void compileMulDiv(const char *& s) {
    compileTerm(s);
    for (;;) {
        if (*s == '*') {
            s++;
            printf("    push eax\n");
            compileTerm(s);
            printf("    mov  ebx, eax\n");
            printf("    pop  eax\n");
            printf("    imul ebx\n");
        } else if (*s == '/') {
            s++;
            printf("    push eax\n");
            compileTerm(s);
            printf("    mov  ebx, eax\n");
            printf("    pop  eax\n");
            printf("    idiv ebx\n");
        } else break;
    }
}

void compileAddSub(const char *& s) {
    compileMulDiv(s);
    for (;;) {
        if (*s == '+') {
            s++;
            printf("    push eax\n");
            compileMulDiv(s);
            printf("    mov  ebx, eax\n");
            printf("    pop  eax\n");
            printf("    add  eax, ebx\n");
        } else if (*s == '-') {
            s++;
            printf("    push eax\n");
            compileMulDiv(s);
            printf("    mov  ebx, eax\n");
            printf("    pop  eax\n");
            printf("    sub  eax, ebx\n");
        } else break;
    }
}

void compileExpression(const char *& s) {
    compileAddSub(s);
}

int main(int argc, const char *argv[]) {
    if (argc != 2) error("Syntax: simple-compiler <expr>\n");
    compileExpression(argv[1]);
    return 0;
}

例如，以 1+y*(-3+x) 作为输入运行编译器，您将得到输出

mov  eax, 1
push eax
mov  eax, dword ptr y
push eax
mov  eax, 3
neg  eax
push eax
mov  eax, dword ptr x
mov  ebx, eax
pop  eax
add  eax, ebx
mov  ebx, eax
pop  eax
imul ebx
mov  ebx, eax
pop  eax
add  eax, ebx

但是，这种编写编译器的方法不能很好地扩展到优化编译器。

虽然可以通过在输出阶段添加“窥视孔”优化器来获得一些优化，但许多有用的优化只能从更高的角度查看代码。

此外，即使是裸机代码生成也可以通过查看更多代码而受益，例如，决定将哪个寄存器分配给什么，或者决定哪些可能的汇编器实现对特定的代码模式更方便。

例如，相同的表达式可以由优化编译器编译为

mov  eax, dword ptr x
sub  eax, 3
imul dword ptr y
inc  eax