La création d’un langage de programmation est quelque chose qui peut paraitre insurmontable et abstraite pour les développeurs. Cela dit, on peut quand même arriver à faire un mini langage qui gère certains concepts. Dans cet article, nous allons voir comment faire un compilateur en utilisant F#.

Pourquoi créer un langage ?

En tant que développeur, l’utilisation des langages de programmation est courante. Le choix est vaste et nous utilisons des langages créés et éprouvés en production. Mais il arrive que de nouveaux langages de programmation apparaissent. L’envie de créer un langage de programmation est liée à différentes raisons. Que cela soit pour créer un DSL (Domain specific language) qui permettra de faire évoluer les règles de l’application dans le langage du métier, ou que l’on ait envie d’augmenter un autre langage (exemple TypeScript qui permet de rajouter des concepts de type et interfaces dans Javascript) ou tout simplement pour créer un langage fun tel que le Emojicode.

Dans tous les cas, la création d’un langage utilise les mêmes concepts, il faudra créer un compilateur. En Javascript, l’utilisation des « transpiler » permet de convertir des versions de Javascript dans d’autres versions de Javascript. C’est le même principe qu’un compilateur. On convertit un langage de programmation dans un autre langage de programmation.

Il y a différents types de langages de programmation. La première étape est de savoir quel type de langage créer. Par exemple, la création d’un langage impératif. Cela veut dire que le langage est basé sur l’idée d’une exécution étape par étape. Ou encore un langage fonctionnel ou l’idée est basée sur la déclaration de fonctions mathématiques.

Une fois le type de langage choisi, l’idée est de s’inspirer d’un ou plusieurs langages qui existent pour en prendre les concepts qui nous intéressent et les inclure dans notre nouveau langage.

J’ai eu envie de créer un langage pour expliquer comment fonctionne un compilateur. Mon compilateur est loin d’être parfait, mais il intègre beaucoup de briques importantes.

Un compilateur c’est une suite d’étapes. Chacune des étapes est intéressante, il m’est arrivé d’utiliser certaines étapes plus que d’autres pour créer des DSL, parser des fichiers avec un format spécial, ou encore faire des transformations.

Le langage

Avant de créer un compilateur, il nous faut un langage. Nous allons réfléchir au langage de programmation que l’on souhaite créer.

J’ai décidé de créer un langage de programmation impératif et scriptable. C’est-à-dire que je peux commencer à écrire du code sans avoir de concepts de méthodes et objets.

Un exemple simple de ce que je souhaitais écrire :

var x = 1 + 2;
x = 5;

Dans mon langage, je ne souhaite pas non plus spécifier le type comme on peut le faire en C# :

int x = 1 + 2;
x = 5;

Cela veut dire que mon compilateur retournera une erreur lorsque j’utiliserai le mot cléf « int ».

Par contre je souhaite que mon langage soit fortement typé. Ce qui veut dire que je ne pourrai pas écrire :

var x = 1 + 2;
x = true;

En effet, mon compilateur va déduire de l’utilisation que x est de type int donc il ne peut pas recevoir la valeur booléenne « true ».

Maintenant dans ce langage je souhaitais une notion de méthodes. J’ai repris une syntaxe similaire au fonctionnel :

var maMethod = fun(x) -> { return x + 1; };

Il me reste à donner une notion d’objet. Pour cela j’ai décidé que mes objets allaient se définir par leur création :

var monObjet = { MaPropriete=1, MaPropriete2=true};

Ainsi je crée un objet avec deux propriétés, la propriété « MaPropriete » de valeur entière et l’autre « MaPropriete2 » de valeur booléenne.

J’ai nommé mon langage KISS pour Keep It Simple Stupid.

Maintenant que l’on a quelques syntaxes de notre langage, il nous reste à créer le compilateur qui sera capable d’interpréter ce langage pour l’exécuter.

Qu’est-ce qu’un compilateur ?

Un compilateur est une application qui permet de lire un ou plusieurs fichiers texte et en faire un fichier exécutable. Ce fichier exécutable sera l’exécution de ce qui est décrit dans les fichiers textes.

Pour faire un fichier exécutable nous allons produire du code machine. Notre compilateur va donc lire un fichier texte et produire un code machine.

Le code machine est un langage de programmation. Ainsi notre compilateur doit transformer un langage de haut niveau en langage de bas niveau.

Un langage de haut niveau est un langage facilement compréhensible par un humain. Du C# par exemple, peut être lu et compris. Il dispose de plein de mots clés qui lui permettent d’avoir une grande expressivité. Ce langage de programmation peut être compris de manière simple par un humain. Plus le langage de programmation est de haut niveau, plus votre langage est facilement compréhensible.

Un langage de bas niveau, c’est celui qui sera le plus proche de la machine. Ainsi, les instructions son très proches du processeur, nous aurons moins de facilité à le lire, mais le processeur, lui, n’aura aucune difficulté à l’exécuter. Par contre le programme devra gérer des problématiques liées au processeur. Ainsi, les stacks, emplacement mémoire, et registres devront être correctement utilisés.

Le langage de plus bas niveau que nous pouvons générer est de l’assembleur. Pour simplifier nous allons générer du MSIL (Microsoft Intermediate Language)

Par exemple, le compilateur C# généré du MSIL qui sera lui compilé, a l’exécution par le CLR de .Net. Le MSIL est proche d’un langage assembleur mais enlève beaucoup de contraintes.

MSIL simplifie pas mal de concepts bas niveaux tels que les gestions des jumps et de la pile. C’est des concepts à prendre en compte lorsque nous voulons faire des méthodes dans notre code. La pile permet de stocker le contexte d’appel tandis que le jump passe à une suite d’instructions.

En assembleur nous n’avons pas de notions de méthode, mais seulement une suite d’instructions.

Avec la CLR nous allons aussi profiter d’un garbage collector, de check de division par zéro, …

MSIL introduit une notion de classe et de méthode, mais le contenu de ses méthodes reste un langage à base d’instructions.

Nous allons maintenant voir quelles sont les étapes pour passer d’un langage de haut niveau à un langage de bas niveau.

Structure d’un compilateur

Un compilateur contient trois grandes phases :

  • Analyse Syntaxique
  • Analyse Sémantique
  • Générateur

Pendant la première phase nous allons lire un fichier texte et le convertir en arbre syntaxique abstrait. Cet arbre syntaxique est une représentation abstraite du code écrit dans le fichier. Nous allons donc avoir un objet manipulable par code pour pouvoir faire des analyses. Pendant cette phase, si notre fichier texte ne contient pas les bons mots clés, ou si l’ordre des mots clés n’est pas correct nous ne pourrons pas déduire l’arbre syntaxique abstrait.

La deuxième phase est l’analyse de cet arbre syntaxique. A ce moment, nous allons vérifier que notre langage est sémantiquement correct. Pendant cette phase nous allons faire beaucoup de tests pour valider que notre programme peut être converti en code machine et exécuté par le processeur d’une manière logique.

Exemple :

var maVariable = 1;
var maVariable = true;
if(maVariable){ return 1; } else { return 0; }

Nous pouvons vérifier plusieurs choses :

  • maVariable est créée deux fois. Mais mon langage accepte de redéfinir le scope de la variable à partir du moment où l’on refait un « var ». Beaucoup de langages ne l’acceptent pas donc dans ce cas-là on génère une erreur.
  • maVariable existe bien avant d’être utilisée. C’est-à-dire que l’on a bien un « var maVariable » avant l’utilisation dans le « if ». Certains langages son plus permissifs et acceptent que le var soit après et certains langages n’ont même pas besoin d’une initialisation de variable.
  • maVariable est bien du type bool. Car elle est utilisée dans un if.
  • Mon programme renvoi bien un entier. Un programme peut renvoyer soit un entier, soit rien.

Dans un code plus complexe, nous allons vérifier la portée des variables et des méthodes. A savoir est-ce que je peux accéder à ces variables dans la méthode ou je me trouve ?  Est-ce que j’ai accès à la méthode là où je me trouve ?

Après la phase d’analyse sémantique, notre compilateur ne générera plus aucune erreur sur le code écrit. Il restera la troisième phase du compilateur qui est la génération de code. Ainsi nous allons générer le code machine qui va exécuter notre code. C’est dans cette phase que le fichier exécutable va être écrit. A partir des deux analyses précédentes nous allons convertir notre arbre syntaxique en code machine interprétable par le compilateur. C’est pendant cette phase aussi que nous allons pouvoir ajouter des optimisations sur les instructions.