This is Jawher Moussa's blog

in which he writes about technical stuff

Le conte de Litil - Chapitre 2, Le dépeceur du texte, aka Lexer

Dans ce deuxième post du conte de Litil, je vais parler de la phase de lexing. C’est généralement la première étape dans la construction d’un compilateur (ou évaluateur) d’un langage donné. Cette phase sert à transformer le texte du code source (séquence de caractères) vers une séquence de tokens, qui seront consommés par le parseur à l’étape suivante.

Les règles suivant lesquelles le texte est découpé en tokens varient d’un langage à un autre, mais en général (avec les langages conventionnels de la famille Algol par exemple), on peut définir les familles de tokens suivants:

On peut donc voir un token comme un couple type (symbole, mot clé, littéral, etc.) et valeur (le contenu textuel de ce token). Optionnellement, on peut enrichir un token pour qu’il contienne aussi le numéro de la ligne et de la colonne où il apparait dans le texte source, ce qui peut s’avérer utile pour signaler l’emplacement d’une erreur.

Enfin, le lexer se charge de cacher ou ignorer le contenu inutile dans le fichier source, comme les blancs, retours à la ligne et autres.

Gestion des blancs

Dans le langage que nous allons implémenter, et à l’encontre de la majorité des autres langages, les blancs sont importants car il servent à démarquer le début et la fin des blocs comme dans Python (et Haskell) par exemple. Le début d’un bloc est signalé par une augmentation du niveau de l’indentation tandis que sa fin est marquée par une dé-indentation.

Exemple:

if n > 0 then
  let x = 10 / n
  print "Ohai"
else
  throw Error

L’équivalent Java serait:

if (n > 0) {
  int x = 10 / n;
  System.out.print("Ohai");
} else {
  throw new Exception();
}

Bien que les corps des branches then et else du code java sont bien indentés, cette indentation est optionnelle et est carrément ignorée par le lexer. Ce sont les accolades ouvrantes et fermantes qui démarquent le début et la fin d’un bloc. On aurait pu obtenir le même résultat avec:

if (n > 0) {
int x = 10 / n;
System.out.print("Ohai");  
} else {
throw new Exception();
}

ou encore:

if (n > 0) {int x = 10 / n;System.out.print("Ohai");} else {throw new Exception();}

La lisibilité du code en souffre, mais cela ne change rien du point de vue du compilateur. Ce n’est pas le cas avec Litil, où comme dit plus haut, l’indentation du code n’est pas optionnelle car elle sert à définir sa structure. De plus, là où dans Java on utilisait le ; pour séparer les instructions d’un même bloc, Litil utilise plutôt les retours à la ligne. Les ; ne sont pas optionnels, ils ne sont pas reconnues. Mon but était de s’inspirer des langages comme Haskell et Python pour créer une syntaxe épurée avec un minimum de bruit et de décorum autour du code utile. Je reveniendrai la dessus dans le*(s)* post*(s)* à venir quand je vais détailler la syntaxe de Litil, mais pour vous donner quelques exemples:

Donc, pour résumer, le lexer que nous allons développer ne va pas complètement ignorer les blancs. Plus précisément, le lexer devra produire des tokens pour signaler les retours à la ligne (pour indiquer la fin d’une instruction) et les espaces (ou leur absence) en début de lignes (pour indiquer le début ou la fin d’un bloc).

Implémentation

Pour commencer, voici la définition d’un Token:

public class Token {
    public enum Type {
        NEWLINE, INDENT, DEINDENT, NAME, NUM, STRING, CHAR, SYM, BOOL, KEYWORD, EOF
    }
    public final Type type;
    public final String text;
    public final int row, col;

    public Token(Type type, String text, int row, int col) {
        this.type = type;
        this.text = text;
        this.row = row;
        this.col = col;
    }
}

Un token est composé de:

Voici maintenant l’interface qui décrit le lexer:

public interface Lexer {
    Token pop() throws LexingException;

    String getCurrentLine();
}

Cette interface définit les 2 méthodes suivantes:

Notez l’absence d’une méthode qui indique la présence ou pas d’un token suivant. En effet, quand le lexer atteint la fin du fichier, il se place en un mode où tous les appels à pop retournent un token de type EOF. J’ai donc estimé inutile d’alourdir l’interface pour ajouter une méthode à la hasNext d’un itérateur par exemple.

Notez aussi que si j’ai défini une interface pour le lexer, c’est parce qu’il y aurait plusieurs implémentations que nous allons voir par la suite.

Comment ça fonctionne

Voici une présentation rapide du fonctionnement de l’implémentation de base du lexer (Code source de BaseLexer.java (sur Github) pour ceux qui voudront suivre avec le code sous les yeux):

Gestion des blancs

A lecture d’une nouvelle ligne, et avant d’exécuter l’algorithme décrit dans la section précédente, le lexer consomme les espaces en début de la ligne en calculant leur nombre, ce qui définit le niveau d’indentation de la ligne. Il compare ensuite cette valeur au niveau d’indentation de la ligne précédente (qu’il maintient dans un champ initialisé à 0):

Un exemple pour clarifier un peu les choses. Etant donné ce texte en entrée:

a
  b
  c
d

Le lexer est censé générer les tokens suivants:

  1. NEWLINE
  2. NAME(a)
  3. INDENT: le niveau d’indentation a augmenté à la 2ième ligne
  4. NEWLINE: toujours produit pour une nouvelle ligne
  5. NAME(b)
  6. NEWLINE: le niveau d’indentation n’a pas changé entre les 2ième et 3ième lignes
  7. NAME(c)
  8. DEINDENT: le niveau d’indentation a diminué
  9. NEWLINE
  10. NAME(d)
  11. EOF: fin de l’entrée

Seulement, l’algorithme décrit jusqu’ici n’est pas suffisant pour que le parseur arrive à gérer proprement l’indentation. En effet, avec l’exemple suivant:

a
  b

Le lexer ne va pas produire un token de type DEINDENT après le NAME(b) mais plutôt un EOF car il n’y a pas de nouvelle ligne après le b. On pourrait imaginer une solution où le parseur utilise EOF en plus de DEINDENT pour détecter la fin d’un bloc, mais ce n’est pas suffisant. En effet, avec l’exemple suivant:

a
  b
    c
d

L’implémentation décrite ici va générer un seul token DEINDENTaprès NAME(c) alors que cette position dans le source marque la fin de 2 blocs et non pas un seul.

Pour gérer ce type de situations, et ne voulant pas complexifier encore le code du lexer de base, j’ai décidé de gérer ça dans une autre implémentation de l’interface Lexer, StructuredLexer. Cette dernière implémente le pattern décorateur en délégant à BaseLexer pour générer les tokens du texte source, mais en l’enrichissant avec les traitements suivants:

Ainsi, avec l’exemple suivant:

a
  b
    c
d

Le lexer structuré génère 1 DEINDENT virtuel, en plus du DEINDENT généré par le lexer de base entre c et d. Comme ça, le parseur au dessus pourra détecter la fin de 2 blocs et détecter correctement que d a le même niveau que a.

Enfin, le code source qui implémente cet algorithme est disponible dans le repo Github de Litil pour les intéressés.

Gestion des commentaires

Dans Litil, les commentaires sont préfixés par -- (double -) et s’étendent sur une seule ligne uniquement. J’ai (arbitrairement) choisi de les gérer au niveau du lexer en les ignorant complètement. Mais j’aurais aussi pu produire des tokens de type COMMENT et les ignorer (ou pas) dans le parseur.

Les commentaires sont gérés à 2 endroits dans le lexer:

Exemples:

-- compute max x y … NOT !
let max x y = x

let max x y = x -- It is a well known fact that x always wins !

Gestion des symboles

Avec la gestion des indentations, c’est la partie la plus intéressante (amha) dans le code du lexer.

Avant de rentrer dans les détails d’implémentation, je vais d’abord parler un peu d’automates finis, qui sont une notion centrale dans la théorie des langages et la compilation.

Un automate fini est un ensemble d’états et de transitions. On peut le voir comme un système de classification: étant donnée une séquence en entrée, il consomme ses éléments un à un en suivant les transitions adaptés (et donc en passant d’un état à un autre) jusqu’à ce qu’il ait consommé toute l’entrée ou encore qu’il arrive dans un état sans aucune transition possible. Quelques états peuvent être marqués comme terminaux ou finals, une façon de dire que ça représente un succès. Donc étant donnée un automate et une entrée, si le traitement s’arrête dans un état terminal, on peut dire qu’on a prouvé une propriété donnée sur l’entrée. Cette propriété va dépendre de l’automate.

Ok, j’explique comme un pied. Un exemple concrêt:

graph

L’automate présenté dans la figure précédente se compose de:

Maintenant, appliquons cet automate à la séquence de caractères ->a. Comme dit plus haut, on se positionne initialement au point d’entrée S0. On examine le premier caractère de la séquence d’entrée (->a) et on cherche une transition qui part de cet état et qui est étiquetée avec ce caractère. Ca tombe bien, le premier caractère - correspond bien à une transition entre S0 et A. On suit donc cette transition pour arriver à l’état A et on passe au caractère suivant (>). L’état A est terminal. On pourrait donc interrompre le traitement et dire et qu’on a réussi à matcher le caractère -. Cependant, dans Litil et presque tous les autres langages, le lexer essai plutôt de matcher la séquence la plus longue. L’alternative est qu’il ne faut jamais avoir plusieurs opérateurs qui commencent par le même caractère, ce qui serait trop contraignant.

On continue donc le traitement. A dispose bien d’une transition étiquetée avec >. On suit donc cette transition et on arrive à l’état C qui est aussi terminal. Mais par la même logique, on n’abandonne pas tout de suite et on tente de voir s’il est possible de matcher une séquence plus longue. Ce n’est pas le cas ici car l’état A n’a aucune transition étiquetée avec le caractère a. Le traitement s’arrête donc ici, et comme c’est un état terminal, on retourne un succès avec la chaîne matchée qui ici est ->.

Notez que l’algorithme que je viens de décrire (et qui est utilisé par l’implémentation actuelle du lexer de Litil) est plutôt simpliste et incomplet par rapport à l’état de l’art car il ne gère pas le backtracking. Par exemple, cet algorithme échoue avec l’automate suivante (censé reconnaitre les symboles - et -->) avec la chaîne --a comme entrée alors qu’il devrait réussir à retourner deux fois le symbole - (le pourquoi est laissé comme exercice au lecteur):

graph

Dans sa version actuelle, les symboles reconnus par Litil sont: ->, ., +, -, *, /, (, ), =, %, <, >, <=, >=, :, ,, [, ], |, _, =>, \\, --, ::, { et }.

Maintenant, juste pour la science, voici l’automate fini correspondant à ces symboles:

graph

L’implémentation de cet automate dans Litil est dynamique, dans la mesure où l’automate est construit au runtime à partir d’une liste des symboles à reconnaitre. Aussi, cette implémentation ne gère pas le backtracking, qui est inutile pour le moment car, et à moins que je ne dise de bêtises, le problème décrit plus haut n’arrive que si on a des symboles à 3 caractères (et qui ont le même préfixe qu’un symbole à un caractère), ce qui n’est pas le cas dans Litil (ce n’est pas Scala tout de même. Enfin, pas encore). Par contre, l’implémentation tient en 50 lignes de code Java, et si on ignore le décorum de Java (les imports, les getters, le toString, le constructeur, etc.), l’essence de l’algorithme tient juste dans une douzaine de lignes. Voici son code source sur Github pour les intéressés.

Lookahead

Une fonctionnalité utile à avoir dans le lexer est le lookahead, i.e. la possibilité de voir les tokens suivants sans pour autant les consommer (comme c’est le cas avec pop). On va revenir la dessus dans le(s) post(s) à propos du parseur.

Tout comme StructuredLexer, j’ai décidé d’implémenter cette fonctionnalité dans un décorateur autour d’un lexer concrêt, pour ne pas complexifier le code de ce dernier. Il s’agit de la classe LookaheadLexerWrapper (dont voici le code source). L’implémentation derrière est plutôt simple. En effet, l’astuce est juste de maintenir une liste de tokens (en plus du lexer concrêt). Quand la méthode lookahead est appelé (avec un paramètre qui indique le niveau du lookahead: 1 pour le token suivant, etc.), on récupère autant de tokens que nécessaire du lexer et on les stocke dans cette liste. Quand pop est appelée, et avant de déléger au lexer concrêt, on vérifie si la liste de tokens n’est pas vide. Si c’est le cas, on retourne le premier élément de cette liste et en prenant soin de l’enlever, comme ça, l’appel suivant à pop va retourner le token suivant. Si cette liste est vide, alors on délègue au lexer.

Conclusion

Dans ce post, j’avais présenté rapidement et sans trop entrer dans les détails quelques techniques de lexing que j’ai utilisé dans Litil. Ce n’est en aucune façon la meilleure façon de faire ni la plus performante. C’était plus une implémentation relativement facile à coder et à étendre tout en restant raisonnable pour tout ce qui est consommation mémoire (le fait de ne pas lire la totalité du fichier dans une seule String d’un coup par exemple).

Il faut aussi noter que c’est la partie la moins marrante à coder dans un langage. J’ai même été tenté de la faire générer par un outil comme AntLR ou SableCC, mais au final j’ai décidé de rester fidèle à ma vision de vraiment tout coder à la main (sauf les parties que je ne coderai pas à la main, NDLR).

Maintenant que cette partie est derrière nous, nous allons enfin pouvoir attaquer les sujets intéressants, e.g. le parseur et l’évaluateur, dans les posts suivants.