#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 descendant, cœur de l’interpréteur. À la clé, le premier programme Lisp réellement exécuté par votre machine.

#1. Tokeniser l’entréeCopier le lien

Le tokenizer (ou lexer) découpe le texte en unités lexicales : parenthèses, symboles, nombres. Il ne comprend rien à la structure, il classe des caractères :

1typedef enum {2    TOK_LPAREN, TOK_RPAREN,3    TOK_SYMBOL, TOK_NUMBER,4    TOK_EOF5} TokenKind;6 7typedef struct {8    TokenKind kind;9    long      number;     /* valide si kind == TOK_NUMBER */10    char     *text;       /* valide si kind == TOK_SYMBOL, pointe dans la source */11} Token;12 13typedef struct {14    const char *src;      /* la chaîne lue, possédée par l'appelant */

lexer_next saute espaces et tabulations, traite ; comme commentaire jusqu’en fin de ligne, puis classifie : ( et ) sont immédiats ; si isdigit(c) (en castant vers unsigned char, cf. chapitre types), on lit tous les chiffres et on convertit avec strtol ; sinon on lit tous les caractères jusqu’au prochain séparateur comme nom de symbole. Le champ text pointe dans la source : c’est un emprunt, la durée de vie est celle du tampon d’entrée ; l’internage copiera ce qu’il faut garder.

Deux disciplines à respecter : les erreurs de lexing (caractère inattendu) renvoient un token d’erreur plutôt que de faire exit ; et le nombre est converti une fois pour toutes dans le token, pas à chaque usage.

#2. Parser récursivementCopier le lien

Le parseur consomme les tokens et construit des valeurs. La grammaire des s-expressions tient en trois règles : une expression est un atome (nombre, symbole) ou ( expr* ) ; une liste expr* est soit NIL, soit une paire dont le cdr est la suite de la liste.

1TaggedValue parse_expr(Lexer *lx, Arena *a) {2    Token tok = lexer_next(lx);3    switch (tok.kind) {4    case TOK_NUMBER:5        return wrap_int(tok.number);6    case TOK_SYMBOL:7        return wrap_symbol(intern(&symbols, tok.text));8    case TOK_LPAREN:9        return parse_list(lx, a);10    case TOK_RPAREN:11    case TOK_EOF:12    default:13        lex_error(lx, "token inattendu");14        return NIL_VALUE;

parse_list est la récursion formatrice de cette étape : elle lit une expression, se rappelle pour la suite de la liste, et consomme la parenthèse fermante :

1TaggedValue parse_list(Lexer *lx, Arena *a) {2    Token tok = lexer_peek(lx);3    if (tok.kind == TOK_RPAREN) {4        lexer_next(lx);                 /* consomme ')' */5        return NIL_VALUE;6    }7    if (tok.kind == TOK_EOF) {8        lex_error(lx, "')' manquant");9        return NIL_VALUE;10    }11    TaggedValue tete = parse_expr(lx, a);12    TaggedValue reste = parse_list(lx, a);13    return cons(a, tete, reste);        /* construite de la fin vers le début */14}

Notez l’ordre : la liste se construit de la fin vers le début (le cons le plus profond est la dernière paire), chaque cons alloue dans l’arène, le GC peut donc se déclencher pendant le parsing. Aussi : une erreur de syntaxe doit vider les tokens restants de l’expression courante avant de rendre la main au REPL, sinon le ) orphelin empoisonne la lecture suivante. Le lexer consomme la source au fil de l’eau, il n’alloue rien : il peut donc avancer jusqu’à la fin de ligne sans risque.

#3. ÉvaluerCopier le lien

eval reçoit une expression et un environnement. Trois familles de cas :

• Atomes : un nombre ou NIL s’évalue en lui-même ; un symbole se résout par env_lookup (jalon 3).
• Formes spéciales : quote rend son argument non évalué ; if évalue la condition puis une seule des deux branches ; define lie un nom dans le cadre courant ; lambda capture l’environnement courant.
• Application : évaluer l’opérateur, évaluer chaque argument, appliquer.

1TaggedValue eval(TaggedValue expr, Env *env, Arena *a) {2    if (is_symbol(expr))3        return env_lookup(env, expr);4    if (!is_cons(expr))5        return expr;                          /* nombre, NIL : auto-évalués */6 7    TaggedValue tete = car_of(expr);8    if (is_symbol(tete)) {9        TaggedValue special = find_special(symbol_name(tete));10        if (!is_nil(special) && special_arity_ok(expr))11            return eval_special(special, cdr_of(expr), env, a);12    }13    TaggedValue op    = eval(tete, env, a);14    TaggedValue args  = eval_list(cdr_of(expr), env, a);

apply distingue deux sortes d’opérateurs : les primitives, écrites en C (+, -, car, cdr, =, <, cons), qui consomment la liste d’arguments déjà évalués ; et les closures, résultat de lambda, qui créent un nouveau cadre contenant les paramètres liés aux arguments, parent = environnement de définition, puis évaluent le corps dans ce cadre. C’est cette capture de l’environnement de définition (et non d’appel) qui rend la portée lexicale.

Un point délicat, hérité du jalon 3 : eval_list et la construction du cadre allouent, donc peuvent déclencher une collecte pendant que expr et args sont partiellement construites dans des variables locales C. Ces temporaires doivent être racines (conservativement ou explicitement) pendant la construction : c’est exactement le piège documenté au chapitre précédent.

#4. Le REPL completCopier le lien

Lire, évaluer, imprimer, boucler :

1int repl(Env *env, Arena *a) {2    char ligne[512];3    for (;;) {4        if (!fgets(ligne, sizeof ligne, stdin)) break;5        Lexer lx = { ligne, 0 };6        TaggedValue expr = parse_expr(&lx, a);7        TaggedValue res  = eval(expr, env, a);8        print_value(res);9        putchar('\n');10    }11    return 0;12}

Le premier programme complet :

1(define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))2(fact 6)

#Atelier : jalon 4Copier le lien

1. Écrivez le lexer (lexer_next, lexer_peek, erreurs sans exit), puis le parseur (parse_expr, parse_list).
2. Implémentez eval avec les quatre formes spéciales et les primitives +, -, *, car, cdr, cons, =, <. L’arithmétique vérifie d’abord que tous les arguments sont des entiers balisés, sinon erreur claire (pas de comportement improvisé sur un mauvais kind).
3. Branchez le REPL, testez la session suivante :
4. Ajoutez let : (let ((x 1) (y 2)) (+ x y)) crée un cadre fils avec les liaisons, évalue le corps dedans.

1cc -std=c17 -Wall -Wextra -Wpedantic -g -fsanitize=address,undefined value.c arena.c symtab.c env.c gc.c reader.c interp.c main.c -o valisp2./valisp

Session de jalon :

1> (+ 1 2)233> (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))4> (fact 6)57206> (let ((x 1) (y 2)) (+ x y))73