Compilation : 2. Expressions régulières et analyse lexicale

Trois notions à distinguer

Le scanner avance dans un flux de caractères. Les blancs et commentaires sont généralement ignorés selon les règles du langage ; les positions restent utiles pour les diagnostics.

Construire une expression régulière

Les briques formelles sont ∅, ε, les symboles de l’alphabet, l’union |, la concaténation et l’étoile *. L’étoile est prioritaire sur la concaténation, elle-même prioritaire sur |. Ainsi ab|c* décrit {ab} ∪ {ε,c,cc,…}.

lettre = [A-Za-z_]
chiffre = [0-9]
identifiant = [A-Za-z_][A-Za-z0-9_]*
entier = [0-9]+
nombre = [0-9]+(\.[0-9]+)?([Ee][+-]?[0-9]+)?

Ces motifs décrivent un mini-langage ASCII. Le nombre accepte 12, 12.5 et 12E-3, mais exclut .5 et 12. ; un signe initial peut être traité séparément comme opérateur. Pour valider une chaîne entière, utilisez une correspondance complète et non une recherche de sous-chaîne.

Choisir le plus long lexème

Avec les opérateurs = et ==, l’entrée a==b doit donner ID EQEQ ID. Le scanner choisit la plus longue correspondance depuis la position courante. En cas d’égalité de longueur, une priorité de règles départage les tokens, par exemple le mot-clé if avant ID. En revanche ifx reste un identifiant car sa correspondance est plus longue.

tant que la source n’est pas terminée :
  état = état_initial ; dernier_final = aucun
  avancer tant qu’une transition existe
  mémoriser chaque état final et sa position
  si aucun état final n’a été atteint : erreur lexicale
  sinon revenir à la dernière position acceptante
        émettre le token ou ignorer le blanc/commentaire

Des motifs à un analyseur

La construction de Thompson associe un ε-AFN à chaque expression : un chemin pour un symbole, un branchement pour l’union, des raccordements pour la concaténation et une boucle avec passage vide pour l’étoile. On réunit les automates de tokens sous un nouvel état initial, puis on déterminise. Les états finaux gardent la priorité du token gagnant. Le chapitre suivant détaille la déterminisation et la minimisation.