Tutoriel : Discussion sur le thème de la compilation et création d'un langage informatique

Je me présente, je m’appelle Charlie Lacroix, je suis ingénieur des Mines de Saint Etienne (cycle ISMIN), spécialisé dans l’informatique, la micro-électronique, et les nouvelles technologies. Malgré ma courte expérience professionnelle, j’ai tout de même eu l’occasion de pouvoir toucher à un domaine de l’informatique un peu exotique, qui me passionne : la création de langage informatique, et la création de compilateurs/interpréteurs.

Ce tutoriel a pour but de vous faire découvrir les problématiques relatives à ce sujet, c’est-à-dire, pourquoi créer un langage ? Quelle est la différence entre un compilateur, et un interpréteur ? ET quelle est la philosophie à avoir pour en créer.

Pour cela, je vais m’appuyer sur deux outils très puissants présents sur les plateformes Unix, Flex et Bison. Il est conseillé d’avoir de bonnes notions en langage C.

Je vous propose de construire un langage très basique, pouvant faire des opérations de bases. Il sera en mesure gérer des variables, les conditions, et des boucles de traitements. Créer un langage sans pouvoir l’utiliser est frustrant… Nous construirons donc un outil de vérification syntaxique pour notre langage, puis un interpréteur dans un second article, ce qui formera un joli environnement virtuel créé pour l’occasion. Soyons créatif, et créons ensemble le BML : le Be My (first) Language ! , avec l’extension .bml

Vous remarquerez que o créer de tels outils, nous allons nous heurter à des questions philosophiques… Créer le BML, c’est créer un dictionnaire de mots, et une grammaire. Ainsi, cela revient à se poser les questions suivantes pour définir la langue française : qu’est-ce qu’une phrase ? Un sujet ? Un complément d’objet ? Un groupe nominal peut-il être une partie d’un sujet ?

 

I.Contexte

1.Des langages de programmations, pourquoi ?

Pour rappel, Les langages de programmations sont des outils pour pouvoir piloter des processeurs, des microcontrôleurs afin de réaliser les tâches, des services que l’on souhaite. Ces langages servent de bases communes  à tous, pour décrire le fonctionnement d’un programme, ou bien d’un service (web), de façon plus ou moins proche du matériel. On parle alors de niveaux de langage. Plus un langage est dit bas, plus il sera dépendant de l’architecture du matériel (et peu compréhensible par l’homme). A l’inverse, un langage de haut niveau est beaucoup plus abordable par une personne, que pour un compilateur.

Je pense que je ne vous apprends pas grand-chose en vous rappelant ça, mais il est tout de même nécessaire de noter que le C, C++, le Java  (Le B, l’Ada, VHDL, Verilog, LIPS, Fortran, C#, …) existent pour s’adresser à des publics différents, car chacun a des besoins élémentaires différents.

Par exemple existe en partie pour prouver formellement la sécurité de logiciels, en s’appuyant sur une description mathématiques des systèmes. Les systèmes de contrôles ferroviaires sont par exemple modélisés en B, car il permet de justifier des taux d’erreurs et de défaillances inférieur à 0,0000001% !!! (…Merci les maths).

 

2.Rôles des compilateurs

Pour utiliser ces langages, il faut bien sur des outils pour que le matériel que l’on utilise (le processeur d’un ordinateur par exemple) puisse interpréter nos désirs. On utilise alors des compilateurs, ou bien des interpréteurs, suivant les langages. On peut citer par exemple les compilateurs Intel XE, ou bien gcc qui sont connus du public.

La différence entre un compilateur et un interpréteur est assez faible. En effet, un compilateur va prendre un langage d’entrée, afin de le convertir en langage machine, exécutable, alors qu’un interpréteur lui va construire un code intermédiaire, puis va interpréter ce bytecode en langage machine… De plus, la détection des erreurs ne se fait pas exactement au même endroit. C’est au moment de l’exécution que l’interpréteur indiquera la présence ou non d’erreurs. Le compilateur nous les donnera  avant de produire le code exécutable par la machine cible

Un compilateur (comme un interpréteur), doit faire plusieurs tâches avant de créer du code en langages machines. Tout d’abord, il doit vérifier la syntaxe des fichiers proposés en entrée. Y a-t-il les bons mots clefs aux bons endroits ? La grammaire est-elle respectée ? Y a-t-il bien la présence d’un axiome et quel est-il ? Comment doit-on parser toutes les données? Ne vous inquiétez pas, tous ces mots sont définis juste à la suite.

 

3.Vocabulaire

Dans la suite de l'article, on emploiera des termes spécifiques à la création de langage. Voici la définition des mots importants à connaître. 

Vocabulaire terminal ou les terminaux : ensemble de mots apparaissant dans le langage. Cette liste est souvent « figée », dans le sens où on repère des entités (comme les entiers et les caractères), ou bien des mots-clefs. Si l’on souhaite faire une comparaison avec la langue française, les terminaux correspondent aux mots inscrits dans le dictionnaire. Ainsi, « if » « for » et « int » font partie de l’ensemble des terminaux du langage C.

Non-terminaux : Ensembles des concepts du langage, définis les uns par rapport aux autres. Cet ensemble correspondrait en français à la définition de la grammaire, et les règles pour construire une phrase, le pluriel. Ainsi, un « groupe nominal » est défini par un « article », un « adjectif », un « nom », avec article, adjectif et nom eux-mêmes des non-terminaux.

Grammaire/Règles : Ensemble de règles qui définissent les non-terminaux grâce à des éléments des ensembles des terminaux et non terminaux. Ainsi,

« if( variable != 0) { expression ;} »
est une règle définissant les conditions en C, avec les terminaux repérés en gras, et les non-terminaux en italique.

Axiome : L’axiome est la règle à l’origine du langage. Ainsi, dire "un programme informatique est une succession d’instructions" est un axiome. De même, « le départ d’un livre est la première page d’un livre après la première de couverture » est aussi un axiome pour définir la façon de lire un roman.

Parseur : Outil/programme servant à découper un flux d’entrée en séquences de mots, d’arguments connus. Par exemple, un correcteur orthographique contient un parseur, afin de repérer les verbes des pronoms, des noms.

Parsing / Parsage : Utilisation d’un parseur afin de découper un flux d’entrée.

Token : Un token est une expression particulière repérée par un parseur, et utilisée par un analyseur syntaxique. Cela peut être un terminal, comme un non-terminal.

Expression régulière ou Regex : écriture compacte afin de représenter un groupe potentiellement infini de caractères. Il serait un peu long de faire un rappel sur les Regex et leurs créations, et il existe de très bons tutoriels sur le net pour les comprendre. Je traduirai (« en français ») les quelques expressions régulières afin que tout le monde puisse profiter du tutoriel.

 

4.Présentation de Flex et Bison

Flex et Bison sont deux outils qui vont nous être utiles pour créer notre environnement pour interpréter le BML. Voici une description très courte des deux outils.

Flex

Flex (Fast Lexical analyzer generator) permet de faire du parsage (d’un fichier par exemple) en reconnaissant des mots terminaux, et des non-terminaux à l’aide d’expressions régulières. On pourra donc facilement donner et décrire tous les éléments du langage à l’aide de ce fichier.

Cet outil est un dérivé de Lex, un autre outil UNIX, mais présente plus de fonctionnalités. Une des forces de Flex est la gestion des entrées multiples à parser. Ainsi, cela peut permettre d’implémenter l’inclusion de librairies au sein d’autres fichiers à étudier. Par ailleurs, il permet de faire de l’étude conditionnel de fichiers: on peut définir des états au sein de la recherche de caractères, mais nous n’utiliserons pas ces fonctionnalités dans ce tutoriel pour ne pas trop le compliquer pour rien.

Flex est donc utile, pour traiter des flux similaire, et de repérer les élements importants. On peut par exemple traiter les JSON uniquement avec Flex (en C bien sur)

Bison

Bison est un parseur de grammaire, venant d’un projet GNU, destiné à remplacer Yet An other Compiler Compiler (YACC). Comme YACC, cet outil a pour but de créer des automates à états finis à partir d’un ensemble de règles données, et d’un axiome. Une analyse descendante Look-Ahead, Left to Right, Rightmost Derivation (LALR) est exécutée sur la cible voulue. Pour faire simple, cette analyse consiste à examiner le texte de gauche à droite, en cherchant les points de grammaire correspondants aux règles décrites dans un fichier particulier. Dès qu’un terminal est détecté, on cherche si on peut dériver vers une règle plus précise, afin de détecter exactement quelle action doit être faite. 

Par exemple, si l’axiome de notre langage est : « un programme est une liste d’instructions », et que « Une instruction est soit une déclaration de variable, soit une condition commençant par un « if » », on dit qu’il y aura dérivation vers la règle condition, si lors du parsage, on est dans la présence d’un if. A ce moment-là, la règle if sera examinée en détails, afin de la réduire en un élément compréhensible par une autre règle.

On voit donc, que toute la partie analyse de la syntaxe va être gérée grâce à Flex et Bison. L’analyse des fichiers BML devra permettre d’écrire un bytecode, que seul notre interpréteur de langage pourra comprendre. On retrouvera donc une création d’instructions élémentaires après certaines règles de grammaires. Ces instructions élémentaires seront traitées par l’interpréteur. Cette phase sera faite grâce à un petit automate fait en C (assez simple).

Je vous propose de suivre l'architecture liée en .jpg avec l'article. Ce schéma explicite les programmes que nous allons créer, ainsi que les outils nécessaires pour les réaliser.

Remarque : il est évident que la génération du bytecode conditionne votre façon de traiter les informations dans votre interpréteur. Il est donc plus que nécessaire de toujours savoir l’ordre des paramètres que l’on écrit, et quels vont être les traitements que l’on souhaite faire. Il est nécessaire d’être rigoureux dans l’écriture du bytecode et dans son traitement, pour garantir un fonctionnement du BML comme l’on souhaite. Je proposerai donc une implémentation possible dans un prochain article, mais après, libre à vous de gérer autrement vos opérations.

 

II.Création de la partie analyse de la syntaxe

Flex sert à décrire les terminaux et non terminaux à détecter, pour pouvoir distribuer des tokens à Bison, qui seront les piliers des règles de grammaires. Nous allons dans un premier temps, écrire le fichier Lex, puis les règles de grammaires qui s’appuieront sur les Tokens fournis par Flex

Remarque : Les extensions qui sont couramment utilisées par Flex et Bison sont les .l, .y . Toutes les sources sont dans le .zip fourni avec l'article, ainsi que le makefile. Je vous conseille de les avoir proche de vous par la suite.

 

1.Création du fichier Flex

Commençons par définir les éléments que nous allons traiter. Pour faire nos opérations (sur un type de variable),  nous allons devoir repérer deux types de noms terminaux : les entiers qui seront composées que de nombres; et les variables qui seront un ensemble de lettres, de chiffres, et aussi d’underscore.

Les expressions régulières pour ces deux groupes sont les suivantes :

ENTIER : [0-9]+ qui se lit : « Le groupe constitué des caractères 0 à 9, répété au moins une fois »

LETTRES_VARIABLES : (([a-zA-Z_]+)([0-9]+) ?)+ qui se lit : « Le groupe composé de caractères entre les lettres a et z, ou A et Z ou le caractère underscore répété au moins une fois . Il peut y avoir un groupe de nombre composés de chiffres entre 0 et 9. Ce groupe doit apparaitre après un groupe de lettres. Enfin, tout cet ensemble est répétable une ou plusieurs fois».

COMMENTAIRE : #[^\n]*\n qui se lit : « Le groupe composé d’un #, puis suivi de tout caractère qui n’est pas une fin de ligne, et qui se termine par une fin de ligne ». Je suis en train de déclarer des commentaires ressemblant au VHDL, des makefile, ou encore ressemblant au « // » du C++. Un commentaire commencera dès l’apparition d’un dièse, et finira à la fin de la ligne.

On peut voir, que j’ai fait un choix pour reconnaitre les variables. J’ai choisi d’imposer à nos utilisateurs du BML, que toutes les variables commenceront par une lettre. « 9Variables » ne sera pas valide comme nom de variable, alors que « a_9_a » est valide. Il suffira de changer l’expression régulière de LETTRES_VARIABLES pour changer le choix que l’on a fait.

Pour faire des boucles, et des conditions, nous pouvons utiliser les terminaux« while, endwhile, if, else, endif ». Voici le Flex correspondant à la détection de ces mots, ainsi que des parenthèses, et des accolades.

On peut remarquer quatre grandes zones dans le fichier.

  • La première entre %{ }% est une partie qui permet d’inclure du code nécessaire pour effectuer des actions dès que l’on repère un terminal, ou un non terminal. On peut aussi déclarer des fonctions, des variables utiles. C’est ainsi que l’on déclare une variable pour compter les caractères et les lignes parcourues.
  • Juste après, on peut voir deux lignes, qui définissent des macros d’expressions régulières. Elles servent à simplifier de grandes expressions régulières, cf. la définition de LETTRES_VARIABLES.
  • L’espace entre %% contient tous les terminaux et non terminaux à reconnaitre. Sur chaque ligne, on donne l’expression a reconnaitre (regex, ou mots clefs), puis entre accolades, les actions à faire par la suite.

Dans notre exemple, je compte le nombre de caractères, et envoie des tokens qui seront connus dans le Bison (on verra cela un peu plus tard). Nous avons la possibilité, en plus d’envoyer un token, lui donner un type, et une valeur. La variable yylval est une union (en termes de structure du langage C) que l’on peut spécifier dans Bison. Pour récupérer le contenu d’une regex, on peut utiliser la variable prédéfinie yytext. Je m’en sers ici, pour convertir les nombres, et renseigner la valeur à traiter dans les tokens que Bison traitera.

  • Un autre espace nous permet d’inclure des fonctions utilisables lors de la phase de parsage du fichier BML, en dessous du %%. On ne l’utilise pas ici.

Remarque : je n’ai pas détaillé deux règles de ce fichier : [ \t], « . » .

La première règle me permet de trouver tous les espaces blancs dans un fichier, et de ne pas les prendre en compte. Cela permet par exemple, de ne pas avoir à se soucier de fautes de frappes, avec trop d’insertion d’espace. La règle « . » est la règle par défaut de Flex. Que faire, si, lors du parsage, Flex tombe sur aucun des terminaux décrits ? Dans notre cas, on ne fait rien.

Le fichier flex_bml.l contient toute la description du langage BML. On y retrouve tous les terminaux, comme les non terminaux définis en introduction. Maintenant que l’on sait quoi trouver, il nous faut encore donner la grammaire,et donner l’ordre des actions qui sont possible. Nous allons maintenant utiliser Bison pour cette partie !

 

2.Création des règles de grammaire avec Bison

La structure d’un fichier Bison est assez similaire au Flex. On peut suggérer des librairies, spécifier des headers, et des variables à utiliser grâce aux partie enter « %{ »   « %} ».

Les options spécifiques à Bison sont à définir avec des %. Ainsi, pour définir des token, il suffit d’écrire « %token MON_TOKEN_A_RECONNAIRE ». Les noms de ces tokens doivent être identiques à ceux utilisés dans le Flex.

La partie de la définition de la grammaire sera entre %% et %%. A la suite, nous pouvons encore décrire des fonctions. C’est ici que nous spécifierons le main de notre analyseur de syntaxe, ainsi qu’une fonction pour signaler les erreurs. Bison possède une fonction yyerror(), mais n'est pas du tout explicite : Elle indique seulement "syntax error", sans donner d'informations complémentaires (numéro de ligne, fichier...)

Par défaut, la première règle sera considérée comme axiome de la grammaire. Pour éviter toute ambiguïté, il est aussi possible de la donner explicitement grâce à %start MA_REGLE_AXIOME

Une règle de grammaire peut être composée de non terminaux, de terminaux, mais aussi de règles de grammaires. L’inclusion de ces règles permet de faire de la récursivité.

Par exemple, une définition de la notion d’instruction pourrait être une opération, une condition, ou bien une déclaration de variables. Dans une condition, on retrouve aussi la notion de test, puis une séquence d’instructions définie en amont.

 

Pour déclarer la règle qui caractérise une liste de plusieurs instructions, on peut utiliser cette implémentation :

Liste_instruction : liste_instruction  instruction| /*empty*/ ;

Remarque : | = ou en Bison

Ainsi, par récursivité, une lite d’instruction peut être vide, d’une voir N instructions. Lorsque vous utilisez des règles avec de la récursivité, il est fortement conseillé de n’utiliser que la récursivité à gauche, comme sur l’exemple ci-dessus. En effet, on peut demander l’exécution de code C après avoir reconnu un élément d’une règle. Dans ce cas, il est nécessaire d’attendre le dernier élément pour pouvoir traiter TOUTE la liste d’instruction… Ce qui peut parfois être gênant.

 

Analysons comment créer le cœur de notre langage primaire : les opérations. Créer des opérations est à la fois simple, mais utilise toutes les notions présentées ci-dessus. Une opération se compose de trois choses. Un opérateur (‘+’ par exemple), et de deux opérandes.

Quelles peuvent être la nature de ces opérandes ? On pourra avoir des entiers (1+1), des variables (cpt = cpt+1), mais aussi d’autres expressions plus complexes (A = ((3+2)*2)+1 ).

Nous avons aussi une notion de prioritée à étudier. En effet,  est-ce que le + est à détecter et à executer avant ou après le * ?

Nous composerons de quatre règles la grammaire des opérations. J’ai choisi de définir les primaires, qui est en fait la définition des opérandes.

Par la suite, je crée la notion de terme, ou les opérations * et / sont définis. On cherchera ainsi les opérations * et / à traiter avant les autres. Dans la construction de terme, on peut voir que j’utilise sa propre définition pour permettre des opérations plus complexes. Dans le cas d’instructions ne contenant pas de multiplication ou de division, il faut tout de même définir qu’un terme peut être seulement un primaire, d’où l’apparition de « | primaire » à la fin de la définition de terme.

Je crée ensuite une règle expression, qui cette fois prend en compte les opérations d’addition et de soustraction. Pour la même raison, je crée un lien directe entre expression et terme, pour prendre en compte les opérations sans addition ni soustraction (A = 1*2).

Enfin, il nous reste à prendre en compte le teste de condition, c’est pourquoi je définis les expression_finale, de façon semblable à terme et expressions.

 

3.Compilation

Maintenant que tous nos fichiers détaillent les terminaux et non terminaux à repérer et les enchaînements possibles, il nous reste encore à construire les cibles pour la compilation.

Pour cela, nous allons utiliser le makefile suivant. Flex par défaut, crée un fichier BLA.yy.c, et Bison crée deux fichiers : BLA_BML.tab.c, et BLA_BML.tab.h . Ces fichiers constituent notre machine d’états finis, ainsi que la définition de tous les tokens. Nous devons inclure dans le BLA.yy.c e BLA_BML.tab.h car Flex a besoin de connaitre la définition des tokens à renvoyer. Je vous laisse aller regarder les retours des mots à reconnaitre.

Nous compilons le tous en deux .o, pour créer les objets fait à partir des Flex et Bison, puis notre exécutable. Dans le makefile que je fournis, il suffit de faire un « make » ou « make default » pour tout compiler.

Pour tester notre langage, il suffit de lancer le syntaxe_bml, puis d’écrire à la console ce que l’on souhaite. On peut remarquer que toutes les règles sont détectées, mais nous n’avons pas de création de bytecode. Par contre, dès que l’on fait une erreur de syntaxe, elle est détectée. Je finis mon programme BML par un point en fin de fichier, pour pouvoir contrôler cette fin (il y a d’autres methodes). Pour simuler un EOF (end of file), qui arrête Flex de parser depuis le terminal, il faut appuyer sur Ctrl + D (sur Windows et Linux). Si on souhaitefournir unfichier en entrée à notre analyseur de syntaxe, on peut utiliser le pipe : « ./syntaxe_bml < mon_fichier », car nous ne traitons pas encore les arguments dans le main… Mais cela ne tardera pas.

 

III.Conclusion de cette première partie

En conclusion, nous avons eu un premier contact avec de puissants outils qui sont Bison et Flex. Il est aussi possible d’utiliser d’autres outils comme SableCC (sous license LGPL), qui propose de faire tout cela en Java. Nous avons pu construire un programme qui analyse toutes les règles de grammaires, mais nous n’avons pas vu comment donner un sens, comment écrire du bytecode suite à la reconnaissance d’instructions BML. Nous aborderons cette problématique la prochaine fois, en même temps que nous construirons l’interpréteur, car ces deux parties sont extrêmement liées.

En tout cas, j’espère que vous avez apprécié ce premier contact avec les manières de concevoir un langage, et les problématiques qui y sont liées.

 

Para obtener información más completa sobre las optimizaciones del compilador, consulte nuestro Aviso de optimización.