TD 1

Du Hello World

au parseur S-expression

9 exercices pour construire un évaluateur d'expressions arithmétiques

Laurent Thiry — Programmation en C

« Chaque expert a commencé par écrire Hello World.
Puis il a oublié un point-virgule. Et ça a marché quand même… enfin, non. »

1 / 12

🗺️ Plan de la séance

Hello World — Écrire, compiler, exécuter
Variables & boucles — Calculer n!
Fonctions — Extraire factorielle
Bibliothèque Sexp — Découvrir les S-expressions
Parser — Lire une expression depuis la ligne de commande
Évaluateur — Calculer (+ 2 (* 3 4))
Bonus — REPL interactif
Aller plus loin — Défis supplémentaires
Sans filet — À vous de jouer

2 heures. 9 exercices. Un seul objectif : arriver à la machine à café en ayant un parseur qui marche. La machine à café, elle, n'aura pas de parseur. Normal.

2 / 12

1. Hello World ★☆☆

Créez un fichier hello.c qui affiche "Hello World".

a) Premier programme

Écrivez le programme avec #include <stdio.h>, main(), printf
Compilez avec gcc
Exécutez ./hello

b) Personnalisation

Modifiez le programme pour qu'il affiche "Hello <votre_prénom>"
Utilisez argv[1] pour passer le prénom en argument
Si aucun argument n'est fourni, affichez "Hello World" par défaut

c) Boucle d'affichage

Affichez tous les arguments : "Hello Alice, Bob, Charlie!"
Gérez le cas où il n'y a qu'un seul argument : "Hello Alice!"

🐍 Voir la solution

/* hello.c — solution complète */
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {
    /* b) argument unique */
    if (argc == 2) {
        printf("Hello %s!\n", argv[1]);
        return 0;
    }
    /* c) arguments multiples */
    if (argc > 2) {
        printf("Hello");
        for (int i = 1; i < argc; i++) {
            printf("%s%s", i == 1 ? " " : ", ", argv[i]);
        }
        printf("!\n");
        return 0;
    }
    /* a) défaut */
    printf("Hello World!\n");
    return 0;
}

💡 Compilation : gcc -Wall -Wextra -std=c99 -o hello hello.c. L'option -Wall active tous les warnings. Le C ne vous tient pas la main, mais -Wall vous offre un gilet de sauvetage.

3 / 12

2. Variables & boucles — factorielle ★☆☆

Calculez la factorielle d'un nombre entier.

a) Version itérative

Demandez un nombre au clavier
Calculez n! avec une boucle for ou while
Affichez le résultat
Testez avec 0!, 5!, 10!

b) Version récursive

Réécrivez factorielle sous forme récursive
Comparez les deux versions : quelle est la limite récursive chez vous ?

c) Suite de Fibonacci

Affichez les n premiers termes de la suite de Fibonacci
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
Testez avec n=10, n=20

🐍 Voir la solution

/* a) itératif */
long long factorielle_iter(int n) {
    long long res = 1;
    for (int i = 2; i <= n; i++) res *= i;
    return res;
}

/* b) récursif */
long long factorielle_rec(int n) {
    if (n <= 1) return 1;
    return n * factorielle_rec(n - 1);
}

/* c) Fibonacci */
void fibonacci(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        printf("%lld ", a);
        long long tmp = a + b;
        a = b; b = tmp;
    }
    printf("\n");
}

21! dépasse les 64 bits. Le C ne vous préviendra pas — il continuera comme si de rien n'était, en vous donnant un résultat faux. C'est ce qu'on appelle une confiance aveugle.

4 / 12

3. Fonctions ★☆☆

Extrayez le calcul dans des fonctions réutilisables.

a) Fonction factorielle

Écrivez une fonction factorielle
Appelez-la depuis le main pour plusieurs valeurs
Ajoutez la gestion d'erreur si n < 0

b) Fonction puissance

Écrivez long long puissance(int a, int b) qui calcule a^b
Utilisez l'exponentiation rapide : O(log b) multiplications
Testez : 2¹⁰=1024, 3⁵=243

c) Combinaison

Écrivez long long combinaison(int n, int k) = n! / (k! × (n-k)!)
Testez : C(5,2)=10, C(10,5)=252

🐍 Voir la solution

/* a) factorielle */
long long factorielle(int n) {
    if (n < 0) return -1;
    long long res = 1;
    for (int i = 2; i <= n; i++) res *= i;
    return res;
}

/* b) exponentiation rapide */
long long puissance(int a, int b) {
    if (b == 0) return 1;
    long long moitie = puissance(a, b / 2);
    return (b % 2 == 0) ? moitie * moitie : moitie * moitie * a;
}

/* c) combinaison */
long long combinaison(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;  /* optimisation */
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - k + i) / i;
    }
    return res;
}

💡 Makefile : N'oubliez pas d'écrire un Makefile avec une tabulation, pas des espaces. Le Makefile est aussi exigeant que votre prof de C.

5 / 12

4. Bibliothèque Sexp ★★☆

Découvrez sexpression.h — la bibliothèque qui permet de manipuler des S-expressions.

a) Premières manipulations

Créez sexplore.c qui inclut "sexpression.h"
Utilisez sexp_int pour créer un entier, sexp_print pour l'afficher
Créez une liste avec sexp_cons
Compilez avec sexpression.c

b) Arbre d'expressions

Créez une S-expression qui représente (+ 2 (* 3 4))
Affichez-la avec sexp_print — le résultat doit être (+ 2 (* 3 4))
Utilisez sexp_sym pour les opérateurs

c) Compter les nœuds

Écrivez une fonction int compte_ndeuds(Sexp *e) qui compte récursivement les nœuds d'une S-expression
Testez sur (+ 2 (* 3 4)) : combien de nœuds ?

🐍 Voir la solution

#include "sexpression.h"
#include <stdio.h>

/* c) compteur récursif */
int compte_ndeuds(Sexp *e) {
    if (!e) return 0;
    if (e->type == SEXPR_CONS)
        return 1 + compte_ndeuds(e->car) + compte_ndeuds(e->cdr);
    return 1;  /* atom */
}

int main() {
    /* a) entier + liste */
    Sexp *e = sexp_int(42);
    sexp_print(e); printf("\n");
    Sexp *lst = sexp_cons(sexp_int(1),
                sexp_cons(sexp_int(2),
                    sexp_cons(sexp_int(3), NULL)));
    sexp_print(lst); printf("\n");

    /* b) arbre (+ 2 (* 3 4)) */
    Sexp *arbre = sexp_cons(sexp_sym("+"),
        sexp_cons(sexp_int(2),
            sexp_cons(sexp_cons(sexp_sym("*"),
                sexp_cons(sexp_int(3),
                    sexp_cons(sexp_int(4), NULL))),
            NULL)));
    sexp_print(arbre); printf("\n");
    printf("Nœuds : %d\n", compte_ndeuds(arbre));

    sexp_free(e); sexp_free(lst); sexp_free(arbre);
    return 0;
}

💡 Types : Sexp peut être SEXPR_INT, SEXPR_SYM, SEXPR_CONS, SEXPR_FLOAT, SEXPR_CELL ou SEXPR_NATIVE. Le champ e->type permet de savoir à quoi on a affaire.

6 / 12

5. Parser une expression ★★☆

Utilisez sexp_parse pour transformer une chaîne en S-expression.

a) Premier parse

Créez parseur.c qui lit une expression depuis la ligne de commande
Utilisez sexp_parse pour la parser
Affichez le résultat parsé
Testez avec : "(+ 2 (* 3 4))", "(lambda (x) x)"

b) Gestion d'erreurs

Testez "(+ 2 (* 3 4)" (parenthèse manquante)
Affichez un message d'erreur clair si sexp_parse retourne NULL
Testez avec "" (chaîne vide)

c) Parse depuis un fichier

Lisez une expression depuis un fichier texte passé en second argument
Utilisez fgets/fread pour récupérer le contenu
Testez : créez expr.txt contenant (+ 10 20 30)

🐍 Voir la solution

#include <stdio.h>
#include <stdlib.h>
#include "sexpression.h"

/* c) lire un fichier */
char *lit_fichier(const char *path) {
    FILE *f = fopen(path, "r");
    if (!f) return NULL;
    fseek(f, 0, SEEK_END);
    long sz = ftell(f);
    rewind(f);
    char *buf = malloc(sz + 1);
    fread(buf, 1, sz, f);
    buf[sz] = 0;
    fclose(f);
    return buf;
}

int main(int argc, char **argv) {
    const char *input;
    char *buf = NULL;

    if (argc >= 3) {         /* c) depuis fichier */
        buf = lit_fichier(argv[2]);
        input = buf ? buf : "";
    } else if (argc > 1) { /* a) depuis argv */
        input = argv[1];
    } else {
        input = "(+ 2 3)";
    }

    Sexp *expr = sexp_parse(input);
    /* b) gestion d'erreur */
    if (!expr) {
        fprintf(stderr, "Erreur : expression invalide\n");
        free(buf);
        return 1;
    }
    printf("Parsé : ");
    sexp_print(expr);
    printf("\n");
    sexp_free(expr);
    free(buf);
    return 0;
}

Les parenthèses, c'est comme les fraises Tagada : si vous en avez trop, ça colle. Si vous en avez pas assez, c'est triste. L'équilibre, voilà la clé.

7 / 12

6. Évaluateur arithmétique ★★★

Évaluez récursivement une expression arithmétique parsée : (+ 2 (* 3 4)) → 14

a) Évaluateur de base

Écrivez une fonction eval qui parcourt l'arbre
Si SEXPR_INT → retourner sa valeur
Si SEXPR_CONS → c'est (op arg1 arg2 ...) : évaluer chaque arg, appliquer l'opérateur
Gérez + , - , * , /

b) Division par zéro

Ajoutez une vérification : si le diviseur vaut 0, affichez "Erreur : division par zéro"
Retournez 0 dans ce cas (ou mieux : exit(1))

c) Opérateurs supplémentaires

Ajoutez l'opérateur % (modulo)
Ajoutez l'opérateur ^ (puissance) — utilisez votre fonction puissance
Testez : (% 10 3) → 1, (^ 2 10) → 1024

🐍 Voir la solution

long long eval(Sexp *e) {
    if (e->type == SEXPR_INT)
        return e->entier;

    char *op = e->car->symbole;
    Sexp *args = e->cdr;

    long long val = eval(args->car);
    args = args->cdr;

    while (args) {
        long long v = eval(args->car);
        if (op[0] == '+') val += v;
        else if (op[0] == '-') val -= v;
        else if (op[0] == '*') val *= v;
        else if (op[0] == '/') {
            if (v == 0) { /* b) */
                fprintf(stderr, "Division par zéro\n");
                return 0;
            }
            val /= v;
        }
        else if (op[0] == '%') val %= v;   /* c) modulo */
        else if (op[0] == '^') val = puissance(val, v); /* c) puissance */
        args = args->cdr;
    }
    return val;
}

💡 Pensez-y : une liste (+ 2 (* 3 4)) est représentée en interne comme cons(+, cons(2, cons(cons(*, cons(3, cons(4, NULL))), NULL))). Le car du CONS est le premier élément, le cdr est le reste.

8 / 12

7. Bonus — REPL interactif ★★☆

Enveloppez votre parseur + évaluateur dans une boucle interactive.

a) Boucle minimale

Boucle infinie qui : affiche un prompt, lit une ligne, parse, évalue, affiche le résultat
Ajoutez la commande exit pour sortir
Testez : (+ 1 2) → (* 3 4) → (- 10 5)

b) Historique

Stockez les 10 dernières expressions dans un tableau circulaire
Ajoutez la commande history pour les afficher
Ajoutez !n pour ré-exécuter la n-ième entrée de l'historique

c) Mode batch

Si un argument est passé, traitez-le comme un fichier .lisp
Lisez le fichier ligne par ligne, évaluez chaque expression, affichez les résultats
Testez : créez test.lisp avec (+ 1 2), (* 3 4)

🐍 Voir la solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "sexpression.h"

/* b) historique circulaire */
#define HIST_SIZE 10
char *history[HIST_SIZE];
int hist_idx = 0, hist_count = 0;

void hist_add(const char *line) {
    free(history[hist_idx]);
    history[hist_idx] = strdup(line);
    hist_idx = (hist_idx + 1) % HIST_SIZE;
    if (hist_count < HIST_SIZE) hist_count++;
}

const char *hist_get(int n) {
    if (n < 0 || n >= hist_count) return NULL;
    int idx = (hist_idx - hist_count + n) % HIST_SIZE;
    return history[idx];
}

int main(int argc, char **argv) {
    /* c) mode batch */
    if (argc > 1) {
        FILE *f = fopen(argv[1], "r");
        if (!f) { perror(argv[1]); return 1; }
        char line[1024];
        while (fgets(line, sizeof(line), f)) {
            line[strcspn(line, "\n")] = 0;
            if (line[0] == 0 || line[0] == ';') continue;
            Sexp *e = sexp_parse(line);
            if (e) { printf("> %lld\n", eval(e)); sexp_free(e); }
        }
        fclose(f);
        return 0;
    }

    /* a) REPL interactif */
    char ligne[1024];
    while (1) {
        printf("λ > ");
        if (!fgets(ligne, sizeof(ligne), stdin)) break;
        ligne[strcspn(ligne, "\n")] = 0;
        if (strcmp(ligne, "exit") == 0) break;
        if (strcmp(ligne, "history") == 0) {
            for (int i = 0; i < hist_count; i++)
                printf("%d: %s\n", i, hist_get(i));
            continue;
        }
        if (ligne[0] == '!') {
            int n = atoi(ligne + 1);
            const char *prev = hist_get(n);
            if (prev) { strcpy(ligne, prev); printf("→ %s\n", ligne); }
            else { printf("Pas d'entrée %d\n", n); continue; }
        }
        if (ligne[0] == 0) continue;
        hist_add(ligne);
        Sexp *expr = sexp_parse(ligne);
        if (!expr) { printf("Erreur de syntaxe\n"); continue; }
        long long r = eval(expr);
        printf("= %lld\n", r);
        sexp_free(expr);
    }
    for (int i = 0; i < HIST_SIZE; i++) free(history[i]);
    return 0;
}

Félicitations, vous venez d'écrire votre premier interpréteur interactif. Les ingénieurs de Lisp Machines Inc. pleurent de joie quelque part.

9 / 12

8. Aller plus loin ★★★

Défis supplémentaires pour les plus rapides. Solutions fournies pour vérification.

🔢 Triangle de Pascal

Affichez les n premières lignes du triangle de Pascal en utilisant votre fonction combinaison.

Exemple pour n=5 :

📊 Mini wc

Écrivez mini-wc.c qui compte les lignes, mots et caractères d'un fichier (comme wc sous Unix).

Utilisez fgetc et un automate à états pour compter les mots.

🐍 Voir la solution

/* Triangle de Pascal */
void pascal(int n) {
    for (int i = 0; i < n; i++) {
        for (int s = 0; s < n - i - 1; s++) printf(" ");
        for (int j = 0; j <= i; j++)
            printf("%lld ", combinaison(i, j));
        printf("\n");
    }
}

/* mini-wc */
int main(int argc, char **argv) {
    FILE *f = argc > 1 ? fopen(argv[1], "r") : stdin;
    int lignes = 0, mots = 0, carac = 0, dans_mot = 0, c;
    while ((c = fgetc(f)) != EOF) {
        carac++;
        if (c == '\n') lignes++;
        if (c == ' ' || c == '\n' || c == '\t') { dans_mot = 0; }
        else if (!dans_mot) { mots++; dans_mot = 1; }
    }
    printf("%d %d %d %s\n", lignes, mots, carac, argc > 1 ? argv[1] : "");
    return 0;
}

Le triangle de Pascal a une infinité de propriétés. Celle que vous venez d'implémenter : il calcule des combinaisons sans faire de factorielles. Pas mal pour un triangle.

10 / 12

9. Sans filet ★★★

⚠️ Pas de solution fournie. Ces exercices sont conçus pour vous faire voler de vos propres ailes. Le code let.c et calc.c peuvent vous servir d'inspiration.

🔬 Vérificateur de parenthèses

Écrivez un programme qui lit une chaîne et vérifie si les parenthèses sont correctement équilibrées.

Exemples :

"(+ 2 (* 3 4))" → OK
"(+ 2 (* 3 4)" → Erreur (parenthèse ouvrante non fermée)
")( 1 2 (" → Erreur (parenthèse fermante avant ouvrante)

Indice

🔄 Opérateurs de comparaison

Ajoutez les opérateurs =, <, > à l'évaluateur arithmétique du TD1.

Ils doivent retourner 0 (faux) ou 1 (vrai).

Testez : (= (+ 2 3) 5) → 1, (> 10 (* 2 3)) → 1

✏️ Défi bonus : Écrivez un programme qui affiche un damier de taille n×n avec des # et des . alternés, sans utiliser de tableau.

11 / 12

TD 1 — Terminé !

En 2 heures, vous êtes passés de printf("Hello World")
à un évaluateur d'expressions arithmétiques S-expressions.

📄 Fichiers créés
hello.c → factorielle.c → sexplore.c → parseur.c → repl.c

📚 Prochaine séance
TD 2 — Environnements & fermetures lexicales

🔑 Mots-clés
compilation, récursivité, S-expression, parseur, REPL

Un interpréteur qui marche, c'est comme un chat qui ronronne : c'est rare, c'est beau, et ça vous regarde avec condescendance.

« On ne devient pas magicien en un jour. Mais on peut parser en une soirée. »

12 / 12