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.

Langage lexical[modifier | modifier le code]

L'analyseur lexical est défini par un ensemble de règles, généralement appelées expressions rationnelles. Celles-ci définissent les séquences de caractères possibles qui sont utilisées pour former des entités lexicales ou des 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 lexicaux non réguliers, qui sont des langages algébriques [réf. souhaitée] (c'est-à-dire non contextuels [Quoi ?]).

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 »).

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.

Segmentation[modifier | modifier le code]

Il s'agit du 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.).

Articles connexes[modifier | modifier le code]

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

  1. Termes normalisés par ISO/IEC 2382-15:1999 Technologies de l'information — Vocabulaire — Partie 15 : Langages de programmation