🧠 Cours 3 — Pointeurs, structures, récursivité & parseur

Aux cours précédents, on a appris à programmer une factorielle en C (cours 1) et à construire une machine virtuelle à pile (cours 2). On a vu le C, l'assembleur x86-64, et le bytecode de notre VM.

Maintenant, on va apprendre à lire du texte, à le comprendre (le parser), et à l'exécuter — soit directement, soit en le compilant vers la VM.

Le format qu'on va lire, c'est celui des s-expressions (expressions symboliques), popularisées par le langage LISP (1958 !). Une s-expression, ça ressemble à ça :

(+ 2 (* 3 4))

Ça dit : « additionne 2 et le résultat de la multiplication de 3 par 4 ». Réponse : 14. Notre programme va lire cette chaîne, construire un arbre en mémoire, et soit calculer le résultat, soit générer le bytecode VM correspondant.

Jusqu'ici, on manipulait des variables : des boîtes nommées qui contiennent des valeurs. Mais en C, chaque variable a aussi une adresse — l'endroit où elle se trouve en mémoire.

Le pointeur est une variable qui contient une adresse. C'est un peu comme un signet dans un livre : au lieu de recopier la page, on note juste son numéro.

int x = 42;
int *p = &x;   // p contient l'adresse de x

printf("x = %d\n", x);      // 42
printf("&x = %p\n", &x);   // adresse (hexadécimal)
printf("p = %p\n", p);        // la même adresse
printf("*p = %d\n", *p);     // 42 (valeur pointée)

*p = 99;                    // modifier x via p
printf("x = %d\n", x);        // 99 !

Arithmétique des pointeurs

Quand on a un pointeur char *p sur un caractère, p + 1 avance à l'octet suivant. C'est comme ça qu'on parcourt une chaîne : en faisant avancer un pointeur caractère par caractère.

Dans notre tokeniseur, on utilise exactement ça :

static char *pos;               // pointeur courant dans la chaîne

void token_suivant(void) {
    while (*pos && isspace((unsigned char)*pos))
        pos++;        // avancer tant que c'est un espace

    if (*pos == '(' || *pos == ')') {
        token[0] = *pos;
        pos++;          // avancer d'un caractère
    }
}

isspace teste si un caractère est un espace, tabulation, etc. On l'utilise avec (unsigned char) pour éviter les surprises avec les caractères négatifs (toutes les têtes sont mises en boîte).

Un int contient un entier. Un tableau contient plusieurs entiers du même type. Mais si on veut regrouper des données de types différents ?

Par exemple, notre arbre (AST) a besoin de stocker : le type du nœud (nombre ou opérateur), sa valeur si c'est un nombre, l'opérateur si c'en est un, et les deux sous-arbres (gauche et droite).

typedef struct Node {
    int type;              /* 0 = nombre, 1 = opérateur */
    int valeur;            /* pour les nombres */
    char op;               /* pour les opérateurs : + - * / */
    struct Node *gauche;   /* enfant gauche (pointeur !) */
    struct Node *droite;   /* enfant droit  (pointeur !) */
} Node;

La structure est auto-référente : elle contient des pointeurs vers d'autres Node. C'est comme ça qu'on construit des arbres : chaque nœud pointe vers ses enfants. Sans pointeurs, on ne pourrait pas — la récursion serait impossible.

typedef struct Point {
    int x;
    int y;
} Point;

int main() {
    Point p;               // sur la pile
    p.x = 3;                // accès direct avec .
    p.y = 5;

    Point *pp = &p;      // pointeur vers p
    pp->x = 7;               // accès via pointeur avec ->
    // (*pp).x = 7 aurait marché aussi, mais -> c'est plus beau

    return 0;
}

Au cours 1, on a vu "bonjour" comme argument de printf. Mais en C, une chaîne n'est rien d'autre qu'un tableau de char terminé par un octet nul ('\0').

char ligne[1024];

printf("> ");
fflush(stdout);                      // vider le tampon d'affichage

if (fgets(ligne, sizeof(ligne), stdin)) {
    // enlever le '\n' final
    size_t len = strlen(ligne);
    if (len > 0 && ligne[len - 1] == '\n')
        ligne[len - 1] = '\0';

    if (strcmp(ligne, "quit") == 0)
        break;

    // chercher un opérateur
    if (strchr("+-*/", ligne[0]))
        printf("Un opérateur !\n");

    // convertir un nombre
    int v = atoi(ligne);
}

Dans notre tokeniseur, on utilise strchr("+-*/", *pos) pour tester si le caractère courant est un opérateur. Et atoi(token) pour convertir un token numérique en entier. Simple, efficace, éprouvé.

size_t est le type retourné par strlen et sizeof — c'est un entier non-signé capable de représenter n'importe quelle taille de mémoire. Il est défini dans <stddef.h> (souvent inclus indirectement).

Jusqu'ici, nos variables étaient statiques ou sur la pile (stack). Mais on ne sait pas à l'avance combien de nœuds notre arbre va contenir — ça dépend de l'expression tapée par l'utilisateur.

L'allocation dynamique permet de demander de la mémoire au moment de l'exécution, sur le tas (heap). En C, on utilise malloc (memory allocation) et free.

Node *nouveau_nombre(int v) {
    Node *n = malloc(sizeof(Node));  // assez grand pour un Node
    n->type   = 0;
    n->valeur = v;
    n->gauche = NULL;
    n->droite = NULL;
    return n;
}

Node *nouvel_operateur(char op, Node *g, Node *d) {
    Node *n = malloc(sizeof(Node));
    n->type   = 1;
    n->op     = op;
    n->gauche = g;
    n->droite = d;
    return n;
}

void liberer_node(Node *n) {
    if (!n) return;
    liberer_node(n->gauche);   // libérer récursivement
    liberer_node(n->droite);
    free(n);
}

Le tableau dynamique Bytecode utilise realloc pour grandir au fur et à mesure qu'on émet des instructions :

void emettre(Bytecode *bc, int v) {
    if (bc->taille >= bc->capacite) {
        bc->capacite *= 2;
        bc->code = realloc(bc->code, bc->capacite * sizeof(int));
    }
    bc->code[bc->taille++] = v;
}

Jusqu'ici, nos programmes ne prenaient pas d'arguments. On veut maintenant pouvoir lancer :

./calc "(+ 2 (* 3 4))"
./calc -vm "(+ 2 (* 3 4))"
./calc -vm "(+ 2 (* 3 4))" -o sortie.c
./calc -f expression.txt

C'est le rôle de main(int argc, char *argv[]).

int main(int argc, char *argv[]) {
    int mode_vm = 0;
    const char *expr = NULL;

    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-vm") == 0)
            mode_vm = 1;
        else if (strcmp(argv[i], "-o") == 0 && i + 1 < argc)
            fichier_sortie = argv[++i];
        else
            expr = argv[i];
    }
}

Avec les fichiers, on peut lire une expression depuis un fichier texte (option -f) et écrire le bytecode généré dans un fichier C (-o).

FILE *f = fopen(fichier_entree, "r");
if (!f) {
    fprintf(stderr, "ERREUR: impossible de lire '%s'\n", fichier_entree);
    return 1;
}
static char buf[4096];
buf[0] = '\0';
char ligne[512];
while (fgets(ligne, sizeof(ligne), f))
    strncat(buf, ligne, sizeof(buf) - strlen(buf) - 1);
fclose(f);

stderr (vu au cours 2) est le flux d'erreur standard. On l'utilise pour les messages d'erreur — comme ça, même si l'utilisateur redirige la sortie standard (stdout) vers un fichier, les erreurs restent visibles dans le terminal.

Quand on génère un fichier .c avec -o, on écrit un tableau C complet, prêt à être copié dans vm.c ou inclus avec #include. C'est un exemple de génération de code — un programme qui en écrit un autre.

Une fonction récursive est une fonction qui s'appelle elle-même. C'est une technique élégante pour résoudre des problèmes qui ont une structure naturellement hiérarchique — comme analyser une expression mathématique ou parcourir un arbre.

Exemple classique : la factorielle, qu'on a déjà écrite de façon itérative au cours 1. Voici la version récursive :

long long factorielle(int n) {
    if (n < 0)  return -1;        // cas d'erreur
    if (n <= 1) return 1;          // cas de base
    return n * factorielle(n - 1);  // pas récursif
}

Chaque appel à factorielle(n - 1) empile un nouveau cadre sur la pile d'appels. Quand on atteint le cas de base (n <= 1), les appels se déplient et les multiplications s'enchaînent.

Dans notre parseur, la récursivité est mutuelle (en fait, directe) :

// parse_expr s'appelle elle-même pour les sous-expressions
Node *parse_expr(void) {
    if (strcmp(token, "(") == 0) {
        token_suivant();                        // '('
        char op = token[0];                   // opérateur
        token_suivant();
        Node *g = parse_expr();              // ← appel récursif
        Node *d = parse_expr();              // ← appel récursif
        token_suivant();                     // ')'
        return nouvel_operateur(op, g, d);
    }
    // cas de base : c'est un nombre
    int v = atoi(token);
    token_suivant();
    return nouveau_nombre(v);
}

Le cas de base, c'est quand on rencontre un nombre (pas de parenthèse ouvrante). Sinon, on s'appelle récursivement pour lire les deux sous-expressions.

L'évaluateur aussi est récursif :

int evaluer(Node *n) {
    if (n->type == 0)                 // cas de base : nombre
        return n->valeur;
    int vg = evaluer(n->gauche);       // ← récursion
    int vd = evaluer(n->droite);       // ← récursion
    // appliquer l'opérateur
    switch (n->op) {
        case '+': return vg + vd;
        case '-': return vg - vd;
        case '*': return vg * vd;
        case '/': return vg / vd;
    }
}

La première étape pour comprendre une expression, c'est de la découper en tokens (ou « jetons »). Chaque token est une unité significative : une parenthèse, un opérateur, un nombre.

Exemple avec (+ 2 (* 3 4)) :

La fonction token_suivant() avance le pointeur pos dans la chaîne, saute les espaces, et remplit le buffer global token :

• Si *pos == '(' ou ')' → token = la parenthèse
• Si *pos ∈ "+-*/" → token = l'opérateur (1 caractère)
• Si *pos est un chiffre ou un '-' suivi d'un chiffre → on lit le nombre
• Sinon → erreur (caractère inattendu)

Les variables pos et token sont globales (statiques dans le fichier) — ça simplifie le code, car le tokeniseur et le parseur partagent un état commun. Ce n'est pas idéal pour un programme multi-threadé, mais pour notre calculette pédagogique, c'est parfait.

Une fois qu'on a des tokens, il faut leur donner une structure. C'est le rôle du parseur. On va définir une grammaire — un ensemble de règles qui décrivent la structure d'une expression valide.

Ça se lit : « une expression, c'est soit une parenthèse ouvrante, un opérateur, deux expressions, une parenthèse fermante ; soit un nombre. » C'est une grammaire récursive — la règle expr fait référence à elle-même.

Le parseur qui implémente cette grammaire s'appelle un parseur récursif descendant (recursive descent parser). Chaque règle de la grammaire devient une fonction. Notre seule règle expr devient la fonction parse_expr() qui regarde le token courant et décide :

• Si c'est ( → on lit l'opérateur, les deux sous-expressions, et )
• Si c'est un nombre → on le lit et on crée un nœud
• Sinon → erreur

appel 1 : token = "(" → op = '+'
  appel 2 : token = "2" → nombre 2
  appel 3 : token = "(" → op = '*'
    appel 4 : token = "3" → nombre 3
    appel 5 : token = "4" → nombre 4
  retour 3 : nœud '*' (3, 4) après ')'
retour 1 : nœud '+' (2, *) après ')'

Chaque appel à parse_expr() consomme les tokens de l'expression et retourne un arbre. La récursivité épouse parfaitement la structure hiérarchique de la grammaire — c'est pour ça que parseur rime avec récursif.

L'AST (Abstract Syntax Tree) est la représentation en mémoire de notre expression sous forme d'arbre. Chaque nœud est un struct Node, et les pointeurs gauche et droite relient les nœuds entre eux.

Pour (+ 2 (* 3 4)), l'AST ressemble à ça :

Pour afficher l'AST, on utilise une fonction récursive qui parcourt l'arbre en profondeur (depth-first) :

void afficher_ast(Node *n, int niveau) {
    for (int i = 0; i < niveau; i++) printf("  ");
    if (n->type == 0)
        printf("nombre %d\n", n->valeur);
    else {
        printf("opérateur '%c'\n", n->op);
        afficher_ast(n->gauche,  niveau + 1);
        afficher_ast(n->droite,  niveau + 1);
    }
}

Ce qui donne pour (+ 2 (* 3 4)) :

opérateur '+'
  nombre 2
  opérateur '*'
    nombre 3
    nombre 4

Une fois qu'on a l'AST, l'évaluation est presque triviale : on parcourt l'arbre de façon récursive, on calcule la valeur de chaque sous-arbre, et on combine les résultats.

int evaluer(Node *n) {
    if (n->type == 0)                    // c'est un nombre
        return n->valeur;

    // c'est un opérateur → évaluer les deux fils
    int vg = evaluer(n->gauche);
    int vd = evaluer(n->droite);

    switch (n->op) {
        case '+': return vg + vd;
        case '-': return vg - vd;
        case '*': return vg * vd;
        case '/':
            if (vd == 0) exit(1);
            return vg / vd;
        default:
            fprintf(stderr, "opérateur inconnu\n");
            exit(1);
    }
}

C'est un parcours en post-ordre (post-order traversal) : on évalue d'abord les enfants, puis le parent. C'est exactement ce que fait le compilateur quand il génère le bytecode (section suivante) — à ceci près qu'au lieu de retourner un entier, il émet des instructions.

La trace pour (+ 2 (* 3 4)) :

evaluer('+')
  evaluer(2) → 2
  evaluer('*')
    evaluer(3) → 3
    evaluer(4) → 4
    → 3 * 4 = 12
  → 2 + 12 = 14

Le clou du spectacle : on va compiler notre s-expression vers le bytecode de la VM du cours 2. C'est un compilateur source-à-source (ou plutôt source-à-bytecode) : on traduit un langage (nos s-expressions) en un autre (les opcodes de la VM).

Le principe est simple : on parcourt l'AST en post-ordre et on émet les instructions correspondantes. Pour un nombre, on émet PUSH valeur. Pour un opérateur, on compile les deux opérandes, puis on émet l'opcode :

void compiler_expr(Bytecode *bc, Node *n) {
    if (n->type == 0) {                    // nombre → PUSH
        emettre(bc, PUSH);
        emettre(bc, n->valeur);
        return;
    }
    // opérateur : compiler d'abord les opérandes
    compiler_expr(bc, n->gauche);
    compiler_expr(bc, n->droite);
    // puis l'opération (parcours postfixé !)
    switch (n->op) {
        case '+': emettre(bc, ADD); break;
        case '-': emettre(bc, SUB); break;
        case '*': emettre(bc, MUL); break;
        case '/': /* refusé : pas de DIV dans la VM */
    }
}

Pour (+ 2 (* 3 4)), ça donne :

PUSH 2        ; évalué en dernier (additionné avec *)
PUSH 3        ; premier enfant de *
PUSH 4        ; second enfant de *
MUL           ; 3 * 4 = 12
ADD           ; 2 + 12 = 14
PRINT         ; afficher le résultat
HALT          ; arrêter la VM

Après compilation, on ajoute PRINT et HALT pour que le programme soit autonome. Le résultat peut être affiché à l'écran ou écrit dans un fichier .C avec -o.

Le REPL

Quand on lance ./calc sans argument, on entre dans un REPL — Read Eval Print Loop :

• Read : lire une ligne au clavier
• Eval : tokeniser, parser, évaluer
• Print : afficher le résultat
• Loop : recommencer

C'est exactement comme ça que fonctionnent les interpréteurs LISP, Python, Ruby, JavaScript (node), etc. — la boucle interactive est au cœur de l'expérience programmeur.

void repl(void) {
    char ligne[1024];
    printf("> ");
    fflush(stdout);
    while (fgets(ligne, sizeof(ligne), stdin)) {
        /* nettoyer le '\n' */
        traiter_expression(ligne, 0, NULL);
        printf("> ");
        fflush(stdout);
    }
    printf("Au revoir !\n");
}

Philosophie Unix

Notre programme illustre plusieurs principes de la philosophie Unix :

Notre programme peut être utilisé dans des pipes Unix :

# Évaluer une expression, extraire le résultat
echo "(+ 2 (* 3 4))" | ./calc | grep "=>"

# Compiler une liste d'expressions depuis un fichier
./calc -vm -f mes_expressions.txt -o tout_le_bytecode.c

Cette philosophie de « petits outils interconnectés » est ce qui a fait le succès d'Unix depuis les années 1970. Elle s'oppose à la philosophie « monolithique » d'un outil qui fait tout tout seul (comme un tableur ou un IDE).

En trois cours, on a traversé plusieurs niveaux d'abstraction en programmation :

Chaque niveau ajoute de l'abstraction :

• Assembleur : on gère les registres, les sauts, les piles. Chaque instruction fait exactement une opération CPU.
• C : on a des variables nommées, des types, des boucles, des fonctions. Le compilateur traduit ça en assembleur.
• Bytecode VM : on a des instructions pour une machine qui n'existe pas (notre VM logicielle). C'est interprété par un programme C.
• S-expression : on écrit des expressions mathématiques avec des parenthèses. Pas de boucles, pas de variables — juste des opérateurs et des nombres. C'est soit interprété (évaluateur), soit compilé (vers le bytecode VM).

Compilation vs Interprétation

Notre programme fait les deux :

• Interprétation : le parseur construit l'AST, l'évaluateur le traverse et calcule le résultat. Pas de code intermédiaire.
• Compilation : le parseur construit l'AST, le compilateur génère du bytecode VM, qui pourrait être exécuté plus tard (par la VM). Il y a une étape de traduction séparée.

En vrai LISP (ou Scheme, Clojure…), la frontière est floue. La plupart des implémentations LISP offrent un compilateur JIT (Just-In-Time) qui compile le code à chaud pendant l'exécution. Notre petite calculette montre le principe : on peut lire une expression, l'analyser, et soit l'exécuter directement, soit produire un code pour une autre machine.

LISP/Scheme

Le langage LISP (LISt Processing), créé par John McCarthy en 1958, est le deuxième plus vieux langage de programmation (après Fortran). Sa particularité : le code et les données ont la même forme — des listes entre parenthèses (des s-expressions). C'est ce qui lui donne une puissance d'abstraction redoutable (les macros).

Notre syntaxe (+ 2 (* 3 4)) vient directement de LISP. La seule différence : en LISP, on peut avoir des listes de longueur variable, et tout est expression (même les définitions de fonctions). Notre langage est un sous-ensemble minuscule de Scheme, un dialecte moderne de LISP.

Ce cours a introduit un bon paquet de nouveaux concepts C. En voici le résumé :

Nouveaux mots-clés

Nouveaux opérateurs

Nouvelles fonctions de la bibliothèque standard

Nouveaux concepts

Et on n'a pas encore tout vu ! Il reste les unions, les pointeurs de fonctions, la gestion avancée de la mémoire, les listes chaînées, les arbres binaires de recherche… Chaque concept ouvre la porte à d'autres.