C Academy · Урок

Разбор выражений

Создайте дерево разбора.

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

От токенов к дереву

Синтаксический анализ превращает плоский поток токенов в структурированное абстрактное синтаксическое дерево (AST). Дерево кодирует приоритет и группировку, которые исходные токены лишь подразумевают.

Для 3 + 4 * 2 AST помещает умножение внутрь сложения, поэтому результат равен 11, а не 14.

Структура узла AST

Каждый узел является либо листом-числом, либо бинарной операцией с двумя дочерними узлами. Структура с меткой и объединением позволяет экономить память.

Символ оператора во время выполнения различает +, -, * и /.

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;

Выделение узлов

Два небольших конструктора выделяют узлы в куче. Построение дерева снизу вверх означает, что сначала создаются листья, а затем они оборачиваются в узлы операторов.

В промышленном интерпретаторе вы отслеживали бы эти выделения, чтобы позднее освободить их.

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

Грамматика

Мы используем классическую грамматику с приоритетами. expr обрабатывает + и -, term — * и /, а factor — числа и скобки.

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

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

Сопоставление токенов

Вспомогательная функция expect извлекает токен требуемого вида или прерывает работу. Это соглашение парсера с лексером.

Мы повторно используем вспомогательные функции просмотра вперёд cur и bump из урока по токенизации.

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

Разбор множителя

Множитель — атом грамматики: это либо числовой литерал, либо выражение в скобках. Скобки рекурсивно возвращают управление в parse_expr.

Именно эта рекурсия дала парсерам с рекурсивным спуском их название.

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

Разбор члена

Разбор члена начинается с одного множителя, затем продолжается в цикле, пока встречается * или /; каждый оператор сворачивается в узел бинарной операции с левой ассоциативностью.

Левая ассоциативность означает, что 8 / 4 / 2 разбирается как (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;
}

Разбор выражения

Верхнее правило подобно parse_term, но обрабатывает + и -. Каждый уровень вызывает правило со следующим более высоким приоритетом, поэтому дерево получает правильную вложенность.

Эта структура из трёх функций — основа парсера.

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

Просмотр дерева

Эта программа разбирает выражение и выводит его в полностью скобочной форме, показывая, как был разрешён приоритет операторов.

Форматировщик рекурсивно обходит ту же структуру узлов, которую построил парсер.

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

Как избежать левой рекурсии

Наивная грамматика вроде expr = expr '+' term заставила бы parse_expr вызывать саму себя бесконечно. Рекурсивный спуск не умеет обрабатывать прямую левую рекурсию.

Переписывание правила в виде цикла while по { '+' term } полностью устраняет бесконечную рекурсию.

Зачем нужен AST?

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

Далее мы обойдём это дерево, чтобы вычислить его значение.

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

Подумайте, как уровни грамматики обеспечивают соблюдение приоритетов.

Итоги

Вы написали парсер с рекурсивным спуском: структуры узлов AST, конструкторы и функции expr/term/factor, кодирующие приоритет и левую ассоциативность.

Получившееся дерево готово к вычислению.

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

Урок «Разбор выражений» бесплатный?

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

Чему я научусь в уроке «Разбор выражений»?

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

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

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

Сколько времени занимает урок «Разбор выражений»?

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

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

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

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

← Назад к C Academy