递归下降解析器

Question

'Modern Compiler Design' 这本书是关于编译器的好书。在它的源代码中，有一些让我困扰的东西，就是 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  -> +|*

- S.A.Parkhid

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

然而，这种编写编译器的方法在优化编译器方面并不具有可扩展性。

虽然可以通过在输出阶段添加“Peephole”优化器来获得一些优化，但是许多有用的优化仅从更高的角度查看代码时才可能实现。

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

例如，同一表达式可以通过优化编译器编译为：

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

- 6502

Answer 2

十有八九，在词法分析和语法分析完成后，你会把AST保存在内存中以供后续处理。

一旦你有了AST，你可以做很多事情：

• 直接评估它（可能使用递归，也可能使用自己的自定义堆栈）
• 将其转换为其他类型的输出，比如另一种语言的代码或其他类型的翻译。
• 编译成首选指令集
• 等等。

- sirbrialliance

Answer 3

你可以使用Dijkstra的Shunting-yard算法创建AST。

但是，除非在解析过程中计算即时结果，否则你最终会将整个表达式或AST存储在内存中。这种方法适用于仅包含文字或编译时常量的（子）表达式，但不适用于任何在运行时计算的变量。

- kapex

Answer 4

这个问题的答案取决于你想要编译器、解释器还是介于两者之间的东西（包装在中间语言周围的解释器）。如果你想要一个解释器，递归下降解析器将同时评估表达式，因此无需将其保存在内存中。如果你想要一个编译器，则像示例中的常量表达式可以和应该被优化，但大多数表达式将操作变量，需要在转换为线性形式之前将其转换为树形式作为中间步骤。

混合编译器/解释器通常会编译表达式，但并非必须如此。将解释器与源代码捆绑在一起是输出可执行文件的一种廉价方法。Matlab使用了这种技术——代码曾经真正地编译过，但与交互版本的一致性存在问题。然而，我不会让生成表达式的语法树的难度决定这个问题。

- Malcolm McLean

Answer 5

那么我应该在内存中保存一个树还是只使用递归调用;

你将在解析器中使用递归调用来构建内存中的树。

当然，您希望将树保留在内存中以进行处理。

优化编译器会在内存中保留代码的多个表示形式（并对其进行转换）。

- Basile Starynkevitch