Vaλisp 4 : Parseurs & interpréteur

#Vaλisp 4 : Lire, analyser et évaluerCopier le lien

Nous avons des valeurs, un environnement et un ramasse-miettes. Il reste à transformer du texte en s‑expressions puis à les évaluer. Cette étape assemble toutes les briques : tokenizer, parseur récursif, cœur de l’interpréteur.

#1. Tokeniser une entrée LispCopier le lien

Le tokenizer lit une chaîne et produit une séquence de tokens ((, ), symboles, nombres, chaînes). Nous utilisons les fonctions standard (isspace, isdigit) pour reconnaître les catégories et nous convertissons les nombres avec strtod.

1typedef enum {2    TOK_LPAREN,3    TOK_RPAREN,4    TOK_SYMBOL,5    TOK_NUMBER,6    TOK_STRING,7    TOK_EOF8} TokenKind;

Un objet Lexer maintient la position courante. Il saute les espaces, reconnaît les commentaires commençant par ; et retourne un token à la demande.

#2. Parser récursivementCopier le lien

Le parseur récursif descend en fonction du token courant :

• si c’est un TOK_LPAREN, il consomme les expressions jusqu’au TOK_RPAREN pour construire une liste ;
• si c’est un nombre, il crée une valeur numérique ;
• sinon il crée un symbole.

1TaggedValue parse_expr(Lexer *lex, Arena *arena) {2    Token tok = lexer_next(lex);3    switch (tok.kind) {4        case TOK_NUMBER:5            return wrap_int((long)tok.number);6        case TOK_SYMBOL:7            return wrap_symbol(intern(tok.symbol));8        case TOK_LPAREN:9            return parse_list(lex, arena);10        default:11            fprintf(stderr, "Token inattendu\n");12            exit(EXIT_FAILURE);13    }14}

parse_list construit les cellules cons en chaîne. Nous nous assurons que le GC surveille les allocations durant le parsing.

#3. Évaluer les expressionsCopier le lien

La fonction eval reçoit une expression et un environnement. Elle gère d’abord les formes spéciales (quote, if, define, lambda) avant de traiter les appels de fonction génériques : on évalue l’opérateur, on évalue chaque argument, puis on applique. L’application distingue les fonctions natives (implémentées en C, par exemple +, car, cdr) et les closures utilisateur qui capturent l’environnement lexical.

1TaggedValue eval(TaggedValue expr, Env *env, Arena *arena) {2    if (is_symbol(expr)) {3        return env_lookup(env, expr);4    }5    if (is_cons(expr)) {6        TaggedValue op = eval(car(expr), env, arena);7        TaggedValue args = eval_list(cdr(expr), env, arena);8        return apply(op, args, arena);9    }10    return expr;11}

Nous terminons le chapitre par la construction d’un REPL : lire une ligne, parser, évaluer, imprimer. L’interpréteur peut désormais exécuter des programmes simples :

1(define fact2  (lambda (n)3    (if (= n 0)4        15        (* n (fact (- n 1))))))6 7(fact 6)

#AtelierCopier le lien

1. Ajoutez les primitives arithmétiques -, *, / et les comparateurs =, <, >.
2. Implémentez l’opérateur let : il crée un environnement temporaire, évalue les bindings puis le corps.
3. Introduisez la gestion des chaînes ("texte") en les stockant comme des symboles internés distincts.

Vaλisp sait maintenant lire et exécuter des fragments de Lisp. Le dernier chapitre polira l’ensemble : finitions, interface utilisateur et ouvertures.