Un fichier en quatre parties
Un fichier-yacc (fichier source pris en entrée par Yacc) contient quatre parties successives :
-
Déclarations (partie facultative) :
code C(1) préalable
(inclusions, déclarations, etc.).
Cette partie commence par %{
et finit par %} chacun
de ces délimiteurs devant être écrit sur une ligne
ne contenant rien d'autre(2).
Toutes les lignes de code C écrites entre ces deux délimiteurs
seront directement recopié par Yacc au début du fichier source
y.tab.c.
-
Définitions (partie facultative)
Cette partie contient les définitions opératoires (lignes commençant
par %), les définitions
de lexèmes (=tokens =unités lexicales) et la table de précédence.
-
Règles (=productions)
Cette partie, qui est la seule obligatoire, commence par le délimitateur
%%
écrit seul dans sa ligne(2). Elle contient une suite de règles de
productions. Chaque règle est suivie, après un (ou plusieurs)
espace(s) et/ou tabulation(s), du code C(1) qui lui est associé.
Ce code utilise des variables prédéfinies : $$, $1, ..., appelées
souvent variables-dollar.
Le code est réduit à un point-virgule s'il n'y a pas d'action associée à la règle.
-
Code utilisateur.(partie facultative)
Cette partie commence par le délimiteur
%%
seul dans sa ligne(2).
Toutes les lignes de code C(1) écrites après
seront directement recopiées par Yacc dans le fichier y.tab.c.
Cette partie permet notamment de redéfinir les fonctions yylex()
(si on n'utilise pas Lex) et main() (si on n'utilise pas la fonction main()
fournit par l'option de compilation −ly).
Byacc et Bison sont des variantes de Yacc.
(1) Dans les parties où il faut ajouter du code,
on peut placer du code C++, y.tab.c sera alors compilé avec un compilateur
C++. Mais le code produit automatiquement par Lex restera du code C,
(ce qui peut produire quelques difficultés supplémentaires).
(2)
Pour être plus précis, ce délimiteur doit seulement être placé en
début de ligne (sans indentation).
Je conseille ces précautions supplémentaires
car la présence d'espace ou de tabulations "mal" placées,
voire de caractères masqués (gare aux copier-coller et aux
FTP!) dans le fichier-yacc peut perturber le travail de Yacc. Ce manque
de robustesse et de convivialité est un des défauts de Yacc,
comme de Lex.
Deux exemples de fichiers-yacc :
Exemple 1 (Yacc sans Lex)
fichier exp1.yacc
%%
MOT : S '\n' { printf("mot accepté\n"); YYACCEPT; }
S : 'a' S 'b'
| 'b' 'a'
;
%%
// définition de yylex()
int yylex() {
char C=getchar();
if (C=='a'||C=='b'||C=='\n') {return(C);}
else { printf("%c: inconnu\n",C); exit(-1); }
}
Exemple 2 (Yacc avec Lex)
fichier-lex exp2.lex
%{
#include "y.tab.h"
%}
%%
[aA] return lettreA;
[bB] return lettreB;
\n return finligne;
. return erreurlexicale;
fichier-yacc exp3.yacc
%token finligne
%token lettreA
%token lettreB
%token erreurlexicale
%%
MOT : S finligne { printf("mot accepté\n"); YYACCEPT; }
;
S : lettreA S lettreB
| lettreB lettreA
;
Précisions sur les parties de Yacc
1e partie : Le code préalable
Comme pour Lex, il sert essentiellement à insérer des directives de précompilation C (#ifdef, ...),
à inclure des bibliothèques et des sources extérieurs (#include, ...),
et à déclarer des variables et constantes globales.
On peut aussi y définir les fonctions et procédures qui serviront dans le code associé aux
expressions (troisième partie) et/ou dans le code utilisateur (quatrième partie).
On peut ajouter dans cette partie une ligne redéfinissant le
type de la variable externe yylval. Cette variable est utilisée
par Lex pour transmettre la valeur d'un token. yylval est de type YYTYPE
qui est par défaut le type int. YYTYPE peut être redéfinit dans cette
partie, par exemple comme un réel en utilisant #define YYSTYPE float.
Si on veut redéfinir ce type comme une union, il faudra par contre le faire dans la deuxième
partie avec la déclaration %union (voir l'exemple 4).
2e partie : Les définitions
2.1. Le départ de la grammaire
Le non-terminal de départ de la grammaire
est normalement le non-terminal situé dans le membre gauche de la première règle
écrite dans la troisième partie (il s'agit de MOT dans les exemples 1 et 2,
mais on choisit souvent S comme en théorie des langages).
On peut décider qu'un autre non-terminal définit le départ de la grammaire
avec : %start D,
où D est un non-terminal présent à gauche d'au moins une règle.
2.2. La définition des tokens
Les tokens sont – avec les caractères explicites,
écrits entre apostrophes, comme dans l'exemple 1 –
les terminaux de la grammaire contenue dans la troisième partie du fichier-yacc.
Du point de vu de la théorie des langages, les tokens sont les éléments de
l'alphabet sur lequel est construit le langage algénrique reconnu par un fichier-yacc.
Ils sont définis, comme dans l'exemple 3(3), par la déclaration
%token suivie d'un ou plusieurs noms de token. Si on veut utiliser une
union pour avoir plusieurs types de tokens, il faudra préciser leur type au moment
de leur définition comme dans l'exemple 4.
Les tokens sont au coeur de l'interfaçage de Lex et Yacc.
Exemple 3 : définition de tokens
%token plus moins multi divi uminus
%token nombre
(3)
La numérotation du code de ces définitions commence à 257,
les valeurs précédentes étant conservées pour
les caractères utilisés en tant que tel.
Dans l'exemple 3, les définitions de token seront traduites en C par :
#define plus 257
#define moins 258
#define multi 259
#define divi 260
#define uminus 261
#define nombre 262
Exemple 4 : typage des terminaux et non-terminaux
%union {char* chaine; int entier;}
%token <entier> nombre
%token <chaine> identificateur
%type <entier> Operation
%type <entier> S
Dans cet exemple, le token nombre est de type int,
alors que le token identificateur est de type char*, de
même que les non-terminaux S et Operation.
2.3. La définition d'une table de précédence
La table de précédence permet de résoudre certaines ambiguïtés de la grammaire placée dans le
fichier-yacc en précisant d'éventuelles règles d'associativité (%left, %right, %nonassoc)
et en ordonnant certains tokens (le premier de la table est le moins prioritaire).
Cela permet notamment de préciser les priorités d'opérateurs, comme dans l'exemple ci-dessous.
Exemple 5 : priorité entre quatre opérateurs numériques
%left plus moins
%left multi divi
%nonassoc uminus
Dans cet exemple, les tokens plus, moins,
multi, etdivi, sont associatif à gauche
(càd (a plus b plus c) sera interprété comme
((a plus b) plus c), et pas comme (a plus (b plus c) )
qui correspondrait à l'associativité à droite).
Le token unminus (moins unaire indiquant le signe, par opposition au moins binaire de la
soustraction) n'est pas associatif. De plus, un ordre croissant de priorité est défini depuis
plus et moins (de même niveau de priorité), passant par
multi et divi, et jusqu'à unminus.
Ainsi, (a plus b multi c) sera interprété comme
(a plus (b multi c)) et pas comme ((a plus b) multi c).
3e partie : Les régles
3.1. Les règles de production
Les règles de production dans un fichier-yacc sont
écrites sur un modèle semblable aux règles de productions
d'une grammaire formelle (la flèche est remplacée par un
deux-points). Elles sont terminées par un point-virgule. Le non-terminal
de gauche de la première règle est le symbole de départ
de l'analyse (sauf spécification contraire par %start).
Les règles peuvent être factorisées avec l'opérateur | comme en théorie des langages.
Exemple 6.a : interprétation des règles de Yacc.
| Règles de production de yacc : |
Règles formelles correspondantes : |
S : ADDition
| DIFFerence
| nombre
;
ADDition : S plus S ;
;
DIFFerence : S moins S ;
;
|
S→A
S→D
S→n (càd S→A|D|n)
A→SpS
D→SmS
|
N.B. Dans cet exemple, le fichier-yacc respecte
la convention de la théorie des langages nomme les terminaux par une minuscule et les non-terminaux par une majuscule.
Il est fortement conseillé de conserver cette convention pour Yacc, en écrivant les terminaux (=les tokens) en minuscules
et les non-terminaux par une majuscule ou un mot commençant par une majuscule.
On évitera donc la convention d'AT&T pour Yacc qui écrit les terminaux en majuscules et les non-terminaux en minuscules ;
on retrouve malheureusement cette convention dans le langage C avec des constantes écrites en majuscules.
3.2. Code associé
A chaque règle, on peut faire correspondre un ensemble d'actions
(principe des grammaires augmentées) programmées en C. L'action
par défaut associée à une règle est $$=$1;
(voir ci-dessous).
Yacc utilise des variables prédéfinies préfixées par $ et appelées souvent
"variables-dollar" :
$$ : représente la valeur associée au
on-terminal qui est le membre de gauche d'une production et elle est transmise par lui,
$1, $2, $3... : représentent
le contenu des éléments successifs (terminaux ou non-terminaux) du membre droit de la
production.
|
On peut ainsi, non seulement transférer des valeurs de l'analyseur
lexical vers l'analyseur syntaxique (voir le rôle de yylval dans
Lex), mais aussi
propager ces valeurs d'une règle à l'autre de l'analyseur
syntaxique. Le passage des valeurs de la partie droite d'une règle vers sa
partie gauche correspondant au mécanisme ascendant de l'analyse grammatical
LALR pratiquée par Yacc, comme le montre les deux exemples ci-dessous
(voir aussi le cours de compilation).
Exemple 6.b : utilisation des variables-dollar
| Règles de production de yacc : |
Actions associées : |
S : ADDition
| DIFFerence
| nombre
;
ADDition : S plus S
;
DIFFerence : S moins S
;
|
{$$=$1;}
{$$=$1;}
{$$=yylval;}
{$$=$1+$3}
{$$=$1-$3}
|
Cet exemple permet de calculer le résultat d'une opération.
La valeur de chaque nombre est transmise par l'analyseur lexical grâce
à yylval, puis l'analyseur syntaxique calcule les résultats
d'opérations correspondant aux règles utilisées.
Exemple 6.c : typage des variables-dollar
| Règles de production de yacc : |
Actions associées : |
S : ADDition
| DIFFerence
| nombre
| identificateur
;
ADDition : S plus S
;
DIFFerence : S moins S
;
|
{$$=$1;}
{$$=$1;}
{$$=yylval.entier;}
{$$=valeurTDS(yylval.chaine);;}
{$$=$1+$3}
{$$=$1-$3}
|
Dans cet exemple, on suppose que YYTYPE a été définie comme une union
(%union {int entier; char* chaine;}) et que la fonction
int valeurTDS(char* Identificateur)
a été créée dans la première
partie du fichier-yacc ou du fichier-lex, pour retourner la valeur entière
d'un identificateur dans une table des symboles à créer en
conséquence. L'analyse d'une expression transmettra
de bas en haut la valeur calculée, jusqu'au symbole de départ
S. On s'est bien assuré ici qu'à chaque affectation $$=$1+$3,
les trois variables utilisées sont du même type.
Le code C associé à chaque règle
de production peut contenir des fonctions et procédures prédéfinies
par Yacc :
YYABORT
YYACCEPT
YYERROR
YYBACKUP
yyerrok
|
est équivalent à return 1,
est équivalent à return 0,
est équivalent à RETURN 1,
à éviter!,
est une procédure d'usage délicat.
|
Dans un analyseur LALR comme Yacc (et plus généralement LR), il y
a quatre types d'actions élémentaires d'analyse :
SHIFT
REDUCE
ACCEPT
ERROR
|
pour consommer un terminal (càd l'empiler),
pour réduire une règle de production
(dépiler les membres de la partie droite et empiler la partie gauche)
indique que l'analyse ascendante se termine avec succès
(normalement quand le sommet de la pile d'analyse
est le symbole de départ de la grammaire),
gère l'absence de consommation (SHIFT) ou de réduction (REDUCE)
applicable lors de l'examen d'une règle. Voir dans la suite l'ustilisation du
pseudo-terminal error pour gérer cette situation parfois délicate.
|
3.3. Gestion des conflits et ambiguïtés
Si la grammaire contenue dans le fichier-yacc est bien
une grammaire algébrique (=context-free) de type LALR, ou
si la table de précédence a rajouté des règles
supprimant les ambiguïtés et ramenant la grammaire à
une grammaire de ce type, alors Yacc construit sans problème la
table LALR et l'analyseur syntaxique associé. Dans le cas contraire,
Yacc doit prendre des initiatives et résoudre les conflits entre
les règles de production. Ces conflits, de type shift/reduce ou
reduce/reduce, n'empêchent généralement pas de
créer un analyseur fonctionnel, mais cet analyseur ne réalisera
pas forcément ce qu'on attend de lui (voir le cours de compilation pour plus de
précisions sur la question). En conclusion, le réglage précis
d'une grammaire Yacc peut s'avérer fastidieux et délicat.
Yacc affiche dans stderr :
– le nombre de règle jamais utilisées (never
reduced)
– le nombre de conflits de chaque type (shift/reduce
et reduce/reduce)
Exemple 7 : un conflit reduce/reduce pour le langage a*
X : 'a' X
| 'a'
|
;
Ici, il y a conflit entre X→a et X→ε.
Le conflit est résolu par Yacc en privilégiant la première règle X->a.
Exemple 8 : deux conflits pour le même langage a*
X : 'a' X
|
| 'a'
;
Ici, il y a le même conflit reduce/reduce que dans l'exemple précédent, mais il y a
en plus une règle qui n'est jamais réduite.
Exemple 9 : un conflit shift/reduce pour le langage a*b+a*
X : 'a' X
| X 'a'
| Y
;
Y : 'b' Y
;
Il y a ici un conflit shift/reduce pour le mot "aaa" car il y a plusieurs
dérivation possibles : aaa←aaS←aS←S ou aaa←Saa←Sa←S.
Les règles suivantes sont appliquées par Yacc en cas de conflit :
– conflit shift/reduce : Yacc choisit la consommation
(shift) d'un token, afin d'avancer dans la séquence de terminaux
à analyser,
– conflit reduce/reduce : Yacc réduit la production
placée en premier dans le fichier-yacc.
D'autre part, on a la possibilité supplémentaire de modifier
localement la priorité d'un terminal avec l'instruction %prec, comme
dans l'exemple suivant.
Exemple 10 : une addition qui prend la priorité d'une multiplication.
E : E plus E %prec MULTI
| E moins E
;
Ici, l'expression (3-9+4) sera ici interprété comme
(3-(9+5)) avec priorité à l'addition au lieu de
((3-9)+5) avec priorité identiques des deux opérateurs plus
et moins et donc analyse de gauche à droite.
3.4) Gestion des erreurs
Si l'analyse ne permet pas la reconnaissance d'un mot par
la grammaire (c'est-à-dire quand l'utilisation de la table LALR
aboutit à une impasse), l'analyseur se termine en affichant par
défaut :Syntax error (ce qui correspond
à l'appe yyerror("Syntax error\n");).
Ce comportement peut être changé en redéfinissant la fonction yyerror().
Le pseudo-terminal prédéfini error permet de gérer
les impasses de la table LALR. Ce pseudo-terminal doit être suivi
d'un terminal indiquant où reprendre l'analyse. Il existe diverses
solutions pour gérer les erreurs lexicales ou syntaxiques (voir
notamment dans le paragraphe suivant).
Exemple 11 : reconnaissance du langage (a+b)+
%%
S : D '\n' { printf("j'accepte le mot\n"); YYACCEPT; }
;
D : 'a' 'b'
| D 'a' 'b'
;
%%
// reecriture ici de yylex() comme dans l'exemple 1
Ici, si l'analyseur trouve une erreur, il affiche Syntax
error, sinon, il affiche j'accepte le mot.
Il s'arrête dans les deux cas après l'analyse d'une ligne :
à cause de l'instruction YYACCEPT (=return 0)
s'il a accepté le mot, ou automatiquement par absence de règle de production applicable,
s'il a refusé le mot.
4e partie : le code utilisateur
La compilation de y.tab.c avec l'option
−ly ajoute par défaut dans ce fichier
les fonctions yyerror() et main(), prédéfinies comme :
yyerror(char* s) {fprintf(stderr,s);}
main() {yyparse();}
Ces deux fonctions peuvent être définies directement par
l'utilisateur dans le code final de son fichier-yacc ; la fonction main()
doit obligatoirement contenir un appel à yyparse() qui contient
elle-même les appels nécessaires à yylex().
La fonction yyparse() lance l'analyse syntaxique, la fonction
yylex() étant définie dans le fichier-lex quand Lex
et Yacc sont interfacés. Quand yyparse() utilise une règle
associée à un code contenant return n; l'analyse
se termine (les actions sont intégrées dans le code de yyparse()).
Cela permet par exemple, en modifiant la fonction main(), de relancer l'analyse
après avoir gérer une erreur.
Exemple 12 : reconnaissances successives de mots
%%
S : D '\n'
{ printf("j'accepte le mot\n"); return 0; }
| error '\n'
{ printf("je refuse le mot\n"); return 1; }
;
D : 'a' 'b'
| D 'a' 'b'
%%
// réécriture de yylex() comme dans l'exemple 1
main()
{ while (yyparse()==0); }
Ici, le pseudo-terminal prédéfini error
récupère une impasse dans la table d'analyse jusqu'à la fin de la ligne concernée.
Si une ligne est un mot reconnu, yyparse() s'arrête
en retournant 0. Si la ligne n'est pas reconnue, l'analyseur affiche
syntax error (car il appelle yyerror), puis yyparse() s'arrête
en retournant 1. La fonction main() relance yyparse() tant que un mot
acceptable (càd élément du langage (ab)+) est reconnu et s'arrête dès qu'il y
a une erreur.
N.B. On n'a pas utilisé ici YYACCEPT ni YYERROR afin de montrer la correspondance entre
le test sur le retour de yyparse() et les return.
Exemple 13 : un analyseur plus robuste
%%
S : D '\n' {return 0;}
| error '\n' {return 1;}
;
D : 'a' 'b'
| D 'a' 'b'
%%
// reecriture de yylex() comme dans l'exemple 1
yyerror() {;}
main() {
int resultat;
while ((resultat=yyparse())<=1) {
if (resultat==0) printf("j'accepte le mot\n");
else printf("je refuse le mot\n");
}
}
Contrairement à l'exemple précédent, l'analyseur
est relancé même si le mot n'est pas reconnu. D'autre part,
il n'y aura pas ici de message syntax error, car la fonction yyerror
a été redéfinie (on aurait pu, bien sûr, la redéfinir différemment).
Les messages ont été déportés dans la fonction main.