Analyse gramaticale avec YACC [“Yet Another Compiler Compiler”[3]] ou Bison

Sommaire du document

Comme nous ne pouvons effectuer toutes les opérations nécessaires avec les expressions rationnelles, YACC 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.

 

Exemple de fichier YACC[ref 3]

  1. %{
  2. #include <ctype.h>
  3. %}
  4.  
  5. %token CHIFFRE
  6.  
  7. %%
  8. ligne&nbsp;: expr '\n' { fprintf("%d\n", $1); }
  9. ;
  10. expr&nbsp;: expr '+' terme { $$ = $1 + $3 }
  11. | terme
  12. ;
  13. terme&nbsp;: 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.

 

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.

 

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

 

%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 union[5]. 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.

 

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.

 

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

 

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.

 

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&nbsp;: 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().

 

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.

 

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.

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Notes

  1.  Gnu's Not Unix : correspond à « GNU n'est pas UNIX” en français

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

  3. a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u Yet Another Compiler Compiler : correspond à « Encore un autre compilateur de compilateur” en français

  4. a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t YACC : “Yet Another Compiler Compiler” (en français, « Encore un autre compilateur de compilateur ») Nous emploierons le terme Yacc, mais il peut s'agir de Bison, son équivalant GNU

  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 : correspond à “shift/reduce » en anglais

 

Références

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

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-9900
Document créé le 27/02/10 09:05, dernière modification le Mercredi 28 Juin 2017, 14:26
Source du document imprimé : http:///www.gaudry.be/langages-yacc.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,16 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Software developer: someone who gets paid to program and then more to fix it.

Venkat Subramaniam [twitter]
 
l'infobrol
Nous sommes le Jeudi 14 Décembre 2017, 17:47, toutes les heures sont au format GMT+1.00 Heure, heure d'hiver