Réalisation d'un compilateur (partie 2)

Création d'un compilateur étape par étape

Réalisation d’un compilateur: Partie 2, le lexing

Dans le précédent article nous avons brièvement vu les différentes étapes qui permettaient de créer un exécutable. Abordons maintenant la première phase plus en détail. Dans cette étape il va falloir non seulement détecter et extraire les tokens du fichier source, mais aussi les vérifier. Enfin, l’ensemble de ces tokens sera sauvegardé puisqu’ils sont indispensables à la réalisation des étapes suivantes.

Quelques bonnes pratiques

Avant d’aller plus loin, il est important lorsqu’on aborde un projet de cette taille, de se fixer quelques bonnes pratiques. Voici donc une liste, qui pourra sembler évidente pour certains, des habitudes à prendre:

  • Fixez-vous une norme d’écriture, c’est à dire choisissez la manière dont vous indenterez votre code, et le style d’écriture que vous adopterez (pascal case, caml case, C case, etc…).
  • Essayez au maximum de rendre votre code le plus proche d’un langage parlé que possible. Pour cela, utilisez des noms explicites d’identifiants et découpez votre code en une série de petites fonctions et classes. Une fonction ne devrait pas excéder en moyenne une cinquantaine de ligne.
  • Évitez de mettre du code dans un fichier header. Pour les templates et fonctions inliner préférez l’utilisation d’un fichier externe inclue dans votre fichier header (l’extension est généralement .hxx sous Unix).
  • Documentez votre code. Un commentaire devrait être écris avant de commencer à écrire le comportement d’une fonction auquel il est rattaché.
  • Essayez de ne faire qu’une classe par fichier.
  • Évitez les using namespace std;. Par exemple, préférez un simple using std::cout;, si votre but est juste de ne pas réécrire std:: devant un cout. Voir: Du bon usage du using namespace
  • Utilisez des namespaces pour modulariser votre code.
  • Usez et abusez des assert ! Assert est une macro fonction, qui permet de s’assurer qu’un prédicat est vrai. En mode release, les assert disparaissent purement et simplement, il n’y a donc aucun coût supplémentaire.

Les design patterns

Un design pattern, ou patron de conception, est une solution élégante et éprouvée pour résoudre un problème récurrent. De nombreux design patterns existent et je ne les détaillerais pas tous. Ce projet en utilise trois: le singleton, le flyweight et le visitor. Chacun de ces patrons de conception seront expliqués au fur et à mesure.

Les symboles et expressions

Dans notre langage, sont présents des mots et des symboles. De manière à aisément les modifier par la suite, nous allons commencer par créer une classe qui se chargera d’externaliser la liste des mots valides. Nous allons appeler cette classe Configuration. Cette classe représentant une configuration unique, ne doit pas être dupliquée, et être accessible en tout endroit de notre code. Le design pattern singleton est donc tout à fait adapté.

Explication du design pattern singleton

Le but de ce design pattern est d’assurer l’unicité d’un objet cible. Le code nécessaire à sa réalisation n’est pas très compliqué. Nous allons créer une classe la plus générique possible. Cette classe sera templatée par l’objet dont l’unicité doit être assurée. Tout d’abord nous allons rendre impossible la construction d’un tel objet. Pour cela, nous allons établir le niveau de visibilité du constructeur par défaut, comme étant inaccessible. Il est maintenant impossible d’instancier la classe directement. Pour instancier une telle classe, nous allons créer une méthode publique, et surtout statique (c’est à dire qui peut être utilisée sans instancier la classe ou elle se trouve), et gérer la construction de cette classe à travers cette méthode. La méthode s’assurera que c’est bien toujours le même objet qui sera renvoyé, et non une duplication. Pour réaliser cela, il suffit d’utiliser une variable locale statique, qui par définition, ne sera initialisée qu’une et une seule fois. Ainsi, il est impossible de faire une copie de ce même objet.

Voici à quoi ressemble notre classe (Ceci est une version simplifiée et compactée):

template<typename T>
class Singleton
{
protected:
  Singleton() {}
public:
  static T& getInstance()
  {
    static T object;
    return object;
  }
};

La classe configuration contiendra un conteneur d’association clé-valeur (std::map), qui associera un type de mot à la représentation que l’on voudra en faire. Par exemple, je peux associer le mot str à “, pour indiquer le sigle qui permet l’ouverture et la fermeture d’une chaîne de caractères. Vous trouverez l’ensemble de ces sigles dans le fichier Configuration.hxx. Maintenant, pour que notre classe configuration soit un singleton, il suffit juste d’hériter de cette classe de la manière suivante:

class Configuration : public Singleton<Configuration>
{
  friend class Singleton<Configuration>;
private:
  Configuration();
  std::map<std::string, std::string> _keyWords;
};

Vous remarquez, que le constructeur de cette classe est mis en visibilité privée, afin d’empêcher la construction de cette dite-classe. De plus, la présence du mot clé friend peut sembler ici étrange. Bien que celui-ci soit facultatif, il va permettre d’alléger l’écriture lors de l’appel à une instance. En effet, pour pouvoir récupérer l’instance il faut écrire:

Configuration& cfg = Singleton<Configuration>::getInstance();

Ce qui n’est pas très élégant. En indiquant que configuration est ami avec le singleton, il est possible de simplifier l’écriture en:

Configuration& cfg = Configuration::getInstance();

Cette écriture étant tout de même plus intuitive.

La classe Error

Quel que soit l’étape, en cas de code source invalide, il faudra signaler l’erreur à l’utilisateur. Pour l’aider dans cette démarche, il faut bien évidemment lui indiquer le type d’erreur, l’endroit ou se situe celle-ci et accompagner le tout d’un message explicatif. Toutes ces informations seront regroupées au sein de cette classe, dont voici le code simplifié:

class Error
{
public:
  Error(const Error::type type, const std::string msg, const int line)
   : _type(type), _msg(msg), _line(line)
  {
  }
private:
  const type _type;
  const std::string _msg;
  const int _line;
};

La classe Error Handler

Lorsqu’une erreur survient, on ne s’arrête généralement pas tout de suite. On cherche à en détecter le plus possible. C’est pour cela que même si un code source est faux, on continuera d’analyser le fichier afin de présenter à l’utilisateur le maximum d’erreur d’un coup. Cette classe n’est pas très compliquée à comprendre et contiendra essentiellement une liste d’erreur (std::vector<Error*> _errors;).

La classe Symbol

À chaque fois que l’on récupérera un token, il faudra non seulement retenir le symbole textuel, mais aussi les informations qui lui sont associées, comme la ligne où était présent celui-ci, ainsi que le type de token (par exemple, si c’est une expression simple, un opérateur, une chaîne de caractères, etc…). La classe Symbol se chargera, en fonction du symbole textuel donné au constructeur d’en déduire le type de token. En délégant cette responsabilité à cette classe, nous allons grandement simplifier celle qui se chargera du lexing.

Cette classe possèdera trois constructeurs, le premier demandera toutes les informations nécessaires à la création d’un symbole (token, ligne et type), le deuxième ne demandera que deux informations, et déduira à partir du token, le type de token, et enfin le troisième construira un nouveau symbole à partir d’un autre. Enfin, vous noterez la présence d’une méthode check() qui permettra de vérifier, dans le cas où le token est de type identifiant (c’est à dire si c’est un nom de variable ou de fonction), si ce nom est correct. Pour qu’un nom soit valide il doit être composé uniquement de lettres, de chiffres, et de caractères _, et commencer par une lettre. Enfin l’opérateur « est redéfini afin de facilement afficher un symbole à l’écran.

Notre classe Symbol à tout de même un défaut. Si un token apparaît plusieurs fois, alors dans la liste des symboles, nous aurons plusieurs fois en mémoire la chaîne de caractères représentant celui-ci. Dans un souci d’optimisation, nous allons faire en sorte d’assurer l’unicité de chaque chaîne rencontrée. Pour cela, nous allons maintenant étudier le design pattern flyweight, qui répond à ce besoin.

Le design pattern Flyweight

Imaginons la situation suivante: vous essayez de coder un logiciel de traitement de texte basique. Chaque lettre tapée possède une représentation visuelle en fonction de sa taille, de sa fonte et de sa couleur. Vous allez donc naturellement crée une classe Lettre. Ainsi, pour chaque lettre tapée, une nouvelle instance de Lettre est crée. Le nombre de lettre tapé pouvant rapidement être important, la mémoire sera saturée très vite. Une approche intelligente, est de tout simplement vérifier lors de la création d’une lettre, que celle-ci n’est pas déjà présente avec les mêmes caractéristiques. Si c’est le cas, autant utiliser celle déjà existante. Cette astuce va permettre de gagner énormément d’espace mémoire.

En C++, pour créer une classe flyweight générique, il suffit de peu de chose. Tout d’abord, utilisons un conteneur commun à tous les instances d’une même classe. Ce conteneur doit assurer l’unicité de chaque élément, nous utiliserons donc un set. Il suffit ensuite de vérifier, lors de la création d’un nouvel élément, si celui est présent ou non. Si ce n’est pas le cas, on ajoute cet élément. On renvoie ensuite l’adresse de l’élément, qui existera forcément. De plus, nous redéfinirons tous les opérateurs d’affectation et de comparaison afin de rendre notre classe la plus aisée à utiliser que possible. Enfin, des méthodes statiques clear() et size() nous permettront respectivement de vider et d’obtenir la taille du conteneur partagé.

Voici un extrait de la classe simplifiée:

template <typename T>
class Flyweight
{
public:
  Flyweight(const T& elt);
  static void clear();
  static unsigned int size();
  const Flyweight& operator=(const T& s);
  bool operator==(const T& elt);
  bool operator!=(const T& elt);
protected:
  static std::set<T> set;
  const T* _elt;
};

La classe SharedString

Maintenant que nous avons créé ce design pattern, nous allons l’appliquer à notre projet. Pour cela nous allons créer la classe SharedString qui permettra de partager en mémoire les instances de chaîne de caractères similaires. La création de cette classe est triviale puisqu’il suffit d’hériter d’un flyweight spécialisé. Quelques méthodes supplémentaires sont présentes, comme la possibilité de récupérer un caractère à une position donnée, obtenir la taille de la chaîne, ainsi que des interactions définies avec les chaînes de caractère sous forme de char*. Ceci permet à cette classe de s’utiliser exactement comme un std::string, ce qui rend son utilisation très intuitive.

Voici un extrait de la classe simplifiée:

class SharedString : public Flyweight<std::string>
{
public:
  SharedString(const SharedString& s);
  SharedString(const std::string& s);
  SharedString(const char* s);
  const SharedString& operator=(const char* s);
  bool operator==(const char* s);
  bool operator!=(const char* s);
  char& operator[](const unsigned int i);
  unsigned int length() const;
};

La classe Lexer

Maintenant que nous avons créé tout le nécessaire, attaquons-nous à la partie principale: le lexing. Notre classe Lexer, n’est pas bien difficile à comprendre. Elle possède une liste d’erreurs (elle encapsule une classe Error Handler), et une liste de symboles. Il suffit juste de récupérer chacun des tokens et de mettre à jour la table des symboles au fur et à mesure. En cas d’erreur, on ignore le token en cours, on ajoute une nouvelle erreur à la liste d’erreur, et on continue d’essayer d’extraire les tokens suivants.

Détaillons maintenant la méthode utilisée pour extraire les tokens. Tout d’abord, on vérifie que le token en cours ne soit pas un token d’ouverture de commentaire, auquel cas, on passe directement à la ligne suivante, puisqu’un commentaire est par définition ignoré. On vérifie aussi que le token en cours ne soit pas un token d’ouverture de chaîne de caractère. Si tel est le cas, alors on se contente de trouver le caractère de fermeture de chaînes de caractères et on enregistre la chaîne ainsi récupérée comme étant un token à part entière.

Il est important de bien différencier les mots clés, des symboles atomiques. Un mot clé doit forcément être écrit de manière stricte, c’est-à-dire sans que celui-ci soit collé à un autre token, ce qui n’est pas le cas des symboles atomiques. Par exemple: begin end sont bien deux mots clés, mais beginend, sera considéré comme une expression simple. En revanche, si on prend le symbole atomique >=, on se rend bien compte que 4 >= 5 et 4>=5 sont deux expressions identiques.

Nous allons commencer par détecter les symboles atomiques ayant deux caractères. En effet, il faut toujours rechercher en priorité les tokens les plus grands pour éviter toutes ambiguïtés. Par exemple, il est important lorsque l’on rencontre la chaînes suivantes: <=, de bien détecter le symbole atomique <= et ne surtout pas détecter deux symboles atomiques qui se suivraient. Si l’expression en cours d’analyse, n’est ni un symbole atomique, ni un mot clé, alors il ne reste plus qu’à vérifier que celle-ci soit une valeur ou une variable. Si l’expression en cours n’est composée que de chiffres, alors c’est une valeur. Dans le cas contraire, si ce n’est aucun des types de token précédemment décrit, ça ne peut donc être qu’une variable.

Mise en place

Maintenant que notre Lexer est terminé, nous allons juste mettre en place un système d’option. Celui-ci est trivial, il suffit juste de considérer que le premier argument de la ligne de commande (argv[1]), représente l’option, et les arguments suivants, les fichiers passés à notre binaire. Nous allons donc créer les deux options suivantes: -l, qui permettra de lancer le lexing sur les fichiers donnés en arguments, c’est-à-dire qui affichera les éventuelles erreurs de lexing, et -L, qui en plus de faire ce que fait la première option, affichera aussi des informations sur tout les tokens récupérés, c’est-à-dire les type de token, la ligne ou ceux-ci ont été extraits, et, leurs symboles textuels. Cette mise en place est suffisamment simple pour que je ne la détaille pas.

Conclusion

Dans le prochain article, nous aborderons le parsing, mais pour les plus impatients d’entre vous, le projet complet pourra être récupéré à cette adresse: https://github.com/cptpingu/Cubs/tree/master/cubs