Réalisation d'un compilateur (partie 1)

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

Réalisation d’un compilateur de pascal simplifié en C++

Introduction : Pourquoi réaliser un compilateur ?

Tout développeur est amené à utiliser un compilateur. Toutefois peu sont ceux qui savent réellement comment fonctionne celui-ci. Cet article et les suivants sont donc là, d’une part pour présenter les différentes étapes de compilation, et d’autre part pour expliquer comment créer un programme qui réalisera l’ensemble de ces étapes.

Qu’est-ce qu’un compilateur ?

Avant la venue des langages de programmation, les programmeurs devaient connaître par cœur l’architecture de la machine sur laquelle ils travaillaient, et parler directement à celle-ci à l’aide d’un langage binaire. Très rapidement, a été inventé un langage utilisant des raccourcis textuels : l’assembleur.

Ce nouveau langage présentait plusieurs avantages: tout d’abord, il était plus facile de lire du texte utilisant des mots sensés, mais surtout une vérification basique était faite lors d’une erreur de saisie. Toutefois ce langage avait de nombreux défauts. Il imposait peu de contrainte au développeur, ce qui pouvait être avantageux, mais était peu pratique pour la productivité et la robustesse du code. La vérification de type n’existant pas, de nombreux bugs en découlaient, et ceux-ci étaient particulièrement difficiles à détecter.

Enfin, le niveau d’abstraction était faible, le langage étant très proche du langage machine. Pour palier à cela, les langages de programmation dit de haut niveau ont été inventés. La principale caractéristique de ceux-ci était un niveau d’abstraction élevé. C’est à dire que le langage ressemblait plus à un langage humain qu’à des instructions machines. Ainsi, la programmation devenait moins ésotérique, et il était plus facile pour un néophyte de se lancer dans l’apprentissage de ce domaine. De plus, ces langages imposaient des contraintes fictives, comme un typage fort des données, qui permettait une meilleure robustesse, ou encore la prise en charge automatique de certains concepts.

Par exemple en Pascal, il est possible de concaténer deux chaînes de caractères à l’aide de l’opérateur +. En assembleur, il aurait fallu allouer de la mémoire pour la nouvelle chaîne, et recopier un à un chacun des caractères de ces deux chaînes. L’avantage d’un compilateur est indéniable, et mis à part dans quelques domaines spécifiques, la très grande majorité des développeurs ne programme pas en assembleur. Beaucoup de programmeurs n’en ont même jamais vu !

Comment fonctionne un compilateur ?

Il y a de nombreux compilateurs. Le fonctionnement de ceux-ci étant propre à un langage, nous n’allons bien évidemment pas tous les passer en revue. Au lieu de cela, nous allons définir à quoi devra ressembler notre langage. À partir de là, nous établirons ce que notre compilateur sera capable de réaliser.

Le langage

Réaliser un compilateur est extrêmement long et peut être particulièrement difficile. Le but de ce projet étant de réaliser un compilateur basique dans un temps acceptable, nous allons utiliser un langage très simple. Le langage choisi aura une syntaxe proche du Pascal.

Définissons maintenant ce que le langage sera capable de faire. Tout d’abord, celui-ci sera typé, c’est-à-dire qu’une variable ne pourra contenir qu’une valeur d’un type compatible. Trois types de bases seront suffisants: entier, booléen, et chaînes de caractères.

Les fonctions et la récursivité, en plus d’être pratique, sont pédagogiquement très intéressantes à mettre en place. Incluons-les, ainsi que le mot clé return, qui permettra de quitter une fonction en renvoyant une valeur. Une fonction sera obligée de renvoyer quelque chose. La présence de fonction implique donc que la portée des variables devient nécessaire. Une variable pourra donc être locale ou globale.

Un langage sans structures de contrôle ne serait pas très intéressant, ajoutons donc la possibilité de faire un choix (if), et de réaliser une opération en boucle (while).

Enfin, dans un souci de simplification, il n’y aura pas d’ambiguïtés sur l’évaluation d’une expression puisqu’on forcera l’utilisateur à mettre des parenthèses de manière explicite, ce qui évite tous soucis de priorités. Nous ne traiterons pas les notions plus compliquées, comme les tableaux, la gestion de la mémoire, les pointeurs ou encore la notions d’objet.

Pour finir, incluons trois builtins, c’est-à-dire trois fonctions préexistantes, read, print et exit, qui permettront respectivement de récupérer une information entrée par l’utilisateur, d’afficher une valeur à l’écran et de quitter le programme avant la fin de son exécution.

Un exemple d’un programme qui demande une valeur à l’utilisateur et affiche la factorielle de celle-ci:

var a : integer;
var s : string;

function facto (nb : integer) : integer;
var res : integer;
begin
   if nb <= 1 then
   begin
      return 1;
   end
   res = nb * facto(nb - 1);
   return res;
end

begin
   print("Entrez un nombre : ");
   read(a);
   res = facto(a);
   s = "La factorielle de ";
   print(s);
   print(a);
   print(" est ");
   print(res);
   print("n");
   exit(0);
   print("Ignore");
end

La grammaire du langage

Maintenant que nous sommes fixés sur les fonctionnalités de notre langage, écrivons en la grammaire. Il faut savoir que tout langage de programmation, tout comme un véritable langage, possède des règles d’écriture. On ne peut pas écrire n’importe quoi, l’ordre des mots du langage à une importance. C’est là qu’intervient cette fameuse grammaire. Elle permet de spécifier de manière claire et exhaustive, comment agencer les mots du langage entre eux. Il est d’usage lors de son écriture, d’utiliser un formalisme universel. Celui que l’on utilisera sera la notation BNF (Backus-Naur Form).

Si vous n’avez pas de connaissance dans le domaine de la théorie des langages, il y a de forte chance que la lecture de cette grammaire soit un peu compliquée. Voici donc quelques règles basiques pour en comprendre le sens:

  • Un terminal est un mot du langage existant, et qui comme son nom l’indique, ne renvoie pas vers une autre règle.
  • Un non terminal est une règle, qui n’est pas présente explicitement dans le langage, et qui est la composée d’autre règles. On l’entoure des signes < et

    pour la différencier des terminaux.

  • Une règle est précédée par le signe ::= qui indique comment est constitué celle-ci.
  • Le | représente un OU, c’est-à-dire un choix entre plusieurs règles. Une règle ou un terminal entre [ et ] veut dire que cet élément est facultatif.

Un petit exemple pour illustrer cela avec la règle de grammaire d’un if en C++:

<if> ::= if ( <expression> ) { <expression> } [ else { <expression>} ]

que l’on pourrait aussi écrire:

<if> ::= if ( <expression> ) { <expression> }
       | if ( <expression> ) { <expression> } else { <expression>}

Voici donc celle de notre langage:

<program> ::= [<declarations>] [<funcs>] [<compound_instruction>]
<declarations> := <declaration>
                | <declaration> <declarations>

<declaration> ::= var <declaration_body> ;

<declaration_body> ::= <ids> : <type>

<ids> ::= <id>
        | <id> , <ids>

<funcs> ::= <func>
          | <func> <funcs>

<func> ::= <header_func> <compound_instruction>
         | <header_func> <declarations> <compound_instruction>

<header_func> ::= function <idfunc> ( [<arguments>] ) : <type> ;

<arguments> ::= <argument>
              | <argument> ; <arguments>

<argument> ::= <declaration_body>
             | <declaration_body> ; <argument>

<compound_instruction> ::= begin end
                         | begin <instructions> <end>

<instructions> ::= <instruction>
                 | <instruction> <instructions>

<instruction> ::= <affect> ;
                | <call_func> ;
                | <compound_instruction>
                | <if>
                | <while>
                | <return> ;
                | <exit> ;
                | <builtin_print> ;
                | <builtin_read> ;

<affect> ::= <id> = <expression>

<return> ::= return <expression>
<exit> ::= exit <expression>

<builtin_print> ::= print ( <expression> )

<builtin_read> ::= read ( <id> )

<if> ::= if <expression> then <compound_instruction>
       | if <expression> then <compound_instruction> else <compound_instruction>

<while> ::= while <cond> do <compound_instruction>

<call_func> ::= <idfunc> ( )
              | <idfunc> ( <expressions> )

<expressions> ::= <expression>
                | <expression>, <expressions>

<expression> ::= <operation>
/* Ce noeud peut paraitre inutile, mais il est present pour une future extension
   du langage, que je ne presenterais pas dans cet article */

<operation> ::= <factor> <symb> <factor>
                | <factor>   /* operation sans facteur droit */
                | - <factor> /* facteur gauche = 0 */

<factor> ::= <id>
           | <call_func>
           | <number>
           | <stringexpr>
           | <boolean>
           | ( <expression> )

<id> ::= [a-zA-Z]([a-zA-Z0-9_]*[a-zA-Z0-9])?
<type> ::= integer | string | boolean
<symb> ::= > | < | >= | <= | != | == | + | - | * | / | %
<number> ::= [0-9]+
<stringexpr> ::= .*
<boolean> ::= true | false

Les différentes étapes de la compilation

Lorsqu’une compilation est lancée, plusieurs étapes se succèdent pour mener à la création d’un exécutable. Tout d’abord la majorité de ces étapes servent à vérifier la cohérence du code écrit. Voici une présentation non exhaustive des différentes étapes que nous allons réaliser. Les détails techniques seront abordés lors de prochains articles dédiés à chaque fois à une phase précise.

La première étape, appelée “lexing” consiste en la lecture du fichier, et la récupération de tokens. Un token est le plus petit morceau atomique définit dans une grammaire. Si l’on prend une analogie avec la langue française, un token représenterait un mot. Donc la phrase suivante: “Bonjour à tous” serait considérée comme valide, tandis que: “Bonjour xvcfbjnb tous” provoquerait une erreur de lexing. En effet, le mot Bonjour et le mot tous, sont bien présent dans le dictionnaire français, mais le mot xvcfbjnb, lui, ne l’est pas. Cette étape va donc vérifier que certains mots impossibles ne soient pas présents dans le code source. Pour provoquer une erreur de lexing dans notre langage, on pourrait écrire : if @@ then. Le mot @@ n’étant pas un token acceptable, le code est considéré comme non valide.

La seconde étape, appelée “parsing”, va, à partir des tokens précédemment récupérés, vérifier que l’agencement soit correct. En effet, ce n’est pas parce que l’on n’a détecté aucun token invalide, que ceux-ci sont forcément dans le bon ordre. Reprenons une analogie avec la langue de Molière. Si je vous dis: “Bonjour, ça va ?” vous devriez me comprendre, tandis qu’avec “va ? ça, Bonjour” la communication serait quelque peu compliquée. Eh bien avec notre langage, c’est la même chose. Si l’utilisateur entre “if then true if if”, alors nous sommes bien en présence d’une erreur de parsing. L’agencement de chacun de ces tokens, ne respectent pas la grammaire que nous avons définit.

L’étape suivante est appelée “binding”. Ici on va vérifier que chacune des variables et fonctions soient correctement reliées entre leurs déclarations et leurs appels. Pour résumer, cette phase se contente de détecter qu’une variable ou une fonction soit bien déclarée une et une seule fois.

Exemple:

var a : integer;
begin
  b = 50;
end

Ici on voit bien que la variable b, n’est pas déclarée. Donc le compilateur doit prévenir l’utilisateur, et refuser de créer un exécutable.

De même:

var b : integer;
var b : integer;
begin
  b = 50;
end

Ici la variable b est définit deux fois, donc c’est aussi une erreur de “binding”. La même vérification est appliquée sur les fonctions, en prenant aussi en compte que le nombre d’argument décrit, et le nombre d’argument réellement passé, corresponde.

Enfin la dernière étape de vérification, est celle appelé “type checking”. Celle-ci vérifie que le typage des expressions est correct et que chaque variable reçoit une valeur dont le type est compatible.

Par exemple:

var b : integer;
begin
  b = 50;
end

Ici b, qui est de type entier recevra une valeur entière, donc la compatibilité est assurée, il n’y a pas d’erreur.

Tandis que dans l’exemple suivant:

var b : integer;
begin
  b = "coucou";
end

La variable b qui est de type entier, reçoit une chaîne de caractère. Ce n’est évidemment pas possible, et c’est ce type de problème qui provoquera une erreur de type checking.

Conclusion

Une fois toutes ces étapes validées, on considère notre code source comme étant valide. Il ne reste alors qu’à l’interpréter, ou à le convertir en assembleur. Ces deux étapes seront détaillées plus tard. Ici se termine ce premier article. J’espère que cette première approche vous aura donné envie d’aller un peu plus loin dans la compréhension de la compilation. Les articles suivant seront un peu plus techniques.