Ewaluacja drzewa
Obliczy Pan/Pani wynik.
Ewaluacja drzewa to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Przechodzenie po AST
Obliczanie jest przejściem postorder: najpierw obliczamy węzły potomne, a następnie łączymy je za pomocą operatora węzła. Liść będący liczbą po prostu zwraca swoją wartość.
Ten interpreter przechodzący po drzewie jest najprostszym backendem, jaki może mieć interpreter.
Sygnatura eval
Nasz ewaluator przyjmuje wskaźnik do węzła i zwraca liczbę całkowitą. Ponieważ drzewo ma strukturę rekurencyjną, funkcja również jest rekurencyjna.
W językach zmiennoprzecinkowych zwracaliby Państwo zamiast tego double albo wartość z tagiem.
int eval(Node *n); /* returns the integer value of the subtree */Obliczanie liścia
Przypadek bazowy zatrzymuje rekurencję. Gdy węzeł jest liczbą, jego wartość stanowi odpowiedź dla tego poddrzewa.
Każde zejście rekurencyjne musi dotrzeć do przypadku bazowego, w przeciwnym razie nigdy by się nie zakończyło.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}Obliczanie BinOp
W przypadku węzła operatora schodzimy rekurencyjnie do obu dzieci, a następnie stosujemy operator. Obliczanie najpierw lewego, a potem prawego dziecka zapewnia zwykłą kolejność od lewej do prawej.
Instrukcja switch dotycząca znaku operatora sprawia, że logika pozostaje czytelna.
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;
}Zabezpieczenie przed dzieleniem przez zero
Dzielenie całkowite przez zero ma w języku C niezdefiniowane zachowanie i zazwyczaj powoduje awarię procesu. Bezpieczny interpreter najpierw sprawdza dzielnik.
Kontrolowany błąd wykonania jest lepszy niż niekontrolowany 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;
}Obliczanie od początku do końca
W tym przykładzie ręcznie zbudowane drzewo dla (2 + 3) * 4 zostaje obliczone jako 20. To samo eval obsłuży każde drzewo utworzone przez parser.
Uruchom program, aby potwierdzić, że przejście postorder oblicza poprawny wynik.
#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;
}Głębokość stosu
Każdy zagnieżdżony operator dodaje ramkę do stosu wywołań C. Głęboko zagnieżdżone wyrażenie, na przykład zawierające tysiąc par nawiasów, może przepełnić stos.
Większość rzeczywistych wyrażeń jest płytko zagnieżdżona, ale solidny interpreter może dla bezpieczeństwa użyć jawnego stosu.
Redukcja stałych
Ponieważ obliczanie i parsowanie korzystają z tego samego drzewa, można je optymalizować. Jeśli oba dzieci węzła binop są liczbami, można obliczyć wynik raz i zastąpić węzeł liściem.
Ta redukcja stałych jest klasyczną optymalizacją interpreterów.
/* 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;
}Zwalnianie drzewa
Węzły zaalokowane na stercie należy zwolnić. Zwalnianie postorder odwiedza dzieci przed rodzicem, tak jak podczas obliczania.
Pomijanie tego kroku powoduje wyciek pamięci przy każdym wyrażeniu wykonywanym przez interpreter.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}Jednoargumentowy minus
Negację, taką jak -5, trzeba obsłużyć. Jedną z możliwości jest węzeł unarny; inną desugaring -x do 0 - x podczas parsowania.
W obu przypadkach obliczanie pozostaje prostym rekurencyjnym przejściem.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}Dlaczego przechodzenie po drzewie?
Interpreter przechodzący po drzewie jest łatwy do napisania i debugowania, choć odbywa się to kosztem szybkości. Języki takie jak wczesne wersje Ruby korzystały z tego modelu, zanim przeszły na maszyny wirtualne z bytecode'em.
W następnym kroku dodamy zmienne, aby interpreter mógł zapamiętywać wartości.
Szybkie sprawdzenie
Zastanów się nad kolejnością, w jakiej eval odwiedza węzły.
Podsumowanie
Zaimplementowali Państwo rekurencyjny ewaluator: przypadek bazowy dla liścia, rekurencję dla binop, zabezpieczenie przed dzieleniem przez zero, a także zwalnianie drzewa i redukcję stałych.
Interpreter oblicza teraz dowolne arytmetyczne AST. Następnym krokiem jest dodanie zmiennych.
Często zadawane pytania
Czy lekcja „Ewaluacja drzewa” jest bezpłatna?
Tak — pełny tekst „Ewaluacja drzewa” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Ewaluacja drzewa”?
Obliczy Pan/Pani wynik. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Ewaluacja drzewa”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.