Ağacı Değerlendirme
Sonucu hesaplayın.
Ağacı Değerlendirme, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 3. 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.
AST Üzerinde Dolaşma
Değerlendirme, son-sıralı bir dolaşmadır: önce alt düğümleri hesaplar, ardından düğümün işleciyle bunları birleştirirsiniz. Sayı yaprağı, değerini doğrudan döndürür.
Bu ağaç üzerinde dolaşan yorumlayıcı, bir yorumlayıcının sahip olabileceği en basit arka uçtur.
eval İmzası
Değerlendiricimiz bir düğüm işaretçisi alır ve bir tamsayı döndürür. Ağaç özyinelemeli olduğu için işlev de özyinelemelidir.
Kayan noktalı dillerde bunun yerine double veya etiketli bir değer döndürürdünüz.
int eval(Node *n); /* returns the integer value of the subtree */Bir Yaprağı Değerlendirme
Temel durum özyinelemeyi durdurur. Bir düğüm sayı olduğunda, değeri o alt ağacın yanıtıdır.
Her özyinelemeli iniş bir temel duruma ulaşmalıdır; aksi hâlde hiç sonlanmaz.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}Bir BinOp'u Değerlendirme
Bir işleç düğümünde iki alt düğüme özyinelemeli olarak iner, ardından işleci uygularız. Solu sağdan önce değerlendirmek, alışılmış soldan sağa sıralamayı sağlar.
İşleç karakteri üzerinde kullanılan bir switch, mantığı okunabilir tutar.
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;
}Sıfıra Bölmeyi Denetleme
Tamsayıları sıfıra bölmek C dilinde tanımsız davranıştır ve genellikle sürecin çökmesine yol açar. Güvenli bir yorumlayıcı önce böleni denetler.
Denetlenmeyen bir SIGFPE yerine düzgün bir çalışma zamanı hatası bildirmek daha iyidir.
#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;
}Uçtan Uca Değerlendirme
Burada (2 + 3) * 4 için elle oluşturulmuş bir ağaç değerlendirilerek 20 sonucu elde edilir. Aynı eval, ayrıştırıcının ürettiği her ağacı çalıştırabilir.
Son-sıralı dolaşmanın doğru yanıtı hesapladığını doğrulamak için çalıştırın.
#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;
}Yığın Derinliği
Her iç içe işleç, C çağrı yığınına bir çerçeve ekler. Bin parantez içeren bir ifade gibi çok derin bir ifade yığını aşırı doldurabilir.
Gerçek ifadelerin çoğu sığdır; ancak sağlam bir yorumlayıcı güvenlik için açık bir yığına geçebilir.
Sabitleri Katlama
Değerlendirme ile ayrıştırma aynı ağacı paylaştığı için eniyileme yapabilirsiniz. Bir ikili işlemin her iki alt düğümü de sayıysa sonucu bir kez hesaplayıp düğümü bir yaprakla değiştirebilirsiniz.
Bu sabit katlama, klasik bir yorumlayıcı eniyilemesidir.
/* 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;
}Ağacı Serbest Bırakma
Yığın üzerinde ayrılan düğümler serbest bırakılmalıdır. Son-sıralı bir serbest bırakma işleminde önce alt düğümler, ardından üst düğüm ziyaret edilir; bu, değerlendirmeyi yansıtır.
Bunu unutmak, yorumlayıcının çalıştırdığı her ifadede bellek sızıntısına neden olur.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}Tekli Eksi
-5 gibi olumsuzlama işlemlerinin ele alınması gerekir. Bir seçenek tekli bir düğüm kullanmaktır; başka bir seçenek ise ayrıştırma sırasında -x ifadesini 0 - x biçimine açmaktır.
Her iki durumda da değerlendirme basit bir özyinelemeli dolaşım olarak kalır.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}Neden Ağaç Üzerinde Dolaşma?
Ağaç üzerinde dolaşan yorumlayıcıları yazmak ve hata ayıklamak kolaydır; bunun karşılığında bir miktar hız kaybedilir. İlk Ruby gibi diller, bayt kodu sanal makinelerine geçmeden önce bu modeli kullanıyordu.
Sırada, yorumlayıcının değerleri hatırlayabilmesi için değişkenler ekleyeceğiz.
Hızlı Kontrol
eval işlevinin düğümleri hangi sırayla ziyaret ettiğini düşünün.
Özet
Özyinelemeli bir değerlendirici uyguladınız: yapraklar için temel durum, binop özyinelemesi, sıfıra bölme denetimi ve ayrıca ağaç serbest bırakma ile sabit katlama.
Yorumlayıcı artık her aritmetik AST'yi hesaplayabiliyor. Sırada değişkenleri eklemek var.
Sıkça Sorulan Sorular
“Ağacı Değerlendirme” dersi ücretsiz mi?
Evet — “Ağacı Değerlendirme” 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.
“Ağacı Değerlendirme” dersinde ne öğreneceğim?
Sonucu hesaplayın. 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 3. dersidir.
“Ağacı Değerlendirme” 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
- Girdiyi Belirteçlere Ayırma
- İfadeleri Ayrıştırma
- Ağacı Değerlendirme
- Değişken Ekleme