Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

utilisation de bison et flex en c++

7 réponses
Avatar
giminik
salut =E0 tous !
voil=E0 mon probl=E8me, pour notre projet de fin de semestre en master
informatique, nous devons par groupe de 8 cr=E9er un compilateur /
interpr=E8teur d'un langage appel=E9 minijaja dont la grammaire peut
=EAtre consult=E9e ici :
http://lifc.univ-fcomte.fr/~bouquet/Enseignement/Compilation/minijaja.html

nous avions le choix entre l'utilisation d'un parser javaCC / jjTree ou
Flex et Bison. C'est sur ce deuxi=E8me =E9l=E9ment que s'est port=E9 notre
choix : nous utilisons donc Flex et Bison sous un environnement Linux.

voici le contenu de mon fichier utilis=E9 par Flex : terminaux.l
Code:
%{

#include "terminaux.tab.h"
extern int yylval;

%}

%x COMMENTS

%%

"class" { return CLASS; }
"{" { return BEGINBLOCK; }
"}" { return ENDBLOCK; }
"=3D=3D" { return EQUAL; }
"=3D" { return ASSIGN; }
"!" { return NOT; }
"+=3D" { return PLUSEQUAL; }
";" { return SEMICOLON; }
"[" { return LEFTBRACKET; }
"]" { return RIGHTBRACKET; }
"final" { return FINAL; }
")" { return RIGHTPARENTHESE; }
"(" { return LEFTPARENTHESE; }
"main" { return MAIN; }
"," { return COMMA; }
"++" { return PLUSPLUS; }
"return" { return RETURN; }
"if" { return IF; }
"else" { return ELSE; }
"while" { return WHILE; }
"-" { return MINUS; }
"&&" { return AND; }
"||" { return OR; }
">" { return GREATER; }
"+" { return PLUS; }
"*" { return MULT; }
"/" { return DIVIDE; }
"true" { return TRUE; }
"false" { return FALSE; }
"void" { return VOID; }
"int" { return INTEGER; }
"boolean" { return BOOLEAN; }
[0-9]+ { /*yylval =3D atoi(yytext);*/ return NUMBER; }
[a-zA-Z_][0-9a-zA-Z_]* { return IDENTIFIER; }
[ \t]+ { ; /* espaces vierges */ }
(\r?\n) { ; /* ligne vide : reconnait les CR-LF
(windows) et les LF (unix) */ }
"//".*\n { ; /* commentaires */ }

"/*" { BEGIN COMMENTS; }
<COMMENTS>. |
<COMMENTS>\n { ; }
<COMMENTS>"*/" { BEGIN 0; }
. { /*yyerror("illegal token");*/ }

%%


voici le contenu de mon fichier utilis=E9 par Bison : terminaux.y
Code:
%{

#include <stdio.h>

void yyerror(char * msg) {
fprintf(stderr, "%s\n", msg);
}

%}

/* l'element par lequel commence l'analyse,
ce ne doit pas etre un token */
%start root

%token CLASS
%token BEGINBLOCK
%token ENDBLOCK
%token EQUAL
%token ASSIGN
%token NOT
%token PLUSEQUAL
%token SEMICOLON
%token LEFTBRACKET
%token RIGHTBRACKET
%token FINAL
%token RIGHTPARENTHESE
%token LEFTPARENTHESE
%token MAIN
%token COMMA
%token PLUSPLUS
%token RETURN
%token IF
%token ELSE
%token WHILE
%token MINUS
%token AND
%token OR
%token GREATER
%token PLUS
%token MULT
%token DIVIDE
%token TRUE
%token FALSE
%token VOID
%token INTEGER
%token BOOLEAN
%token NUMBER
%token IDENTIFIER

%%

root:
classe
;

classe:
CLASS ident BEGINBLOCK decls methmain ENDBLOCK
;

ident:
IDENTIFIER
;

decls:

| decl SEMICOLON decls
;

decl:
var
| methode
;

vars:

| var SEMICOLON vars
;

var:
typemeth ident vexp
| typemeth ident LEFTBRACKET exp RIGHTBRACKET
| FINAL type ident vexp
;

vexp:

| ASSIGN exp
;

methode:
typemeth ident LEFTPARENTHESE entetes RIGHTPARENTHESE
BEGINBLOCK vars instrs ENDBLOCK
;

methmain:
MAIN BEGINBLOCK vars instrs ENDBLOCK
;

entetes:

| entete COMMA entetes
| entete
;

entete:
type ident
;

instrs:

| instr SEMICOLON instrs
;

instr:
ident1 ASSIGN exp
| ident1 PLUSEQUAL exp
| ident1 PLUSPLUS
| ident LEFTPARENTHESE listexp RIGHTPARENTHESE
| RETURN exp
| IF exp BEGINBLOCK instrs ENDBLOCK
| IF exp BEGINBLOCK instrs ENDBLOCK ELSE BEGINBLOCK
instrs ENDBLOCK
| WHILE exp BEGINBLOCK instrs ENDBLOCK
;

listexp:

| exp COMMA listexp
| exp
;

exp:
NOT exp1
| MINUS exp1
| exp AND exp1
| exp OR exp1
| exp1
;

exp1:
exp1 EQUAL exp2
| exp1 GREATER exp2
| exp2
;

exp2: exp2 PLUS terme
| exp2 MINUS terme
| terme
;

terme:
terme MULT fact
| terme DIVIDE fact
| fact
;

fact:
ident1
| ident LEFTPARENTHESE listexp RIGHTPARENTHESE
| TRUE
| FALSE
| NUMBER
| LEFTPARENTHESE exp RIGHTPARENTHESE
;

ident1:
ident
| ident LEFTBRACKET exp RIGHTBRACKET
;

typemeth:
VOID
| type
;

type:
INTEGER
| BOOLEAN
;

%%

main() {
yyparse();
}


voici les commandes que j'ex=E9cute pour tester la grammaire :
Code:
~/compil2 $ flex terminaux.l && bison -d terminaux.y
~/compil2 $ gcc -o test lex.yy.c terminaux.tab.c -ll
~/compil2 $ ./test
class C {
/* un commentaire
* sur plusieurs lignes.
*/

int x =3D 2;
int y =3D 3;

int somme(int a, int b) {
return x + y;
};

main {
int z =3D somme(x, y);
}

}
~/compil2 $


comme vous pouvez le voir, la g=E9n=E9ration de l'analyseur s'effectue
tr=E8s bien en C. seulement, notre projet doit utiliser du C++, c'est
une contrainte du cahier des charges. Est il possible de cr=E9er cet
analyseur en C++ depuis Flex et Bison ? j'ai vaguement entendu parler
de Flex++ et Bison++, est une bonne solution ?

Nous devrons stocker l'arbre syntaxique, et pour cela notre structure
(en cours de d=E9veloppement) sera faite en C++. J'avais =E9ventuellement
pens=E9 =E0 appeler les fonctions de cr=E9ation de la structure (C++)
depuis l'analyseur (C). Est ce possible ?

avez vous d=E9j=E0 utilis=E9 ces outils ? que me conseillez vous ?
J'esp=E8re que vous pourrez m'aider car c'est tr=E8s important, sans cet
analyseur, nous ne pourrons pas avancer dans notre projet.
Merci

7 réponses

Avatar
nico
wrote:

salut à tous !
voilà mon problème, pour notre projet de fin de semestre en master
informatique, nous devons par groupe de 8 créer un compilateur /
interprèteur d'un langage appelé minijaja dont la grammaire peut
être consultée ici :
http://lifc.univ-fcomte.fr/~bouquet/Enseignement/Compilation/minijaja.html
<snip>


J'ai pas tout lu mais tu devrais regarder peut être du coté de flex++ et
bison++, c'est ce que j'utilise et ca marche tres bien.

--
nico

Avatar
giminik
J'ai pas tout lu mais tu devrais regarder peut être du coté de flex++ et
bison++, c'est ce que j'utilise et ca marche tres bien.


salut,
et merci pour ta réponse.
aurais tu un exemple fonctionnel à me passer que je puisse voir ce qui
ne va pas dans mon code ?
simple exemple, avec les lignes de commandes que tu exécutes pour
générer le parseur. ce serait vraiment sympa.
si tu ne veux pas le mettre en ligne sur le forum, tu peux me l'envoyer
à mon adresse mail : giminik [at] gmail [dot] com.

merci.

Avatar
kanze
wrote:

[...]
nous avions le choix entre l'utilisation d'un parser javaCC /
jjTree ou Flex et Bison. C'est sur ce deuxième élément que
s'est porté notre choix : nous utilisons donc Flex et Bison
sous un environnement Linux.


[...]
voici les commandes que j'exécute pour tester la grammaire :
Code:
~/compil2 $ flex terminaux.l && bison -d terminaux.y
~/compil2 $ gcc -o test lex.yy.c terminaux.tab.c -ll
~/compil2 $ ./test
class C {
/* un commentaire
* sur plusieurs lignes.
*/

int x = 2;
int y = 3;

int somme(int a, int b) {
return x + y;
};

main {
int z = somme(x, y);
}

}
~/compil2 $

comme vous pouvez le voir, la génération de l'analyseur
s'effectue très bien en C. seulement, notre projet doit
utiliser du C++, c'est une contrainte du cahier des charges.
Est il possible de créer cet analyseur en C++ depuis Flex et
Bison ? j'ai vaguement entendu parler de Flex++ et Bison++,
est une bonne solution ?


Je ne les connais pas. Je me sers de flex et de bison (voir de
lex et de yacc) directement ; j'utilise les commandes de shell
pour faire des modifications nécessaires pour que le résultat
soit C++.

Dans le cas de flex, il y a déjà un peu de support integré pour
le C++. Mes fichiers de flex commence avec :
%option c++
%option yyclass="EnumScanner"
Voir le manual à http://www.gnu.org/software/flex/manual/ pour
plus de détails.

Attention cependant : flex n'est pas tout à fait à jour en ce
qui concerne le C++ ; le code généré inclut <iostream.h>, par
exemple, avec un déclaration en avant de « class ostream », et
n'utilise pas de namespace. En fait, dans mon fichier make, j'ai
flex -t -8 $< | $(toolsDir)/flex2cc >$@
avec dans flex2cc :
(
echo '#include "gb/Global.hh"'
echo '#include <istream>'
echo '#include <ostream>'
echo '#include <iostream>'
cat $*
) | sed '
/class istream;/d
/^[^#]/s/<istream>/std::istream/g
/^[^#]/s/<ostream>/std::ostream/g
/^[^#]/s/<cin>/std::cin/g
/^[^#]/s/<cout>/std::cout/g
/^[^#]/s/<cerr>/std::cerr/g
s/std::std::/std::/g
'
Note que le contenu exacte pourrait dépendre de la version de
flex, bien que j'utilise exactement le même script sur plusieurs
systèmes différents actuellement (mais toujours avec une version
très récente de flex).

Dans l'ensemble, je suis très content du résultat.

Je n'ai pas eu l'occasion d'utiliser bison dans les mêmes
conditions. Dans une de mes applications actuelles, en revanche,
j'utilise yacc, avec la commande suivante dans le fichier de
make :

yacc -v -d parser.y
( echo '#include <string>' ;
echo '#include "Instruction.h"' ;
echo '#include "AttributeValue.h"' ;
cat y.tab.h
) > parser.h
mv y.output parser.output
sed -e '/{.*} *yytoktype/s/char/char const/' -e '/yyreds/s/char/char
const/' y.tab.c > parser.cc && rm y.tab.c

Le résultat se laisse compiler par un compilateur C++ (g++
3.4.0, en l'occurance). Le parseur même n'est pas une classe ;
le code généré est bien du C, même s'il est compilé par un
compilateur C++. En revanche, dans les actions que je fournis,
je me sers bien de tout ce qui offre le C++. De même, le type de
la valeur sémantique est défini :
%union {
int intConst ;
double floatConst ;
std::string const* stringConst ;
std::string const* symbol ;
Variable const* variable ;
Instruction const* instruction ;
AttributeValueAssertion::Operator const*
opId ;
}
Ici, il faut faire un peu gaffe en ce qui concerne la gestion de
la mémoire. Du fait que cette déclaration donne une union dans
le code généré fait qu'il ne peut contenir que des PODs. D'où
les pointeurs à la place des valeurs. Ici, quand il s'agit de
renvoyer un type comme std::string ou Variable, le lexeur fait
un new, et c'est à charge de l'action de la règle qui l'utilise
de faire le delete. Ça marche, mais c'est assez fragile, et
exige une certaine rigueur. (Le code en question est un
simulateur de test. Les exigeances de qualité sont donc bien
moins que pour les serveurs que j'écris d'habitude. Aussi, il ne
parse qu'une fois, au début -- alors, même s'il y a une fuite de
mémoire, les conséquences en sont limitées. Si j'avais à
integrer un parseur dans le serveur, pour traiter des requêtes
client, par exemple, je crois que je chercherais une solution
plus robuste.)

Cette technique marchera sûrement avec bison aussi, mais les
modifications à faire dans le code généré seront certainement
différentes. Selon la documentation, bison a un peu de support
pour C++, ce qui n'est pas le cas de yacc. (Voir le manual :
http://www.gnu.org/software/bison/manual/. La description du
support pour C++ se trouve dans le chapître 10.) Je n'ai pas eu
l'occasion de l'essayer jusqu'ici. Je remarque néaumoins : « The
%union directive works as for C, [...]. In particular it produces
a genuine union [...]. Because objects have to be stored via
pointers, memory is not reclaimed automatically: using the
%destructor directive is the only means to avoid leaks. » Alors,
le problème décris ci-dessus existe toujours, mais ils
fournissent quelque chose (%destructor) pour assister à sa
solution.

Aussi, je m'attendrais au moins aux problèmes de portabilité du
C++, comme pour flex. Prévois donc un post-processeur dans tous
les cas.

Dans les deux cas, ne neglige pas non plus les possibilités des
macros définis dans la prologue. Au moins une fois dans la
passée, je me suis servi d'un « #define yylex() » pour que yacc
passe davantage d'information au lexeur, et lex et flex utilise
beaucoup de « fonctions » du genre yyinput qu'on peut définir
soi-même.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Avatar
SerGioGio
salut à tous !
voilà mon problème, pour notre projet de fin de semestre en master
informatique, nous devons par groupe de 8 créer un compilateur /
interprèteur d'un langage appelé minijaja dont la grammaire peut
être consultée ici :
http://lifc.univ-fcomte.fr/~bouquet/Enseignement/Compilation/minijaja.html

nous avions le choix entre l'utilisation d'un parser javaCC / jjTree ou
Flex et Bison. C'est sur ce deuxième élément que s'est porté notre
choix : nous utilisons donc Flex et Bison sous un environnement Linux.


Lemon est un autre bon parser generator, je trouve plus propre et plus
flexible que Bison.
Il est aussi plus facile a C++iser.
http://www.hwaci.com/sw/lemon/

Bon courage.

SerGioGioGio

Avatar
Fabien LE LEZ
On 14 Oct 2005 00:46:06 -0700, "kanze" :

et c'est à charge de l'action de la règle qui l'utilise
de faire le delete.


Le garbage collector, que tu as commencé à utiliser si j'ai bien
compris, ne peut-il pas s'en occuper ?

Avatar
Thierry Miceli
J'utilise ANTLR (http://www.antlr.org). C'est un générateur de parseur qui
peut génerer du code C++ conforme avec le standard actuel du C++ (il peut
également générer du code en java, C#, C et peut-être d'autres langages).
Parcequ'il permet le retour arrière (backtracking) il fait de l'excellent
travail avec des grammaires ambigues, de plus le code généré est beaucoup
plus lisible que celui généré par yacc ou bison.

--
Thierry
Refactoring tool for C++ (www.refpp.com)
Avatar
James Kanze
Fabien LE LEZ wrote:
On 14 Oct 2005 00:46:06 -0700, "kanze" :


et c'est à charge de l'action de la règle qui l'utilise de
faire le delete.



Le garbage collector, que tu as commencé à utiliser si j'ai
bien compris, ne peut-il pas s'en occuper ?


Parfaitement.

Le code que j'ai cité dans mon posting date d'un
certain temps. Et j'ai expliqué les problèmes que j'ai eu à
l'époque, sans trop reflechir. Alors que tu as parfaitement
raison à dire que c'est un problème où le glaneurs de cellules
se prête particulièrement bien. La probabilité qu'une valeur
sémantique a besoin d'un destructeur deterministe me semble
véritablement nulle.

--
James Kanze mailto:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34