递归下降解析器

Question

"现代编译器设计"一书是关于编译器的好书.在它的源代码中,令我烦恼的是AST或抽象语法树.假设我们想写一个括号表达式解析器解析是这样的:((2+3)*4) * 2!这本书说我们有一个像:

        ((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