C Academy · Lektion

Ausdrücke parsen

Erstellen Sie einen Parsebaum.

Ausdrücke parsen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Von Tokens zum Baum

Beim Parsing wird ein flacher Token-Datenstrom in einen strukturierten Abstrakten Syntaxbaum (AST) umgewandelt. Der Baum bildet Präzedenz und Gruppierung ab, die in den rohen Tokens nur angedeutet sind.

Für 3 + 4 * 2 verschachtelt der AST die Multiplikation unter der Addition. Dadurch ergibt sich 11 statt 14.

Aufbau eines AST-Knotens

Jeder Knoten ist entweder ein Zahlenblatt oder eine binäre Operation mit zwei Kindern. Eine markierte Struct mit einer Union hält den Speicherbedarf gering.

Das Operatorzeichen unterscheidet zur Laufzeit +, -, * und /.

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;

Knoten allokieren

Zwei kleine Konstruktoren allokieren Knoten auf dem Heap. Beim Aufbau des Baums von unten nach oben werden zuerst Blätter erstellt und anschließend in Operator-Knoten eingeschlossen.

In einem produktiven Interpreter würden Sie diese Allokationen verfolgen, um sie später freizugeben.

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

Die Grammatik

Wir verwenden eine klassische Grammatik mit Vorrangregeln. expr verarbeitet + und -, term verarbeitet * und /, und factor verarbeitet Zahlen und Klammern.

Da Regeln mit höherem Vorrang tiefer liegen, bindet die Multiplikation automatisch stärker als die Addition.

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

Tokens abgleichen

Ein expect-Hilfsprogramm konsumiert ein Token der erforderlichen Art oder bricht ab. Es ist der Vertrag des Parsers mit dem Lexer.

Wir verwenden die Lookahead-Hilfsfunktionen cur und bump aus der Lektion zum Tokenizer erneut.

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

Einen Factor parsen

Ein Factor ist das Atom der Grammatik: entweder eine Literalkonstante oder ein geklammerter Teilausdruck. Klammern führen rekursiv zurück zu parse_expr.

Diese Rekursion gibt Parsern mit rekursivem Abstieg ihren Namen.

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

Einen Term parsen

Ein Term parst zunächst einen Factor und wiederholt dies, solange * oder / gefunden wird. Jeder Operator wird dabei in einen linksassoziativen Binop-Knoten eingefügt.

Linksassoziativität bedeutet, dass 8 / 4 / 2 als (8 / 4) / 2 = 1 geparst wird.

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

Einen Ausdruck parsen

Die oberste Regel entspricht parse_term, verarbeitet aber + und -. Jede Ebene ruft die Regel mit dem nächsthöheren Vorrang auf, sodass der Baum korrekt verschachtelt wird.

Diese Struktur aus drei Funktionen bildet das Herzstück des Parsers.

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

Den Baum untersuchen

Dieses Programm parst einen Ausdruck und gibt ihn in vollständig geklammerter Form wieder aus. So wird sichtbar, wie der Vorrang aufgelöst wurde.

Der Pretty-Printer durchläuft rekursiv dieselbe Knotenstruktur, die der Parser aufgebaut hat.

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

Linke Rekursion vermeiden

Eine naive Grammatik wie expr = expr '+' term würde dazu führen, dass parse_expr sich endlos selbst aufruft. Rekursiver Abstieg kann direkte linke Rekursion nicht verarbeiten.

Wenn Sie die Regel als while-Schleife über { '+' term } umformulieren, umgehen Sie die Endlosrekursion vollständig.

Warum ein AST?

Der AST trennt Syntax und Ausführung. Derselbe Baum kann ausgewertet, optimiert oder in Bytecode kompiliert werden, ohne ihn erneut zu parsen.

Als Nächstes durchlaufen wir diesen Baum, um seinen Wert zu berechnen.

Schnelltest

Überlegen Sie, wie die Ebenen der Grammatik den Vorrang erzwingen.

Zusammenfassung

Sie haben einen Parser mit rekursivem Abstieg geschrieben: AST-Knotenstrukturen, Konstruktoren sowie die Funktionen expr/term/factor, die Vorrang und Linksassoziativität codieren.

Der daraus entstandene Baum ist zur Auswertung bereit.

Häufig gestellte Fragen

Ist die Lektion „Ausdrücke parsen“ kostenlos?

Ja — der vollständige Text von „Ausdrücke parsen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Ausdrücke parsen“?

Erstellen Sie einen Parsebaum. Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.

Wie lange dauert die Lektion „Ausdrücke parsen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C Academy