Analyse lexicale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'analyse lexicale ou segmentation fait partie de la première phase de la chaîne de compilation. Elle consiste à convertir une chaîne de caractères en une liste de symboles (tokens en anglais). Ces symboles sont ensuite consommés lors de l'analyse syntaxique.

Processus[modifier | modifier le code]

L'analyse lexicale d'une chaîne de caractères se déroule en deux étapes :

  1. Le balayage (scanning en anglais) qui segmente la chaîne de caractères d'entrée en lexèmes (unités lexicales)[1] et leur associe une catégorie lexicale (entier littéral, opérateur d'addition, identifiant, …).
  2. L'évaluation (evaluating en anglais) qui convertit chaque lexème en une valeur.

Le couple catégorie lexicalevaleur associé à un lexème s'appelle un symbole (token en anglais).

Exemple[modifier | modifier le code]

L'instruction sum = 2 + 3; en langage C produit après analyse lexicale la liste de symboles suivante :

Valeur Catégorie lexicale
sum identifiant
= opérateur d'affectation
2 entier littéral
+ opérateur d'addition
3 entier littéral
; fin de déclaration

Grammaire lexicale[modifier | modifier le code]

Les langages de programmation définissent souvent des règles, sous la forme d'une grammaire, définissant la syntaxe à adopter. Ces règles prennent souvent la forme d'expressions rationnelles et définissent les séquences de caractères utilisées pour former des lexèmes.

Les langages reconnus par une expression rationnelle sont appelés les langages rationnels. À toute expression rationnelle, on peut associer un automate fini. Il existe également des langages non rationnels.

Analyseur lexical[modifier | modifier le code]

On appelle analyseur lexical (lexer en anglais) tout programme effectuant une analyse lexicale.

L'analyseur lexical sert à

  • éliminer les « bruits » du texte source : commentaires, espaces ;
  • reconnaître les opérateurs et les mots-clés : +, >, if, return, … ;
  • reconnaître les identificateurs, les chaînes de caractères littérales et les nombres littéraux.

Lorsque l'analyseur lexical détecte un lexème invalide, il rapporte une erreur. En revanche, les combinaisons de lexèmes sont généralement laissées à l'analyseur syntaxique : par exemple, un analyseur lexical typique reconnaît les parenthèses comme étant des lexèmes mais ne vérifie pas qu'une parenthèse ouvrante « ( » est forcément associée à une parenthèse fermante « ) ».

Un analyseur lexical peut être écrit

  • « à la main » : il faut construire l'automate fini non déterministe à partir d'une expression rationnelle E, puis l'exécuter pour déterminer si une chaîne d'entrée appartient au langage reconnu par E ;
  • par une table décrivant l'automate et un programme exploitant cette table ;
  • par un générateur d'analyseurs : flex, ANTLR, etc.

Complexité algorithmique[modifier | modifier le code]

Algorithme naïf[modifier | modifier le code]

  1. On génère pour chaque symbole un automate qui reconnait l'expression rationnelle associée au symbole. Cet automate sera identifié par le symbole.
  2. Tant que le mot n'a pas été entièrement analysé et qu'il n'y a pas d'erreur :
    1. On lit le mot lettre par lettre en faisant avancer les automates en parallèle pour chaque lettre.
    2. Lorsqu'un automate entre dans un état final, on conserve le sous-mot trouvé et l'identificateur de l'automate.
    3. Si tous les automates sont dans un état puits ou que le mot a été entièrement analysé :
      1. Si aucun automate n'a atteint d'état final : on renvoie une erreur.
      2. Sinon, on ajoute le couple (plus grand sous-mot avec un automate en état final, type de l'automate l'ayant trouvé) à la liste des entités lexicales. On se replace alors juste après ce sous-mot, on remet les automates à zéro et on continue la lecture du mot.

Analyse de la complexité[modifier | modifier le code]

Dans le cas des langages de programmation, cet algorithme s’exécute souvent en temps linéaire par rapport à la taille du mot d'entrée. Cependant, il existe des cas pathologiques où l'algorithme s'exécute en temps quadratique, tel que celui-ci : avec 2 lexèmes : a et a…ab, l'entrée an nécessite que l'algorithme aille jusqu'à la fin du mot pour chaque a qu'il reconnait. La complexité est alors quadratique.

Autres algorithmes[modifier | modifier le code]

Il existe d'autres algorithmes capable d'analyser un mot en temps linéaire[2].

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Termes normalisés par ISO/CEI 2382-15:1999 Technologies de l'information — Vocabulaire — Partie 15 : Langages de programmation
  2. (en) Thomas Reps, « “Maximal-Munch” Tokenization in Linear Time », ACM Transactions on Programming Languages and Systems, Vol. 20, No. 2,‎ (lire en ligne)

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]