Changes between Initial Version and Version 1 of 2009/CaoCourseTme3

Timestamp:

Jan 10, 2010, 11:53:40 PM (15 years ago)

Author:

franck

Comment:

--

2009/CaoCourseTme3

@@ +1 @@
+{{{
+#!html
+<h1> TME3 : Analyseur syntaxique  pour le format de fichier ''.vst''</h1>
+}}}
+[[PageOutline]]
+
+= Objectifs =
+
+L'objectif de ce TME est de vous familiariser avec les outils ''flex'' et ''bison'',
+qui sont des outils de la distribution GNU permettant de générer automatiquement des 
+analyseurs lexicaux (ou ''scaner'') et des analyseurs syntaxiques (ou ''parser'')
+pour différents formats de fichiers. Les outils ''flex'' et ''bison'' sont des versions
+"logiciel libre" des outils UNIX ''lex'' et ''yacc''.
+
+Vous allez développer un analyseur lexical, puis un analyseur syntaxique
+pour le format de fichier ".vst". Ce format de fichier correspond au sous-ensemble 
+du  langage VHDL utilisé  par la chaîne de CAO Alliance 
+pour décrire la vue structurelle d'un circuit intégré. La structure de donnée 
+construite en mémoire sera la structure de données ''lofig'' présentée en cours. 
+On fait l'hypothèse que tous les signaux sont de type bit, et il n'est donc pas demandé de traiter 
+les vecteurs de bits.
+Dans ce TME3, on se limitera à l'analyse grammaticale du format''.vst''. La construction effective
+de la structure de données ''lofig'' sera réalisée dans le TME4.
+
+Nous ne vous donnons pas la grammaire du format ''.vst'' mais vous devrez 
+la construire en analysant la structure du fichier [wiki:CaoCourseTme3exemple exemple.vst].
+
+Vous pourrez également utiliser des extraits du fichier complet comme [wiki:CaoCourseTME3signal signal.vst] 
+qui ne décrit que la liste des déclarations de signaux, dans le but de mettre au point l'analyseur syntaxique partie par partie.
+
+Ces deux fichiers sont disponibles dans le répertoire:
+{{{
+/users/enseig/encadr/cao/tme3/vst
+}}}
+
+Commencez par créez un répertoire ''tme3''. Il est recommandé de créer un sous-répertoire
+pour chacune des étapes de ce TME, et à recopier vos fichiers d'un répertoire dans le suivant,
+de façon à conserver les résultats intermédiaires.
+
+Si vous ne connaissez pas bien les outils lex (flex) et yacc (bison), les liens ci-dessous pourront vous aider à comprendre.
+  [http://www-128.ibm.com/developerworks/library/l-lex.html "Lex & Yacc Essentiel"]::
+    L'essentiel des outils est rappelé ici, à lire absolument.
+  [http://epaperpress.com/lexandyacc/download/lexyacc.pdf "Lex & Yacc Compact"]::
+    Un peu de théorie, et un exemple classique. Document à lire pour comprendre un peu comment ces outils fonctionnent.
+  [http://flex.sourceforge.net/manual/ "Lex Official"]::
+    LE manuel officiel de flex. C'est la que vous pourrez savoir quelles sont les options possibles sur la ligne de commande et toutes les fonctions.
+    Document à feuilleter, sa lecture n'est pas nécessaire pour résoudre ce TME.
+  [http://www.gnu.org/software/bison/manual/html_mono/bison.html "Yacc Official"]::
+    LE manuel officiel de Yacc.
+
+= Etape 1 : Analyseur lexical =
+
+L'outil '''flex''' est un générateur d'analyseur lexical. Il prend en entrée un fichier ''vst.l'' 
+contenant la définition des "token" à reconnaître, et génère en sortie un fichier ''vst.yy.c'' 
+qui contient le code C de l'analyseur lexical, et en particulier la fonction yylex().
+ 
+On appelle ''token'' une séquence de caractères lus dans le fichier texte qu'on cherche à analyser, 
+et correspondant à une expression régulière : mot-clef, identificateur, etc...
+Le but de cette première étape est d'écrire le fichier ''vst.l'' qui définit les expressions 
+régulières correspondant à tous les "tokens" utilisés dans un fichier texte respectant le format ''.vst''.
+
+  1. On rappelle qu'en VHDL, les lettres majuscules et minuscules ne sont pas différenciées. Cherchez dans le manuel de '''flex''' une manière simple de générer un analyseur lexical qui ne fasse pas la différence entre majuscules et minuscules.
+  1. Etablir la liste des mots clefs du format ''.vst'', et en déduire les expressions régulières en langage '''flex''' permettant de les reconnaître.
+  1. Etablir la liste des opérateurs du format ''.vst'', et écrire les règles en langage '''flex''' permettant de les reconnaître. On utilisera une classe pour les opérateurs possédant un seul caractère.
+  1. Etablir la règle de reconnaissance d'un identificateur, sachant qu'un identificateur du VHDL commence toujours par une lettre, suivied'un nombre quelconque de lettres, chiffres ou ''underscore'', avec la contrainte que l'on ne doit pas avoir 2 ''underscore'' successifs.
+  1. Etablir la règle permettant d'absorber les commentaires, sachant qu'un commentaire commence par "--" et s'achève en fin de ligne.  
+  1. Etablir la règle permettant d'absorber les caractères d'espace et les caractères de tabulation.
+
+A chaque règle reconnaissant un token particulier, on peut associer une séquence de code qui sera exécutée par
+l'analyseur lexical chaque fois que ce token est reconnu. Dans cette première étape, on se contente d'utiliser
+la fonction printf() pour afficher un message définissant le type de token reconnu, ainsi que la chaîne de 
+caractère correspondante. On rappelle que la variable globale {{{yytext}}} contient un pointeur sur la chaîne 
+de caractère constituant le dernier token reconnu.
+
+On donne ci-dessous une partie du fichier ''vst.l'' que vous devez écrire. Comme vous pouvez le constater,
+ce fichier se termine par la définition du programme main() qui appelle la fonction {{{yylex() }}}.
+La variable globale yyin est un pointeur sur le fichier à analyser. 
+{{{
+%{
+#include <string.h>
+#include <stdio.h>
+int yylineno = 1;     /* numero de ligne (pour les messages d'erreur) */
+#define YY_NO_UNPUT  
+%}
+
+%%
+[ \t]                {}                 
+\n                   {yylineno++;}
+expression1          {printf("TOKEN1: %s\n", yytext);}
+expression2          {printf("TOKEN2: %s\n", yytext);}
+expression3          {printf("TOKEN3: %s\n", yytext);}
+%%
+
+int main(int argc, char *argv[])
+{
+  if(argc != 2) {
+    printf("\n******* usage : %s filename \n", argv[0]);
+    exit(1);
+  }
+
+  yyin = fopen(argv[1], "r");
+
+  if(!yyin) {
+    printf("\n******* cannot open file : %s \n", argv[1]);
+    exit(1);
+  }
+  yylex();
+  return 0;
+}
+}}}
+Modifiez ce fichier en introduisant les règles correspondant aux différents "token" à reconnaître.
+
+La compilation du fichier ''vst.l'' s'effectue comme suit, à charge pour vous d'intégrer cela dans un Makefile:
+{{{
+$ flex -t vst.l > vst.yy.c
+$ gcc -Wall -Werror -o scanner vst.yy.c -lfl
+}}}
+
+Validez votre travail en lançant l'analyseur lexical sur les fichiers ''signal.vst'' et ''exemple.vst''.
+{{{
+$ scanner ../signal.vst
+}}}
+
+= Etape 2 : Modification de l'analyseur lexical =
+
+On cherche maintenant à modifier l'analyseur lexical pour préparer la communication
+entre l'analyseur lexical et l'analyseur syntaxique. On va demander à l'analyseur lexical d'afficher non plus
+la chaîne de caractères associée à chaque token, mais un entier représentant le type du token reconnu.
+
+Pour cela:
+
+  * Définir dans le prologue du fichier ''vst.l'' un type énuméré qui associe à chaque token un entier définissant son type. On utilise en général des valeurs supérieures à 255 pour les token correspondant à une chaîne de plusieurs caractères, de façon à pouvoir directement utiliser le code ascii du caractère dans le cas d'un token constitué d'un seul caractère.
+  * Modifier les actions associées aux règles afin qu'elles retournent le type du token. Par exemple :
+{{{
+entity   {return T_ENTITY;}
+}}}
+  * Modifier la fonction main() pour qu'elle affiche le type des tokens reconnus. On rappelle que ''yylex'' retourne 0 lorsque la fin de fichier est lue.
+  * Lancer cette nouvelle version de l'analyseur lexical sur les fichiers ''exemple.vst'' et ''signal.vst''.
+{{{
+$ scanner ../exemple.vst
+}}}
+
+= Etape 3 : Analyseur syntaxique =
+
+L'outil '''bison''' est un générateur d'analyseur syntaxique.
+Il prend en entrée un fichier ''vst.y'' contenant la définition des règles de la grammaire 
+correspondant au format ''.vst'', et génère la fonction yyparse() constituant l'analyseur
+syntaxique, dans un fichier vst.tab.c. 
+
+Cette étape vise à analyser le fichier ''signal.vst'', qui ne constitue qu'une
+partie du fichier ''exemple.vst'', et contient une liste de déclarations de signaux. 
+On cherche à écrire une règle permettant de reconnaître un nombre variable d'arguments
+(une liste de signaux dans notre cas).
+
+  1. Déclarez dans le fichier ''vst.y'', les différents token utilisés par le parser susceptibles d'être reconnus par le scaner.
+  1. Définissez les deux règles de grammaire correspondant a la déclaration d'une liste de signaux, et implanter ces règles dans le fichier ''vst.y''. On définira successivement la règle décrivant un signal, puis la règle décrivant une liste de signaux. '''Bison''' permet d'associer à chaque règle une "action de compilation" qui est exécutée pendant l'analyse du fichier, au moment ou la règle est reconnue, mais dans cette première étape, on n'associera aucune action aux deux régles définies.
+  1. La fonction main() est maintenant définie dans le fichier ''vst.y'', et doit appeller la fonction yyparse(). Il faut donc modifier la dernière partie du fichier du fichier ''vst.l'', qui ne contient plus que la définition de la fonction
+
+Voici une ébauche du fichier ''vst.y'' que vous devez modifier et compléter:
+{{{
+%{
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+extern int      yylex(void);
+extern int      yylineno;
+extern FILE     *yyin;
+
+int yyerror(char *s)
+{
+   fprintf(stderr, "%s line %d\n", s, yylineno);
+   return 1;
+}
+%}
+
+%token ... déclarer ici les differents types de token
+
+%%
+
+... ecrire ici les règles grammaticales
+
+%%
+
+int main(int argc, char *argv[])
+{
+   if(argc != 2) {
+        printf(usage : %s filename\n", argv[0]);
+        exit(1);
+   }
+   yyin = fopen(argv[1],"r");
+   if(!yyin) {
+        printf(cannot open file : %s\n", argv[1]);
+        exit(1);
+   }
+   yydebug = 1;
+   yyparse();
+   return 0;
+}
+}}}
+
+La compilation s'effectue comme suit, à charge pour vous d'intégrer ces commandes dans le Makefile.
+  * L'option -d sur la ligne de commande de '''bison''' active le mode debug, qui vous permet de suivre le déroulement de l'analyse syntaxique du fichier. Il faut de plus affecter une valeur non-nulle à la variable globale yydebug dans la fonction main().
+  * L'option -t sur la ligne de commande de '''bison''' demande à '''bison''' de générer un  fichier ''vst.tab.h''. Ce fichier est utilisé par '''flex''', et contient la définition des "tokens" utilisés par '''bison'''. Ce fichier doit être inclus dans l'en-tête du fichier ''vst.l'', et la compilation de '''flex''' doit dépendre de ce fichier ''vst.tab.h'' généré par '''bison'''.
+{{{
+bison -t -d vst.y 
+gcc -Wall -Werror -o parser vst.tab.c vst.yy.c -lfl
+}}}
+Validez l'ensemble en lançant l'analyse syntaxique du fichier ''signal.vst'':
+{{{
+$ parser ../signal.vst
+}}}
+
+= Etape 4 : Extension de l'analyseur syntaxique =
+
+Une règle de grammaire est construction grammaticale utilisant soit des token reconnus par ''flex'',
+soit d'autres constructions grammaticales, plus simples. La grammaire a donc une structure arborescente. 
+
+Dessinez explicitement le graphe représentant la grammaire associée au format ''.vst''.
+Dans ce graphe, qui a - presque - une structure d'arbre, chaque noeud correspond à une construction grammaticale (c'est à dire une règle de grammaire), et un arc orienté entre deux noeuds X et Y signifie : "La construction grammaticale Y est contenue dans la construction grammaticale X". Les constructions grammaticales élémentaires sont les tokens, et constituent les "feuilles" de l'arbre.
+
+La syntaxe de la construction grammaticale correspondant à la déclaration d'un signal a déjà été définie. Il faut donc :
+  1. Définir la construction grammaticale correspondant à la déclaration d'un port
+  1. Définir la construction grammaticale correspondant à la déclaration d'un composant
+  1. Définir la construction grammaticale correspondant à la déclaration d'une entité
+  1. Définir la construction grammaticale correspondant à la déclaration d'une instance
+  1. Définir toutes les règles nécessaires à l'analyse du fichier complet.
+
+Dans cette étape, on n'attachera aucune action de compilation aux règles grammaticales
+définies dans le fichier ''vst.y''. 
+
+Vous pouvez considérer que le TME est terminé lorsque le parser, construit automatiquement
+par le Makefile à partir des deux fichiers ''vst.l'' et ''vst.y'', est capable de lire et de reconnaitre
+la totalité du fichier ''exemple.vst''.
+Vous validerez le parser complet en lançant l'analyse syntaxique du fichier ''exemple.vst''.
+{{{
+$ parser ../exemple.vst
+}}}
+
+= Compte-Rendu =
+
+Il n'y a pas de compte-rendu écrit à rendre pour ce TME.
+Il vous sera demandé une démonstration de votre analyseur lexical
+et de votre analyseur syntaxique au début du TME4.
+Attention... Cette démonstration pourra porter sur un autre fichier 
+que le fichier ''exemple.vst''.
+