[解決済み] 再帰的降下法パーサ

質問

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  -> +|*

解決方法は？

ツリーをメモリに保存することも、必要な出力コードを直接生成することもできます。中間形式を保存するのは、通常、出力を生成する前に、より高いレベルでコードに何らかの処理を行うことができるようにするためです。

例えばこの場合、式に変数が含まれていないため、結果が固定数であることを発見するのは簡単でしょう。しかし、一度に1つのノードだけを見ると、これは不可能です。もっとはっきり言うと、"2*" を見た後、何かの2倍を計算する機械コードを生成した場合、もう一つの部分が例えば "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

しかし、このようなコンパイラの書き方は、最適化コンパイラではうまくいきません。

出力段階でquot;peephole"オプティマイザを追加することで、ある程度の最適化は可能ですが、多くの有用な最適化は、コードを高い視点から見ることでのみ可能です。

例えば、どのレジスタを何に割り当てるかを決めたり、特定のコードパターンに対してどのアセンブラ実装が便利かを決めたりするために、ベアマシンコード生成でさえ、より多くのコードを見ることで利益を得ることができます。

例えば、同じ式を最適化コンパイラでコンパイルすると、次のようになります。

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