C Academy · Lekcja

Parsowanie wyrażeń

Zbuduje Pan/Pani drzewo parsowania.

Parsowanie wyrażeń to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 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.

Od tokenów do drzewa

Parsowanie przekształca płaski strumień tokenów w uporządkowane abstrakcyjne drzewo składniowe (AST). Drzewo koduje priorytety i grupowanie, które surowe tokeny jedynie sugerują.

Dla 3 + 4 * 2 AST umieszcza mnożenie wewnątrz dodawania, więc wyrażenie daje wynik 11, a nie 14.

Budowa węzła AST

Każdy węzeł jest albo liściem zawierającym liczbę, albo operacją binarną z dwojgiem dzieci. Struktura ze znacznikiem i unią pozwala oszczędnie wykorzystać pamięć.

Znak operatora rozróżnia w czasie działania +, -, * i /.

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;

Alokowanie węzłów

Dwa niewielkie konstruktory przydzielają węzły na stercie. Budowanie drzewa od dołu oznacza, że najpierw tworzone są liście, a następnie opakowywane w węzły operatorów.

W interpreterze produkcyjnym należałoby śledzić te alokacje, aby później je zwolnić.

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

Gramatyka

Używamy klasycznej gramatyki z priorytetami operatorów. expr obsługuje + i -, term obsługuje * i /, a factor obsługuje liczby i nawiasy.

Ponieważ reguły o wyższym priorytecie znajdują się głębiej, mnożenie automatycznie wiąże silniej niż dodawanie.

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

Dopasowywanie tokenów

Pomocnicza funkcja expect pobiera token wymaganego rodzaju albo przerywa działanie. Jest ona kontraktem parsera z lekserem.

Ponownie wykorzystujemy funkcje pomocnicze do podglądu cur i bump z lekcji o tokenizatorze.

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

Parsowanie czynnika

Czynnik jest atomem gramatyki: albo dosłowną liczbą, albo podwyrażeniem ujętym w nawiasy. Nawiasy prowadzą rekurencyjnie z powrotem do parse_expr.

To właśnie ta rekurencja nadaje parserom rekurencyjnego zejścia ich nazwę.

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

Parsowanie składnika

Składnik parsuje jeden czynnik, a następnie wykonuje pętlę, dopóki napotyka * lub /, składając każdy z nich w lewostronnie łączny węzeł binop.

Lewostronna łączność oznacza, że 8 / 4 / 2 jest parsowane jako (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;
}

Parsowanie wyrażenia

Reguła najwyższego poziomu przypomina parse_term, ale obsługuje + i -. Każda warstwa wywołuje regułę o następnym wyższym priorytecie, dzięki czemu drzewo otrzymuje poprawne zagnieżdżenie.

Ta trójfunkcyjna struktura stanowi serce parsera.

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

Analizowanie drzewa

Ten program parsuje wyrażenie i wypisuje je ponownie w pełni nawiasowanej postaci, pokazując, jak rozstrzygnięto priorytety.

Formater rekurencyjnie przechodzi po tej samej strukturze węzłów, którą zbudował parser.

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

Unikanie lewostronnej rekurencji

Naiwna gramatyka, taka jak expr = expr '+' term, powodowałaby, że parse_expr wywoływałaby samą siebie bez końca. Parser rekurencyjnego zejścia nie obsługuje bezpośredniej lewostronnej rekurencji.

Przepisanie reguły na pętlę while po { '+' term } całkowicie omija nieskończoną rekurencję.

Dlaczego AST?

AST oddziela składnię od wykonania. To samo drzewo można obliczać, optymalizować lub kompilować do bytecode'u bez ponownego parsowania.

W następnym kroku przejdziemy po tym drzewie, aby obliczyć jego wartość.

Szybkie sprawdzenie

Zastanów się, jak warstwy gramatyki wymuszają priorytety operatorów.

Podsumowanie

Napisali Państwo parser rekurencyjnego zejścia: struktury węzłów AST, konstruktory oraz funkcje expr/term/factor, które kodują priorytety i lewostronną łączność.

Powstałe drzewo jest gotowe do obliczenia.

Często zadawane pytania

Czy lekcja „Parsowanie wyrażeń” jest bezpłatna?

Tak — pełny tekst „Parsowanie wyrażeń” 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 „Parsowanie wyrażeń”?

Zbuduje Pan/Pani drzewo parsowania. Ć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 2 z 4.

Ile czasu zajmuje lekcja „Parsowanie wyrażeń”?

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.

Wszystkie lekcje w tym kursie

← Powrót do C Academy