Analyse lexicale - Lexical analysis

En informatique , l'analyse lexicale , le lexage ou la tokenisation est le processus de conversion d'une séquence de caractères (comme dans un programme informatique ou une page Web ) en une séquence de jetons ( chaînes avec une signification attribuée et donc identifiée). Un programme qui effectue une analyse lexicale peut être appelé un lexer , tokenizer ou scanner , bien que scanner soit également un terme pour la première étape d'un lexer. Un lexer est généralement associé à un analyseur syntaxique , qui, ensemble, analyse la syntaxe des langages de programmation , des pages Web , etc.

Applications

Un lexer constitue la première phase d'une interface de compilateur dans le traitement moderne. L'analyse se fait généralement en une seule passe.

Dans les langages plus anciens tels que ALGOL , l'étape initiale était à la place une reconstruction de ligne , qui effectuait un découplage et supprimait les espaces et les commentaires (et avait des analyseurs syntaxiques sans scanner, sans lexer séparé). Ces étapes sont maintenant effectuées dans le cadre du lexer.

Lexers et sont parseurs le plus souvent utilisés pour les statisticiens, mais peuvent être utilisés pour d' autres outils de langage informatique, tels que prettyprinters ou bourres . Le lexing peut être divisé en deux étapes : le scanning , qui segmente la chaîne d'entrée en unités syntaxiques appelées lexèmes et les catégorise en classes de jetons ; et l' évaluation , qui convertit les lexèmes en valeurs traitées.

Les lexers sont généralement assez simples, avec la plupart de la complexité reportée aux phases d' analyse syntaxique ou d' analyse sémantique , et peuvent souvent être générés par un générateur de lexer , notamment lex ou dérivés. Cependant, les lexers peuvent parfois inclure une certaine complexité, comme le traitement de la structure des phrases pour faciliter la saisie et simplifier l'analyseur, et peuvent être écrits partiellement ou entièrement à la main, soit pour prendre en charge plus de fonctionnalités, soit pour des performances.

L'analyse lexicale est également une étape précoce importante dans le traitement du langage naturel , où le texte ou les ondes sonores sont segmentés en mots et autres unités. Cela nécessite une variété de décisions qui ne sont pas entièrement standardisées, et le nombre de jetons produits par les systèmes varie pour des chaînes telles que "1/2", "chair's", "can't", "and/or", "1/1/ 2010", "2x4", "...", et bien d'autres. Cela contraste avec l'analyse lexicale pour la programmation et les langages similaires où les règles exactes sont généralement définies et connues.

Lexème

Un lexème est une séquence de caractères dans le programme source qui correspond au modèle d'un jeton et est identifié par l'analyseur lexical comme une instance de ce jeton.

Certains auteurs appellent cela un « jeton », utilisant « jeton » de manière interchangeable pour représenter la chaîne en cours de tokenisation et la structure de données de jeton résultant de la mise en place de cette chaîne dans le processus de tokenisation .

Le mot lexème en informatique est défini différemment du lexème en linguistique. Un lexème en informatique correspond grosso modo à un mot en linguistique (à ne pas confondre avec un mot en architecture informatique ), bien que dans certains cas il puisse s'apparenter davantage à un morphème .

Jeton

Un jeton lexical ou simplement un jeton est une chaîne avec une signification assignée et ainsi identifiée. Il est structuré comme une paire composée d'un nom de jeton et d'une valeur de jeton facultative . Le nom du token est une catégorie d'unité lexicale. Les noms de jetons communs sont

  • identifiant : noms choisis par le programmeur ;
  • mot - clé : noms déjà dans le langage de programmation ;
  • séparateur (également appelé ponctuation) : caractères de ponctuation et délimiteurs appariés ;
  • opérateur : symboles qui opèrent sur des arguments et produisent des résultats ;
  • littéral : littéraux numériques, logiques, textuels, de référence ;
  • comment : ligne, bloc (dépend du compilateur si le compilateur implémente les commentaires sous forme de jetons sinon il sera supprimé).
Exemples de valeurs de jeton
Nom du jeton Exemples de valeurs de jeton
identifiant x, color,UP
mot-clé if, ,whilereturn
séparateur }, (,;
opérateur +, ,<=
littéral true, ,6.02e23"music"
commenter /* Retrieves user data */, // must be negative

Considérez cette expression dans le langage de programmation C :

x = a + b * 2;

L'analyse lexicale de cette expression donne la séquence de jetons suivante :

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

Un nom symbolique est ce qu'on pourrait appeler une partie du discours en linguistique.

Grammaire lexicale

La spécification d'un langage de programmation comprend souvent un ensemble de règles, la grammaire lexicale , qui définit la syntaxe lexicale. La syntaxe lexicale est généralement un langage régulier , avec des règles de grammaire constituées d' expressions régulières ; ils définissent l'ensemble des séquences de caractères possibles (lexèmes) d'un jeton. Un lexer reconnaît les chaînes, et pour chaque type de chaîne trouvée, le programme lexical entreprend une action, produisant le plus simplement un jeton.

Deux catégories lexicales communes importantes sont les espaces blancs et les commentaires . Ceux-ci sont également définis dans la grammaire et traités par le lexer, mais peuvent être rejetés (ne produisant aucun jeton) et considérés comme non significatifs , séparant au plus deux jetons (comme dans if xau lieu de ifx). Il y a deux exceptions importantes à cela. Premièrement, dans les langages de règles hors-jeu qui délimitent les blocs avec indentation, les espaces initiaux sont importants, car ils déterminent la structure des blocs et sont généralement gérés au niveau du lexer ; voir la structure de la phrase ci-dessous. Deuxièmement, dans certaines utilisations de lexers, les commentaires et les espaces blancs doivent être préservés - par exemple, une jolie imprimante doit également afficher les commentaires et certains outils de débogage peuvent fournir des messages au programmeur montrant le code source d'origine. Dans les années 1960, notamment pour ALGOL , les espaces et les commentaires ont été éliminés dans le cadre de la phase de reconstruction de ligne (la phase initiale du frontend du compilateur ), mais cette phase séparée a été supprimée et ceux-ci sont désormais gérés par le lexer.

Tokenisation

La tokenisation est le processus de démarcation et éventuellement de classification des sections d'une chaîne de caractères d'entrée. Les jetons résultants sont ensuite transmis à une autre forme de traitement. Le processus peut être considéré comme une sous-tâche de l' analyse des entrées.

Par exemple, dans la chaîne de texte :

The quick brown fox jumps over the lazy dog

la chaîne n'est pas implicitement segmentée sur des espaces, comme le ferait un locuteur en langage naturel . L'entrée brute, les 43 caractères, doit être explicitement divisée en 9 jetons avec un délimiteur d'espace donné (c'est-à-dire correspondant à la chaîne " "ou à l'expression régulière /\s{1}/ ).

Les jetons pourraient être représentés en XML ,

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
</sentence>

ou en tant qu'expression s ,

(sentence
  (word The)
  (word quick)
  (word brown)
  (word fox)
  (word jumps)
  (word over)
  (word the)
  (word lazy)
  (word dog))

Lorsqu'une classe de jetons représente plus d'un lexème possible, le lexique enregistre souvent suffisamment d'informations pour reproduire le lexème d'origine, afin qu'il puisse être utilisé dans l'analyse sémantique . L' analyseur syntaxique récupère généralement ces informations du lexer et les stocke dans l' arbre de syntaxe abstraite . Ceci est nécessaire afin d'éviter la perte d'informations dans le cas où les nombres peuvent également être des identifiants valides.

Les jetons sont identifiés en fonction des règles spécifiques du lexer. Certaines méthodes utilisées pour identifier les jetons incluent : des expressions régulières , des séquences spécifiques de caractères appelées drapeau , des caractères de séparation spécifiques appelés délimiteurs et une définition explicite par un dictionnaire. Les caractères spéciaux, y compris les caractères de ponctuation, sont couramment utilisés par les lexistes pour identifier les jetons en raison de leur utilisation naturelle dans les langages écrits et de programmation.

Les jetons sont souvent classés par contenu de caractère ou par contexte dans le flux de données. Les catégories sont définies par les règles du lexer. Les catégories impliquent souvent des éléments de grammaire de la langue utilisée dans le flux de données. Les langages de programmation classent souvent les jetons en identifiants, opérateurs, symboles de regroupement ou par type de données . Les langues écrites catégorisent généralement les jetons comme des noms, des verbes, des adjectifs ou des signes de ponctuation. Les catégories sont utilisées pour le post-traitement des jetons soit par l'analyseur, soit par d'autres fonctions du programme.

Un analyseur lexical ne fait généralement rien avec des combinaisons de jetons, une tâche laissée à un parseur . Par exemple, un analyseur lexical typique reconnaît les parenthèses comme des jetons, mais ne fait rien pour s'assurer que chaque "(" correspond à un ")".

Lorsqu'un lexer fournit des jetons à l'analyseur, la représentation utilisée est généralement une liste énumérée de représentations numériques. Par exemple, "Identifiant" est représenté par 0, "Opérateur d'affectation" par 1, "Opérateur d'addition" par 2, etc.

Les jetons sont souvent définis par des expressions régulières , qui sont comprises par un générateur d' analyseur lexical tel que lex . L'analyseur lexical (généré automatiquement par un outil comme lex, ou fabriqué à la main) lit un flux de caractères, identifie les lexèmes dans le flux et les catégorise en jetons. C'est ce qu'on appelle la tokenisation . Si le lexer trouve un jeton invalide, il signalera une erreur.

La tokenisation suivante est l' analyse . À partir de là, les données interprétées peuvent être chargées dans des structures de données pour une utilisation générale, une interprétation ou une compilation .

Scanner

La première étape, le scanner , est généralement basée sur une machine à états finis (FSM). Il a codé en son sein des informations sur les séquences possibles de caractères qui peuvent être contenus dans l'un des jetons qu'il gère (les instances individuelles de ces séquences de caractères sont appelées lexèmes ). Par exemple, un lexème entier peut contenir n'importe quelle séquence de caractères numériques . Dans de nombreux cas, le premier caractère non blanc peut être utilisé pour déduire le type de jeton qui suit et les caractères d'entrée suivants sont ensuite traités un par un jusqu'à atteindre un caractère qui n'est pas dans l'ensemble de caractères acceptable pour ce jeton (cela est appelée la règle du munch maximal , ou la règle de la correspondance la plus longue ). Dans certaines langues, les règles de création de lexème sont plus complexes et peuvent impliquer un retour en arrière sur les caractères précédemment lus. Par exemple, en C, un caractère 'L' n'est pas suffisant pour faire la distinction entre un identifiant qui commence par 'L' et un littéral de chaîne de caractères larges.

Évaluateur

Un lexème , cependant, n'est qu'une chaîne de caractères connus pour être d'un certain type (par exemple, un littéral de chaîne, une séquence de lettres). Pour construire un jeton, l'analyseur lexical a besoin d'une seconde étape, l' évaluateur , qui parcourt les caractères du lexème pour produire une valeur . Le type du lexème combiné à sa valeur est ce qui constitue proprement un jeton, qui peut être donné à un analyseur. Certains jetons tels que les parenthèses n'ont pas vraiment de valeurs, et donc la fonction d'évaluation pour ceux-ci ne peut rien renvoyer : seul le type est nécessaire. De même, les évaluateurs peuvent parfois supprimer complètement un lexème, le cachant à l'analyseur, ce qui est utile pour les espaces et les commentaires. Les évaluateurs d'identifiants sont généralement simples (représentant littéralement l'identifiant), mais peuvent inclure des fichiers . Les évaluateurs pour les littéraux entiers peuvent transmettre la chaîne (en reportant l'évaluation à la phase d'analyse sémantique), ou peuvent effectuer eux-mêmes l'évaluation, ce qui peut être impliqué pour différentes bases ou nombres à virgule flottante. Pour un littéral de chaîne simple entre guillemets, l'évaluateur n'a besoin de supprimer que les guillemets, mais l'évaluateur d'un littéral de chaîne échappé incorpore un lexer, qui libère les séquences d'échappement.

Par exemple, dans le code source d'un programme informatique, la chaîne

net_worth_future = (assets liabilities);

peut être converti dans le flux de jetons lexical suivant ; les espaces sont supprimés et les caractères spéciaux n'ont aucune valeur :

IDENTIFIER net_worth_future
EQUALS
OPEN_PARENTHESIS
IDENTIFIER assets
MINUS
IDENTIFIER liabilities
CLOSE_PARENTHESIS
SEMICOLON

En raison des restrictions de licence des analyseurs existants, il peut être nécessaire d'écrire un lexer à la main. C'est pratique si la liste des tokens est petite, mais en général, les lexers sont générés par des outils automatisés. Ces outils acceptent généralement des expressions régulières qui décrivent les jetons autorisés dans le flux d'entrée. Chaque expression régulière est associée à une règle de production dans la grammaire lexicale du langage de programmation qui évalue les lexèmes correspondant à l'expression régulière. Ces outils peuvent générer du code source qui peut être compilé et exécuté ou construire une table de transition d'état pour une machine à états finis (qui est connectée au code modèle pour la compilation et l'exécution).

Les expressions régulières représentent de manière compacte des modèles que les caractères des lexèmes peuvent suivre. Par exemple, pour une langue basée sur l' anglais , un jeton IDENTIFIER peut être n'importe quel caractère alphabétique anglais ou un trait de soulignement, suivi d'un nombre quelconque d'instances de caractères alphanumériques ASCII et/ou de traits de soulignement. Cela pourrait être représenté de manière compacte par la chaîne [a-zA-Z_][a-zA-Z_0-9]*. Cela signifie "tout caractère az, AZ ou _, suivi de 0 ou plus de az, AZ, _ ou 0-9".

Les expressions régulières et les machines à états finis qu'elles génèrent ne sont pas assez puissantes pour gérer les modèles récursifs, tels que « n parenthèses ouvrantes, suivies d'une instruction, suivies de n parenthèses fermantes ». Ils sont incapables de compter et vérifient que n est le même des deux côtés, à moins qu'un ensemble fini de valeurs admissibles existe pour n . Il faut un analyseur complet pour reconnaître de tels modèles dans leur pleine généralité. Un analyseur peut placer des parenthèses sur une pile, puis essayer de les supprimer et voir si la pile est vide à la fin (voir l'exemple dans le livre Structure and Interpretation of Computer Programs ).

Obstacles

En règle générale, la tokenisation se produit au niveau du mot. Cependant, il est parfois difficile de définir ce que l'on entend par un « mot ». Souvent, un tokenizer repose sur des heuristiques simples, par exemple :

  • La ponctuation et les espaces peuvent ou non être inclus dans la liste de jetons résultante.
  • Toutes les chaînes contiguës de caractères alphabétiques font partie d'un jeton ; de même avec les nombres.
  • Les jetons sont séparés par des espaces , tels qu'un espace ou un saut de ligne, ou par des caractères de ponctuation.

Dans les langues qui utilisent des espaces inter-mots (comme la plupart qui utilisent l'alphabet latin et la plupart des langages de programmation), cette approche est assez simple. Cependant, même ici, il existe de nombreux cas limites tels que les contractions , les mots coupés , les émoticônes et les constructions plus larges telles que les URI (qui, à certaines fins, peuvent compter comme des jetons uniques). Un exemple classique est " basé à New York ", qu'un tokenizer naïf peut casser à l'espace même si la meilleure coupure est (sans doute) au trait d'union.

La tokenisation est particulièrement difficile pour les langues écrites en scriptio continua qui ne présentent aucune limite de mots comme le grec ancien , le chinois ou le thaï . Les langues agglutinantes , comme le coréen, compliquent également les tâches de tokenisation.

Certaines façons de résoudre les problèmes les plus difficiles incluent le développement d'heuristiques plus complexes, l'interrogation d'une table de cas spéciaux courants ou l'ajustement des jetons à un modèle de langage qui identifie les collocations lors d'une étape de traitement ultérieure.

Générateur Lexer

Les lexers sont souvent générés par un générateur de lexer , analogue aux générateurs d'analyseurs syntaxiques , et ces outils sont souvent réunis. Le plus établi est lex , associé au générateur d'analyseur syntaxique yacc , ou plutôt à certaines de leurs nombreuses réimplémentations, comme flex (souvent associé à GNU Bison ). Ces générateurs sont une forme de langage spécifique à un domaine , prenant en charge une spécification lexicale – généralement des expressions régulières avec un certain balisage – et émettant un lexique.

Ces outils permettent un développement très rapide, ce qui est très important au début du développement, à la fois pour obtenir un lexer fonctionnel et parce qu'une spécification de langage peut changer souvent. De plus, ils fournissent souvent des fonctionnalités avancées, telles que des conditions préalables et postérieures qui sont difficiles à programmer à la main. Cependant, un lexer généré automatiquement peut manquer de flexibilité et peut donc nécessiter des modifications manuelles, ou un lexer entièrement écrit manuellement.

Les performances du lexer sont une préoccupation et l'optimisation en vaut la peine, d'autant plus dans les langages stables où le lexer est exécuté très souvent (tels que C ou HTML). Les lexers générés par lex/flex sont raisonnablement rapides, mais des améliorations de deux à trois fois sont possibles en utilisant des générateurs plus réglés. Des lexers écrits à la main sont parfois utilisés, mais les générateurs de lexer modernes produisent des lexers plus rapides que la plupart des lexiques codés à la main. La famille de générateurs lex/flex utilise une approche basée sur des tables qui est beaucoup moins efficace que l'approche à codage direct. Avec cette dernière approche, le générateur produit un moteur qui passe directement aux états de suivi via des instructions goto. Des outils comme re2c ont prouvé qu'ils produisaient des moteurs qui sont entre deux et trois fois plus rapides que les moteurs flex. Il est en général difficile d'écrire à la main des analyseurs plus performants que les moteurs générés par ces derniers outils.

Structure d'expression

L'analyse lexicale segmente principalement le flux de caractères d'entrée en jetons, en regroupant simplement les caractères en morceaux et en les catégorisant. Cependant, la lexique peut être nettement plus complexe ; plus simplement, les lexeurs peuvent omettre des jetons ou insérer des jetons ajoutés. L'omission de jetons, notamment d'espaces et de commentaires, est très courante, lorsqu'ils ne sont pas nécessaires au compilateur. Moins fréquemment, des jetons ajoutés peuvent être insérés. Ceci est fait principalement pour regrouper les jetons en instructions , ou les instructions en blocs, afin de simplifier l'analyseur.

Suite de ligne

La continuation de ligne est une caractéristique de certaines langues où un saut de ligne est normalement un terminateur d'instruction. Le plus souvent, la fin d'une ligne par une barre oblique inverse (immédiatement suivie d'une nouvelle ligne ) entraîne la poursuite de la ligne – la ligne suivante est jointe à la ligne précédente. Ceci est généralement fait dans le lexer : la barre oblique inverse et la nouvelle ligne sont supprimées, plutôt que la nouvelle ligne étant tokenisée. Les exemples incluent bash , d'autres scripts shell et Python.

Insertion de point-virgule

De nombreuses langues utilisent le point-virgule comme terminateur d'instruction. Le plus souvent, cela est obligatoire, mais dans certaines langues, le point-virgule est facultatif dans de nombreux contextes. Cela se fait principalement au niveau du lexer, où le lexer génère un point-virgule dans le flux de jetons, bien qu'il ne soit pas présent dans le flux de caractères d'entrée, et est appelé insertion de point-virgule ou insertion automatique de point-virgule . Dans ces cas, les points-virgules font partie de la grammaire formelle de la langue, mais peuvent ne pas être trouvés dans le texte d'entrée, car ils peuvent être insérés par le lexer. Des points-virgules facultatifs ou d'autres fins ou séparateurs sont également parfois traités au niveau de l'analyseur, notamment dans le cas de virgules ou de points- virgules de fin .

L'insertion de point-virgule est une fonctionnalité de BCPL et de son descendant éloigné Go , bien qu'elle soit absente en B ou C. L'insertion de point-virgule est présente dans JavaScript , bien que les règles soient quelque peu complexes et très critiquées ; pour éviter les bogues, certains recommandent de toujours utiliser des points-virgules, tandis que d'autres utilisent des points-virgules initiaux, appelés points - virgules défensifs , au début des instructions potentiellement ambiguës.

L'insertion de point-virgule (dans les langues avec des instructions terminées par un point-virgule) et la continuation de ligne (dans les langues avec des instructions terminées par un saut de ligne) peuvent être considérées comme complémentaires : l'insertion de point-virgule ajoute un jeton, même si les nouvelles lignes ne génèrent généralement pas de jetons, tandis que la continuation de ligne empêche un jeton d'être produit, même si les nouvelles lignes généralement faire générer des jetons.

Règle du hors-jeu

La règle de hors-jeu (blocs déterminés par l'indentation) peut être implémentée dans le lexer, comme dans Python , où l'augmentation de l'indentation entraîne l'émission par le lexeur d'un jeton INDENT et la diminution de l'indentation entraîne l'émission par le lexeur d'un jeton DEDENT. Ces jetons correspondent à l'accolade ouvrante {et à l'accolade fermante }dans les langues qui utilisent des accolades pour les blocs, et signifient que la grammaire de l'expression ne dépend pas de l'utilisation des accolades ou de l'indentation. Cela nécessite que le lexer conserve l'état, à savoir le niveau d'indentation actuel, et peut donc détecter les changements d'indentation lorsque cela change, et donc la grammaire lexicale n'est pas sans contexte : INDENT–DEDENT dépendent des informations contextuelles du niveau d'indentation précédent.

Lexage contextuel

Généralement, les grammaires lexicales sont sans contexte, ou presque, et ne nécessitent donc pas de regard en arrière ou en avant, ou de retour en arrière, ce qui permet une implémentation simple, propre et efficace. Cela permet également une communication unidirectionnelle simple du lexer à l'analyseur, sans qu'aucune information ne revienne vers le lexer.

Il y a cependant des exceptions. Des exemples simples incluent : l'insertion d'un point-virgule dans Go, qui nécessite de regarder en arrière un jeton ; concaténation de chaînes littérales consécutives en Python, ce qui nécessite de conserver un jeton dans un tampon avant de l'émettre (pour voir si le jeton suivant est un autre littéral chaîne); et la règle de hors-jeu en Python, qui nécessite de maintenir un nombre de niveaux d'indentation (en effet, une pile de chaque niveau d'indentation). Ces exemples ne nécessitent tous qu'un contexte lexical, et bien qu'ils compliquent quelque peu un lexer, ils sont invisibles pour l'analyseur et les phases ultérieures.

Un exemple plus complexe est le lexer hack en C, où la classe de jetons d'une séquence de caractères ne peut être déterminée qu'à la phase d'analyse sémantique, car les noms de typedef et les noms de variables sont lexicalement identiques mais constituent des classes de jetons différentes. Ainsi, dans le hack, le lexer appelle l'analyseur sémantique (disons, table de symboles) et vérifie si la séquence nécessite un nom de typedef. Dans ce cas, les informations doivent revenir non seulement de l'analyseur syntaxique, mais de l'analyseur sémantique vers le lexer, ce qui complique la conception.

Voir également

Les références

Sources

  • Compilation avec C# et Java , Pat Terry, 2005, ISBN  032126360X
  • Algorithmes + Structures de données = Programmes , Niklaus Wirth, 1975, ISBN  0-13-022418-9
  • Construction du compilateur , Niklaus Wirth, 1996, ISBN  0-201-40353-6
  • Sebesta, RW (2006). Concepts de langages de programmation (Septième édition) pp. 177. Boston : Pearson/Addison-Wesley.

Liens externes