Au chapitre précédent, on a vu qu’un compilateur représente un programme comme un arbre. Mais on a triché : on est parti du texte directement à l’arbre, comme si c’était évident. Ça ne l’est pas. Entre les deux, il y a une étape — la toute première de tout compilateur — et c’est elle qu’on ouvre aujourd’hui.

Lire, c’est d’abord découper

Faites l’expérience : lisez cette phrase.

Le chat dort sur le canapé.

Vous n’avez pas lu des lettres une par une. Votre cerveau a découpé la phrase en mots — « Le », « chat », « dort »… — et c’est sur les mots que le sens s’est construit. Personne ne se demande ce que veut dire « at do » (la fin de « chat » collée au début de « dort ») : le découpage précède la compréhension.

Un compilateur a exactement le même besoin. Pour lui, le texte d’un programme n’est au départ qu’une suite d’octets — des nombres, un par caractère :

  Le texte :     x + 42

  Ce que la machine voit réellement (un octet = un nombre) :

  ┌─────┬─────┬─────┬─────┬─────┬─────┐
  │ 120 │ 32  │ 43  │ 32  │ 52  │ 50  │
  └─────┴─────┴─────┴─────┴─────┴─────┘
    'x'   esp   '+'   esp   '4'   '2'

Le 120, c’est la lettre x dans la table ASCII. Le 32, une espace. Le 43, un +. Et 52 50, les deux caractères 4 et 2 — qui, ensemble, forment le nombre 42. Rien, dans cette suite, ne dit où un « mot » commence ni où il finit.

Le tokenizer (ou lexer) est l’outil qui fait ce découpage : il transforme la suite d’octets en une suite de tokens — les « mots » du langage. C’est la première étape de tout compilateur, et c’est celle qu’on a écrite en verbose.

Les espèces de tokens

Dans une phrase française, il y a des noms, des verbes, des ponctuations. Dans un programme verbose, il y a cinq espèces principales :

  espèce        exemple          c'est quoi

  Ident         x, total, foo    un nom — variable ou règle
  Keyword       rule, logic, if  un mot réservé du langage
  Num           42, 7, 1000      un nombre littéral
  Op            +, *, ==, (      un opérateur ou une ponctuation
  Str           "hello"          une chaîne entre guillemets

Et chaque token retient où il a été trouvé dans le texte — sa position et sa longueur. Ça paraît un détail ; c’est ce qui permettra plus tard (chapitre 4) d’afficher « variable inconnue à la ligne 3, colonne 11 » plutôt que « erreur quelque part ».

En verbose, ces espèces se déclarent comme un type somme — la même mécanique que les nœuds d’arbre du chapitre 1 :

concept Token
  variants:
    Ident   of (start : number, len : number)
    Keyword of (start : number, len : number, kw : number)
    Num     of (value : number, len : number)
    Op      of (code : number, len : number)
    Str     of (start : number, len : number)
    Newline of (pos : number)

Suivons « x + 42 » pas à pas

Le cœur du tokenizer est une règle, next_token : « donne-moi le prochain mot à partir d’ici ». On la rappelle autant de fois qu’il y a de mots. Déroulons-la sur notre exemple, octet par octet.

Étape 1 — position 0. Le tokenizer regarde l’octet 120 (x). C’est une lettre → il démarre un « run » d’identifiant : il avance tant qu’il voit des lettres ou des chiffres. Ici, l’octet suivant est 32 (espace), donc le run s’arrête après 1 caractère.

   pos: 0
   ┌─────┬─────┬─────┬─────┬─────┬─────┐
   │ 120 │ 32  │ 43  │ 32  │ 52  │ 50  │
   └─────┴─────┴─────┴─────┴─────┴─────┘
     ▲▲▲
     run de lettres, longueur 1
                              → émet  Ident(start: 0, len: 1)

Étape 2 — position 1. L’octet 32 est une espace. Les espaces ne sont pas des mots — le tokenizer les saute (c’est la règle skip_spaces). Il se retrouve en position 2 : l’octet 43 (+). C’est un opérateur connu → token.

   pos: 1 → saute l'espace → pos: 2
   ┌─────┬─────┬─────┬─────┬─────┬─────┐
   │ 120 │ 32  │ 43  │ 32  │ 52  │ 50  │
   └─────┴─────┴─────┴─────┴─────┴─────┘
                 ▲▲▲
                              → émet  Op(code: +, len: 1)

Étape 3 — position 3. Espace, sautée. Position 4 : l’octet 52 (4). C’est un chiffre → run de chiffres. 50 (2) est aussi un chiffre, on continue ; fin du texte, on s’arrête. Deux caractères — et au passage, le tokenizer calcule la valeur : 4×10 + 2 = 42.

   pos: 3 → saute l'espace → pos: 4
   ┌─────┬─────┬─────┬─────┬─────┬─────┐
   │ 120 │ 32  │ 43  │ 32  │ 52  │ 50  │
   └─────┴─────┴─────┴─────┴─────┴─────┘
                             ▲▲▲▲▲▲▲▲
                              → émet  Num(value: 42, len: 2)

Résultat. Six octets sont devenus trois tokens :

  AVANT  (6 octets)  : 120 · 32 · 43 · 32 · 52 · 50
  APRÈS  (3 tokens)  : Ident(x) · Op(+) · Num(42)

C’est tout le travail du tokenizer : le bruit (espaces, découpage en caractères) a disparu, le sens (un nom, un opérateur, un nombre) est apparu. Le parser, au prochain chapitre, n’aura plus jamais à penser en octets.

Et voici à quoi ça ressemble dans le code réel — la décision centrale de next_token, qui choisit l’espèce selon le premier octet utile :

out = if p >= len then Token::Eof
      else if isnl == 1    then Token::Newline { pos: p }
      else if isalpha == 1 then (if kwc > 0
                                 then Token::Keyword { start: p, len: irun, kw: kwc }
                                 else Token::Ident   { start: p, len: irun })
      else if isdigit == 1 then Token::Num { value: nval, len: drun }
      else if isstr == 1   then Token::Str { start: p, len: srun }
      else if opc > 0      then Token::Op  { code: opc, len: opl }
      else Token::Eof

Une cascade de questions : « c’est la fin ? un saut de ligne ? une lettre ? un chiffre ? un guillemet ? un opérateur ? ». Notez le raffinement sur les lettres : si le run de lettres correspond à un mot réservé (rule, logic, if…), c’est un Keyword, sinon un Ident. C’est comme distinguer, en français, un nom propre d’un nom commun : même forme, rôle différent.

Le casse-tête : l’indentation

Jusqu’ici, c’était la partie facile. Voici la difficile — et elle est intéressante parce qu’elle est invisible.

En verbose (comme en Python), la structure du programme est portée par l’indentation :

rule add(x : number, y : number)
  logic:
    out = x + y

Le logic: appartient à la règle parce qu’il est décalé. Le out = … appartient au bloc logic parce qu’il l’est davantage. Mais pour le tokenizer, une indentation, c’est… des espaces. Et on vient de dire qu’il les saute ! Comment transformer du vide en structure ?

L’astuce, classique et élégante, consiste à inventer deux tokens fantômes : Indent (« on entre dans un bloc ») et Dedent (« on en sort »). Ils ne correspondent à aucun caractère — ils matérialisent un changement de profondeur.

L’analogie qui marche bien : une pile d’assiettes, où chaque assiette est une profondeur d’indentation en cours.

  Le texte :                         La pile de colonnes :

  rule add(...)          col 0       │ 0 │            (départ)
    logic:               col 2       │ 0 │ 2 │        col 2 > 0 → Indent, on empile
      out = x + y        col 4       │ 0 │ 2 │ 4 │    col 4 > 2 → Indent, on empile
  rule main              col 0       │ 0 │            col 0 < 4 → on dépile 4 et 2
                                                       → Dedent, Dedent

À chaque début de ligne, le tokenizer mesure la colonne du premier caractère utile, et la compare au sommet de la pile :

  • colonne plus grande → on entre dans un bloc : émettre Indent, empiler la colonne ;
  • colonne égale → même niveau, rien à faire ;
  • colonne plus petite → on sort d’un ou plusieurs blocs : dépiler jusqu’à retrouver la colonne, en émettant un Dedent par niveau quitté.

Le dernier cas est le piège subtil : passer de la colonne 4 à la colonne 0 ferme deux blocs d’un coup, donc deux Dedent. Si la pile ne retombe pas exactement sur une colonne connue (par exemple revenir en colonne 3 alors qu’on ne connaît que 0, 2 et 4), c’est une erreur d’indentation — et le tokenizer l’attrape ici même, avant tout le reste.

Au final, le flux de tokens contient la structure, explicitement :

  Keyword(rule) Ident(add) Op(() ... Newline
  Indent Keyword(logic) Op(:) Newline
  Indent Ident(out) Op(=) Ident(x) Op(+) Ident(y) Newline
  Dedent Dedent
  Keyword(rule) Ident(main) ...

Ce qui était du vide (des espaces en début de ligne) est devenu des tokens que le parser pourra traiter comme des accolades { et } invisibles. C’est exactement ce que fait Python depuis trente ans — la règle dite de l’offside, empruntée au football : on note de quel côté de la ligne vous êtes.

Et tout ça, vérifié

Rappel du cadre, parce qu’il change tout : ce tokenizer n’est pas écrit en Rust dans le compilateur — il est écrit en verbose, dans vexprparse.verbose, sous le même régime que tout le reste de la série :

  • chaque règle déclare sa pureté (ce qu’elle lit, ce qu’elle appelle — rien d’autre) ;
  • chaque boucle de scan porte une preuve de terminaison (le tokenizer ne peut pas boucler à l’infini sur votre source, c’est prouvé à la compilation — chapitre 3) ;
  • et le tout est compilé par verbosec en code machine natif. Le tokenizer qui découpe « x + 42 » est un binaire autonome, pas un script.

Du texte brut, on a fait un flux de mots étiquetés, positions comprises, structure d’indentation incluse. Le prochain chapitre prend ce flux et construit l’arbre du chapitre 1 : c’est le parser — la grammaire, l’échelle de priorité des opérateurs, et la descente récursive.