Analyse lexicale

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

L'analyse lexicale se trouve tout au début de la chaîne de compilation. C'est la tâche consistant à décomposer une chaîne de caractères en lexèmes, unités ou entités lexicales [1], aussi appelées tokens en anglais. Ces entités lexicales, « produites » à la demande de l'analyseur syntaxique, sont ensuite « consommées » par ce dernier.

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 entités lexicales (ou lexèmes).

Tout langage reconnu par une expression rationnelle est appelé langage régulier. À toute expression rationnelle, on peut associer un automate fini.

Il existe également des langages non réguliers, qui sont des langages algébriques.

Entité lexicale[modifier | modifier le code]

Une entité lexicale est une chaîne de caractères qui correspond à un symbole (exemples : NUMBER, IDENTIFIER, ..). Elle est généralement définie par des expressions rationnelles. On appelle segmentation (en entités) (tokenization en anglais) le processus permettant de former des entités lexicales à partir d'un flux entrant de caractères : l'analyseur lexical identifie les lexèmes de ce flux et les range dans des catégories d'entités lexicales. S'il détecte une entité lexicale invalide, il rapporte une erreur.

Généralement, les combinaisons d'entités lexicales sont laissées au soin de l'analyseur. Par exemple, un analyseur lexical typique reconnaît les parenthèses comme étant des entités lexicales, mais ne s'assure pas qu'une parenthèse ouvrante « ( » est forcément associée à une parenthèse fermante « ) ».

L'étape suivant la phase de « segmentation » est l'« analyse syntaxique » (parfois appelée « parsage »).

Segmentation[modifier | modifier le code]

Article détaillé : Segmentation (linguistique).

Il s’agit d'un processus permettant de démarquer les différentes sections d'une chaîne de caractères. En effet, un ordinateur n'est pas capable seul de déterminer quels sont les "mots" d'une phrase ; il n'y voit qu'une chaîne de caractères. Un processus de segmentation consisterait donc à séparer ces mots, selon les espaces dans la plupart des cas. En effet, on peut avoir des "mots" (token en anglais) non séparés par des espaces, mais par divers signes de ponctuation. Ainsi, dans la phrase: "L'enfant, aimait les bonbons.", les mots "L'" et "enfant" ou encore "bonbons" et "." et "enfant" et "," ne sont pas séparés par des espaces. Cette tâche de segmentation paraît donc parfois plus complexe qu'il n'y parait. En anglais par exemple il faut être capable de gérer les formes contractées (exemple: I'm, I don't, etc.).

Voici ce que donnerait la segmentation de la ligne écrite en langage C suivante :

sum = 2 + 3;

Après segmentation :

Entité lexicale Symbole
sum "Identificateur"
= "Opérateur d'affectation"
2 "Entier littéral"
+ "Opérateur d'addition"
3 "Entier littéral"
; "Fin de déclaration"

Analyseur lexical[modifier | modifier le code]

On appelle analyseur lexical, lexeur, ou encore scanneur, tout programme effectuant une analyse lexicale. Il s'agit le plus souvent d'une unique fonction qui sera appelée par l'analyseur syntaxique ou par une autre fonction.

Le scanneur contient toutes les informations sur les séquences de caractères qui peuvent être contenues dans les entités lexicales qu'il génère. Par exemple, une entité lexicale de type « INTEGER » peut contenir n'importe quelle séquence de caractères numériques (chiffres).

Son rôle consiste à :

  • éliminer les « bruits » du texte source : commentaires, espaces, …
  • reconnaître les opérateurs et les mots-clés : <=, ==, if, …
  • reconnaître les chaînes de caractères, les identificateurs et les constantes numériques

Il produit en sortie une entité lexicale qui sera utilisée par l'analyseur syntaxique.

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é de l'analyse lexicale[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 régulière 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]

Articles connexes[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)