0Pricing
C Academy · Урок

Вычисление дерева

Вычислите результат.

«Вычисление дерева» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Обход AST

Вычисление выполняется постфиксным обходом: сначала вычисляются дочерние узлы, затем их значения объединяются оператором узла. Лист-число просто возвращает своё значение.

Этот интерпретатор с обходом дерева — самый простой вид серверной части интерпретатора.

Сигнатура eval

Наш вычислитель принимает указатель на узел и возвращает целое число. Поскольку дерево рекурсивно, рекурсивной является и функция.

Для языков с числами с плавающей точкой вместо этого можно возвращать double или значение с указанием типа.

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

Вычисление листа

Базовый случай останавливает рекурсию. Если узел содержит число, его значение является ответом для этого поддерева.

Каждый рекурсивный спуск должен достигать базового случая, иначе он никогда не завершится.

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

Вычисление BinOp

Для узла оператора мы рекурсивно обходим обоих потомков, а затем применяем оператор. Вычисление левого потомка перед правым обеспечивает обычный порядок слева направо.

Конструкция switch по символу оператора делает логику понятной.

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

Защита от деления на ноль

Целочисленное деление на ноль в C — неопределённое поведение, которое обычно приводит к аварийному завершению процесса. Безопасный интерпретатор сначала проверяет делитель.

Сообщить понятную ошибку времени выполнения лучше, чем допустить неконтролируемый 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;
}

Сквозное вычисление

Здесь вручную построенное дерево для (2 + 3) * 4 вычисляется как 20. Та же функция eval сможет обработать любое дерево, созданное парсером.

Запустите программу, чтобы убедиться, что постфиксный обход вычисляет правильный результат.

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

Глубина стека

Каждый вложенный оператор добавляет кадр в стек вызовов C. Глубоко вложенное выражение, например с тысячей скобок, может переполнить стек.

Большинство настоящих выражений неглубоки, но надёжный интерпретатор может для безопасности перейти на явный стек.

Свёртка констант

Поскольку вычисление и разбор используют одно дерево, его можно оптимизировать. Если оба потомка бинарной операции — числа, результат можно вычислить один раз и заменить узел листом.

Такая свёртка констант — классическая оптимизация интерпретатора.

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

Освобождение дерева

Узлы, выделенные в куче, необходимо освобождать. При постфиксном освобождении сначала посещаются потомки, а затем родитель — так же, как при вычислении.

Если забыть об этом, каждое выражение, обработанное интерпретатором, будет приводить к утечке памяти.

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

Унарный минус

Нужно обрабатывать отрицание, например -5. Один вариант — использовать унарный узел; другой — преобразовать -x в 0 - x во время разбора.

В любом случае вычисление остаётся простым рекурсивным обходом.

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

Зачем обходить дерево?

Интерпретаторы с обходом дерева легко писать и отлаживать, хотя это снижает скорость. Такие языки, как ранние версии Ruby, использовали эту модель до перехода к виртуальным машинам с байткодом.

Далее мы добавим переменные, чтобы интерпретатор мог запоминать значения.

Быстрая проверка

Определите порядок, в котором eval посещает узлы.

Итоги

Вы реализовали рекурсивный вычислитель: базовый случай для листа, рекурсию для бинарных операций, защиту от деления на ноль, а также освобождение дерева и свёртку констант.

Теперь интерпретатор вычисляет любой арифметический AST. Следующий шаг — добавление переменных.

Часто задаваемые вопросы

Урок «Вычисление дерева» бесплатный?

Да — полный текст урока «Вычисление дерева» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Вычисление дерева»?

Вычислите результат. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Вычисление дерева»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Токенизация входных данных
  2. Разбор выражений
  3. Вычисление дерева
  4. Добавление переменных
← Назад к C Academy