C Academy · Pelajaran

Mengevaluasi Pohon

Hitung hasilnya.

Mengevaluasi Pohon adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.

Menelusuri AST

Evaluasi adalah penelusuran pascapesanan: hitung anak-anak terlebih dahulu, lalu gabungkan hasilnya dengan operator pada simpul. Daun berupa angka cukup mengembalikan nilainya.

Interpreter yang menelusuri pohon ini adalah backend paling sederhana yang dapat dimiliki interpreter.

Tanda Tangan eval

Evaluator kita menerima penunjuk simpul dan mengembalikan bilangan bulat. Karena pohonnya rekursif, fungsinya juga bersifat rekursif.

Untuk bahasa dengan bilangan pecahan, Anda dapat mengembalikan double atau nilai bertanda sebagai gantinya.

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

Mengevaluasi Daun

Kasus dasar menghentikan rekursi. Ketika sebuah simpul adalah angka, nilainya menjadi jawaban untuk subpohon tersebut.

Setiap recursive descent harus mencapai kasus dasar; jika tidak, proses tidak akan pernah berhenti.

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

Mengevaluasi BinOp

Untuk simpul operator, kita melakukan rekursi pada kedua anak, lalu menerapkan operatornya. Mengevaluasi anak kiri sebelum anak kanan menghasilkan urutan kiri-ke-kanan yang lazim.

switch pada karakter operator membuat logikanya tetap mudah dibaca.

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;
}

Melindungi dari Pembagian dengan Nol

Pembagian bilangan bulat dengan nol merupakan perilaku yang tidak terdefinisi dalam C dan biasanya membuat proses berhenti secara tiba-tiba. Interpreter yang aman memeriksa pembagi terlebih dahulu.

Melaporkan kesalahan saat runtime dengan rapi lebih baik daripada membiarkan SIGFPE yang tidak terkendali.

#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;
}

Evaluasi Ujung ke Ujung

Di sini, pohon yang dibuat secara manual untuk (2 + 3) * 4 dievaluasi menjadi 20. eval yang sama dapat menjalankan pohon apa pun yang dihasilkan parser.

Jalankan untuk memastikan penelusuran pascapesanan menghitung jawaban yang benar.

#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;
}

Kedalaman Tumpukan

Setiap operator bertingkat menambahkan satu bingkai ke tumpukan pemanggilan C. Ekspresi yang sangat bertingkat, seperti seribu tanda kurung, dapat membuat tumpukan meluap.

Sebagian besar ekspresi nyata tidak terlalu dalam, tetapi interpreter yang tangguh dapat beralih ke tumpukan eksplisit agar lebih aman.

Melipat Konstanta

Karena evaluasi dan penguraian menggunakan pohon yang sama, Anda dapat melakukan pengoptimalan. Jika kedua anak dari operasi biner berupa angka, Anda dapat menghitung hasilnya sekali dan mengganti simpul tersebut dengan daun.

Pelipatan konstanta ini merupakan pengoptimalan interpreter yang klasik.

/* 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;
}

Membebaskan Pohon

Simpul yang dialokasikan di heap harus dilepaskan. Pembebasan pascapesanan mengunjungi anak-anak sebelum induknya, sehingga mencerminkan evaluasi.

Melupakan langkah ini menyebabkan kebocoran memori pada setiap ekspresi yang dijalankan interpreter.

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

Minus Unary

Negasi seperti -5 perlu ditangani. Salah satu pilihannya adalah menggunakan simpul unary; pilihan lainnya adalah mengubah -x menjadi 0 - x saat penguraian.

Bagaimanapun caranya, evaluasi tetap menjadi penelusuran rekursif yang sederhana.

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

Mengapa Menelusuri Pohon?

Interpreter yang menelusuri pohon mudah ditulis dan diperbaiki, meskipun kecepatannya lebih rendah. Bahasa seperti Ruby awal menggunakan model ini sebelum beralih ke mesin virtual bytecode.

Selanjutnya, kita menambahkan variabel agar interpreter dapat mengingat nilai.

Pemeriksaan Singkat

Analisis urutan eval mengunjungi simpul-simpul.

Ringkasan

Anda telah mengimplementasikan evaluator rekursif: kasus dasar daun, rekursi operasi biner, perlindungan dari pembagian dengan nol, serta pembebasan pohon dan pelipatan konstanta.

Interpreter kini dapat menghitung AST aritmetika apa pun. Penambahan variabel adalah langkah berikutnya.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Mengevaluasi Pohon” gratis?

Ya — teks lengkap “Mengevaluasi Pohon” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Mengevaluasi Pohon”?

Hitung hasilnya. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C Academy?

Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Mengevaluasi Pohon” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke C Academy