25

Flex et Bison

mar
No Comments |  Posted by Etienne SOBOLE |  Category:Divers Infos

Bien qu’il existe des outils un peu plus modernes aujourd’hui pour réaliser un parser de code, le duo Flex et Bison (versions “modernes” de Lex et Yacc) reste la référence. Des milliers de langages reposent sur l’analyseur lexical Flex et l’analyseur syntaxique Bison. L’apprentissage de ces outils n’est pas forcement des plus simples. Pourtant, comme souvent, une fois qu’on sait faire, c’est relativement simple.
On trouve quelques tutoriaux sur internet pour expliquer l’utilisation de ces outils. Avec ce post, ça en fera un de plus. On ira par contre un peu plus loin que le traditionnelle calculatrice.

Introduction

Généralités

Flex et Bison sont des outils qui aident grandement à la réalisation d’un compilateur.
Mais attention… Comme j’ai déjà eu l’occasion de le dire :

Un compilateur est un programme informatique qui transforme
un code source écrit dans un langage de programmation (le langage source)
en un autre langage informatique (le langage cible).

Cela veut dire entre autre qu’un compilateur ne génère pas forcément un programme exécutable par un ordinateur. Dans mon cas, je cherche a convertir du PHP en C++ ce qui entre totalement dans la définition données ci-dessus.

Avant d’aller plus avant dans le compréhension de Flex et de Bison, il y a quelques points qu’il vaut mieux comprendre et assimiler tout de suite concernant ces outils.

  • Flex, tout comme Bison génèrent un fichier C que vous allez compiler puis linker avec le code de votre compilateur. Ces commandes ne s’appliquent pas sur le code source que vous cherchez à traiter.
  • Aucune des deux commandes ne doit être exécutée avant l’autre. Les deux programmes ne sont pas dépendant l’un de l’autre, même si au final vous ne pouvez guère utiliser l’un sans l’autre.
  • On imagine souvent à tord qu’on doivent d’abord utilise Flex puis Bison sous prétexte que l’analyse lexicale arrive en amont de l’analyse syntaxique, mais non !

Il vaut mieux bien comprendre ce que j’ai écrit ci-dessus. Cela vous évitera quelques arrachage de cheveux par la suite. En gros Flex et Bison écrivent à votre place des fonctions C dont le but est d’analyser le code source fourni au compilateur.

Fonctionnement de Flex et de Bison

Bon a quoi ça sert alors?

Essayons d’imaginer ce que va faire notre compilateur.
Notre compilateur va ouvrir un fichier source (dans mon cas, un fichier PHP) puis envoyer les caractères 1 à 1 au code C produit par Flex.
Ce code va accumuler les caractères reçu jusqu’à ce qu’une suite de caractères corresponde à un lexème (ou token en anglais).

C’est quoi un lexème ?
Un lexème c’est un mot (parfois ne faisant qu’un seul caractère) qui représente quelques chose pour notre langage.
Par exemple

  • $ma_variable représente une variable PHP
  • 125 représente un entier
  • { représente le début d’un bloc en PHP
  • Par contre 45xy ne représente rien pour le PHP. Si un tel lexème est trouvé, il faudra gérer l’erreur produite.

Donc Flex accumule les caractères jusqu’à ce qu’il trouve un lexème (ou qu’il arrive à une contradiction (une erreur quoi)) puis envoie un identifiant de lexème (ainsi que la valeur du lexème généralement) au code C produit par Bison
Ce dernier (le code produit par Bison) lui aussi accumule les lexèmes jusqu’à ce qu’un ensemble corresponde à une des règles qui régissent le langage.

Par exemple, supposons que le code produit par Flex envoie au code produit par Bison les lexèmes suivants

1 – Lexème VARIABLE ayant pour valeur $value
2 – Lexème EGALITE ayant pour valeur =
3 – Lexème NOMBRE ayant pour valeur 156
4 – Lexème POINTVIRGULE ayant pour valeur ;

A l’arrivée du 4éme Lexème, Le code produit par Bison se rend compte qu’il existe une règle…

VARIABLE EGALITE NOMBRE POINTVIRGULE

…qui veut dire qu’il a reconnu que…

$a = 156;

…est une instruction.

Dès lors, Bison éxécute un code que vous aurez fourni sensé savoir quoi faire avec les 4 lexèmes.

  • Si vous voulez faire un interpreteur PHP vous allez simuler cette instruction.
  • Si vous voulez faire un compilateur vous allez transformer ce comme en pseudo instruction assembleur.
  • Si vous voulez faire un convertisseur PHP vers C++ vous allez générer l’équivalent en C++ de l’instruction.

Bon c’est un petit peu idyllique raconté comme ça. En vrai c’est un peu plus compliqué, et il ne va pas être possible de traiter les instructions une par une. Je voulais juste expliquer ou s’arrête le travail de Flex et de Bison. Une fois les lexèmes et les règles d’association de ces lexèmes définies, le travail suivant sera pour vous.

Arbre syntaxique abstrait

C’est à ce moment qu’entre en jeu les Arbres Syntaxiques Abstraits.

Un arbre syntaxique abstrait est un arbre binaire dont

  • les nœuds représentent les opérations
  • les feuilles représentent les variables ou les valeurs

Parfois un dessin vaut mieux qu’un long discours.
J’ai piqué l’image ci-dessous sur le site gengis.scann.free.fr.
Elle monte la représentation dans l’arbre syntaxique de l’instruction : Y = (A * X) + B

Nous allons essayer de convertir chaque instruction de notre code source en arbre syntaxique, avant de le convertir au final dans le langage destination de notre compilateur.

De l’ASA à l’ARM

C’est bien sympa ces arbres, mais à quoi cela peut-il bien servir de convertir nos instruction en arbres ?

Il est vrai que de prime abord, on est en droit de se demander à quoi peut bien servir cette conversion !

En fait c’est très utile…
Prenons par exemple le noeud Multip dans l’image ci-dessus. Il représente la multiplication entre la variable A et la variable X.
Imaginons à présent que nous souhaitions convertir ce noeud en assembleur (ARM par exemple). Un tel noeud serait équivalent à l’instruction

	mul	r10, r1, r2

où r1 = A et r2 = X
r10 étant un registre temporaire.

Le Noeud parent Addition pourrait alors être converti en

	add	r11, r10, r3

où r3 = B
r11 est lui aussi un registre temporaire.

Enfin le Noeud Affectation serait converti en

	mov	r4, r11

où r4 = Y

la compilation (en assembleur) de notre arbre donnerait donc au final le code suivant

	mul	r10, r1, r2
	add	r11, r10, r3
	mov	r4, r11

Le premier (mais pas le seul) intérêt de l’arbre syntaxique abstrait est qu’il décompose les instructions en sous instructions plus simples plus facile à transformer en code assembleur.

Remarque : Ce code n’est pas optimal, et le compilateur appliquerai sur ce code une phase d’optimisation pour réduire le nombre d’instruction et le nombre de registre utilisé, mais c’est un peu Hors sujet ici.

Remarque : L’arbre syntaxique abstrait décompose tellement les instructions qu’il va parfois trop loin. Par exemple dans l’ARM il existe une instruction MLA qui réalise en use seule opération le calcul Y = A * X + B. Malheureusement, il n’est pas trivial de se rendre compte que l’on aurai pu utiliser cette instruction. Il repose donc sur l’optimiseur de code de corriger le problème.

Autres intérêts des Arbres Syntaxique Abstraits

Notre compilateur n’a pas vocation à produire de l’assembleur alors les arbres sont-ils utiles dans notre cas ?

La réponse est OUI.

Ils sont utiles car d’une part leur production prouve que les instructions que l’on a décodée sont valides.
En clair, si on arrive à produire l’arbre alors il n’y a pas d’erreur de syntaxe.

D’autre part, La production du code de destination sera plus aisé en partant de l’arbre surtout en ce qui concerne les différence entre langage.

Par exemple convertir

if ($a === $b)

en

if (test_type_equal($a, $b))

sera plus facile en partant d’un arbre qu’en utilisant une simple expression régulière (par exemple).

Implémentation

On a assez défriché le terrain comme ça.
Place au code !

Pour commencer intéressons nous au code suivant.

$my_var = 154 + 9;
$other_var = 2 + $my_var * 3;

On va le parser, l’analyser, et le convertir en arbres syntaxiques abstraits.
Ensuite on réalisera une petite fonction pour afficher nos arbres (histoire de voir a quoi ça ressemble)
Enfin on produira à partir de
s arbres du code C++ !

Flex

Notre analyseur lexical doit être capable de reconnaître les lexèmes suivants

  • Les variables : \$[_a-zA-Z][_a-zA-Z0-9]*
  • Les entiers : 0|[1-9][0-9]*
  • Les caractères = + – * / et ; qui sont a eux seuls des lexèmes

On n’a rien besoin de plus pour le moment.

Le ficher que l’on va fournir à la commande flex s’appelle ebola.l.
Il est composé de plusieurs 3 parties qui sont séparées par %%

La première partie du fichier sera purement et simplement copié dans le fichier C que Flex va produire

%{
	#include <string>

	#include "asaNode.h"
	#include "ebola.tab.hpp"

	int yyerror(std::string);
%}

On inclue <string> car on va utiliser des std::string pour conserver les valeur de lexèmes.

asaNode.h contient la déclaration des objets utilisés pour la construction des arbres syntaxique abstraits. Son inclusion est nécessaire à cause du paramétrage que l’on va faire dans Bison. En gros sans cette, ligne Flex fonctionnera, mais au linkage vous aurez une erreur sans cette inclusion.

ebola.tab.hpp va être produit par Bison.

La deuxième partie du fichier contient la déclaration des règles de détection des lexèmes

%option noyywrap
%option yylineno

integer			0|[1-9][0-9]*
variable			\$[_a-zA-Z][_a-zA-Z0-9]*

%%
";"							{ return(yytext[0]); }
"="							{ return(yytext[0]); }
"+"							{ return(yytext[0]); }
"-"							{ return(yytext[0]); }
"*"							{ return(yytext[0]); }
"/"							{ return(yytext[0]); }

{integer}					{
									yylval.string = new std::string(yytext, yyleng);
									return(INTEGER);
								}
{variable}					{
									yylval.string = new std::string(yytext, yyleng);
									return(VARIABLE);
								}
[ \t]+						{ /* Do Nothing */ }
\n								{ /* Do Nothing */ }

.								{ /* Tout autre caractère sera considéré comme une erreur */
									yyerror(std::string("Error"));
								}
%%

%option noyywrap évite d’appeler une fonction en fin de traitement.
%option yylineno active un compteur de ligne. A chaque détection du caractère \n cette variable est incrémentée.

Lorsqu’on détecte un entier ou une variable on la recopie la chaîne dans yylval.string avant de retourner un “ID ” permettant à Bison de savoir quel est le lexème détecté.
Ne cherchez pas ou sont défini les chaîne INTEGER ou VARIABLE, c’est Flex qui va les définir dans le fichier qu’il va générer.

Remarque : dans le cas d’un lexème composé d’un seul caractère on retourne en guise d’ID le caractère lui même. On n’aurait très bien pu utiliser des “ID ” pour ces lexèmes. Par exemple on pourrait très bien remplacer la ligne détectant le caractère ; par
“;” { return(POINTVIRGULE); }.
Personnellement je préfère renvoyer le caractère lui même car les règles de Bison n’en seront que plus facile à lire. Enfin c’est une question de préférence.

La dernière partie sert à mettre votre code C si vous en avez.
Pour l’instant j’en n’ai pas, donc cette partie est vide.

Bon si ça ne vous semble pas très clair, ne vous inquiétez pas. C’est assez normal.
Vous pourriez par exemple vous demander ce qu’est ce que c’est de yylval!
Il s’agit d’une structure définie dans Bison. Tout va s’éclaircir bientôt.

Compilation

Pour compiler notre fichier ebola.l, on utilise la commande suivante:

flex ebola.l

Flex va produire un fichier lex.yy.c

Bison

Flex était la partie la plus simple. II nous faut à présent aborder Bison, l’analyseur syntaxique.

Le Fichier de config de Bison (Yacc) s’appelle ebola.ypp.
Il est lui aussi composé de 3 parties séparées elles aussi par %%.

Le première partie, comme pour Flex sert (entre autre) à inclure les headers

%{
	#include <string>
	#include <vector>
	#include <stdio .h>

	#include "asaNode.h"

	std::vector<asanode *> gl_instructions;

	int yylex();
	int yyerror(std::string err) { printf("Error: %s\n", err.c_str()); }
%}

%union {
	asaNode *node;
	std::string *string;
}

%error-verbose
%locations
%token <string>INTEGER
%token <string>VARIABLE

%type <node> expr variable instruction

%left '+' '-'
%left '*' '/' 

%start program

La variable gl_instructions est un tableau (std::vector) qui va contenir les arbres syntaxiques abstraits représentant les instructions.

On remarque aussi la définition d’une union.
Cette union est très importante car il s’agit du seul et unique type de variable que manipulent Flex et Bison.
La fameuse variable yylval remplie par Flex n’est autre qu’une variable ayant pour type cette union.
De même, les règles définies dans Bison vont prendre en entrée des variables de cette union, et retourner également des variables de cette union.

Remarque: Lorsque Flex envoie la valeur d’un lexème dans string, il va créer des objets de type std::string.
Bison lui va créer des objets de type asaNode.
Dans les deux cas, il faudra penser à détruire tout ce qu’on à créé. Toutes les destructions se feront du coté de Bison.

On trouve également dans cette partie le casting des tokens.
En fonction des lexèmes reçu on indique quelle est la variable de l’union que représente yylval.

%token <string>INTEGER
%token <string>VARIABLE

indique que lorsque Bison reçoit un lexème INTEGER ou VARIABLE alors la valeur de du lexème dans la variable string.

De même Bison va retourner des valeurs dans un objet du type de l’union. Il faut donc indiquer dans quelle variable sera retournée la donnée.

%type <node> expr variable instruction

En gros, dans notre cas, les lexèmes envoient toujours leur valeur dans string, et les règles Bison vont toujours retourner un noeud de type asaNode dans le variable node.

Pour finir on définit la précédence des opérateurs en commençant par les moins prioritaire.
Ici définir ‘-’ et ‘+’ avant ‘*’ et ‘/’ indique que les multiplications et les divisions doivent être évaluées AVANT les additions et les soustractions.

La deuxième partie du fichier ebola.ypp contient les règles Bison.

%%
program: command program						{ }
	| command
	;

command: instruction								{ }
	;

/*******************************************************************
-- Instructions
*******************************************************************/

instruction: variable '=' expr ';'			{ gl_instructions.push_back((asaNode *)new asaNode(ASA_AFFECTATION, $1, $3, "Affectation")); }
	;

expr: INTEGER	 									{ $$ = new asaNode(ASA_INTEGER_VALUE, $1, "Creation Interger Node"); }
	| variable										{ $$ = $1; }
	| expr '+' expr 								{ $$ = new asaNode(ASA_ADDITION, $1, $3, "Addition"); }
	| expr '-' expr 								{ $$ = new asaNode(ASA_SOUSTRACTION, $1, $3, "Soustraction"); }
	| expr '*' expr 								{ $$ = new asaNode(ASA_MULTIPLICATION, $1, $3, "Multiplication"); }
	| expr '/' expr 								{ $$ = new asaNode(ASA_DIVISION, $1, $3, "Division"); }
	| '(' expr ')'									{ $$ = $1 }
	;

variable: VARIABLE								{ $$ = new asaNode(ASA_VARIABLE_VALUE, $1, "Creation Variable Node"); }
	;

On peut lire ces règle de la façon suivante:

  • un program est un ensemble de command
  • une command est une instruction
  • une instruction est composée d’une variable suivie du signe = suivi d’une expr suivi du signe ;
  • une instruction est composée d’une variable suivie du signe = suivi d’une expr suivi du signe ;
  • une expr soit un lexème INTEGER soit une variable soit une association d’expre
  • une variable est un lexème VARIABLE

Remarque: on aurait pu avoir une règle disant qu’un entier est un lexème INTEGER, un peu comme on l’a fait pour variable. Cela n’aurait pas été stupide. Ça aurait même été une bonne idée 8)

comme on vient de la voir, une règle est définie par une ou plusieurs associations de règles et de lexèmes.
Face à chacune de ces associations on trouve un code C.
$1, $2, $3, …. représente les entrées de la règle.
$$ est la sortie.

Par exemple, que dit la règle ‘expr’ définie ci-dessus

  • un lexème INTEGER est une expression. Si on détecte ce cas alors on crée un Noeud qui contient l’entier ($1) et on retourne le noeud créé.
  • une variable (qui n’est pas un lexème mais un autre règle) est une expression. Si on détecte on retourne le Noeud reçu.
  • une expression + une expression est une expression. Si on détecte ce cas alors on crée un Noeud de type addition qui contient comme noeud fils les deux noeuds reçus.
  • une expression – une expression est une expression. Idem +
  • une expression * une expression est une expression. Idem +
  • une expression / une expression est une expression. Idem +
  • une expression entourée de parenthèse est une expression.

Par convention (personnelle), les entrées écrites en majuscule sont des lexèmes reçus de Flex alors que les entrées écrites en minuscule sont des résultats provenant d’autre règles Bison.

expr: INTEGER			{ $$ = new asaNode(ASA_INTEGER_VALUE, $1, "Creation Interger Node"); }

appelle le constructeur asaNode(int, std::string *, const char*);
$1 représente yylval.string lors de cet appel.
Le constructeur crée un “noeud” de type feuille. Il enregistre la valeur du lexème fournit. Il en profite aussi pour libérer le sdt::string puisqu’il ne sera plus utilisé.
il retourne le noeud créé dans $$ qui représente l’attribut node d’une nouvelle variable du type de l’union.

expr: expr '+' expr	{ $$ = new asaNode(ASA_ADDITION, $1, $3, "Addition"); }

appelle le constructeur asaNode(int, asaNode *, asaNode *, const char*);
$1 et $3 représente la variable node d’une union précédemment retourné par une autre règle Bison.
$2 est le lexème ‘+’ qu’on va ignorer
Le constructeur crée un “noeud” qui va lier les 2 expressions à l’opérateur +.

Ce n’est finalement pas très compliqué. Par contre, il faut bien s’assurer que l’ensemble des règles couvre toutes les possibilités du langage source et qu’aucune règle n’est redondante.
Ce deuxième cas est contrôlé par Bison qui refusera générer son fichier s’il y a risque de confusion de règle.

La troisième est dernière partie du fichier ebola.ypp contient le fonction main.
Cela n’est pas obligatoire, vous pourriez mettre la fonction main dans Flex ou même dans un fichier à part car au final, comme je l’ai déjà dit, Flex et Bison vont juste produire du code C qu’il va falloir compiler puis linker. Rien n’empeche donc de mettre l’ensemble du code C dans un fichier séparé.

int main()
{
	yyparse();
	printf("\nFin Program - %d instruction(s)\n", gl_instructions.size());

	std::vector::iterator it;
	std::string rebuilded_instruction;
	int i;
	for (it = gl_instructions.begin(), i=0 ; it != gl_instructions.end(); it++, i++)
	{
		printf("Instruction #%d\n", i);
		printf("---------------\n");
		rebuilded_instruction = (*it)->displayTree();

		printf("\nInstruction reconstruite : %s\n", rebuilded_instruction.c_str());

		printf("\n");
	}
	return 0;
}

Dans ce code, c’est l’appel à la fonction yyparse qui fait tout le travail.
Le reste du code ne fait qu’afficher le contenu des arbres.

Compilation

Pour compiler notre fichier ebola.ypp, on utilise la commande suivante:

bison -d ebola.ypp

Bison va produire deux fichiers ebola.tab.hpp et ebola.tab.cpp.

Implémentation des arbres syntaxique Abstraits

L’implémentation des arbres syntaxiques que j’ai réalisée est tellement simple que je vais rester très sommaire sur le sujet.
Voici la class asaNode.

class asaNode
{
public:
	int nodeType;
	std::string sData;
	asaNode *left;
	asaNode *right;

public:
	asaNode();																			// Constructeur par defaut
	asaNode(const asaNode &);														// Constructeur par copie
	asaNode &operator=(const asaNode &);										// Constructeur d'affectation
	~asaNode();																			// Destructeur

	asaNode(int);
	asaNode(int, std::string *);
	asaNode(int, std::string *, const char*);
	asaNode(int, asaNode *, asaNode *, const char*);

	std::string displayTree(int prof = 0);
};

Je ne vois pas trop quoi en dire, si ce n’est que j’utilise la même class pour les noeuds et pour les feuilles de l’arbre.

En récupérant le code source fourni en bas de ce post, vous pourrez regarder en détails les fichiers asaNode.h et asaNode.cpp

Exécution

pour rappel, nous voulions parser le code suivant (code.txt)

$my_var = 154 + 9;
$other_var = 2 + $my_var * 3;

Pour utiliser Flex, Bison et compiler notre compilateur on a utiliser les commande suivante

flex ebola.l
bison -d ebola.ypp
g++ -o ebola asaNode.cpp ebola.tab.cpp lex.yy.c

On execute notre programme

./ebola < code.txt

Le compilateur produit

Creation Variable Node [$my_var]
Creation Interger Node [154]
Creation Interger Node [9]
Link Node : Addition
Link Node : Affectation
Creation Variable Node [$other_var]
Creation Interger Node [2]
Creation Variable Node [$my_var]
Creation Interger Node [3]
Link Node : Multiplication
Link Node : Addition
Link Node : Affectation

Fin Program - 2 instruction(s)
Instruction #0
---------------
Op =
 - Gauche : Variable $my_var
 - Droite : Op +
   - Gauche : Entier 154
   - Droite : Entier 9

Instruction reconstruite : $my_var = (154 + 9)

Instruction #1
---------------
Op =
 - Gauche : Variable $other_var
 - Droite : Op +
   - Gauche : Entier 2
   - Droite : Op *
     - Gauche : Variable $my_var
     - Droite : Entier 3

Instruction reconstruite : $other_var = (2 + ($my_var * 3))

Et ben voila ça semble pas mal.

Conclusion et Code source

Vous pouvez retrouvez les sources de ce post dans l’archive téléchargeable ici.

Afin de m’initier à Flex et Bison, je me suis appuyé sur ressources trouvées sur Internet. Voici (d’après moi) les plus intéressantes.

Répondre

Human control : 7 + 4 =