'Techniques de compilation $

Générer un analyseur avec Flex&Bison

Généralités
Analyse lexicale avec Flex
Analyse syntaxique avec Bison
Association de Flex et Bison
Fabrice Harrouet
École Nationale d’Ingénieurs de Brest
harrouet@[Link]
[Link]

& enib, F.H . . . 1/44 %

' $
Flex&Bison
Origine des outils
. Lex&Yacc
 Générateurs d’analyseurs lexicaux/syntaxiques en C
 ' années 1970, laboratoires Bell
 Outils UNIX (Posix) standards
 + de nombreuses variantes (commerciales ou non)
. Flex&Bison
 Version GNU de Lex&Yacc
 Flex : “fast Lex” Bison : jeu de mot sur Yacc
 Beaucoup de possibilités supplémentaires !
 Disponible pour un très grand nombre de plateformes
. ∃ de nombreux outils différents ayant le même propos
 AntLR, Spirit . . .
 On retrouve des choses issues de Lex&Yacc
& enib, F.H . . . 2/44 %
' $
Flex&Bison
Principe des outils

. Lex/Flex : LEXical analyzer

 Reconnaisseur de langages réguliers
 Expressions rationnelles → code C d’un analyseur lexical
 Permet de reconnaı̂tre les mots d’un langage
. Yacc/Bison : Yet Another Compiler Compiler
 Reconnaisseur de langages non contextuels
 Grammaire non contextuelle → code C d’un analyseur syntaxique
 Permet de reconnaı̂tre les phrases d’un langage

& enib, F.H . . . 3/44 %

' $
Flex&Bison
Principe des outils
Fic

Fic
hie

Flex
hie
rF

rC
lex
Fic

Ex
Fic

Compilation et
hie

éc

Bison
hie

uta
r

édition de liens
Bis

rC

b
le
on

Fic
hie
rs
C

. Génération d’analyseurs statiques et non dynamiques

 Le code C produit est spécifique au langage à reconnaitre → efficacité
 Compilation du code généré comme le reste de l’application
 Modif du langage → regénération du code des analyseurs
& enib, F.H . . . 4/44 %
' $
A. lexicale en Flex
Structure d’un programme Flex
Fichier Flex Fichier C généré
%{ Déclarations, macros

Pré−code C Tables d’analyse

%} Copie du pré−code C

Définitions et options int yylex(void)

{
%% ...
Copie du code C
Règles de production ...
}
%% Autres fonctions ...
Post−code C Copie du post−code C

. Pré/post-code C : du C tout à fait classique

. Options : %quelquechose pour paramétrer le fonctionnement
. Définitions : Expressions rationnelles auxquelles on attribue un nom
. Règles de production : Associations ER → code C à exécuter
& enib, F.H . . . 5/44 %

' $
A. lexicale en Flex
Expressions rationnelles en Flex
. Comprend les ER POSIX
 Voir le cours correspondant
. Quelques possibilités supplémentaires
 Un atome peut être une chaı̂ne C littérale
◦ ex : "ab"{3} → ababab
 Les caractères spéciaux du C sont reconnus
◦ ex : Hello\tWorld , Hello\123World , Hello\x2aWorld
 La notation { } permet aussi de réutiliser une ER nommée
◦ ex : ({integer}|{real})? (integer et real définies avant)
 L’atome <<EOF>> représente la fin de fichier
 Les start-conditions (voir plus loin)
& enib, F.H . . . 6/44 %
' $
A. lexicale en Flex
Syntaxe Flex

. Définition des ER nommées

 Un nom collé à gauche, une ou plusieurs espaces, une ER
 ex : integer [1-9][0-9]*|0
 ex : indent [a-zA-Z ][0-9a-zA-Z ]*
. Règles de production
 Une ER collée à gauche, une ou plusieurs espaces, du code C
 Code sur une seule ligne ou bloc avec { sur la même ligne que l’ER
 ex : {integer} cerr << "INTEGER" << endl;
 ex : {indent} {
cerr << "IDENT" << endl;
}
 Les commentaires ne doivent pas être collés à gauche (→ ER!)

& enib, F.H . . . 7/44 %

' $
A. lexicale en Flex
L’analyseur généré
. La fonction int yylex(void)
 Extrait des caractères du flux yyin (stdin par défaut)
 Confronte les séquences aux ER des règles de production
◦ Test de haut en bas, la plus longue correspondance est retenue
 Exécute les actions sémantiques (code C ) associées
◦ Variable yytext : chaı̂ne de caractères correspondant à l’ER
◦ Variable yyleng : longueur de yytext
 Écrit les non-correspondances sur yyout (stdout par défaut)
 Jusqu’à la fin de fichier ou un return dans les actions C
. La valeur de retour
 0 en cas de fin de fichier
 Un code numérique (#define, enum) indiquant l’ER reconnue
→ Analyse lexicale
& enib, F.H . . . 8/44 %
' $
A. lexicale en Flex
Compteur de lignes, mots et caractères
%{
int nbChar=0,nbWord=0,nbLine=0; $
%} $ flex -oprog.c prog.l
$ gcc -oprog prog.c
/* doesn’t need yywrap() */ $ ./prog < prog.l
%option noyywrap 24 39 347
$
endOfLine \n
character [^ \t\n]

%%
{endOfLine} { ++nbChar; ++nbLine; }
{character}+ { nbChar+=yyleng; ++nbWord; }
. { ++nbChar; }
%%

int
main(void)
{
yylex();
fprintf(stderr,"%d\t%d\t%d\n",nbLine,nbWord,nbChar);
return(0);
&
} %
enib, F.H . . . 9/44

' $
A. lexicale en Flex
Un analyseur trivial

%{ $ cat [Link]
%} var1=123*45.67;
%option noyywrap _attr+=var1;
integer [0-9]+ $ ./prog < [Link]
real [0-9]+\.[0-9]*|\.[0-9]+ IDENT [var1]
ident [a-zA-Z_][0-9a-zA-Z_]* UNKNOWN [=]
%% INTEGER [123]
{real} { fprintf(stderr,"REAL [%s]\n",yytext); } UNKNOWN [*]
{integer} { fprintf(stderr,"INTEGER [%s]\n",yytext); } REAL [45.67]
{ident} { fprintf(stderr,"IDENT [%s]\n",yytext); } UNKNOWN [;]
\n { fprintf(stderr,"NEW_LINE [%s]\n",yytext); } NEW_LINE [
. { fprintf(stderr,"UNKNOWN [%s]\n",yytext); } ]
%% IDENT [_attr]
UNKNOWN [+]
int UNKNOWN [=]
main(void) IDENT [var1]
{ UNKNOWN [;]
yylex(); NEW_LINE [
return(0); ]
} $

& enib, F.H . . . 10/44 %

' $
A. lexicale en Flex
Un analyseur plus conventionnel — 1/2
%{ $ cat [Link]
#include <string.h> var1=123*45.67;
enum {INTEGER=1,REAL,IDENT,NEW_LINE,UNKNOWN}; _attr+=var1;
char globalValue[0x100]; $ ./prog < [Link]
%} IDENT [var1]
UNKNOWN [=]
%option noyywrap INTEGER [123]
UNKNOWN [*]
integer [0-9]+ REAL [45.67]
real [0-9]+\.[0-9]*|\.[0-9]+ UNKNOWN [;]
ident [a-zA-Z_][0-9a-zA-Z_]* NEW_LINE [
]
%% IDENT [_attr]
UNKNOWN [+]
{real} { strcpy(globalValue,yytext); return(REAL); } UNKNOWN [=]
{integer} { strcpy(globalValue,yytext); return(INTEGER); } IDENT [var1]
{ident} { strcpy(globalValue,yytext); return(IDENT); } UNKNOWN [;]
\n { strcpy(globalValue,yytext); return(NEW_LINE); } NEW_LINE [
. { strcpy(globalValue,yytext); return(UNKNOWN); } ]
END_OF_FILE
%% $
& enib, F.H . . . 11/44 %

' $
A. lexicale en Flex
Un analyseur plus conventionnel — 2/2

int
main(void)
{
int token;
do
{
token=yylex();
switch(token)
{
case 0: fprintf(stderr,"END_OF_FILE\n"); break;
case INTEGER: fprintf(stderr,"INTEGER [%s]\n",globalValue); break;
case REAL: fprintf(stderr,"REAL [%s]\n",globalValue); break;
case IDENT: fprintf(stderr,"IDENT [%s]\n",globalValue); break;
case NEW_LINE: fprintf(stderr,"NEW_LINE [%s]\n",globalValue); break;
case UNKNOWN: fprintf(stderr,"UNKNOWN [%s]\n",globalValue); break;
}
} while(token);
return(0);
}

& enib, F.H . . . 12/44 %

' $
A. lexicale en Flex
Une calculette à pile — 1/2
%{ $ cat [Link]
#include <iostream> 1 2 +
#include <vector> 4 *
using namespace std; 5 10 - @/
enum {VALUE=1,PLUS,MINUS,MULT,DIV}; $ ./prog [Link]
double val; --> 1
%} --> 1 2
--> 3
%option noyywrap --> 3 4
--> 12
integer [0-9]+ --> 12 5
real [0-9]+\.[0-9]*|\.[0-9]+ --> 12 5 10
value {integer}|{real} --> 12 -5
lexical error: @
%% --> -2.4
{value} { sscanf(yytext,"%lf",&val); return(VALUE); } --> -2.4
"+" { return(PLUS); } $
"-" { return(MINUS); }
"*" { return(MULT); }
"/" { return(DIV); }
[ \t\n]+ { /* nothing to be done */ }
. { cerr << "lexical error: " << yytext << endl; }
&
%% %
enib, F.H . . . 13/44

' $
A. lexicale en Flex
Une calculette à pile — 2/2
int main(int argc,char ** argv)
{
vector<double> s;
int token;
if(argc>1) yyin=fopen(argv[1],"r"); // check result !!!
do
{
double x1,x2;
token=yylex();
switch(token)
{
case VALUE: s.push_back(val); break;
case PLUS: x2=[Link](); s.pop_back(); x1=[Link](); s.pop_back();
s.push_back(x1+x2); break;
case MINUS: /* ... x1-x2 ... */ break;
case MULT: /* ... x1*x2 ... */ break;
case DIV: /* ... x1/x2 ... */ break;
}
cerr << "-->"; for(size_t i=0;i<[Link]();i++) { cerr << " " << s[i]; } cerr << endl;
} while(token);
return(0);
}
& enib, F.H . . . 14/44 %
' $
A. lexicale en Flex
Les start-conditions

. Conditions inclusives
 %s name dans les options, <name>ER dans les règles de production
 Les règles qui commencent par <name> ou sans <> sont valables quand
on est dans la condition name
. Conditions exclusives
 %x name dans les options, <name>ER dans les règles de production
 Seules les règles qui commencent par <name> sont valables quand on
est dans la condition name
. Changement de condition
 BEGIN(name) dans le code C place l’analyseur dans la condition name
 BEGIN(INITIAL) pour revenir dans l’état de départ (règles sans <>)

& enib, F.H . . . 15/44 %

' $
A. lexicale en Flex
Reconnaı̂tre des chaı̂nes C — 1/3

%{ $
#include <iostream> $ cat [Link]
#include <string> 123
using namespace std; "ab\tcd\n456\"hello"
enum {STRING=1,INTEGER}; 789 "toto
string val; $ ./prog [Link]
int nbLines; INTEGER[123]
%} STRING[ab cd
456"hello]
%option noyywrap INTEGER[789]
multi-line strings not allowed
%x strEnv STRING[toto]
3 lines
integer [0-9]+ $

%%

& enib, F.H . . . 16/44 %

' $
A. lexicale en Flex
Reconnaı̂tre des chaı̂nes C — 2/3

{integer} { val=yytext; return(INTEGER); }

"\"" { [Link](); BEGIN(strEnv); }
<strEnv>"\"" { BEGIN(INITIAL); return(STRING); }
<strEnv>"\\a" { val+=’\a’; }
<strEnv>"\\b" { val+=’\b’; }
<strEnv>"\\f" { val+=’\f’; }
<strEnv>"\\n" { val+=’\n’; }
<strEnv>"\\r" { val+=’\r’; }
<strEnv>"\\t" { val+=’\t’; }
<strEnv>"\\v" { val+=’\v’; }
<strEnv>"\\\\" { val+=’\\’; }
<strEnv>"\\\"" { val+=’\"’; }
<strEnv>"\n" { cerr << "multi-line strings not allowed" << endl; ++nbLines; }
<strEnv>"\\\n" { val+=’\n’; ++nbLines; } // line cut by \
<strEnv>"\\". { val+=yytext[1]; }
<strEnv><<EOF>> { BEGIN(INITIAL); return(STRING); }
<strEnv>. { val+=yytext[0]; }
[ \t]+ { /* nothing to be done */ }
"\n" { ++nbLines; }
. { cerr << "lexical error: " << yytext << endl; }

& enib, F.H . . . 17/44 %

' $
A. lexicale en Flex
Reconnaı̂tre des chaı̂nes C — 3/3

%%
int main(int argc,char ** argv)
{
int token;
if(argc>1) yyin=fopen(argv[1],"r"); // check result !!!
do
{
token=yylex();
switch(token)
{
case STRING: cerr << "STRING[" << val << "]" << endl; break;
case INTEGER: cerr << "INTEGER[" << val << "]" << endl; break;
}
} while(token);
cerr << nbLines << " lines" << endl;
return(0);
}

& enib, F.H . . . 18/44 %

' $
A. lexicale en Flex
Quelques remarques
. Utilisation de variables globales (internes et applicatives)
 Chaque invocation analyse la suite du flux, l’état est sauvé
 Plusieurs analyseurs différents → PB à l’édition de liens
 Non réentrant → PB si plusieurs analyses simultanées
. L’ordre des règles est important
 Commencer par le plus spécifique, finir par le plus général
ex : {ident} doit être pris en compte après les mot-clefs
 La plus longue correspondance est tout de même preférée
ex : form est reconnu comme un {ident} même si le mot-clef
for est testé avant.
. Beaucoup d’autres options, fonctions, macros, variables
 Le minimum est vu ici, très proche du Lex originel
 Permettent des horreurs, ou de contourner certaines limitations
& enib, F.H . . . 19/44 %

'
A. syntaxique en Bison $

Structure d’un programme Bison

Fichier Bison Fichier C généré
%{ Déclarations, macros

Pré−code C Copie du pré−code C

%} Tables d’analyse

Définitions et options int yyparse(void)

{
%% ...
Copie du code C
Règles de production ...
}
%% Autres fonctions ...
Post−code C Copie du post−code C

. Pré/post-code C : du C tout à fait classique

. Options : %quelquechose pour paramétrer le fonctionnement
. Définitions : %autrechose pour définir les lexèmes, les priorités . . .
. Règles de production : Règles de grammaires et code C à exécuter
& enib, F.H . . . 20/44 %
'
A. syntaxique en Bison $

Syntaxe Bison
. Règles de production
 non terminal : sequence de symboles { /* code C */ }
| autre sequence { /* code C */ }
| ...
;
 Les symboles sont représentés par des identificateurs
◦ Terminaux : lexèmes provenant de l’analyse lexicale
◦ Non-terminaux : symboles internes à l’analyseur syntaxique
 Le code C est optionnel et est exécuté lorsque la règle est réduite
program : START instList END { cerr << "program" << endl; }
;
instList : instList inst
| inst
;
inst : IDENT ASSIGN expr SEMICOLON { cerr << "inst" << endl; }
;
expr : INTEGER { cerr << "integer expr" << endl; }
| REAL { cerr << "real expr" << endl; }
| IDENT { cerr << "ident expr" << endl; }
;
& enib, F.H . . . 21/44 %

'
A. syntaxique en Bison $

L’analyseur généré
. La fonction int yyparse(void)
 Consomme les lexèmes obtenus par des appels à yylex() (à fournir)
int yylex(void);
 Vérifie (LALR(1)) si la séquence de lexèmes permet de réduire l’axiome
de la grammaire exprimée
(%start non terminal dans les définitions)
 Exécute les actions sémantiques (code C ) associées aux règles réduites
 Signale les erreurs à l’aide de la fonction yyerror() (à fournir)
void yyerror(const char * msg);
◦ Possibilité de récupération sur erreur pour poursuivre l’analyse
 Jusqu’à ce que l’axiome de la grammaire soit reconnu ou erreur
. La valeur de retour
 0 si ok, 1 si erreur
 Résultat de l’analyse complète → une seule invocation
& enib, F.H . . . 22/44 %
'
A. syntaxique en Bison $

Association Flex/Bison
. Flex fourni les lexèmes à Bison
 Bison invoque la fonction yylex() produite par Flex
 yylex() doit renvoyer des constantes connues de Bison
→ %token IDENT INTEGER ... dans les définitions de Bison
 Bison genère un .h definissant ces constantes (et d’autres choses)
 Le pré-code C de Flex inclu ce .h
. Étapes de la construction :
 $ bison -d -[Link] prog.y
→ Produit le code C [Link] depuis le fichier Bison prog.y
→ Option -d pour générer le .h [Link]
 $ flex -[Link] prog.l
→ Produit le code C [Link] depuis le fichier Flex prog.l
→ Le pré-code C doit inclure [Link]
 $ g++ -oprog [Link] [Link]
& enib, F.H . . . 23/44 %

'
A. syntaxique en Bison $

Analyse syntaxique simple — 1/4

%{ /*-------- prog.l --------*/
extern int lineNumber; // definie dans prog.y, utilise par notre code pour \n
void yyerror(const char * msg); // definie dans prog.y, utilise par notre code pour .
#include "[Link]" // genere par prog.y --> constantes START, END ...
%}
%option noyywrap
integer [0-9]+
real [0-9]+\.[0-9]*|\.[0-9]+
ident [a-zA-Z_][0-9a-zA-Z_]*
%%
"start" { return(START); }
"end" { return(END); }
":=" { return(ASSIGN); }
";" { return(SEMICOLON); }
{ident} { return(IDENT); }
{real} { return(REAL); }
{integer} { return(INTEGER); }
"\n" { ++lineNumber; }
[ \t]+ { /* nothing to be done */ }
. { char msg[0x20]; sprintf(msg,"lexical error <%s>",yytext); yyerror(msg); }
%%
& enib, F.H . . . 24/44 %
' A. syntaxique en Bison $

Analyse syntaxique simple — 2/4

%{ /*-------- prog.y --------*/

#include <stdio.h>
#include <iostream>
using namespace std;

int yylex(void); // defini dans [Link], utilise par yyparse()

void yyerror(const char * msg); // defini plus loin, utilise par yyparse()

int lineNumber; // notre compteur de lignes

extern FILE * yyin; // defini dans [Link], utilise par main()
%}

%token START END // les lexemes que doit fournir yylex()

%token ASSIGN SEMICOLON
%token IDENT REAL INTEGER

%start program // l’axiome de notre grammaire

%%

& enib, F.H . . . 25/44 %

' A. syntaxique en Bison $

Analyse syntaxique simple — 3/4

program : START instList END { cerr << "program" << endl; }
;
instList : instList inst
| inst
;
inst : IDENT ASSIGN expr SEMICOLON { cerr << "inst" << endl; }
;
expr : INTEGER { cerr << "integer expr" << endl; }
| REAL { cerr << "real expr" << endl; }
| IDENT { cerr << "ident expr" << endl; }
;
%%
void yyerror(const char * msg)
{
cerr << "line " << lineNumber << ": " << msg << endl;
}
int main(int argc,char ** argv)
{
if(argc>1) yyin=fopen(argv[1],"r"); // check result !!!
lineNumber=1;
if(!yyparse()) cerr << "Success" << endl;
return(0);
&
} %
enib, F.H . . . 26/44
'
A. syntaxique en Bison $

Analyse syntaxique simple — 4/4

$ bison -d -[Link] prog.y
$ flex -[Link] prog.l
$ g++ -oprog [Link] [Link]
$
$ cat [Link] $ cat [Link] $ cat [Link]
start start start
a := 1 ; a := -1 ; a := 1 ;
b := 2.3 ; b := 2,3 ; b := 2.3 ;
c := a ; c := a ; c := a ;
end end end
$ ./prog [Link] $ ./prog [Link] and then ...
integer expr line 2: lexical error <-> $ ./prog [Link]
inst integer expr integer expr
real expr inst inst
inst integer expr real expr
ident expr line 3: lexical error <,> inst
inst line 3: parse error ident expr
program $ inst
Success program
$ line 6: parse error
$
& enib, F.H . . . 27/44 %

'
A. syntaxique en Bison $

Valeurs associées aux symboles

. Chaque symbole peut contenir une valeur
 Au-delà de l’analyse syntaxique → analyse sémantique
 %union{ ... } dans les définitions de Bison (union C )
. Valeur d’un symbole → un seul champ de l’union
 %type<nom champ> symboles dans les définitions de Bison
. Accès aux valeurs depuis Bison
 Dans le code associé à non terminal : symboles
 $$ valeur associée au non-terminal de la partie gauche (écriture)
 $1 valeur associée au premier symbole de la partie droite (lecture)
 $2 , $3 . . . pour les autres symboles de la partie droite
 Si pas de code C → équivalent de {$$=$1;} par défaut
◦ Attention aux %type → warnings
◦ Inhiber avec du code vide {}
& enib, F.H . . . 28/44 %
' A. syntaxique en Bison $

Initialiser la valeur associée à un lexème

. Variable globale yylval de type %union

 Déclarée dans le .h généré par Bison
 yylex() doit initialiser cette variable
 yyparse() récupere cette valeur juste après l’appel à yylex()
. Choix du champ de l’union
 yylex() ne connait pas les %type
 Initialiser dans yylval le champ indiqué par le %type du lexème
◦ Aucune vérification de la cohérence par les outils !
◦ Responsabilité du programmeur

& enib, F.H . . . 29/44 %

' A. syntaxique en Bison $

Analyse syntaxique avec passage de valeurs — 1/2

%{ /*-------- prog.l --------*/ $ bison -d -[Link] prog.y
/* idem ‘‘Analyse syntaxique simple’’ */ $ flex -[Link] prog.l
%} $ g++ -oprog [Link] [Link]
%option noyywrap $ cat [Link]
integer [0-9]+ start
real [0-9]+\.[0-9]*|\.[0-9]+ a := 1 ;
ident [a-zA-Z_][0-9a-zA-Z_]* b := 2.3 ;
%% c := a ;
"start" { return(START); } end
"end" { return(END); } $ ./prog [Link]
":=" { return(ASSIGN); } integer 1
";" { return(SEMICOLON); } assign a with i:1
{ident} { sprintf([Link],"%s",yytext); real 2.3
return(IDENT); } // %type<str> IDENT assign b with r:2.3
{real} { sscanf(yytext,"%lf",&[Link]); ident a
return(REAL); } // %type<real> REAL assign c with s:a
{integer} { sscanf(yytext,"%d",&[Link]); program
return(INTEGER); } // %type<integer> INTEGER Success
"\n" { ++lineNumber; } $
[ \t]+ { /* nothing to be done */ }
. { char msg[0x20]; sprintf(msg,"lexical error <%s>",yytext); yyerror(msg); }
%%
& enib, F.H . . . 30/44 %
' A. syntaxique en Bison $

Analyse syntaxique avec passage de valeurs — 2/2

%{ /*-------- prog.y --------*/
/* idem ‘‘Analyse syntaxique simple’’ */
%}
%token START END ASSIGN SEMICOLON IDENT REAL INTEGER
%union { char str[0x100]; double real; int integer; }
%type<str> IDENT expr
%type<real> REAL
%type<integer> INTEGER
%start program
%%
program : START instList END { cerr << "program" << endl; }
;
instList : instList inst
| inst
;
inst : IDENT ASSIGN expr SEMICOLON { cerr << "assign " << $1 << " with " << $3 << endl; }
;
expr : INTEGER { cerr << "integer " << $1 << endl; sprintf($$,"i:%d",$1); }
| REAL { cerr << "real " << $1 << endl; sprintf($$,"r:%g",$1); }
| IDENT { cerr << "ident " << $1 << endl; sprintf($$,"s:%s",$1); }
;
%%
&
/* idem ‘‘Analyse syntaxique simple’’ */ %
enib, F.H . . . 31/44

' A. syntaxique en Bison $

Une calculette à pile . . . sans pile ! — 1/2

%{ /*-------- prog.l --------*/ $ bison -d -[Link] prog.y
/* idem ‘‘Analyse syntaxique simple’’ */ $ flex -[Link] prog.l
%} $ g++ -oprog [Link] [Link]
%option noyywrap $ echo "1 2 + 4 * 5 10 - /" | ./prog
integer [0-9]+ value=1
real [0-9]+\.[0-9]*|\.[0-9]+ value=2
value {integer}|{real} 1+2=3
%% value=4
{value} { 3*4=12
sscanf(yytext,"%lf",&[Link]); value=5
return(VALUE); value=10
} 5-10=-5
"+" { return(PLUS); } 12/-5=-2.4
"-" { return(MINUS); } Result: -2.4
"*" { return(MULT); } Success
"/" { return(DIV); } $
"\n" { ++lineNumber; }
[ \t]+ { /* nothing to be done */ }
. { char msg[0x20]; sprintf(msg,"lexical error <%s>",yytext);
yyerror(msg);
}
%%
& enib, F.H . . . 32/44 %
'
A. syntaxique en Bison $

Une calculette à pile . . . sans pile ! — 2/2

%{ /*-------- prog.y --------*/
/* idem ‘‘Analyse syntaxique simple’’ */
%}
%token VALUE PLUS MINUS MULT DIV
%union
{
double val;
}
%type<val> VALUE expr
%start calc
%%
calc : expr { cerr << "Result: " << $1 << endl; }
;
expr : VALUE { $$=$1; cerr << "value=" << $1 << endl;}
| expr expr PLUS { $$=$1+$2; cerr << $1 << "+" << $2 << "=" << $$ << endl; }
| expr expr MINUS { $$=$1-$2; cerr << $1 << "-" << $2 << "=" << $$ << endl; }
| expr expr MULT { $$=$1*$2; cerr << $1 << "*" << $2 << "=" << $$ << endl; }
| expr expr DIV { $$=$1/$2; cerr << $1 << "/" << $2 << "=" << $$ << endl; }
;
%%
/* idem ‘‘Analyse syntaxique simple’’ */
& enib, F.H . . . 33/44 %

'
A. syntaxique en Bison $

Les conflits de la grammaire

. Conflit réduire/réduire
 À un certain stade de l’analyse, le lexème suivant ne permet pas
de dire s’il faut réduire une règle ou bien une autre
→ modifier la grammaire pour lever l’ambiguité
 Doit toujours être éliminé !
. Conflit décaler/réduire
 À un certain stade de l’analyse, le lexème suivant ne permet pas
de dire s’il faut réduire une règle ou bien continuer à décaler pour
reconnaitre une règle plus longue
→ modifier la grammaire pour lever l’ambiguité
 Doit toujours être éliminé (sauf circonstances exceptionnelles) !
→ Bison fait le choix du décalage !
. L’analyseur regarde toujours un lexème à l’avance
 Permet de retarder le choix
& enib, F.H . . . 34/44 %
'
A. syntaxique en Bison $

Exemples triviaux de conflits réduire/réduire

%token A1 B1 %token A2 B2 C2 D2 %token A3 B3 C3
%start g1 %start g2 %start g3
%% %% %%
g1 : e1 B1 g2 : e2 B2 C2 g3 : e3 B3
| f1 B1 | f2 B2 D2 | f3 C3
; ; ;
e1 : A1 e2 : A2 e3 : A3
; ; ;
f1 : A1 f2 : A2 f3 : A3
; ; ;
. Cas 1 : réduire A1 en e1 ou f1 ?
 Après A1 : e1 -> A1 . et f1 -> A1 .
 Le lexème suivant (B1) ne permet pas de choisir !
. Cas 2 : réduire A2 en e2 ou f2 ?
 Idem, il faudrait repousser le choix à deux lexèmes (C2 ou D2)
. Cas 3 : pas de conflit !
 Le lexème suivant A3 (B3 ou C3) permet de choisir !
& enib, F.H . . . 35/44 %

'
A. syntaxique en Bison $

Exemples triviaux de conflits décaler/réduire

%token A1 B1 %token A2 B2 C2 D2 %token A3 B3 C3

%start g1 %start g2 %start g3
%% %% %%
g1 : e1 B1 g2 : e2 B2 C2 g3 : e3 B3
| A1 B1 | A2 B2 D2 | A3 C3
; ; ;
e1 : A1 e2 : A2 e3 : A3
; ; ;

. Cas 1 : réduire A1 en e1 ou décaler pour g1 -> A1 B1 ?

 Après A1 : g1 -> A1 . B1 et e1 -> A1 .
 Le lexème suivant (B1) ne permet pas de choisir !
. Cas 2 : réduire A2 en e2 ou décaler pour g2 -> A2 B2 D2 ?
 Idem, il faudrait repousser le choix à deux lexèmes (C2 ou D2)
. Cas 3 : pas de conflit !
 Le lexème suivant A3 (B3 ou C3) permet de choisir !

& enib, F.H . . . 36/44 %

'
A. syntaxique en Bison $

Exemples de conflits classiques

%token A1 B1 instr : ifInstr SEMICOLON

%start list | LB instrList RB
%% | ...
list : list elem ;
| /* empty */ instrList : instrList instr
; | /* empty */
elem : A1 ;
| B1 ifInstr : IF LP cond RP instr
| /* empty */ | IF LP cond RP instr ELSE instr
; ;

. Zéro ou plusieurs éléments

 Deux fois le cas vide (réduire/réduire) → retirer elem -> ε
. Décaler/réduire dans if/else
 if(c1)if(c2)f();else g(); → if(c1){if(c2)f();}else g(); ?
→ if(c1){if(c2)f();else g();} ?
 Le décalage par défaut est correct ! → on ne change rien !

& enib, F.H . . . 37/44 %

'
A. syntaxique en Bison $

Repérer les conflits

. Générer une description du procédé d’analyse

 bison -v -[Link] progY.l produit [Link] (-v)
 Début du fichier : conflits avec numéro de l’état où ils se situent
 Juste après : récapitulatif des règles, terminaux et non terminaux
 Toute la suite : les différents états de l’analyseur
◦ État d’avancement dans la reconnaissance des règles
◦ Actions possibles (décaler, réduire) selon les symboles reconnus
State 1 contains 1 shift/reduce conflict.
...
state 1
g1 -> A1 . B1 (rule 2)
e1 -> A1 . (rule 3)

B1 shift, and go to state 3

B1 [reduce using rule 3 (e1)]
$default reduce using rule 3 (e1)
...
& enib, F.H . . . 38/44 %
'
A. syntaxique en Bison $

Associativité et précédence

. Permettent d’éliminer facilement les conflits

 %left, %right ou %nonassoc dans les définitions de Bison
 Indique l’associativité du ou des lexèmes indiqués sur la ligne
 Ces lignes sont triées selon les priorités croissantes
 %prec pour substituer une priorité dans la grammaire
 Les conflits résolus sont tout de même reportés dans le .output
 ex : expressions arithmétiques et logiques
%left OR
%left AND
%right NOT
%nonassoc LT GT LE GE EQ NEQ
%left PLUS MINUS
%left MULT DIV MODULO
%right UMINUS

& enib, F.H . . . 39/44 %

'
A. syntaxique en Bison $

Expressions arithmétiques et logiques — 1/3

%token OR AND NOT expr : expr OR expr
%token LT GT LE GE EQ NEQ | expr AND expr
%token PLUS MINUS | NOT expr
%token MULT DIV MODULO | expr LT expr
%token VALUE LP RP | expr GT expr
| expr LE expr
%start expr | expr GE expr
%% | expr EQ expr
| expr NEQ expr
| expr PLUS expr
| expr MINUS expr // - binaire
| expr MULT expr
| expr DIV expr
| expr MODULO expr
| MINUS expr // - unaire
| VALUE
| LP expr RP
;

$ bison -v prog.y
prog.y contains 195 shift/reduce conflicts.
$
& enib, F.H . . . 40/44 %
'
A. syntaxique en Bison $

Expressions arithmétiques et logiques — 2/3

%token PLUS MINUS
%token MULT DIV MODULO
%token VALUE LP RP

%start expr
%%
expr : expr PLUS prod // associativite a gauche
| expr MINUS prod // operations les moins prioritaires
| prod
;
prod : prod MULT factor // associativite a gauche
| prod DIV factor // operations un peu plus prioritaires
| prod MODULO factor
| factor
;
factor : VALUE // constructions les plus prioritaires
| LP expr RP
;

$ bison -v prog.y --> pas de conflits mais demarche tres fastidieuse !!!
$
& enib, F.H . . . 41/44 %

'
A. syntaxique en Bison $

Expressions arithmétiques et logiques — 3/3

%token OR AND NOT expr : expr OR expr
%token LT GT LE GE EQ NEQ | expr AND expr
%token PLUS MINUS | NOT expr
%token MULT DIV MODULO | expr LT expr
%token VALUE LP RP | expr GT expr
| expr LE expr
%left OR | expr GE expr
%left AND | expr EQ expr
%right NOT | expr NEQ expr
%nonassoc LT GT LE GE EQ NEQ | expr PLUS expr
%left PLUS MINUS | expr MINUS expr // - binaire
%left MULT DIV MODULO | expr MULT expr
%right UMINUS | expr DIV expr
| expr MODULO expr // yylex() ne renvoie
%start expr | MINUS expr %prec UMINUS // jamais UMINUS !!!
%% | VALUE // --> subst. de prio.
| LP expr RP
;

$ bison -v prog.y --> conflits resolus facilement par les %left %right %nonassoc
$
& enib, F.H . . . 42/44 %
'
A. syntaxique en Bison $

Récupération sur erreurs

. Entrée non-conforme à la grammaire
 Appel automatique de yyerror("parse error")
 yyparse() se termine en renvoyant 1
 La suite du flux d’entrée n’est pas analysée !
. Le symbole spécial error
 Permet d’enrichir la grammaire
 Lorsqu’aucune règle ne permet de poursuivre l’analyse
→ réduire celle qui utilise error
 Synchronisation sur le lexème qui suit le symbole error
→ consommation des lexèmes intermédiaires
 Utilisation de la macro yyerrok; dans le code C
→ évite la sortie de yyparse() après le message
assign : IDENT ASSIGN expr SEMICOLON { /* ... */ }
| IDENT ASSIGN error SEMICOLON { yyerrok; }
;
& enib, F.H . . . 43/44 %

'
A. syntaxique en Bison $

Démarche usuelle pour la mise en œuvre

. Mise au point de l’analyse lexical
 Fichier Flex complet : reconnaı̂tre tous les lexèmes
 Fichier Bison avec une grammaire dégénérée
◦ Accepter tous les lexèmes dans un ordre quelconque
◦ Actions sémantiques : afficher le lexème reçu
. Mise au point de l’analyse syntaxique
 Grammaire complète du langage à reconnaı̂tre
 Actions sémantiques : afficher les constructions reconnues
. Mise en place des actions sémantiques
 Construire/calculer les données utiles pour l’application
. Envisager la récupération sur erreurs
 Rend la grammaire plus complexe ! → À effectuer en dernier lieu
& enib, F.H . . . 44/44 %