- Analyse lexicale
-
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 unités lexicales, aussi appelées tokens. Ces tokens, "produits" à la demande de l'analyseur syntaxique, sont ensuite "consommés" par ce dernier.
Sommaire
Langage lexical
L'analyseur lexical est défini par un ensemble de règles, généralement appelées expressions régulières. Celles-ci définissent les séquences de caractères possibles qui sont utilisées pour former des tokens ou des léxèmes.
Tout langage reconnu par une expression régulière est appelé langage régulier. A toute expression régulière, on peut associer un automate fini. Il existe également des langages lexicaux non réguliers, qui sont des langages algébriques (c'est-à-dire non contextuels).
Token
Un token est une chaîne de caractères qui correspond à un symbole (exemples : NUMBER, IDENTIFIER, ..). Il est généralement défini par des expressions régulières. On appelle tokenization le processus permettant de former des tokens à partir d'un flux entrant de caractères : l'analyseur lexical identifie les léxèmes de ce flux et les range dans des catégories de tokens. S'il détecte un token invalide, il reporte une erreur.
Généralement, les combinaisons de tokens sont laissées au soin du parser (voir Analyse syntaxique). Par exemple, un analyseur lexical typique reconnaît les parenthèses comme étant des tokens, 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 "tokenizing" est le "parsing".
Analyseur lexical
On appelle analyseur lexical, lexer, ou encore scanner, tout programme effectuant une analyse lexicale. Il s'agit le plus souvent d'une unique fonction qui sera appelée par le parser (voir Analyse syntaxique) ou par une autre fonction.
Le scanner contient toutes les informations sur les séquences de caractères qui peuvent être contenues dans les tokens qu'il génère. Par exemple, un token 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 un token qui sera utilisé 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 régulière 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
Tokenization
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 tokenization consisterait donc à séparer ces mots, selon les espaces.
Articles connexes
Catégorie :- Théorie de la compilation
Wikimedia Foundation. 2010.
