#Lexing (analyse lexicale)Copier le lien

Objectifs d'apprentissage

• Écrire des règles de tokens et gérer espaces/commentaires.
• Lever les ambiguïtés par plus long match et ordre des règles.
• Comprendre pourquoi un lexer déterministe évite le retour arrière.

Prérequis: expressions régulières de base (classes, quantificateurs) et le langage Expr défini en page d'introduction.

#Le fil conducteur: 2*(3+4)-5Copier le lien

Le lexer du langage Expr reconnaît quatre catégories: nombres (NUM), identifiants (ID), opérateurs et parenthèses (OP), plus le mot-clé let réservé pour les déclarations. Pour l'entrée 2*(3+4)-5, il produit exactement:

1[('NUM', 2), ('OP', '*'), ('OP', '('), ('NUM', 3), ('OP', '+'),2 ('NUM', 4), ('OP', ')'), ('OP', '-'), ('NUM', 5), ('EOF', None)]

Le token EOF final est explicite: le parseur s'en servira comme condition d'arrêt, ce qui évite les tests de débordement de liste partout.

#Tokenizer par regex pour les expressions arithmétiquesCopier le lien

La dernière ligne lève SyntaxError: caractère inattendu: '=': c'est un comportement voulu. Un lexer qui rejette tôt un caractère inconnu produit un diagnostic précis (position, caractère) au lieu de laisser le parseur échouer de façon confuse plus loin.

#Plus long match et priorité des règlesCopier le lien

Deux règles peuvent matcher au même endroit. L'exemple canonique du langage C: l'entrée <= doit produire un seul token <= et non LT suivi de EQ. Deux principes résolvent ces cas.

• Plus long match: parmi les règles qui matchent, garder celle qui consomme le plus de caractères. <= (2 caractères) bat < (1 caractère).
• Ordre des règles: à égalité de longueur, la règle déclarée en premier gagne. C'est ainsi qu'un mot-clé let est distingué d'un identifiant: même longueur possible, mais la règle des mots-clés précède celle des identifiants.

Dans le playground ci-dessus, l'alternance (\d+)|([a-zA-Z]...) de Python applique naturellement ces principes: les nombres sont matchés en premier, et un identifiant ne peut pas commencer par un chiffre.

#Exercice : extension du tokenizer pour identifiants et mots-clésCopier le lien

Étendez le tokenizer pour reconnaître identifiants et mots-clés du langage Expr étendu, avec suivi de position.

#InstructionsCopier le lien

1. Modifiez l'expression régulière pour reconnaître les identifiants: suites de lettres et chiffres commençant par une lettre.
2. Ajoutez la reconnaissance des mots-clés let, if, else, while après le découpage lexical, par test d'égalité exacte.
3. Gérez les majuscules/minuscules: le langage est sensible à la casse, donc Let reste un identifiant.
4. Propagez la position (index de départ) dans chaque token pour des diagnostics précis.

#Correction commentéeCopier le lien

1import re2 3# Chaque règle est (nom, regex). L'ordre du tableau fait foi à longueur égale.4RULES = [5    ('NUM',  r'\d+'),6    ('ID',   r'[a-zA-Z][a-zA-Z0-9]*'),7    ('OP',   r'[+\-*/()=;{}<>]'),8]9KEYWORDS = {'let', 'if', 'else', 'while'}10 11MASTER = re.compile('|'.join(f'(?P<{name}>{pattern})' for name, pattern in RULES))12 13def tokenize(src):14    tokens, pos = [], 0

Vérification attendue: let x = 5; produit [('KW','let',0), ('ID','x',4), ('OP','=',6), ('NUM','5',8), ('OP',';',9), ('EOF',None,10)], tandis que letters + 2 produit bien ('ID','letters',0) et non un mot-clé. Le test d'égalité text in KEYWORDS garantit ce comportement.

#Le lexer en pratique: l'outil lexCopier le lien

Les lexers réels ne s'écrivent pas à la main: on décrit les règles dans un fichier .l, et l'outil lex (ou sa version libre flex) génère l'analyseur en C. Le fichier suit une structure en trois sections séparées par %%:

1%{2/* section 1 : declarations C, prototypes, variables globales */3%}4/* definitions : motifs nommes */5CHIFFRE  [0-9]6%%7/* section 2 : regles, une par ligne : MOTIF ACTION */8{CHIFFRE}+   { return NOMBRE; }9[ \t\n]+     ;              /* ignorer les blancs */10.            { return yytext[0]; }11%%12/* section 3 : code C auxiliaire (main, fonctions) */

yytext contient le texte reconnu, yyleng sa longueur. Chaque action est du C exécuté quand le motif matche.

#Les deux règles de résolution d'ambiguïté, dans lexCopier le lien

Quand plusieurs motifs peuvent matcher au même endroit, lex tranche par:

1. plus long match — le motif qui consomme le plus de caractères gagne;
2. ordre de déclaration — à longueur égale, la règle écrite en premier gagne.

La seconde règle est celle qui sert tous les jours: on déclare les mots-clés avant la règle des identifiants.

1"let"        { return LET; }        /* declare en premier */2[A-Za-z]+    { return ID;  }

Sans cet ordre, let serait reconnu comme un identifiant, et le parseur ne verrait jamais le mot-clé. Comme les deux motifs consomment exactement 3 caractères sur l'entrée let, c'est bien l'ordre qui décide — pas la longueur.

#Les conditions de démarrageCopier le lien

Un lexer n'a pas de mémoire non bornée, mais il peut avoir plusieurs modes: ce sont les conditions de démarrage. On les déclare avec %x (exclusives) ou %s (inclusives), et on les active par BEGIN(nom).

1%x CHAINE2 3%%4\"             { BEGIN(CHAINE); }5<CHAINE>\"     { BEGIN(INITIAL); }6<CHAINE>[^"]+  { /* le contenu de la chaine */ }

L'intérêt: la même séquence de caractères peut avoir un sens différent selon le contexte. Dans une chaîne de caractères, un { n'ouvre pas un bloc; dans un commentaire, un mot-clé n'en est pas un. Les conditions de démarrage se compilent en dupliquant l'automate par contexte: on reste dans le modèle fini, on change seulement de table de transitions.

#Un cas concret: analyser une ligne de logCopier le lien

Le cas d'école, tiré des annales de ce module: une ligne de log HTTP contient plusieurs champs séparés par des espaces, dont deux champs entre guillemets qui se ressemblent.

1193.51.25.77 - - [12/Jul/2004:13:44:46 +0200] "GET /~hpc/ HTTP/1.0" 200 3822 "-" "Mozilla/4.73 [en] (X11; ...)"

Le référent ("-") et le navigateur ("Mozilla/4.73 ...") ont la même forme lexicale: une chaîne entre guillemets. Le premier doit être ignoré, le second retenu. Une règle unique \"{NAV}[^"]*\" attraperait le référent dès qu'il commence par une lettre — et le compteur de navigateurs serait faux, sans aucun message d'erreur. La solution est de suivre la progression dans la ligne avec des conditions de démarrage: un état pour les champs d'identité et de date, un pour les deux champs numériques, un pour le référent, un pour le navigateur.

C'est la leçon générale de cet exercice: un lexer ne se contente pas de reconnaître des motifs, il doit savoir où il en est. Le contexte est de l'information, et les conditions de démarrage sont le seul endroit où un lexer peut la stocker.

#Mini quizCopier le lien