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 :

Le parseur récursif descend en fonction de la nature du token courant. Si c'est une parenthèse ouvrante (TOK_LPAREN), il consomme les expressions suivantes jusqu'à rencontrer la parenthèse fermante correspondante pour construire une liste. Si c'est un nombre, il crée directement la valeur numérique associée. Dans les autres cas, il génère un symbole correspondant.

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

Commencez par enrichir le langage en ajoutant les primitives arithmétiques de base (-, *, /) ainsi que les comparateurs usuels (=, <, >). Ensuite, implémentez l'opérateur let, qui nécessite la création d'un environnement temporaire pour évaluer les liaisons avant d'exécuter le corps de l'expression. Enfin, introduisez la gestion des chaînes de caractères délimitées par des guillemets, en les stockant par exemple 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.