Un lexer est la première chose que votre code rencontre. Il transforme des caractères en sens. Avant qu'un parser puisse comprendre la structure de votre programme, avant qu'un vérificateur de types puisse vérifier sa correction, avant qu'un générateur de code puisse émettre du bytecode -- le lexer doit lire votre fichier source un caractère à la fois et produire un flux de tokens. C'est la phase la plus humble d'un compilateur, et sans doute la plus importante. Si le lexer se trompe sur un token, chaque phase suivante hérite de l'erreur.
Le lexer de FLIN a un défi inhabituel que la plupart des lexers de langage n'affrontent pas : il doit gérer deux modes syntaxiques fondamentalement différents dans le même fichier source. Les programmes FLIN contiennent du code impératif -- déclarations de variables, flux de contrôle, appels de fonctions -- entrelacé avec des déclarations de vues de type HTML. Le lexer doit basculer de manière transparente entre ces modes sans perdre sa place, mal identifier des tokens ou confondre un opérateur inférieur-à avec une balise HTML ouvrante.
C'est l'histoire de comment nous avons construit ce lexer en Rust, du premier Peekable<CharIndices> au dernier test qui passe.
Le struct Scanner
Tout lexer est, en son coeur, un curseur se déplaçant à travers un flux de caractères. Le scanner de FLIN maintient six éléments d'état :
rustpub struct Lexer<'a> {
source: &'a str,
chars: Peekable<CharIndices<'a>>,
line: u32,
column: u32,
start: u32,
mode: LexerMode,
}
#[derive(Debug, Clone, Copy, PartialEq)]
enum LexerMode {
Code, // Code normal
View, // À l'intérieur de balises de type HTML
ViewExpression, // À l'intérieur de {expression} dans une vue
}Le champ source contient une référence vers le texte source original. Nous ne le copions jamais -- le lexer l'emprunte pour toute sa durée de vie, et chaque lexème est produit en découpant cette chaîne originale. C'est le modèle de propriété de Rust qui travaille pour nous : le borrow checker garantit que la chaîne source vit au moins aussi longtemps que le lexer, donc nos tranches sont toujours valides.
Le champ chars est un Peekable<CharIndices<'a>> -- l'itérateur de la bibliothèque standard de Rust qui produit des paires (décalage_octets, char). Le wrapper Peekable nous permet de regarder un caractère en avant sans le consommer, ce qui est essentiel pour désambiguïser les tokens multi-caractères comme == versus =.
Les champs line et column suivent la position courante pour les messages d'erreur. Le champ start marque le décalage en octets où le token courant a commencé -- quand nous finissons de scanner un token, nous découpons source[start..current] pour obtenir le lexème.
Et il y a mode. C'est le champ qui distingue le lexer de FLIN d'une implémentation classique.
La boucle de tokenisation
La boucle principale est d'une simplicité trompeuse :
rustpub fn tokenize(&mut self) -> Result<Vec<Token>, LexError> {
let mut tokens = Vec::new();
while let Some(token) = self.next_token()? {
tokens.push(token);
}
tokens.push(Token {
kind: TokenKind::Eof,
span: self.current_span(),
lexeme: String::new(),
});
Ok(tokens)
}Appeler next_token() en boucle. Pousser chaque token dans un vecteur. Quand la source est épuisée, ajouter un token Eof. Retourner le vecteur.
Le token Eof n'est pas juste une sentinelle -- c'est un contrat avec le parser. Le parser peut toujours appeler self.peek() sans vérifier un flux de tokens vide, parce qu'il y a toujours au moins un token : Eof. Cela élimine les conditionnelles de vérification de bornes dans tout le parser, ce qui rend le code de parsing plus propre et plus difficile à casser.
Dispatch caractère par caractère
La méthode next_token() est là où le vrai travail se fait. Après avoir sauté les espaces blancs et les commentaires, elle lit un caractère et dispatche :
rustfn next_token(&mut self) -> Result<Option<Token>, LexError> {
self.skip_whitespace();
self.skip_comments();
self.start = self.current_offset();
match self.advance() {
None => Ok(None),
Some((_, c)) => {
let kind = match c {
// Tokens d'un seul caractère
'(' => TokenKind::LeftParen,
')' => TokenKind::RightParen,
'{' => self.handle_left_brace(),
'}' => self.handle_right_brace(),
'[' => TokenKind::LeftBracket,
']' => TokenKind::RightBracket,
',' => TokenKind::Comma,
':' => TokenKind::Colon,
';' => TokenKind::Semicolon,
'.' => TokenKind::Dot,
'@' => TokenKind::At,
// Tokens multi-caractères
'+' => self.match_char('+', TokenKind::PlusPlus, TokenKind::Plus),
'-' => self.match_char('-', TokenKind::MinusMinus, TokenKind::Minus),
'=' => self.match_char('=', TokenKind::EqualEqual, TokenKind::Equal),
'!' => self.match_char('=', TokenKind::NotEqual, TokenKind::Not),
'<' => self.scan_tag_or_less(),
'>' => self.match_char('=', TokenKind::GreaterEqual, TokenKind::TagClose),
'&' => self.expect_char('&', TokenKind::And)?,
'|' => self.expect_char('|', TokenKind::Or)?,
// Littéraux
'"' => self.scan_string()?,
c if c.is_ascii_digit() => self.scan_number()?,
c if c.is_alphabetic() || c == '_' => self.scan_identifier(),
_ => return Err(LexError::UnexpectedCharacter(c, self.current_position())),
};
Ok(Some(Token {
kind,
span: self.current_span(),
lexeme: self.current_lexeme(),
}))
}
}
}C'est un dispatch de scanner classique, avec une exception critique : le caractère <. Dans la plupart des langages, < est sans ambiguïté un opérateur inférieur-à. Dans FLIN, il pourrait être un opérateur inférieur-à, un opérateur inférieur-ou-égal (<=), ou le début d'une balise HTML (<button>). Résoudre cette ambiguïté est le travail le plus difficile du lexer.
Le lexer modal : Code, View et ViewExpression
Les fichiers source FLIN ressemblent à ceci :
flincount = 0 // Mode code
<button click={count++}> // Mode vue
{count} // Expression embarquée
</button> // Mode vueLe lexer doit gérer trois contextes distincts :
Le mode Code est le mode par défaut. Les tokens sont des opérateurs, des mots-clés, des identifiants et des littéraux. Le caractère < est un opérateur de comparaison.
Le mode View s'active quand le lexer rencontre un < suivi d'un caractère alphabétique (indiquant un nom de balise) ou d'un / (indiquant une balise fermante). En mode vue, le lexer émet des tokens TagOpen, TagName, AttrName, TagClose, TagSelfClose et TagEnd au lieu d'opérateurs arithmétiques et de comparaison.
Le mode ViewExpression s'active quand le lexer rencontre un { en mode vue. À l'intérieur des accolades, le lexer revient à la tokenisation en mode code -- des expressions comme count++ sont scannées comme des identifiants et des opérateurs, pas comme du contenu de balise. Quand le } correspondant est trouvé, le lexer retourne en mode vue.
Les transitions de mode sont gérées par trois méthodes :
rustfn scan_tag_or_less(&mut self) -> TokenKind {
if self.peek_is_alpha() || self.peek_char() == Some('/') {
self.mode = LexerMode::View;
TokenKind::TagOpen
} else if self.match_next('=') {
TokenKind::LessEqual
} else {
TokenKind::Less
}
}
fn handle_left_brace(&mut self) -> TokenKind {
if self.mode == LexerMode::View {
self.mode = LexerMode::ViewExpression;
}
TokenKind::LeftBrace
}
fn handle_right_brace(&mut self) -> TokenKind {
if self.mode == LexerMode::ViewExpression {
self.mode = LexerMode::View;
}
TokenKind::RightBrace
}La méthode scan_tag_or_less est le point de désambiguïsation critique. Quand le lexer voit <, il regarde le caractère suivant. S'il est alphabétique (<button) ou un slash (</button>), c'est une balise -- basculer en mode vue et émettre TagOpen. Si le caractère suivant est =, c'est <= -- émettre LessEqual. Sinon, c'est un simple < -- émettre Less.
Ce lookahead est la raison pour laquelle le lexer utilise Peekable<CharIndices> au lieu d'un itérateur brut. Le peek ne coûte rien -- il n'avance pas le curseur -- et il résout l'ambiguïté en temps constant.
Scanner les chaînes
Le scanning de chaînes est direct mais nécessite une gestion soigneuse des séquences d'échappement :
FLIN supporte les séquences d'échappement standard : \n (retour à la ligne), \t (tabulation), \\ (backslash), \" (guillemet double). Le scanner lit les caractères jusqu'à rencontrer un guillemet double non échappé ou la fin du fichier. Si le fichier se termine avant que la chaîne ne soit fermée, le lexer retourne un LexError::UnterminatedString avec la position où la chaîne a commencé -- pas où le fichier s'est terminé. Cette distinction compte pour les messages d'erreur : "chaîne non terminée commençant à la ligne 7, colonne 12" est exploitable. "fin de fichier inattendue à la ligne 94" ne l'est pas.
Scanner les nombres
Le scanning de nombres a deux phases. D'abord, consommer tous les chiffres ASCII (avec des séparateurs underscore optionnels pour la lisibilité : 1_000_000). Puis vérifier la présence d'un point suivi de plus de chiffres pour distinguer les entiers des flottants.
La valeur parsée est stockée directement dans le token : TokenKind::Integer(i64) ou TokenKind::Float(f64). Cela signifie que le parser n'a jamais à re-parser un littéral numérique depuis sa représentation en chaîne. Le lexer le fait une fois, correctement, et chaque phase suivante utilise la valeur parsée.
FLIN supporte aussi les littéraux entiers hexadécimaux (0xFF) et binaires (0b1010). Le lexer détecte le préfixe 0x ou 0b et bascule vers l'ensemble de chiffres approprié. Si un littéral hexadécimal contient des caractères non-hex, ou un littéral binaire contient des chiffres autres que 0 et 1, le lexer produit une erreur spécifique : LexError::InvalidHexLiteral ou LexError::InvalidBinaryLiteral. Des types d'erreur spécifiques signifient des messages d'erreur spécifiques, et des messages d'erreur spécifiques signifient que les développeurs corrigent leur code plus vite.
Scanner les identifiants et les mots-clés
C'est la méthode que nous avons définie dans l'article précédent, mais le flux mérite un examen :
- Le lexer rencontre un caractère alphabétique ou un underscore.
- Il consomme tous les caractères alphanumériques et underscores suivants.
- Il extrait le lexème en découpant la chaîne source.
- Il vérifie le lexème contre 42 chaînes de mots-clés.
- Si un mot-clé correspond, il retourne
TokenKind::Keyword(Keyword::...). - Sinon, il retourne
TokenKind::Identifier(lexeme).
La vérification de mot-clé est un match sur &str, que Rust compile en une recherche efficace. Pour 42 mots-clés, c'est assez rapide pour qu'une fonction de hachage parfaite ne produise pas d'amélioration mesurable sur un fichier source réaliste.
Une subtilité : le lexème pour un identifiant est un String, pas un &str. Cela signifie que le lexer alloue une nouvelle chaîne pour chaque token identifiant. Nous aurions pu utiliser l'interning de chaînes (une table globale qui déduplique les chaînes) pour réduire les allocations. Nous avons choisi de ne pas le faire, pour deux raisons. Premièrement, le lexer s'exécute une fois par compilation, et l'allocation de chaînes n'est pas le goulot d'étranglement dans un compilateur qui fait aussi du parsing, de la vérification de types et de la génération de bytecode. Deuxièmement, l'interning ajoute de l'état global, ce qui complique les tests et rend le lexer plus difficile à raisonner. La simplicité a gagné.
Espaces blancs et commentaires
La méthode skip_whitespace() consomme les espaces, tabulations et retours chariot sans produire de tokens. Les retours à la ligne, cependant, sont traités différemment selon le mode.
En mode code, les retours à la ligne sont significatifs -- FLIN utilise les retours à la ligne comme terminateurs d'instructions dans de nombreux contextes, similaire à Go ou Python. Le lexer émet un TokenKind::Newline pour chaque caractère de retour à la ligne, que le parser utilise pour déterminer les limites d'instructions.
En mode vue, les espaces blancs (y compris les retours à la ligne) entre les balises sont condensés en contenu texte, suivant les conventions HTML. La conception modale garantit que le même caractère d'espace blanc est géré différemment selon le contexte.
Les commentaires utilisent le préfixe // et s'étendent jusqu'à la fin de la ligne. Le lexer les saute entièrement -- ils ne produisent aucun token. Les commentaires bloc (/<em> ... </em>/) ne sont pas supportés dans FLIN. C'était un choix de conception délibéré : les commentaires bloc ajoutent de la complexité au lexer (ils peuvent s'imbriquer, ils peuvent s'étendre sur des fichiers si vous n'êtes pas prudent, ils interagissent mal avec les littéraux de chaîne) et leur absence n'a jamais été un problème pratique dans des langages comme Python ou Ruby qui en manquent aussi.
Gestion des erreurs
Le lexer peut échouer de quatre façons :
- Caractère inattendu : un caractère qui ne correspond à aucune règle de scanning. De l'Unicode en dehors des littéraux de chaîne, par exemple.
- Chaîne non terminée : un guillemet double qui n'est jamais fermé.
- Littéral numérique invalide : un préfixe hex suivi de chiffres non-hex, ou un nombre avec plusieurs points décimaux.
- Caractère attendu non trouvé : le lexer voit
&et attend un autre&(pour former&&), mais le caractère suivant est autre chose.
Chaque variante d'erreur transporte une Position, pour que le message d'erreur puisse pointer vers l'emplacement exact dans le fichier source. C'est un petit investissement qui rapporte des dividendes : un compilateur avec de bons messages d'erreur est un compilateur que les développeurs utiliseront réellement.
rustpub enum LexError {
UnexpectedCharacter(char, Position),
UnterminatedString(Position),
InvalidHexLiteral(Position),
InvalidBinaryLiteral(Position),
ExpectedCharacter { expected: char, found: Option<char>, position: Position },
}Nous avons choisi de faire de LexError un vrai enum plutôt que de retourner des messages sous forme de chaînes. Cela signifie que le code en aval peut matcher sur les variantes d'erreur et les gérer différemment -- un plugin d'IDE pourrait vouloir auto-corriger une chaîne non terminée, par exemple, tandis qu'un caractère inattendu reçoit juste un soulignement rouge. Les erreurs structurées demandent plus de travail à définir, mais elles se composent mieux que les chaînes.
Tester le lexer
À la session 4, le lexer avait 97 tests unitaires. Ils se répartissaient en plusieurs catégories :
Tests de token unique : vérifier que chaque type de token individuel est scanné correctement. "+" produit Plus. "==" produit EqualEqual. "entity" produit Keyword(Keyword::Entity). C'est ennuyeux mais essentiel -- cela garantit que la table de dispatch est correctement câblée.
Tests multi-tokens : vérifier que les séquences de tokens sont scannées dans le bon ordre. "x = 42" produit [Identifier("x"), Equal, Integer(42), Eof]. Cela détecte les bugs d'interaction où scanner un token laisse le curseur à la mauvaise position pour le suivant.
Tests de transition de mode : vérifier que le lexer bascule correctement entre les modes code, vue et vue-expression. "<button click={x}>" doit produire [TagOpen, Identifier("button"), Identifier("click"), Equal, LeftBrace, Identifier("x"), RightBrace, TagClose] avec les transitions de mode correctes à chaque accolade.
Tests d'erreur : vérifier que le lexer produit la bonne erreur pour une entrée mal formée. Une chaîne non terminée doit retourner UnterminatedString, pas un panic ou un mauvais token.
Les 97 tests compilaient et passaient à la fin de la session 4. Quand nous avons commencé à construire le parser en session 5, le flux de tokens était digne de confiance. Nous n'avons jamais eu à déboguer un bug du parser qui s'est avéré être un bug du lexer. C'est le retour sur investissement de tests de lexer approfondis.
Caractéristiques de performance
Le lexer de FLIN est mono-passe et O(n) dans la longueur du fichier source. Chaque caractère est examiné au plus deux fois : une fois par peek() et une fois par advance(). La seule allocation est le vecteur de tokens lui-même et les champs String à l'intérieur des tokens d'identifiant et de littéral de chaîne.
Pour un fichier source FLIN typique de quelques centaines de lignes, le lexing prend des microsecondes. Ce n'est pas parce que nous avons optimisé agressivement -- c'est parce que nous avons évité le travail inutile. Pas d'expressions régulières. Pas de retour en arrière. Pas de scanning multi-passe. Juste un curseur, un match et un push.
Si FLIN a un jour besoin de lexer des fichiers assez grands pour que la performance compte (ce qui semble peu probable pour un langage spécialisé), la première optimisation serait l'interning de chaînes, suivi de l'allocation en arène pour le vecteur de tokens. Mais ce sont des ponts que nous traverserons si nous les atteignons.
Leçons apprises
Trois leçons de la construction du lexer :
La conception modale était le bon choix. Nous avons considéré des alternatives : scanner le fichier entier en mode code et post-traiter les sections de vue, ou utiliser un lexer séparé pour le contenu de vue. Les deux alternatives auraient compliqué le parser. Le lexer modal produit un flux de tokens unifié que le parser peut consommer sans connaître les modes. La complexité reste à un endroit -- les trois méthodes de transition de mode -- au lieu de fuiter à travers tout le pipeline de compilation.
Transporter les valeurs parsées dans les tokens. Stocker Integer(42) au lieu de Integer("42") déplace le travail de parsing du parser vers le lexer. C'est un gain net parce que le lexer a le meilleur contexte pour parser les littéraux (il sait exactement où le littéral commence et finit) et le parser peut traiter tous les littéraux uniformément sans logique de parsing spécifique au type.
Tester les tokens exhaustivement avant de construire le parser. Les 97 tests du lexer ont pris quelques heures à écrire à travers les sessions 1 à 4. Ils ont prévenu un nombre inconnu mais certainement non nul de sessions de débogage du parser. Dans un compilateur, les bugs dans les phases précoces se font passer pour des bugs dans les phases tardives. Tester exhaustivement les phases précoces est le moyen le moins cher de garder les phases tardives déboguables.
Ce qui a suivi
Avec le lexer produisant un flux de tokens propre et bien testé, nous étions prêts pour le parser. Mais le parser de FLIN n'est pas un simple parser à descente récursive -- il utilise un parser Pratt pour la gestion des expressions, ce qui nous donne la précédence des opérateurs sans table de grammaire et l'extensibilité sans réécriture de la boucle de parsing.
Le prochain article explique comment fonctionne le parsing Pratt, pourquoi nous l'avons choisi pour FLIN et comment il gère tout, de l'arithmétique simple aux opérateurs d'accès temporel et aux requêtes d'intention IA.
Ceci est la partie 12 de la série "Comment nous avons construit FLIN", qui documente comment un CEO à Abidjan et une IA CTO ont construit un langage de programmation en partant de zéro.
Navigation de la série : - [11] Session 1 : mise en place du projet et 42 mots-clés - [12] Construire un lexer en partant de zéro en Rust (vous êtes ici) - [13] Pratt Parsing : comment FLIN lit votre code - [14] L'arbre syntaxique abstrait : la représentation interne de FLIN - [15] L'inférence de types Hindley-Milner dans un langage personnalisé