Lex & Yacc (Flex & Bison) - Freejo.fabrizio.free.fr/teaching/1112_thl/flex_bison.pdf · 1 Lex &...
Transcript of Lex & Yacc (Flex & Bison) - Freejo.fabrizio.free.fr/teaching/1112_thl/flex_bison.pdf · 1 Lex &...
-
1
Lex & Yacc (Lex & Yacc (Flex & Flex & Bison)Bison)– – ING1/APP ING1ING1/APP ING1 – –
Jonathan FabrizioJonathan FabrizioLRDEEPITALRDEEPITA
http://lrde.epita.fr/~jonathan/http://lrde.epita.fr/~jonathan/
Nov/Dec 2011
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
2/25
Lex & Yacc
● LexLex : – Génère un analyseur
lexical– Traite les langages de
type 3 (réguliers)
– FlexFlex : Fast lexical analyzer generator
● YaccYacc– Yet another compiler
compiler– Génère des parsers
LALR
– BisonBison
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
3/25
Lex&Yacc
● Lex et Yacc sont souvent utilisés ensemble toutefois ils sont indépendants : – Lex crée l'analyseur lexical et cet analyseur peut être
utilisé sans Yacc (par exemple, si on écrit à la main un analyseur syntaxique LL(1))
– Yacc crée l'analyseur syntaxique et cet analyseur peut être utilisé sans lex
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
4/25
Lex&Yacc
fic1.l
LEX
fic1.c
Compilateur
fic1.o
fic2.y
YACC
fic2.c
Compilateur
fic2.o
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
5/25
Bison
● Format du fichier :Format du fichier :
prologue : définitions et options%%règles%%épilogue : code utilisateur
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
6/25
Bison
● Appel :Appel :bison [options] fic.y -o fic.cretour : le code du compilateur en c prêt à être compilé...
Quelques options possibles :Quelques options possibles : --xml : sortie en xml--report=all : génère un rapport complet sur le parser--graph : sauvegarde du parser sous forme de graphNote : certaines options peuvent être mises indifféremment dans le
prologue ou passées en ligne de commande
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
7/25
Bison
● Sortie :Sortie : Bison génère un programme c du parser, il peut être
appelé via la fonction :int yyparse();
Pour fonctionner correctement, cette fonction a besoin d'une fonction int yylex(); ainsi que
void yyerror(const char *s);
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
8/25
Bison
● Gestion d'erreurs :Gestion d'erreurs :– En cas d'erreur la fonction int yyerreur(const char *s)
est appelée avec un message d'erreur (en général syntaxe error) – c'est à l'utilisateur de définir cette fonction
– Il est possible d'avoir des messages plus explicites avec l'option %define parse.error verbose dans le prologue
– Il existe des possibilités pour faire de la reprise sur erreur...
– yyparse renvoie 0 si le parsing est complet 1 sinon
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
9/25
Bison
● Conflits shift-reduce :Conflits shift-reduce :– Il est possible de spécifier combien de conflits
shift/reduce on prévoit pour la grammaire donnéeoption %expect n dans le prologue
– Dans la pratique :%expect 0
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
10/25
Bison
● La Grammairesyntaxe :
exp:exp ''+'' exp | exp ''*'' exp| exp ''-'' exp| exp ''/'' exp;
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
11/25
Bison
● La Grammairesyntaxe :
exp:exp ''+'' exp {printf(''Branche +\n'');}| exp ''*'' exp {printf(''Branche *\n'');}| exp ''-'' exp {printf(''Branche -\n'');}| exp ''/'' exp {printf(''Branche /\n'');};
On insère des actions à accomplir pendant le processus
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
12/25
Bison
● La Grammairesyntaxe :
exp:exp ''+'' exp {$$ = $1 + $3;}| exp ''*'' exp {$$ = $1 * $3;}| exp ''-'' exp {$$ = $1 - $3;}| exp ''/'' exp {$$ = $1 / $3;};
On peut faire apparaître les valeurs
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
13/25
Bison
● La Grammaire– Axiome :
première règle ou %start
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
14/25
Bison
● La Grammaire– L'analyseur généré fait appel à yylex() pour avoir le
prochain token à analyser. Deux informations doivent être transmises : le token et, éventuellement, la valeur associée. Il faut donc 1/ définir les types possibles et 2/les tokens avec éventuellement leur type :
%token TOK_PLUS ''+'' TOK_MOINS ''-'
%token TOK_NUMBER ''number''%type exp
%union{
int ival;float fval;
}
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
15/25
Bison
● La Grammaire– L'analyseur généré fait appel à yylex() pour avoir le
prochain token à analyser. Deux informations doivent être transmises : le token et, éventuellement, la valeur associée. Il faut donc 1/ définir les types possibles et 2/les tokens avec éventuellement leur type :
%define api.tokens.prefix ''TOK_''%token PLUS ''+''
MOINS ''-'%token NUMBER ''number''%type exp
%union{
int ival;float fval;
}
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
16/25
Bison
● La Grammaire– Définir, dans le prologue, les priorités et
l'associativité :%left%right%nonassoc%precedence
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
17/25
Bison
● Un exemple (prologue) :%expect 0%debug%defines
%code provides {void yyerror(const char *msg); ...
}
%left ...
%define api.tokens.prefix ...%token ...%type ...
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
18/25
Bison
● Un exemple (règles) :
%%nt1:
nt2 ''t3'' {printf(''%d\n'', $1);}| nt3 ''t4'' {printf(''%d\n'', $1);};
%%
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
19/25
Bison
● Un exemple (épilogue) :
void yyerror(const char *msg) {
...}
int main(int argc, char *argv[]){
...}
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
20/25
Bison
● Faire générer l'analyseur lexical par flex.
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
21/25
Flex
● Structure proche des fichiers :
prologue%%règles %%epilogue
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
22/25
Flex
● Dans le prologue :– Insertion de code %{ %}– Ajout d'options par %option
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
23/25
Flex
● Règles
%%''abc'' {action;}[0-9]+ {action;}%%
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
24/25
Flex
● Epilogue
Ajout direct de lignes de code...
-
« Lex et Yacc », J. Fabrizio – http://lrde.epita.fr/~jonathan/ – LRDE – EPITA – Nov/Dec 11
25/25
Bison et Flex
● Variables importantes – yylval– yytext– yyleng
Diapo 1Diapo 2Diapo 3Diapo 4Diapo 5Diapo 6Diapo 7Diapo 8Diapo 9Diapo 10Diapo 11Diapo 12Diapo 13Diapo 14Diapo 15Diapo 16Diapo 17Diapo 18Diapo 19Diapo 20Diapo 21Diapo 22Diapo 23Diapo 24Diapo 25