B.A. BA de Yacc (ou Bison).

1 Introduction

Après avoir découvert Lex, il faut nécessairement s'intéresser à l'outils complémentaire : YACC. Yacc est aussi un utilitaire Unix. Il permet de produire des analyseurs syntaxiques selon une grammaire hors-contexte décrite dans un fichier. En fait, il est même possible, à l'aide de Yacc, de produire des interpréteurs ou des compilateurs complets, c'est-à-dire comportant en plus analyse sémantique et l'interprétation et/ou la génération de code.

Yacc s'utilise la plupart du temps conjointement à Lex. Lex fournit les unités lexicales à Yacc qui se charge d'analyser leur organisation syntaxique et qui, au fur et à mesure de la reconnaissance, est capable d'exécuter certaines actions appelées actions sémantiques.

flot d'entrée

→

Analyseur
Lexical
(lex)

→

Unités Lexicales

→

Analyseur
Syntaxique
(yacc)

→

Code/Résultats

Figure 1: Principe de fonctionnement du programme engendré par LEX et YACC

2 Présentation succincte de Yacc

L'analyseur syntaxique produit par Yacc est décrit dans un fichier texte composé de trois parties séparées par "%%" (fig. 2) :

La première comporte d'abord les déclarations C utiles pour l'analyse syntaxique et sémantique ainsi que pour la génération de code. Ces déclarations C débutent par "%{" et terminent par "%}". Dans cette partie, on trouve aussi les déclarations des unités lexicales ("token"), le typage des symboles non-terminaux, les règles d'associativité et de priorité.
La seconde décrit les règles de la grammaire du langage (hors-contexte) auxquelles ont été ajoutées les actions sémantiques.
La dernière partie comprend les fonctions C utilisées par les actions sémantiques ainsi que la fonction "main".

[ 1 - Définitions ]
  %%
[ 2 - Règles de grammaire ]  
  %%
[ 3 - Fonctions utilisateur ]

Figure 2: Forme générale d'un fichier YACC

Pour en savoir plus, il faut lire attentivement le man Unix de Yacc (" > man yacc "). Vous pouvez également consulter différentes sources sur Lex et Yacc dont : "http://members.xoom.com/thomasn/y_man.htm",
ou le livre de Levine, Mason et Brown "Lex & Yacc" Ed. O'Reilly Int. Thomson, ou encore le livre "Compilateurs : principes, techniques et outils" de Aho, Sethi et Ullman chez InterEdition.

Remarque : vous pouvez aussi consulter le manuel Bison.

Les figures 3 et 4 proposent un exemple de codes Yacc et Lex pour une calculatrice très simple (exemple désespérément classique !).

 %token INTEGER
 %%
 program:
         expr '.'         { printf("=%d\n", $1); }
         |
         ;
 expr:
         INTEGER
         | expr '+' expr           { $$ = $1 + $3; } 
         | expr '-' expr           { $$ = $1 - $3; }
         ;
 %%
 int main(void) {
     yyparse();
     return 0;
 }

Figure 3: Fichier Yacc pour une calculatrice extrêmement simple

Sur ces exemples, remarquez que les unités lexicales sont définies dans Yacc et que Lex les connaît par l'intermédiaire du "y.tab.h".

%{
#include "y.tab.h" 
extern int yylval;/* Cas standard. Absent si redef. dans yacc */
                  /* car dans y.tab.h*/
%}
%%
[0-9]+	{yylval = atoi(yytext);
	 return INTEGER;}
[-+\.]	{return *yytext;} 
[ \t\n]	; 
.	yyerror("Caractere non valide");
%%
int yywrap(void) {
    return 1;
}

Figure 4: Fichier Lex utile pour le premier exemple Yacc

3 Génération du compilateur

Pour voir comment utiliser Yacc et Lex, c'est-à-dire, comment à partir d'une description on obtient l'analyseur lexical et l'analyseur syntaxique, écrire dans un fichier "tp2.l" une description pour Lex et dans "tp2.y" une description de Yacc (par exemple, le code des figures 3 et 4).

Utiliser Lex et Yacc est simple, il suffit de compiler sous Unix "tp2.l" avec Lex pour obtenir un fichier intermédiaire C ("lex.yy.c") puis de compiler "tp2.y" avec Yacc pour obtenir les fichiers intermédiaires C ("y.tab.c" et "y.tab.h"). Finalement, il faut compiler ces fichiers C avec les bonnes bibliothèques ("-ll" et "-ly"). L'analyseur se trouve alors dans l'exécutable spécifié. Le plus simple est d'écrire un fichier "makefile" à utiliser avec la commande Unix "make". Voici un exemple de fichier make pour des fichiers "tp2.l" et "tp2.y" permettant d'obtenir le programme "tp2" :

tp2 : y.tab.c lex.yy.c
      cc y.tab.c lex.yy.c -ly -ll -o tp2
y.tab.c : tp2.y
      yacc -d tp2.y
lex.yy.c : tp2.l 
      lex tp2.l

Par curiosité, observez le fichier construit par Yacc "y.tab.h". Enfin, exécutez l'analyseur. Taper "3+2.", puis pour finir "Ctrl-D".

4 Description du fichier Yacc

Comme vous connaissez parfaitement Lex, nous n'allons décrire que les éléments importants du fichier Yacc. Cette description se base sur l'exemple de la figure 3.

La première partie comporte, dans cet exemple, seulement la définition d'une seule unité lexicale (UL). Cette déclaration sera insérée par Yacc dans le fichier "y.tab.h" (inclus dans le code Lex). Par conséquent, Lex connaît aussi cette UL.

La seconde partie propose la grammaire hors-contexte décrivant le langage choisi. Cette grammaire est la suivante :

→

Dans cette grammaire, les ASi sont des actions sémantiques, c'est-à-dire du code permettant d'effectuer certaines opérations (calcul, vérification...) au c cours de l'analyse syntaxique (mélange analyse syntaxique, analyse sémantique et phase de synthèse). Dans l'action sémantique, $i indique la valeur du vocabulaire i de l'alternative courante. $$ correspond à la nouvelle valeur du non terminal se trouvant en partie gauche de la règle.

L'axiome de la grammaire est désigné en première partie par le mot clé "%start". Par exemple, pour notre grammaire, on peut avoir "%start program". Cependant, par défaut, l'axiome est le nom terminal en partie gauche de la première règle.

5 Lien entre Lex et Yacc

Le passage des informations entre Lex et Yacc s'effectue selon deux manières :

par la valeur entière retournée par "yylex()", c'est-à-dire par le "return" se trouvant dans une action liée à une expression régulière (dans le fichier Lex) ;
par la variable globale "yylval". Elle sera la valeur d'une unité lexicale ("Token") dans le fichier Yacc (valeur du $_i pour les symboles terminaux). Par défaut, cette variable est un entier. Mais il est possible de lui donner d'autres types (des types C).

Pour utiliser le "yylval" par défaut, il suffit d'ajouter "extern int yylval;" dans les déclarations C du fichier Lex. Pour donner son propre type, il faut le faire en première partie du fichier Yacc. Ce type doit être le type C "union" avec les champs que l'on veut. Cela se fait, en dehors des déclarations C et précédé par "%" de la manière suivante :

% union{
    int entier;
    float reel;
};

Cette déclaration sera automatiquement incluse dans "y.tab.h" par Yacc. Par contre, il en découle qu'il est nécessaire de spécifier les types de certains non-terminaux. Cela peut se faire par exemple par "%type < reel > expr" avec la définition ci-dessus.

jeudi, 27/05/04 15:09