Introduction▲
« lexer »… Vous avez peut-être déjà lu ou entendu ce mot… C'est bien gentil, mais qu'est-ce que c'est ? Et à quoi ça sert, comment ça marche ?!
Dans ce tutoriel, c'est ce que je compte vous expliquer, en commençant par cette première partie théorique suivie d'une partie plus pratique, de codage principalement !
La partie théorique que voici n'a pas la prétention de présenter dans son intégralité tout ce qu'on peut trouver sur les lexers. L'ambition est de vous introduire au sujet, de vous y donner goût, en présentant principalement l'utilité d'un lexer et son mode de fonctionnement global.
Ceci fait, nous enchainerons en toute logique sur la seconde partie, pratique, pour mettre en œuvre la méthode apprise et ainsi aboutir à un lexer fonctionnel !
I. Qu'est-ce qu'un lexer ?▲
I-A. Définition▲
Un lexer est un outil d'analyse, et particulièrement d'analyse de texte, sous toutes les formes que cela puisse être : simple document, document formaté, script, code, ligne de calculs…
Un lexer va fournir au développeur un moyen puissant pour parcourir, décomposer et analyser un bloc de texte structuré.
Il existe plusieurs types de lexers, qui ne fonctionnent pas tous de la même manière… Plus particulièrement, il faut en réalité développer un lexer par structure que l'on veut analyser. Le pourquoi du comment de cette spécificité est expliqué en deuxième partie.
I-B. Quelques exemples▲
Voici une liste de quelques exemples d'applications utilisant un/des lexer(s), et à quelles fins elles les utilisent :
- Delphi : coloration syntaxique, compilation du code, établissement de la liste des classes d'une unité… ;
- PHP : recherche de PHP dans du HTML, exécution du code PHP… ;
- MySQL : exécution des requêtes SQL ;
- Maple, MatLab : interprétation/exécution de lignes de calculs mathématiques ;
- Word : correction orthographique, formatage de texte (rtf, doc)… ;
- Excel : interprétation/exécution de formules ;
- Mozilla : lecture de pages HTML, exécution de JavaScript dans une page…
Toutes ces applications utilisent, d'une manière ou d'une autre, un outil d'analyse que l'on peut appeler lexer, du plus simple (recherche de mots pour la correction orthographique) au plus complexe (compilation de code) !
II. Comment ça marche ?▲
II-A. Introduction▲
Dans ce paragraphe, il n'est pas question de fournir d'ores et déjà du code correspondant au processus de traitement d'un lexer. Il s'agit de donner les bases de fonctionnement d'un lexer en général.
Qui plus est, ce n'est pas l'unique solution pour développer un lexer, mais la méthode est calquée sur un certain nombre de lexers, dont celui implémenté dans la classe TParser de Delphi (voir l'unité classes.pas). Cette méthode est d'après moi, une approche assez intéressante et qui, surtout, s'applique dans un bon nombre de cas d'utilisation !
La méthode en question est une méthode « séquentielle » : le flux de caractères fourni est parcouru du début jusqu'à la fin, et ce, de manière unidirectionnelle, c'est-à-dire sans possibilité de faire marche arrière.
Voyons maintenant plus en détail ses caractéristiques…
II-B. Un peu de vocabulaire▲
Il n'y a pas beaucoup de vocabulaire à définir… En réalité, il est particulièrement un mot qui mérite d'être explicité, car il sera souvent utilisé : token.
Je ne m'attacherai pas à essayer d'en donner une traduction acceptable en français, vu que nous n'utiliserons de toute façon que le terme anglais.
Un token est en quelque sorte le plus petit élément « unitaire » des données que nous voulons analyser. Comme il s'agit dans notre cas de texte, nous appellerons token tout mot, groupe de mots ou de caractères (lettres, chiffres, point…) constituant un tout, relativement à la structure du texte analysé.
Je m'explique par un exemple : prenons le cas d'un code en Pascal Objet, et ici une simple fonction :
procedure AfficherMessage(IdMsg: Integer; Texte: String);
var Msg: String;
Sng: Single;
begin
//Formatage du message
Sng := 1.5;
Msg := Format('Message ID: %f'#10#13'%s', [IdMsg * Sng, Texte]);
ShowMessage(Msg);
end;J'imagine que la coloration syntaxique de code de ce genre vous est relativement familière, et cela va nous être des plus pratiques !
Dans ces quelques lignes, on peut remarquer plusieurs tokens. Il est plus facile de les repérer, car ils sont justement mis en valeur par un changement ou non de style de la police dans Delphi :
- « //Formatage du message » est un commentaire, en bleu marine ;
- « procedure », « string », « var », « begin » et « end » sont des mots réservés, en gras ;
- « 1.5 » est un nombre à virgule flottante, en bleu marine ;
- « 10 » et « 13 » sont des nombres, en bleu marine ;
- « 'Message ID: %f' » et « '%s' » sont des chaines de caractères, en bleu marine ;
- « AfficherMessage », « IdMsg », « Integer », « Texte », « Sng » (…) sont ce qu'on appelle des symboles, leur police ne change pas.
Tous les éléments cités ci-dessus, dans un lexer de code Delphi, seront chacun considérés comme un token… Ainsi, le groupe de mots entre apostrophes ('Message ID…') est considéré comme une entité, un unique élément qui sera identifié comme une chaine de caractères. Le token, comme dit au-dessus, est donc l'ensemble des caractères constituant cette entité.
Il convient bien sûr de définir dans le lexer chaque type de token pouvant être rencontré, car dans le cas contraire « procedure » ou même « Message » seraient considérés comme des symboles au même titre que « AfficheMessage ».
Le travail du lexer va donc être d'identifier chaque token du texte donné afin de permettre une analyse de celui-ci. Il est alors évident que chaque lexer sera spécifique à une structure particulière… Essayez de compiler du VisualBasic dans Delphi s'il vous faut un exemple concret pour comprendre pourquoi !! Les tokens du VB, du C/C++ (…) ne sont pas ceux de Delphi, et ces derniers ne sont pas également ceux d'un document au format RTF !
Il reste maintenant à voir comment, dans un texte donné, un lexer va pouvoir extraire chaque token, en déterminer le type, et ce que peux en faire une application.
II-C. Fonctionnement et utilisation▲
II-C-1. Analyse descendante▲
Voici une analyse descendante, qui reste assez générale, du processus de parsing d'un document afin de montrer les interactions entre le lexer et l'application qui l'utilise.
Cette analyse sera ensuite commentée afin de mieux décrire le fonctionnement et les actions de chaque partie.
Voilà pour une vue « globale » du mécanisme… On pourrait presque dire que l'application n'a rien à faire, si ce n'est traiter ce qu'on lui donne. Mais justement ce traitement peut s'avérer relativement compliqué… tout est fonction des données analysées !
Quant au lexer, il a plus de choses à effectuer, et elles peuvent s'avérer assez longues à implémenter, suivant là encore les données à analyser.
Reprenons donc les points de l'analyse ci-dessus, en les détaillant.
II-C-2. Côté lexer▲
Je vais me répéter, mais il n'y aura pas de code dans ces deux sous-paragraphes, donc ne vous étonnez pas si les explications ne semblent pas très longues. L'implémentation qui suit peut l'être beaucoup plus !
Le lexer reçoit du texte à analyser
Ici, il n'y a pas grand-chose à faire… Le lexer doit copier le texte fourni dans un buffer et initialiser un pointeur sur le premier caractère de ce dernier.
Dans la classe TParser de classes.pas, c'est à la création du lexer que l'on passe un Stream en paramètre. (Le TParser étant bel et bien un lexer !) Ce stream contient les données à analyser et le lexer l'exploitera directement en extrayant dans un buffer les données à analyser.
Rechercher le prochain token
Pour trouver un token, le lexer va tout d'abord passer tous les caractères considérés comme des espaces (tabulations, espaces… cela dépend du texte analysé) jusqu'à arriver sur un premier caractère reconnu. En fonction de ce caractère, il va continuer à avancer dans le texte tant qu'il trouvera des caractères « corrects » pour le token en cours.
Par exemple dans le cas de code Delphi, s'il trouve le caractère '$', il va avancer dans le texte tant qu'il trouvera des nombres hexadécimaux ([0..9], [a..f] et [A..F]). Le lexer obtiendra ainsi le nouveau token : un nombre hexadécimal.
Déterminer le type du token trouvé
Cela se fait assez « naturellement »… En fonction du premier caractère trouvé la recherche effectuée pour avoir le token complet montre que l'on « sait » quel type de token on renvoie. Dans l'exemple précédent, le lexer pourra immédiatement renvoyer un type « nombre hexa ».
Cela est vrai, certes, pour un nombre ou un commentaire qui commence par « // » ou « { », mais si l'on tombe sur un symbole, c'est-à-dire un mot, c'est différent : un mot réservé, un nom de variable, de classe ou de fonctions sont tous quatre des symboles, mais on peut vouloir les distinguer… L'astuce ici est par exemple d'avoir un tableau contenant tous les mots réservés reconnus afin d'en identifier un éventuel.
En règle générale une deuxième « analyse » sur le token trouvé sera nécessaire, mais elle peut à la limite être effectuée côté application.
Renvoyer le token et son type
Une fois le token trouvé et son type, il suffit au lexer de les renvoyer à l'application… Rien de plus simple si la recherche se faisait dans une fonction du lexer appelée par le programme !
On est cependant confronté à un problème : une fonction ne peut renvoyer qu'un seul type… donc soit un record, soit un integer, soit une string (…) ! Pour palier cela, le TParser de classes.pas ne renvoie en réalité que le type du token trouvé, et fournit différentes fonctions (TokenInt, TokenString…) qui permettent de récupérer le token trouvé dans le type désiré.
II-C-3. Côté application▲
Je ne vous ferai pas l'affront de vous expliquer ce qui doit se passer pour la création et la libération du lexer ! Il n'y a donc qu'un point à détailler.
Traitement en fonction du token et de son type
Ce traitement dépend complètement des données analysées…
Dans le cadre d'une interprétation de code, par exemple, cela peut-être d'évaluer une condition après le renvoi d'un token « if » et la récupération du code de cette condition.
Dans le cas de Delphi et de ses DFM (pour lesquels est utilisé TParser de Classes.pas) il s'agirait de créer les composants correspondant aux noms de classes renvoyés par le lexer, puis d'assigner les bonnes valeurs aux propriétés de cet objet.
Pour un dernier exemple, on peut considérer un lexer de lignes de calculs : si le lexer renvoie un nombre suivi d'un opérateur et d'un autre nombre, il faut avoir stocké le premier nombre et effectuer l'opération demandée avec le second nombre.
Les traitements peuvent donc être très variés, et ce sera au développeur de savoir ce qu'il veut faire des données qu'il reçoit, le tout étant de bien réagir à chaque type de token !
III. Quand utiliser un lexer ?▲
Maintenant que nous avons expliqué le fonctionnement d'un lexer, nous sommes en droit de nous demander quand cela peut servir ! Effectivement, bien que ce soit finalement utile et « puissant », un lexer est un outil assez lourd à mettre en place et il n'est donc pas question d'en utiliser à tout va !
Toutefois il ne devrait pas être trop compliqué de répondre à la question « quand » après ce descriptif des lexers. En effet, si vous avez un fichier de données organisées de telle sorte que ces dernières peuvent être récupérées dans un ou plusieurs records, nul besoin de développer un lexer !
Par contre, si vous avez un fichier contenant du texte structuré comme un fichier XML, HTML, du code et j'en passe, là, suivant ce que vous voulez en faire, l'utilisation d'un lexer peut être justifiée.
L'essentiel est de bien définir ce dont vous avez besoin… Parfois vous pourrez peut-être « contourner » l'emploi d'un lexer par une autre méthode, d'autre fois cette solution se présentera comme la plus efficace. À titre d'exemple, les utilisations les plus courantes des lexers sont principalement l'interprétation de script, la compilation de code, l'exécution de calculs et la coloration syntaxique.
Conclusion▲
Voilà donc cette première partie terminée ! J'espère qu'elle vous aura aidé à bien (ou mieux) comprendre ce qu'est un lexer et à déjà vous faire une idée de la manière dont un tel outil peut être employé.
Il reste maintenant à en implémenter un afin d'expérimenter l'idée et pour, tant qu'à faire, satisfaire notre irrésistible besoin de code !
Je vous donne donc rendez-vous pour la prochaine partie de ce tutoriel, dans lequel nous réaliserons de A à Z une application de coloration de code HTML !
Si vous avez des suggestions quant à cet article, je vous invite à m'en faire part en m'envoyant un MP.
Nota▲
Une première version de cet article était intitulée « Parsers 1/2 : Théorie ». Ce changement de titre et, de manière plus générale, le remplacement de « parser » par « lexer » dans le texte de l'article ont été effectués par souci de précision par rapport au sujet.
En effet, un parser est bien un « analyseur », mais c'est le lexer qui a la charge de découper un texte en tokens, ces derniers étant par la suite réutilisés par le parser pour créer un arbre de parsing du document.
Références▲
Voici quelques liens qui vous permettront d'approfondir vos connaissances sur le sujet :
Remerciements▲
Je tiens à remercier Laurent Dardenne, Nono40 et sjrd pour leur relecture et leurs suggestions.