C Academy · Ders

İfadeleri Ayrıştırma

Bir ayrıştırma ağacı oluşturun.

İfadeleri Ayrıştırma, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.

Belirteçlerden Ağaca

Ayrıştırma, düz bir belirteç akışını yapılandırılmış bir Abstract Syntax Tree (AST) biçimine dönüştürür. Ağaç, ham belirteçlerin yalnızca ima ettiği öncelik ve gruplamayı kodlar.

3 + 4 * 2 için AST, çarpma işlemini toplamanın içine yerleştirir; böylece sonuç 14 değil 11 olur.

AST Node Biçimi

Her Node ya bir sayı yaprağı ya da iki çocuğu olan ikili bir işlemdir. Etiketli bir struct ile union kullanmak belleği verimli tutar.

İşleç karakteri, çalışma zamanında +, -, * ve / arasında ayrım yapar.

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;

Node Ayırma

İki küçük kurucu, Node'ları heap üzerinde ayırır. Ağacı aşağıdan yukarıya oluşturmak, önce yaprakların, ardından işleç Node'larının oluşturulması anlamına gelir.

Üretim ortamındaki bir yorumlayıcıda, daha sonra serbest bırakabilmek için bu ayırmaları takip ederdiniz.

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

Dilbilgisi

Klasik bir öncelik dilbilgisi kullanıyoruz. expr + ve - işlemlerini, term * ve / işlemlerini, factor ise sayıları ve parantezleri işler.

Daha yüksek öncelikli kurallar daha derinde yer aldığı için çarpma, ek bir işlem gerektirmeden toplamadan daha sıkı bağlanır.

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

Belirteçleri Eşleştirme

Bir expect yardımcı işlevi, gereken türdeki bir belirteci tüketir veya işlemi sonlandırır. Bu, ayrıştırıcının sözcük çözümleyiciyle yaptığı sözleşmedir.

Belirteç oluşturma dersindeki cur ve bump ileri bakış yardımcılarını yeniden kullanıyoruz.

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

Bir Çarpanı Ayrıştırma

Çarpan, dilbilgisinin atomudur: ya bir sayı sabiti ya da parantez içine alınmış bir alt ifadedir. Parantezler, parse_expr işlevine geri dönerek özyineleme yapar.

Özyinelemeli iniş ayrıştırıcılarının adını almasının nedeni bu özyinelemedir.

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

Bir Terimi Ayrıştırma

Bir terim, önce bir çarpanı ayrıştırır; ardından * veya / gördüğü sürece döngüye girerek her birini soldan birleşimli bir ikili işlem düğümünde birleştirir.

Soldan birleşimlilik, 8 / 4 / 2 ifadesinin (8 / 4) / 2 = 1 olarak ayrıştırılması demektir.

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

Bir İfadeyi Ayrıştırma

En üst düzey kural, parse_term işlevini örnek alır; ancak + ve - işlemlerini işler. Her katman, kendisinden daha yüksek öncelikli bir sonraki kuralı çağırır; böylece ağaç doğru biçimde iç içe oluşturulur.

Bu üç işlevli yapı, ayrıştırıcının temelidir.

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

Ağacı İnceleme

Bu program bir ifadeyi ayrıştırır ve önceliğin nasıl çözümlendiğini göstererek ifadeyi bütünüyle parantezlenmiş biçimde yeniden yazdırır.

Biçimlendirici, ayrıştırıcının oluşturduğu düğüm yapısının aynısı üzerinde özyinelemeli olarak çalışır.

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

Soldan Özyinelemeden Kaçınma

expr = expr '+' term gibi saf bir dilbilgisi, parse_expr işlevinin kendisini sonsuza dek çağırmasına neden olur. Özyinelemeli iniş, doğrudan soldan özyinelemeyi işleyemez.

Kuralı { '+' term } üzerinde çalışan bir while döngüsü olarak yeniden yazmak, sonsuz özyinelemeyi tamamen önler.

Neden AST?

AST, söz dizimini yürütmeden ayırır. Aynı ağaç, yeniden ayrıştırmaya gerek kalmadan değerlendirilebilir, eniyileştirilebilir veya bayt koduna derlenebilir.

Sırada, değerini hesaplamak için bu ağaç üzerinde dolaşacağız.

Hızlı Kontrol

Dilbilgisi katmanlarının önceliği nasıl zorunlu kıldığını düşünün.

Özet

Özyinelemeli iniş ayrıştırıcısı yazdınız: AST düğüm yapılarını, oluşturucuları ve öncelik ile soldan birleşimliliği kodlayan expr/term/factor işlevlerini oluşturdunuz.

Ortaya çıkan ağaç artık değerlendirmeye hazırdır.

Sıkça Sorulan Sorular

“İfadeleri Ayrıştırma” dersi ücretsiz mi?

Evet — “İfadeleri Ayrıştırma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.

“İfadeleri Ayrıştırma” dersinde ne öğreneceğim?

Bir ayrıştırma ağacı oluşturun. C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

C Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.

“İfadeleri Ayrıştırma” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu C Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

← C Academy Sayfasına Dön