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.

Inhoudsopgave 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.

Inhoudsopgave 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.

Inhoudsopgave 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.

Inhoudsopgave 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.

Inhoudsopgave 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.

Inhoudsopgave 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.

Inhoudsopgave 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.

Inhoudsopgave 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().

Inhoudsopgave 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.

Inhoudsopgave 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.

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 27/02/2010 gemaakt, de laatste keer de 28/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/langages-yacc.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes

  1. a,b,c,d,e,f… 15 meer links… Yet Another Compiler Compiler : komt overeen met « Encore un autre compilateur de compilateur » en français

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

  3.  Gnu's Not Unix : komt overeen met « 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 : komt overeen met “shift/reduce” en anglais

Inhoudsopgave Haut

Referenties

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

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut