Analyse gramaticale avec YACC ou Bison

Comme nous ne pouvons effectuer toutes les opérations nécessaires avec les expressions rationnelles, YACC [“Yet Another Compiler Compiler”1] nous offre la possibilité d'effectuer des vérifications plus poussées.

Structure du fichier YACC

Le fichier YACC peut se décomposer en trois parties, séparées chacune par une ligne qui ne comporte que deux signes pourcent (%%).

  1. //declarations
  2. %%
  3. //regles de traduction
  4. %%
  5. //code additionnel

Pour le code additionnel, ainsi que pour les méthodes utilisées dans les règles de traductions, nous utiliserons le langage C.

Contents Haut

Exemple de fichier YACCref 3

  1. %{
  2. #include <ctype.h>
  3. %}
  4.  
  5. %token CHIFFRE
  6.  
  7. %%
  8. ligne : expr '\n'         { fprintf("%d\n", $1); }
  9.       ;
  10. expr : expr '+' terme     { $$ = $1 + $3 }
  11.      | terme
  12.      ;
  13. terme : terme '*' facteur { $$ = $1 * $3 }
  14.       | facteur
  15.       ;
  16. facteur : '(' expr ')'    { $$ = $2 }
  17.         | CHIFFRE
  18.         ;
  19.  
  20. %%
  21. yylex(){
  22.   int c;
  23.   c = getchar();
  24.   if(isdigit(c)){
  25.     yyval = c-'0';
  26.     return CHIFFRE;
  27.   }
  28.   return c;
  29. }

Cet exemple nous montre la spécification YACC d'une calculatrice simple.

Contents Haut

Première partie du fichier YACC : déclarations

%{...%}

Nous retrouverons ici les déclarations, dans notre cas en langage C, entourées par %{ et %}

Dans l'exemple ci-dessus, la déclaration #include nous permet l'utilisation de isdigit

Nous pouvons utiliser cette partie pour déclarer les variables dont nous aurons besoin dans le traitement des règles de traduction et dans la troisième partie du fichier YACC.

Contents Haut

%token ...

Nous déclarerons aussi dans cette partie les symboles terminaux (les lexèmes) précédés par %token. Par convension, nous pouvons utiliser les majuscules pour ces noms de symboles terminaux.

Une fois que nous avons déclaré ces lexèmes, nous pouvons les utiliser dans la deuxième partie, et quelques fois même dans la troisième partie du fichier YACC.

Dans le cas oû nous confions l'analyse lexicale à Lex, ce dernier peut utiliser les lexèmes que nous avons déclarés ici.

Contents Haut

%type ...

Nous déclarerons dans cette partie les symboles non terminaux précédés par %type. Par convension, nous pouvons utiliser les minuscules pour ces noms de symboles non-terminaux.

%union

  1. %union {
  2.   int cmd;
  3.   char * text;
  4.   double val;
  5. }

Nous pouvons déclarer dans cette partie les symboles terminaux déclarés avec %token seront une union5. YACC utilisera donc cette union comme type pour yylval.

Après avoir défini notre union, nous pouvons associer un symbole terminal (%token) ou un symbole non-terminal (%type) à un élément particulier de l'union.

Exemple simple

  1. %union {
  2.   int cmd;
  3.   char * text;
  4.   double val;
  5. }
  6. %token<val> CHIFFRE
  7. %token<text> ID
  8.  
  9. %type<val> term

Exemple avec l'arbre syntaxique abstrait

  1. extern char* yytext;
  2.  
  3. pLSD_NODE lsdNode;
  4.  
  5. %}
  6.  
  7. %union{
  8.     int nval;
  9.     char *text;
  10.     pLSD_NODE node;
  11.   }
  12.  
  13. %token <nval> NB
  14. %token <cval> ID
  1. <CODE>;{ID}    {
  2.                  yylval.text=(char*)calloc(strlen(yytext)+1,sizeof(char));
  3.                  strcpy(yylval.text,yytext);
  4.                  return ID;
  5.               }
  6. <CODE>;{NB}+   {
  7.                  yylval.nval = atoi(yytext);
  8.                  return NB;
  9.               }

Nous devons spécifier explicitement dans le fichier Lex quel élément de notre union yyval nous utilisons.

Contents Haut

Règles d'associativité  %left, %right, et %nonassoc

Afin d'éviter les conflits de type « décalage/réduction » (en anglais, “shift/reduce”) entre nos symboles terminaux (généralement des opérateurs), ces symboles seront précédés par les directives %left ou %right.

Contents Haut

%start ...

Nous pouvons aussi retrouver la déclaration %start suivie par une des productions de la deuxième partie du fichier YACC.

Cette déclaration nous permet de spécifier par quelle production YACC devra commencer.

Dans le cas où nous ne définissions pas la production de départ, nous pouvons ommettre cette ligne et YACC commençera par la première production dans l'ordre d'apparition dans le fichier YACC.

Contents Haut

Deuxième partie du fichier YACC : productions

Nous retrouverons ici les les règles de traduction de la grammaire, chaque règle étant composée d'une production suivie le plus souvent par l'action sémantique qui correspond.

  1. <partie_gauche> :
  2.     <partie_droite_1> [{<action_partie_droite_1>}]
  3.   | <partie_droite_2> [{<action_partie_droite_2>}]
  4.   | ...
  5.   | <partie_droite_n> [{<action_partie_droite_n>}]
  6.   ;

Les chaînes de caractères qui ne correspondent pas à une déclaration seront considérées comme des symboles non-terminaux. Dans notre exemple, nous retrouvons par exemple à la ligne 10 le symbole '+'. En réalité, c'est une valeur sous forme d'entier qui est transmise

Nous utilisons le symbole pipe (|) pour séparer les parties droites concurentes qui correspondent à une même partie gauche.

Contents Haut

Attributs $$ et $1, ...

Nous avons accès à chaque partie de nos productions dans l'action qui lui est associée, gràce aux attributs &&, &1, &2, ...

  1. expression : expression '+' term {$$ = $1 + $3};
  • Dans cet exemple,
    • && est l'attribut de la partie gauche de la règle (la partie expression qui se trouve à gauche des deux points).
    • $1 est l'attribut du premier symbole de la partie droite de la règle (la partie expression qui se trouve à droite des deux points).
    • &3 est l'attribut du troisième symbole de la partie droite de la règle (la partie term).

Les différents attributs &n correspondent à la valeur affectée à yylval par la fonction yylex().

Contents Haut

Troisième partie du fichier YACC : code

C'est dans cette partie que nous plaçerons la fonction main qui démarrera l'analyse en appelant la fonction yyparse().

Nous retrouverons aussi dans cette partie la fonction yyerror(char *info) qui permettra l'affichage d'un message lors d'une erreur de syntaxe.

Contents Haut

Commandes YACC à exécuter

Voici un exemple d'utilisation des commandes Yacc ou bison.

Convensions

Les commandes introduites dans le terminal sont affichées de cette manière, et les réponses du terminal de cette manière.

steph@astate:∼$ cd /mnt/steph_docs/FUNDP/lsd010
steph@astate:/mnt/steph_docs/FUNDP/lsd010$ bison -dty *.y
lsd010.y:34.1-2: syntax error, unexpected %%
steph@astate:/mnt/steph_docs/FUNDP/lsd010$

Pourquoi avons nous un message d'erreur ?
Dans le fichier traité la deuxième partie du fichier YACC était vide.

Nous utilisons l'option -d pour que YACC génère le fichier y.tab.h qui permettra à Lex d'utiliser les symboles que nous avons définis dans le fichier YACC.

Contents Haut

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 27/02/2010, last modified the 28/10/2018
Source of the printed document:https://www.gaudry.be/en/langages-yacc.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

Notes

  1. a,b,c,d,e,f… 15 more links… Yet Another Compiler Compiler : corresponds to « Encore un autre compilateur de compilateur » en français

  2. a,b,c,d,e,f… 14 more links… YACC : “Yet Another Compiler Compiler” (en français, « Encore un autre compilateur de compilateur »)

  3.  Gnu's Not Unix : corresponds to « GNU n'est pas UNIX » en français

  4.  GNU : “Gnu's Not Unix” (en français, « GNU n'est pas UNIX ») Groupement de logiciels libres. Il s'agit d'un acronyme récursif, car nous retrouvons l'acronyme dans sa propre définition.

  5.  union : Le mot clé union dans le langage C permet de désigner un seul espace mémoire dans leque nous pouvons stocker différents types de données. L'espace sera celui du type qui requiert le plus grand espace mémoire.

  6.  décalage/réduction : corresponds to “shift/reduce” en anglais

Contents Haut

References

  1. book Language of the document:fr IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique (January 2010)
  2. book Language of the document:fr Compilateurs : Dick Grune, Henry E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen, Cours et exercices corrigés
  3. book Language of the document:fr Compilateurs : A. Aho, M. Lam, R. Sethi, J. Ulman, Principes; techniques et outils
  4. View the nbsp;document Language of the document:fr Mini manuel d'utilisation de Lex et Yacc : Etienne Bernard, Lex et Yacc (version 26/02/10)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut