Discussion :

[gridaine]

Je vous propose un tuto d'initiation à Flex/Bison en C++ pour gcc et applicable à Visual C++.

N'hésitez pas à faire un retour.

Présentation Flex/Bison
Flex et Bison sont des utilitaires unix robuste et éprouvé dans le temps qui permettent d'écrire des parseurs pour plusieurs types de format.

Flex joue le rôle d'analyseur.
Bison joue le rôle du parseur.

Flex et Bison sont plus récent et performant que Lex et Yacc qui sont les versions originales. Ils restent compatible avec ceux-ci.

Flex et Bison c'est :
- La génération d'un parseur très rapide.
- Un code très lisible, plus facile à maintenir et à faire évoluer qu'un code maison.
- Une gestion des erreurs prise en charge.
- Un code avec moins de bogues dû à ses nombreuses années d'expériences.

Référence
Man Flex(fr) : http://www.delafond.org/traducmanfr/...ex.1.html#lbAF
Aquamentus (en): http://aquamentus.com/flex_bison.html

Installation
Sous Unix et Linux les utilisateurs sont déjà présent. Sinon apt-get, urpmi, yum… et autres gestionnaire de packages sont vos amis.

Sous Windows télécharger les binaires pour Windows et les ajouter à votre variable d'environnement PATH.
http://gnuwin32.sourceforge.net/packages/flex.htm
http://gnuwin32.sourceforge.net/packages/bison.htm
Pour Windows appeler les exécutables en ligne de commande et utiliser votre compilateur préféré. Ces outils fonctionne avec Visual Studio.

Lex

Afficher bonjour en C
L'exemple suivant permet de comprendre le fonctionnement de Flex.

Objectif
Lorsque que l'analyseur détecte "coucou" il affiche "Bonjour".

Réalisation
Saisir au clavier "coucou", l'analyseur reconnaît le motif et exécute le code associé "printf("Bonjour\r\n");" pour afficher "Bonjour". Sinon l'analyseur recopie la saisie.

Fichier
Ecrire le fichier "bonjour.l" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
%%
coucou  printf("Bonjour\r\n");

Compilation
Générer le fichier analyseur "lex.yy.c" avec l'utilitaire flex
$ flex bonjour.l

Compiler le fichier "lex.yy.cc" avec gcc. L'option –lfl permet de linker avec les librairie flex sinon essayer avec –ll qui utilise lex
$ gcc lex.yy.cc –lfl –o bonjour

Résultat
Tester
$ ./bonjour

Saisir au clavier des caractères ceux-ci sont reproduit sur l'écran tel que. Essayer en écrivant "coucou" et l'analyseur affiche "bonjour".
test
test
divers
divers
coucou
Bonjour

Comprendre les sections flex et bison
L'exemple suivant permet de comprendre les sections dans les fichiers Flex et bison.

Objectif
Lorsque que l'analyseur détecte "coucou" il affiche "Bonjour".

Réalisation
Saisir au clavier "coucou", l'analyseur reconnaît le motif et exécute le code associé "printf("Bonjour\r\n");" pour afficher "Bonjour". Sinon l'analyseur recopie la saisie.

Il y a 3 sections dans les fichiers Flex et Bison. Chaque section est délimité par le double modulo "%%".
Les sections :
1. Le "control" d'information. Les délimiteur modulo avec accolade permettent de déclarer du code à recopier, la déclaration des inclusions, fonctions…
2. La définition des motifs et des actions. Je cherche coucou et j'affiche Bonjour.
"coucou" est une expression régulière.
3. Le code C/c++. Le code à recopier à l'identique dans le fichier résultant. L'appel dans le main() de yylex() permet la saisie des entrées sur le clavier.

Fichier
Ecrire le fichier "bonjour.l" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
%{
#include <stdio.h>
%}
 
%%
coucou  printf("Bonjour\r\n");
 
%%
int main(void) {
    yylex();
    return 0;
}

Compilation
Générer le fichier analyseur "lex.yy.c" avec l'utilitaire flex
$ flex bonjour.l

Compiler le fichier "lex.yy.cc" avec gcc. L'option –lfl permet de linker avec les librairie flex sinon essayer avec –ll qui utilise lex
$ gcc lex.yy.cc –lfl –o bonjour

Résultat
Tester
$ ./bonjour

Saisir au clavier des caractères ceux-ci sont reproduit sur l'écran tel que. Essayer en écrivant "coucou" et l'analyseur affiche "bonjour".
test
test
divers
divers
coucou
Bonjour

Afficher bonjour en c++
L'exemple suivant permet de comprendre le fonctionnement de Flex en c++.

Objectif
Lorsque que l'analyseur détecte "coucou" il affiche "Bonjour".

Réalisation
Ajouter l'inclusion iostream pour l'utilisation de cout et endl.
Forcer le compilateur g++ à ne pas faire de "name-mangling" pour l'identifiant "yylex" sinon le compilateur g++ génère un nom de fonction "_XYZyylexv", plus difficile à retrouver et à linker.

Lorsque que l'analyseur détecte quelque chose qu'il reconnaît "coucou" il exécute le code associé "std::cout<<"Bonjour\r\n");"

Fichier
Ecrire le fichier "bonjour_cpp.l" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
%{
#include <iostream>
#define YY_DECL extern "C" int yylex()
%}
 
%%
coucou  std::cout << "Bonjour" << std::endl;
 
%%
int main(void) {
    yylex();
    return 0;
}

Compilation
Générer le fichier analyseur "lex.yy.c" avec l'utilitaire flex
$ flex bonjour_cpp.l

Compiler le fichier "lex.yy.cc" avec g++. L'option –lfl permet de linker avec les librairie flex sinon essayer avec –ll qui utilise lex
$ g++ lex.yy.cc –lfl –o bonjour

Résultat
Tester
$ ./bonjour

Saisir au clavier des caractères ceux-ci sont reproduit sur l'écran tel que. Essayer en écrivant "coucou" et l'analyseur affiche "bonjour".
test
test
divers
divers
coucou
Bonjour

Reconnaître quelle est le type de donnée
L'exemple suivant permet de reconnaître le type de données.

Objectif
L'utilisateur saisie au clavier, un entier, un nombre à virgule ou une chaîne de caractères et le parseur affiche le type. Le parseur ignore les espaces, les tabulations et les retours à la lignes.

Réalisation
Créer quatre expression régulières pour :
1. Reconnaître les entiers. Soit tous les chiffres de compris entre 0 et 9 quelque soit le nombre d'occurrence.
[0-9]+
2. Reconnaître les nombres à virgules. Soit tous les nombres entiers séparés par une virgules.
[0-9]+,[0-9]+
3. Reconnaître les chaînes de caractères. Soit tous les caractères alphanumérique compris de a à z, de A à Z et de 0 à 9 quelque soit le nombre d'occurrence.
[a-zA-Z0-9]+
4. Ignorer les espaces, les tabulations et les retours à la ligne.
[ \t\n]+

Définir les priorités :
1. Ignorer les espaces, les tabulations et les retours à la ligne.
2. Reconnaître les nombres à virgules.
3. Reconnaître les entiers.
4. Reconnaître les chaînes de caractères

Fichier
Ecrire le fichier "quelletype.l" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 %{
 #include <iostream>
 #define YY_DECL extern "C" int yylex()
 %}
 
 %%
 [ \t\n]       ;
 [0-9]+,[0-9]+ { std::cout << "Nombre à virgule : " << yytext << std::endl; }
 [0-9]+        { std::cout << "Nombre entier : " << yytext << std::endl; }
 [a-zA-Z0-9]+  { std::cout << "Chaine de caractères : " << yytext << std::endl; }
 
 %%
 int main(void) {
   yylex();
   return 0;
 }

Détails :
- Lignes 6 et 12 : Les sections sont divisé par des %%
- Lignes 1 et 4 : Les délimiteurs signalent que les lignes 2 à 4 sont du code à recopier dans le lexer généré.
- Ligne 2 : La Définition permet l'utilisation du "cout".
- Ligne 3 : Le define force le compilateur g++ à ne pas faire de "name-mangling" pour l'identifiant "yylex". Sans faire ceci le compilateur g++ génère un nom de fonction comme "_Z5yylexv", difficile à retrouver ou à linker

- Ligne 6 : Le délimiter %% signifie que l'on passe de la section de control à la section motif. Noter que l'on ne peut pas avoir beaucoup plus dans la section control. La section control de Bison permet plus de chose que la section control de Flex.
- Lignes 7 à 10 : Elles représentent une expression régulière suivi d'une action. Lorsque Flex lit une entrée correspondant à une des expressions régulières il exécute l'action. L'expression régulière n'est pas de type Perl les "\d" sont interdit mais le reste fonctionne. L'action est du code C ou C++ qui est copié dans la sortie Flex. Il est possible d'avoir une simple action ou bien des accolades avec plusieurs actions. Une spécificité du format est que l'action doit être justifié à gauche. Si il y a des espaces au début de la ligne où une pattern est attendu la ligne est considérée comme un commentaire. La séparation entre une pattern et une action est un espaces. L'action peut être décrite sur plusieurs lignes si elle est encadrée par des accolades.

- Ligne 12 : Le délimiteur %% signifie que l'on passe de la section motif à le dernière section code C ou C++.
- Ligne 13 à 16 : Le code est recopié. Contrairement à la première section il n'y a pas de délimiteurs "%{" et "%}". Pour le fichier Flex cette section n'est pas utile mais pour cet exemple une fonction "main" permet d'exécuter la sortie sans avoir à créer un autre fichier à linker.

Compilation
Compiler avec la commande :
% flex quelletype.l

Cela produit le fichier "lex.yy.c" qui peut être compilé avec g++ :
% g++ lex.yy.cc –lfl –o quelletype

L'option "-lfl" permet de linker avec les librairies Flex. Si Flex n'est pas installé essayer "-ll" qui utilisera les librairies Lex au lieu de Flex.

Résultat
Exécuter et saisir sur l'entrée standard STDIN pour être analyser :
% ./quelletype
1
Nombre entier : 1
23
Nombre entier : 23
4,5
Nombre à virgule : 4,5
6 texte à afficher
Nombre entier : 6
Chaine de caractères : texte
àChaine de caractères : afficher
7 texte et chiffre 8
Nombre entier : 7
Chaine de caractères : texte
Chaine de caractères : et
Chaine de caractères : chiffre
Nombre entier : 8
!
!


Le point d'exclamation à la fin est réécrit : lorsque Flex trouve quelque chose qui ne correspond à aucune des expressions régulières il l'écrit sur la sortie standard STDOUT. C'est une bonne indication que la définition des motifs n'est pas suffisamment complète.


J'espère que cette présentation vous donnera envie d'utiliser ce super utilitaire !

[Joel F]

Pourquoi utiliser cette antiquité de Flex alors que Boost.Spirit est bien plus efficace et lisible ?

[gridaine]

De nombreux projets ont été réalisé en lex/yacc et Flex/Bison.

[Joel F]

et ?

De nombreux projets ont été réalisé avec Boost.Spirtit.

l'argumentaire est un peu leger

[gridaine]

Sur un nouveau projet ma préférence va à Spirit.

J'aimerais ajouter (ou quelqu'un d'autres ?) des exemples Spirit vs Flex/Bison.

Sur un projet existant tu ne ré-écris pas des milliers de lignes de codes voir plus juste parce que Spirit est plus récent.


En pratique :
- Spirit est plus récent, sous forme de librairie, en C++ et utilise des Template en grande quantité (peut être corrigé dans une version plus récente ?).
- Bison/Flex a plus d'expérience, est sous forme d'utilitaire, utilise un autre langage.

J'ai lu les résultats de google spirit vs Flex/Bison et les résultats sont mitigés pas de réel cas où l'un est vraiment meilleur que l'autre.

Si tu as des exemples cela serait intéressant de les ajouter .

[Ehonn]

Spirit est plus récent, sous forme de librairie, en C++ et utilise des Template en grande quantité (peut être corrigé dans une version plus récente ?)

Spirit est une bibliothèque "header-only". Pour pouvoir l'utiliser, il suffit d'un compilateur C++, aucun "link" de bibliothèque n'est requis.
L'utilisation de template n'est pas un bug ! Si tu remets en cause l'utilité et l'importance de la programmation générique et la méta-programmation... (alors toute notre vie n'a pas de sens :p)

[JolyLoic]

Pourquoi utiliser cette antiquité de Flex alors que Boost.Spirit est bien plus efficace et lisible ?

<Mode taunt="On">Pour ne pas multiplier par 10 nos temps de compilation ?</Mode>

[ternel]

Un point… malheureusement…

[jblecanard]

Et parce que les messages d'erreurs quand on se vautre dans Spirit équivalent à peu près à se faire vomir dessus par GCC.

Heureusement, c'est beaucoup mieux avec clang.

[Luc Hermitte]

Même sans dégainer spirit, il existait déjà ANTLR depuis pas mal de temps comme alternative viable à lex/yacc.

[Joel F]

Même sans dégainer spirit, il existait déjà ANTLR depuis pas mal de temps comme alternative viable à lex/yacc.

diantre oui, ANTLR ! j avais oublie cette perle

[Joker-eph]

C'est vrai que comprendre Flex/Bison est utile, au moins pour convertir un code existant vers Spirit ;-)

Je n'ai jamais utilisé ANTLR mais j'avais en tête que c'était plutôt orienté Java, on peut générer du natif pour s'intégrer dans du C/C++ ?

[gridaine]

Je vais éditer/ajouter :
- un exemple bison
- un exemple Flex/Bison
- des liens pour ANTLR et Spirit

[gridaine]

Un morceau de plus pour Bison.

Références
Bison : http://www.gnu.org/software/bison/ma...ode/index.html
Boost-sprit (cité ci-dessus) : http://irmatden.developpez.com/tutor...c-boost-spirit

Bison

Calculer
L'exemple suivant permet de faire une addition ou une multiplication.

Objectif
L'utilisateur saisit au clavier, des additions ou multiplications d'entiers et bison affiche le résultat.

Fichier
Ecrire le fichier "calculer.y" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
%{
#include <iostream>
 
int yylex();
void yyerror(const char *msg);
%}
 
%token valeur ajouter multiplier fin
%left ajouter
%left multiplier
%start axiome
 
%%
axiome: /* boucler */
			| axiome expr fin { std::cout << $2 << std::endl; }
;
 
 
expr:	valeur { $$ = $1 }
		| expr ajouter expr { $$ = $1 + $3 }
		| expr multiplier expr { $$ = $1 * $3 }
 
;
%%
 
int main(void) {
	yyparse();
	return 0;
}
 
int yylex() {
	const int car = getchar();
 
	if(car == EOF) { 
		return 0; 
	}
 
	if(isdigit(car)) {
		yylval = car - '0';
		return valeur;
	}
 
	switch(car) {
		case '+': return ajouter;
		case '*': return multiplier;
		case '\n': return fin;
	}
 
	return car;
}
 
void yyerror(const char *msg) {
	std::cerr << "Completer les expressions: " << msg << std::endl;
	exit(-1);
}

Détails :
- Lignes 13 et 24 : Les sections sont divisées par des %%
- Lignes 1 et 6 : Les délimiteurs signalent que les lignes 2 à 5 sont du code à recopier dans le fichier généré.
- Ligne 2 : La Définition permet l'utilisation du "cout".
- Ligne 4 et 5 : La déclaration des fonctions parseur définies plus bas.

- Ligne 8 : token utilisés dans les expressions.
- Ligne 9 et 10 : priorité des token utilisés dans les expressions.
- Ligne 11 : expression de démarrage pour l'interprétation.

- Ligne 13 : Le délimiter %% signifie que l'on passe de la section de control à la section motif.
- Lignes 14 à 23 : Elles représentent les expressions reconnues suivi de l'action. Lorsque la fonction yylex lit une entrée et recherche une expression correspondant pour exécuter l'action.

- Ligne 24 : Le délimiteur %% signifie que l'on passe de la section motif à la dernière section code C ou C++.
- Ligne 26 à 55 : Le code est recopié. Contrairement à la première section il n'y a pas de délimiteur "%{" et "%}". Une fonction "main" permet d'exécuter la sortie sans avoir à créer un autre fichier à linker.

Compilation
Compiler avec la commande :
% bison calculer.y

Cela produit le fichier "calculer.tab.c" qui peut être compilé avec g++ :
% g++ calculer.tab.c –o calculer

Résultat
Exécuter et saisir sur l'entrée standard STDIN pour être analyser :
% ./calculer
1+2+4
Résultat = 7
1+2*3+4
Résultat = 11

[Emmanuel Deloget]

Enfin, au final, on a du C, pas du C++.

flex/bison ne génère pas de code C++, ce qui implique que l'architecture de l'application doit faire un détour sauvage.

Je conseille plutôt des alternatives comme ANTLR ou Coco/R (simple, efficace, génère un code clair et très, très simple à lire et à comprendre, et en plus le template de génération en C++ peut être changé pour coller à à peu près tous les besoins).