C Academy · レッスン

構文木を評価する

Q: 「構文木を評価する」で何を学びますか？

結果を計算します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

結果を計算します。

「構文木を評価する」はCoddyKit上の無料C Academyレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

ASTをたどる

評価は後順走査です。まず子ノードを計算し、その後ノードの演算子で結果を組み合わせます。数値の葉ノードは、その値をそのまま返します。

この木をたどるインタープリターは、インタープリターで実装できる最も単純なバックエンドです。

evalのシグネチャ

評価器はノードへのポインターを受け取り、整数を返します。木が再帰的な構造なので、この関数も再帰的になります。

浮動小数点数を扱う言語では、代わりに double またはタグ付きの値を返します。

int eval(Node *n);  /* returns the integer value of the subtree */

葉ノードの評価

基底ケースが再帰を止めます。ノードが数値の場合、その値が部分木の答えになります。

すべての再帰的な下降処理は基底ケースに到達する必要があります。そうでなければ処理は終了しません。

int eval(Node *n) {
  if (n->kind == N_NUM) {
    return n->value;
  }
  /* ... handle N_BINOP below ... */
  return 0;
}

BinOpの評価

演算子ノードでは、両方の子ノードを再帰的に処理してから演算子を適用します。左の子を右の子より先に評価することで、通常の左から右への順序になります。

演算子の文字に対する switch を使うと、ロジックを読みやすく保てます。

int eval(Node *n) {
  if (n->kind == N_NUM) return n->value;
  int l = eval(n->bin.left);
  int r = eval(n->bin.right);
  switch (n->bin.op) {
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

ゼロ除算の防止

C における整数のゼロ除算は未定義動作で、通常はプロセスのクラッシュにつながります。安全なインタープリターでは、先に除数を確認します。

制御不能な SIGFPE を発生させるより、適切な実行時エラーを報告するほうが優れています。

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

static int safe_div(int a, int b) {
  if (b == 0) {
    fprintf(stderr, "runtime error: division by zero\n");
    exit(1);
  }
  return a / b;
}

評価の一連の流れ

ここでは、(2 + 3) * 4 を表す手作業で構築した木を評価し、20 を得ます。同じ eval で、パーサーが生成するどのような木でも処理できます。

実行して、後順走査によって正しい答えが計算されることを確認してください。

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

typedef struct Node {
  int is_num; int value;
  char op; struct Node *l, *r;
} Node;

static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }

static int eval(Node *n){
  if (n->is_num) return n->value;
  int l = eval(n->l), r = eval(n->r);
  switch (n->op){
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

int main(void){
  Node *ast = B('*', B('+', N(2), N(3)), N(4));
  printf("%d\n", eval(ast));
  return 0;
}

スタックの深さ

入れ子になった各演算子によって、C の呼び出しスタックにフレームが1つ追加されます。括弧が1000個あるような深く入れ子になった式では、スタックがあふれる可能性があります。

実際の式の多くは浅いものですが、堅牢なインタープリターでは安全のため、明示的なスタックに切り替えることがあります。

定数畳み込み

評価と解析が同じ木を共有しているため、最適化が可能です。二項演算の両方の子が数値なら、結果を一度計算し、そのノードを葉ノードに置き換えられます。

この定数畳み込みは、インタープリターで使われる代表的な最適化です。

/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
  if (n->kind == N_BINOP) {
    n->bin.left  = fold(n->bin.left);
    n->bin.right = fold(n->bin.right);
    if (n->bin.left->kind == N_NUM &&
        n->bin.right->kind == N_NUM)
      return num(eval(n));
  }
  return n;
}

木の解放

ヒープに確保したノードは解放する必要があります。後順で解放すると、評価と同じように、親ノードより先に子ノードを処理できます。

これを忘れると、インタープリターが式を処理するたびにメモリリークが発生します。

void free_tree(Node *n) {
  if (n->kind == N_BINOP) {
    free_tree(n->bin.left);
    free_tree(n->bin.right);
  }
  free(n);
}

単項マイナス

-5 のような否定を処理する必要があります。方法の1つは単項演算ノードを用意することです。もう1つは、解析時に -x を 0 - x へ変換することです。

どちらの方法でも、評価は単純な再帰的走査のままです。

/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
  bump();
  return binop('-', num(0), parse_factor());
}

木をたどる方式の理由

木をたどるインタープリターは、速度を多少犠牲にする代わりに、簡単に作成してデバッグできます。初期の Ruby などの言語は、バイトコード VM に移行する前にこの方式を使用していました。

次は変数を追加し、インタープリターが値を記憶できるようにします。

理解度チェック

eval がノードを訪問する順序について考えてみましょう。

まとめ

再帰的な評価器を実装しました。葉ノードの基底ケース、二項演算の再帰、ゼロ除算の防止に加え、木の解放と定数畳み込みも実装しました。

これでインタープリターは、任意の算術 AST を計算できます。次は変数を追加します。

よくある質問

「構文木を評価する」レッスンは無料ですか？

はい。「構文木を評価する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「構文木を評価する」で何を学びますか？

結果を計算します。ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン3/4です。

「構文木を評価する」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← C Academyに戻る