C Academy · Pelajaran

Mengurai Ekspresi

Bangun pohon hasil penguraian.

Mengurai Ekspresi adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 2 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.

Dari Token Menjadi Pohon

Parsing mengubah aliran token datar menjadi Pohon Sintaksis Abstrak (AST) yang terstruktur. Pohon tersebut menyandikan prioritas dan pengelompokan yang hanya tersirat dalam token mentah.

Untuk 3 + 4 * 2, AST menempatkan perkalian di dalam penjumlahan, sehingga hasilnya 11, bukan 14.

Bentuk Node AST

Setiap Node berupa daun angka atau operasi biner dengan dua anak. Struct bertag yang memiliki union menjaga penggunaan memori tetap ringkas.

Karakter operator membedakan +, -, *, dan / saat runtime.

typedef struct Node {
  enum { N_NUM, N_BINOP } kind;
  union {
    int value;                 /* N_NUM */
    struct {                   /* N_BINOP */
      char op;
      struct Node *left, *right;
    } bin;
  };
} Node;

Mengalokasikan Node

Dua konstruktor kecil mengalokasikan Node di heap. Membangun pohon dari bawah ke atas berarti daun dibuat terlebih dahulu, kemudian dibungkus dalam Node operator.

Dalam interpreter produksi, Anda perlu mencatat alokasi-alokasi ini agar dapat membebaskannya nanti.

#include <stdlib.h>

static Node *num(int v) {
  Node *n = malloc(sizeof *n);
  n->kind = N_NUM; n->value = v;
  return n;
}

static Node *binop(char op, Node *l, Node *r) {
  Node *n = malloc(sizeof *n);
  n->kind = N_BINOP;
  n->bin.op = op; n->bin.left = l; n->bin.right = r;
  return n;
}

Tata Bahasa

Kami menggunakan tata bahasa dengan prioritas klasik. expr menangani + dan -, term menangani * dan /, sedangkan factor menangani angka dan tanda kurung.

Karena aturan dengan prioritas lebih tinggi berada lebih dalam, perkalian secara otomatis memiliki ikatan yang lebih kuat daripada penjumlahan.

/* Grammar (EBNF):
   expr   = term   { ('+' | '-') term } ;
   term   = factor { ('*' | '/') factor } ;
   factor = NUMBER | '(' expr ')' ; */

Mencocokkan Token

Pembantu expect menggunakan token dengan jenis yang diwajibkan atau menghentikan proses. Pembantu ini merupakan kontrak parser dengan lexer.

Kami menggunakan kembali pembantu lookahead cur dan bump dari pelajaran tokenizer.

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

static void expect(TokKind k) {
  if (cur().kind != k) {
    fprintf(stderr, "parse error: unexpected token\n");
    exit(1);
  }
  bump();
}

Mengurai Faktor

Faktor adalah atom dalam tata bahasa: bisa berupa angka literal atau subekspresi dalam tanda kurung. Tanda kurung kembali memanggil parse_expr secara rekursif.

Rekursi inilah yang membuat parser recursive-descent mendapatkan namanya.

static Node *parse_expr(void);

static Node *parse_factor(void) {
  if (cur().kind == TOK_NUM) {
    int v = cur().value; bump();
    return num(v);
  }
  expect(TOK_LPAREN);
  Node *e = parse_expr();
  expect(TOK_RPAREN);
  return e;
}

Mengurai Suku

Suku mengurai satu faktor, lalu mengulang selama menemukan * atau /, dengan menggabungkan setiap operator menjadi simpul operasi biner yang asosiatif-kiri.

Asosiatif-kiri berarti 8 / 4 / 2 diurai sebagai (8 / 4) / 2 = 1.

static Node *parse_term(void) {
  Node *left = parse_factor();
  while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
    char op = (cur().kind == TOK_STAR) ? '*' : '/';
    bump();
    left = binop(op, left, parse_factor());
  }
  return left;
}

Mengurai Ekspresi

Aturan teratas mencerminkan parse_term, tetapi menangani + dan -. Setiap lapisan memanggil aturan dengan prioritas lebih tinggi berikutnya, sehingga pohon tersusun bertingkat dengan benar.

Struktur tiga fungsi ini adalah inti parser.

static Node *parse_expr(void) {
  Node *left = parse_term();
  while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
    char op = (cur().kind == TOK_PLUS) ? '+' : '-';
    bump();
    left = binop(op, left, parse_term());
  }
  return left;
}

Memeriksa Pohon

Program ini mengurai sebuah ekspresi dan mencetaknya kembali dalam bentuk dengan tanda kurung lengkap, sehingga memperlihatkan bagaimana prioritas diselesaikan.

Pencetak yang rapi melakukan rekursi pada struktur simpul yang sama seperti yang dibangun parser.

#include <stdio.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 void show(Node *n){
  if (n->is_num){ printf("%d", n->value); return; }
  printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}

int main(void){
  /* 3 + 4 * 2  ->  (3 + (4 * 2)) */
  Node *ast = B('+', N(3), B('*', N(4), N(2)));
  show(ast); printf("\n");
  return 0;
}

Menghindari Rekursi-Kiri

Tata bahasa naif seperti expr = expr '+' term akan membuat parse_expr memanggil dirinya sendiri tanpa henti. Recursive descent tidak dapat menangani rekursi-kiri langsung.

Dengan menulis ulang aturan tersebut sebagai perulangan while atas { '+' term }, rekursi tak berhingga dapat dihindari sepenuhnya.

Mengapa AST?

AST memisahkan sintaks dari eksekusi. Pohon yang sama dapat dievaluasi, dioptimalkan, atau dikompilasi menjadi bytecode tanpa mengurai ulang.

Selanjutnya, kita menelusuri pohon ini untuk menghitung nilainya.

Pemeriksaan Singkat

Perhatikan bagaimana lapisan tata bahasa menegakkan prioritas.

Ringkasan

Anda telah menulis parser recursive-descent: struktur simpul AST, konstruktor, serta fungsi expr/term/factor yang menyandikan prioritas dan asosiativitas-kiri.

Pohon yang dihasilkan siap dievaluasi.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Mengurai Ekspresi” gratis?

Ya — teks lengkap “Mengurai Ekspresi” 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 “Mengurai Ekspresi”?

Bangun pohon hasil penguraian. 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 2 dari 4.

Berapa lama pelajaran “Mengurai Ekspresi” 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