Software is all about logic. La programmation a acquis la réputation d’être un domaine lourd en mathématiques et en équations folles. Et l’informatique semble être au cœur de cette idée fausse.

Bien sûr, il y a des mathématiques et des formules — mais aucun d’entre nous n’a besoin d’avoir un doctorat en calcul pour comprendre le fonctionnement de nos machines! En fait, beaucoup de règles et de paradigmes que nous apprenons dans le processus d’écriture de code sont les mêmes règles et paradigmes qui s’appliquent aux concepts informatiques complexes. Et parfois, ces idées proviennent en fait de l’informatique, et nous ne l’avons tout simplement jamais su.

Quel que soit le langage de programmation que nous utilisons, lorsque la plupart d’entre nous écrivent notre code, nous visons à encapsuler des choses distinctes dans des classes, des objets ou des méthodes, en séparant intentionnellement les différentes parties de notre code. En d’autres termes, nous savons qu’il est généralement bon de diviser notre code de sorte qu’une classe, un objet ou une méthode ne soit concerné et responsable que d’une seule chose. Si nous ne faisions pas cela, les choses pourraient devenir très désordonnées et s’entrelacer dans un désordre d’un web. Parfois, cela se produit encore, même avec la séparation des préoccupations.

Il s’avère que même le fonctionnement interne de nos ordinateurs suit des paradigmes de conception très similaires. Notre compilateur, par exemple, a des parties différentes, et chaque partie est responsable de la gestion d’une partie spécifique du processus de compilation. Nous en avons rencontré un peu la semaine dernière, lorsque nous avons appris l’existence de l’analyseur, responsable de la création d’arbres d’analyse. Mais l’analyseur ne peut pas être chargé de tout.

L’analyseur a besoin de l’aide de ses copains, et il est enfin temps pour nous d’apprendre qui ils sont !

Lorsque nous avons appris l’analyse syntaxique récemment, nous avons plongé nos orteils dans la grammaire, la syntaxe et la façon dont le compilateur réagit et répond à ces choses dans un langage de programmation. Mais nous n’avons jamais vraiment mis en évidence ce qu’est exactement un compilateur! Au fur et à mesure que nous entrons dans le fonctionnement interne du processus de compilation, nous allons en apprendre beaucoup sur la conception du compilateur, il est donc essentiel pour nous de comprendre de quoi nous parlons exactement ici.

Les compilateurs peuvent sembler un peu effrayants, mais leur travail n’est en fait pas trop complexe à comprendre, en particulier lorsque nous décomposons les différentes parties d’un complicateur en petites parties.

Mais d’abord, commençons par la définition la plus simple possible. Un compilateur est un programme qui lit notre code (ou n’importe quel code, dans n’importe quel langage de programmation) et le traduit dans un autre langage.

De manière générale, un compilateur ne traduira jamais que du code d’un langage de haut niveau vers un langage de bas niveau. Les langages de niveau inférieur dans lesquels un compilateur traduit du code sont souvent appelés code d’assemblage, code machine ou code objet. Il convient de mentionner que la plupart des programmeurs ne traitent ou n’écrivent pas vraiment de code machine; nous dépendons plutôt du compilateur pour prendre nos programmes et les traduire en code machine, ce que notre ordinateur exécutera en tant que programme exécutable.

Nous pouvons considérer les compilateurs comme l’intermédiaire entre nous, les programmeurs et nos ordinateurs, qui ne peuvent exécuter des programmes exécutables que dans des langages de niveau inférieur.

Le compilateur fait le travail de traduction de ce que nous voulons arriver d’une manière compréhensible et exécutable par nos machines.

Sans le compilateur, nous serions obligés de communiquer avec nos ordinateurs en écrivant du code machine, qui est incroyablement illisible et difficile à déchiffrer. Le code machine peut souvent ressembler à un tas de 0 et de 1 à l’œil humain — tout est binaire, vous vous souvenez? — ce qui le rend très difficile à lire, à écrire et à déboguer. Le compilateur a soustrait le code machine pour nous en tant que programmeurs, car il nous permettait très facilement de ne pas penser au code machine et d’écrire des programmes en utilisant des langages beaucoup plus élégants, clairs et faciles à lire.

Nous allons continuer à déballer de plus en plus sur le compilateur mystérieux au cours des prochaines semaines, ce qui, espérons-le, en fera moins une énigme dans le processus. Mais pour l’instant, revenons à la question à portée de main: quelles sont les parties les plus simples possibles d’un compilateur?

Chaque compilateur, quelle que soit sa conception, a des phases distinctes. Ces phases permettent de distinguer les parties uniques du compilateur.

Nous avons déjà rencontré l’une des phases de nos aventures de compilation lorsque nous avons récemment appris sur l’analyseur et les arbres d’analyse. Nous savons que l’analyse est le processus qui consiste à extraire des données et à en construire un arbre d’analyse, ce qui est parfois appelé l’acte d’analyse. Il s’avère que le travail d’analyse est spécifique à une phase du processus de compilation appelée analyse syntaxique.

Cependant, l’analyseur ne se contente pas de construire un arbre d’analyse à partir de rien. Il a de l’aide! Nous nous souviendrons que l’analyseur reçoit des jetons (également appelés terminaux), et il construit un arbre d’analyse à partir de ces jetons. Mais d’où proviennent ces jetons ? Heureusement pour l’analyseur, il n’a pas à fonctionner dans le vide; au lieu de cela, il a de l’aide.

Cela nous amène à une autre phase du processus de compilation, celle qui précède la phase d’analyse syntaxique : la phase d’analyse lexicale.

Le terme « lexical » désigne la signification d’un mot indépendamment de la phrase qui le contient, et quel que soit son contexte grammatical. Si nous essayons de deviner notre propre signification en nous basant uniquement sur cette définition, nous pourrions poser que la phase d’analyse lexicale a à voir avec les mots / termes individuels du programme eux-mêmes, et rien à voir avec la grammaire ou le sens de la phrase qui contient les mots.

La phase d’analyse lexicale est la première étape du processus de compilation. Il ne connaît pas ou ne se soucie pas de la grammaire d’une phrase ou de la signification d’un texte ou d’un programme; tout ce qu’il sait, c’est la signification des mots eux-mêmes.

L’analyse lexicale doit avoir lieu avant qu’un code provenant d’un programme source puisse être analysé. Avant qu’il puisse être lu par l’analyseur, un programme doit d’abord être analysé, divisé et regroupé de certaines manières.

Lorsque nous avons commencé à examiner la phase d’analyse syntaxique la semaine dernière, nous avons appris que l’arbre d’analyse est construit en examinant des parties individuelles de la phrase et en décomposant les expressions en parties plus simples. Mais pendant la phase d’analyse lexicale, le compilateur ne connaît pas ou n’a pas accès à ces « parties individuelles ». Au contraire, il doit d’abord les identifier et les trouver, puis faire le travail de diviser le texte en morceaux individuels.

Par exemple, lorsque nous lisons une phrase de Shakespeare comme To sleep, perchance to dream., nous savons que les espaces et la ponctuation divisent les « mots » d’une phrase. C’est, bien sûr, parce que nous avons été formés pour lire une phrase, la « lex », et l’analyser pour la grammaire.

Mais, pour un compilateur, cette même phrase pourrait ressembler à ceci la première fois qu’il la lit : Tosleepperhachancetodream. Lorsque nous lisons cette phrase, il nous est un peu plus difficile de déterminer quels sont les « mots » réels! Je suis sûr que notre compilateur ressent la même chose.

Alors, comment notre machine gère-t-elle ce problème? Eh bien, pendant la phase d’analyse lexicale du processus de compilation, il fait toujours deux choses importantes: il scanne le code, puis il l’évalue.

Le travail de numérisation et d’évaluation peut parfois être regroupé en un seul programme, ou il peut s’agir de deux programmes distincts qui dépendent l’un de l’autre; c’est vraiment juste une question de savoir comment un complieur a été conçu. Le programme du compilateur qui est responsable du travail de numérisation et d’évaluation est souvent appelé lexer ou tokenizer, et toute la phase d’analyse lexicale est parfois appelée processus de lexing ou de tokenizing.

Pour numériser, peut-être pour lire

La première des deux étapes principales de l’analyse lexicale consiste à numériser. Nous pouvons considérer la numérisation comme le travail de « lire » un texte d’entrée. N’oubliez pas que ce texte d’entrée peut être une chaîne, une phrase, une expression ou même un programme entier! Cela n’a pas vraiment d’importance, car, dans cette phase du processus, c’est juste une goutte géante de caractères qui ne veut rien dire pour l’instant, et qui est un morceau contigu.

Regardons un exemple pour voir comment cela se produit exactement. Nous utiliserons notre phrase originale, To sleep, perchance to dream., qui est notre texte source ou notre code source. Pour notre compilateur, ce texte source sera lu comme un texte d’entrée qui ressemble à Tosleep,perchancetodream., qui n’est qu’une chaîne de caractères qui n’a pas encore été déchiffrée.

La première chose que notre compilateur doit faire est de diviser ce blob de texte en ses plus petits morceaux possibles, ce qui facilitera grandement l’identification des mots du blob de texte.

La façon la plus simple de plonger un gros morceau de texte est de le lire lentement et systématiquement, un caractère à la fois. Et c’est exactement ce que fait le compilateur.

Souvent, le processus de numérisation est géré par un programme distinct appelé scanner, dont le seul travail consiste à lire un fichier/texte source, un caractère à la fois. Pour notre scanner, peu importe la taille de notre texte; tout ce qu’il verra lorsqu’il « lit » notre fichier est un caractère à la fois.

Voici ce que notre phrase shakespearienne serait lue par notre scanner:

Nous remarquerons que To sleep, perchance to dream. a été divisé en caractères individuels par notre scanner. De plus, même les espaces entre les mots sont traités comme des caractères, tout comme la ponctuation de notre phrase. Il y a aussi un caractère à la fin de cette séquence qui est particulièrement intéressant : eof. C’est le caractère « fin de fichier », et il est similaire à tabspace, et newline. Puisque notre texte source n’est qu’une seule phrase, lorsque notre scanner arrive à la fin du fichier (dans ce cas, la fin de la phrase), il lit la fin du fichier et le traite comme un caractère.

Ainsi, en réalité, lorsque notre scanner a lu notre texte d’entrée, il l’a interprété comme des caractères individuels, ce qui a abouti à ceci: .

Maintenant que notre scanner a lu et divisé notre texte source en ses plus petites parties possibles, il sera beaucoup plus facile de comprendre les « mots » de notre phrase.

Ensuite, le scanner doit examiner ses caractères divisés dans l’ordre et déterminer quels caractères sont des parties d’un mot et lesquels ne le sont pas. Pour chaque caractère lu par le scanner, il marque la ligne et la position de l’endroit où ce caractère a été trouvé dans le texte source.

L’image présentée ici illustre ce processus pour notre phrase shakespearienne. Nous pouvons voir que notre scanner marque la ligne et la colonne pour chaque caractère de notre phrase. Nous pouvons considérer la représentation en ligne et en colonne comme une matrice ou un tableau de caractères.

Rappelons que, comme notre fichier ne contient qu’une seule ligne, tout vit à la ligne 0. Cependant, au fur et à mesure que nous parcourons la phrase, la colonne de chaque caractère s’incrémente. Il convient également de mentionner que, puisque notre scanner lit spacesnewlineseof, et toutes les ponctuations en tant que caractères, ceux-ci apparaissent également dans notre table de caractères!

Une fois le texte source numérisé et marqué, notre compilateur est prêt à transformer ces caractères en mots. Étant donné que le scanner sait non seulement où se trouvent les spacesnewlines et eof dans le fichier, mais aussi où ils vivent par rapport aux autres caractères qui les entourent, il peut parcourir les caractères et les diviser en chaînes individuelles si nécessaire.

Dans notre exemple, le scanner examinera les caractères T, puis o, puis un space. Lorsqu’il trouve un espace, il divise To en son propre mot — la combinaison de caractères la plus simple possible avant que le scanner ne rencontre un espace.

C’est une histoire similaire pour le mot suivant qu’il trouve, qui est sleep. Cependant, dans ce scénario, il lit s-l-e-e-p, puis lit un ,, un signe de ponctuation. Comme cette virgule est flanquée d’un caractère (p) et d’un space de chaque côté, la virgule est, elle-même, considérée comme un « mot ».

Le mot sleep et le symbole de ponctuation , sont appelés lexèmes, qui sont des sous-chaînes du texte source. Un lexème est un regroupement des plus petites séquences de caractères possibles dans notre code source. Les lexèmes d’un fichier source sont considérés comme les « mots » individuels du fichier lui-même. Une fois que notre scanner aura fini de lire les caractères uniques de notre fichier, il renverra un ensemble de lexèmes qui ressemblent à ceci: .

Remarquez comment notre scanner a pris une goutte de texte comme entrée, qu’il ne pouvait pas initialement lire, et a procédé à la numérisation une fois caractère à la fois, en lisant et en marquant simultanément le contenu. Il a ensuite procédé à la division de la chaîne en leurs plus petits lexèmes possibles en utilisant les espaces et la ponctuation entre les caractères comme délimiteurs.

Cependant, malgré tout ce travail, à ce stade de la phase d’analyse lexicale, notre scanner ne sait rien de ces mots. Bien sûr, il a divisé le texte en mots de différentes formes et tailles, mais en ce qui concerne ces mots, le scanner n’en a aucune idée! Les mots pourraient être une chaîne littérale, ou ils pourraient être un signe de ponctuation, ou ils pourraient être tout autre chose!

Le scanner ne sait rien des mots eux-mêmes, ni de quel « type » de mot ils sont. Il sait juste où les mots se terminent et commencent dans le texte lui-même.

Cela nous prépare à la deuxième phase de l’analyse lexicale: l’évaluation. Une fois que nous avons numérisé notre texte et divisé le code source en unités de lexème individuelles, nous devons évaluer les mots que le scanner nous a retournés et déterminer les types de mots auxquels nous avons affaire — en particulier, nous devons rechercher des mots importants qui signifient quelque chose de spécial dans la langue que nous essayons de compiler.

Evaluer les parties importantes

Une fois que nous aurons fini de numériser notre texte source et identifié nos lexèmes, nous devrons faire quelque chose avec nos « mots » lexèmes. Il s’agit de l’étape d’évaluation de l’analyse lexicale, qui est souvent appelée dans complier design le processus de lexing ou de tokenisation de notre entrée.

Lorsque nous évaluons notre code numérisé, tout ce que nous faisons vraiment est d’examiner de plus près chacun des lexèmes générés par notre scanner. Notre compilateur devra examiner chaque mot lexémique et décider de quel type de mot il s’agit. Le processus de détermination du type de lexème de chaque « mot » dans notre texte est la façon dont notre compilateur transforme chaque lexème individuel en jeton, symbolisant ainsi notre chaîne d’entrée.

Nous avons rencontré des jetons pour la première fois lorsque nous apprenions les arbres d’analyse. Les jetons sont des symboles spéciaux qui sont au cœur de chaque langage de programmation. Les jetons, tels que (, ), +, -, if, else, then, aident tous un compilateur à comprendre comment différentes parties d’une expression et divers éléments se rapportent les uns aux autres. L’analyseur, qui est au cœur de la phase d’analyse syntaxique, dépend de la réception de jetons de quelque part, puis transforme ces jetons en un arbre d’analyse.

Eh bien, devinez quoi? Nous avons enfin compris le « quelque part »! Il s’avère que les jetons envoyés à l’analyseur sont générés dans la phase d’analyse lexicale par le tokenizer, également appelé lexer.

Alors à quoi ressemble exactement un jeton? Un jeton est assez simple et est généralement représenté par une paire, composée d’un nom de jeton et d’une valeur (facultative).

Par exemple, si nous jetons notre chaîne shakespearienne, nous nous retrouverions avec des jetons qui seraient principalement des littéraux de chaînes et des séparateurs. Nous pourrions représenter le lexème "dream” comme un jeton comme ceci: <string literal, "dream">. Dans la même veine, nous pourrions représenter le lexème . comme jeton, <separator, .>.

Nous remarquerons que chacun de ces jetons ne modifie pas du tout le lexème — ils leur ajoutent simplement des informations supplémentaires. Un jeton est un lexème ou une unité lexicale avec plus de détails; plus précisément, le détail ajouté nous indique quelle catégorie de jeton (quel type de « mot ») nous avons affaire.

Maintenant que nous avons tokenisé notre phrase shakespearienne, nous pouvons voir qu’il n’y a pas beaucoup de variété dans les types de jetons dans notre fichier source. Notre phrase n’avait que des chaînes et de la ponctuation — mais ce n’est que la pointe de l’iceberg symbolique! Il existe de nombreux autres types de « mots » dans lesquels un lexème pourrait être classé.

Le tableau présenté ici illustre certains des jetons les plus courants que notre compilateur verrait lors de la lecture d’un fichier source dans à peu près n’importe quel langage de programmation. Nous avons vu des exemples de literals, qui peuvent être n’importe quelle chaîne, nombre ou valeur logique / booléenne, ainsi que separators, qui sont tout type de ponctuation, y compris les accolades ({}) et les parenthèses (() div>).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). Nous pourrions également rencontrer des lexèmes qui pourraient être segmentés en tant que identifiers, qui sont généralement des noms de variables ou des choses écrites par l’utilisateur / programmeur pour faire référence à autre chose, ainsi que , qui peuvent être des commentaires de ligne ou de bloc écrits par l’utilisateur.

Notre phrase originale ne nous montrait que deux exemples de jetons. Réécrivons notre phrase pour lire à la place: var toSleep = "to dream";. Comment notre compilateur pourrait-il lex cette version de Shakespeare?

Ici, nous verrons que nous avons une plus grande variété de jetons. Nous avons un keyword dans var, où nous déclarons une variable, et un identifiertoSleep, qui est la façon dont nous nommons notre variable ou référençons la valeur à venir. Vient ensuite notre =, qui est un jeton operator, suivi de la chaîne littérale "to dream". Notre instruction se termine par un séparateur ;, indiquant la fin d’une ligne et délimitant des espaces.

Une chose importante à noter à propos du processus de tokenisation est que nous ne jetons aucun espace (espaces, nouvelles lignes, tabulations, fin de ligne, etc.), ni le transmettre à l’analyseur. N’oubliez pas que seuls les jetons sont donnés à l’analyseur et se retrouveront dans l’arbre d’analyse.

Il convient également de mentionner que différentes langues auront des caractères différents qui constituent des espaces. Par exemple, dans certaines situations, le langage de programmation Python utilise l’indentation — y compris les onglets et les espaces — afin d’indiquer comment la portée d’une fonction change. Ainsi, le tokenizer du compilateur Python doit être conscient du fait que, dans certaines situations, un tab ou space doit en fait être tokenisé sous forme de mot, car il doit en fait être passé à l’analyseur!

Cet aspect du tokenizer est un bon moyen de comparer la différence entre un lexer/tokenizer et un scanner. Alors qu’un scanner est ignorant et ne sait comment décomposer un texte qu’en ses plus petites parties possibles (ses « mots »), un lexer/ tokenizer est beaucoup plus conscient et plus précis en comparaison.

Le tokenizer doit connaître les subtilités et les spécifications du langage en cours de compilation. Si tabs sont importants, il doit le savoir; si newlines peut avoir certaines significations dans le langage en cours de compilation, le tokenizer doit être conscient de ces détails. D’un autre côté, le scanner ne sait même pas quels sont les mots qu’il divise, encore moins ce qu’ils signifient.

Le scanner d’un complieur est beaucoup plus indépendant du langage, tandis qu’un tokenizer doit être spécifique au langage par définition.

Ces deux parties du processus d’analyse lexicale vont de pair, et elles sont au cœur de la première phase du processus de compilation. Bien sûr, différents compliers sont conçus de manière unique. Certains compilateurs effectuent l’étape de numérisation et de création de jetons en un seul processus et en un seul programme, tandis que d’autres les diviseront en différentes classes, auquel cas le générateur de jetons appellera la classe du scanner lorsqu’il sera exécuté.

Dans les deux cas, l’étape de l’analyse lexicale est très importante pour la compilation, car la phase d’analyse syntaxique en dépend directement. Et même si chaque partie du compilateur a ses propres rôles spécifiques, ils s’appuient les uns sur les autres et dépendent les uns des autres — comme le font toujours les bons amis.

Ressources

Comme il existe de nombreuses façons d’écrire et de concevoir un compilateur, il existe également de nombreuses façons de les enseigner. Si vous faites suffisamment de recherches sur les bases de la compilation, il devient assez clair que certaines explications vont beaucoup plus en détail que d’autres, ce qui peut être utile ou non. Si vous souhaitez en savoir plus, vous trouverez ci—dessous une variété de ressources sur les compilateurs, en mettant l’accent sur la phase d’analyse lexicale.

1. Chapitre 4 – Crafting Interpreters, Robert Nystrom
2. Construction du compilateur, Professeur Allan Gottlieb
3. Bases du compilateur, Professeur James Alan Farrell
4. Écriture d’un langage de programmation – le Lexer, Andy Balaam
5. Notes sur le fonctionnement des analyseurs et des compilateurs, Stephen Raymond Ferg
6. Quelle est la différence entre un jeton et un lexème?, StackOverflow