Cours n° 2-10, 20 mai 2010

Jean-François Perrot

Génération de parseurs par Lex & YACC (suite)

1. De quoi s'agit-il ?
   1. Principe
      1. Que veut-on faire ?
      2. Dans quel but ?
      3. Par quel moyen ? la commande make et le fichier makefile
   2. Choix d'une application
      1. Principe
      2. Exemple d'exécution
      3. Choix de la classe des arbres
      4. Le code C++ de l'application


2. Réalisation pratique
   1. Point de départ
      1. Hypothèses
      2. Données
   2. Création du répertoire projet
      1. Principe
      2. Réalisation
      3. Complétion
   3. Compilation et recompilation
      1. Les commandes make et make clean
      2. Pour mieux comprendre...
         

De quoi s'agit-il ?

1. Principe

   • Que veut-on faire ?

     Il s'agit d'un outil permettant d'engendrer un parseur ascendant à partir de la donnée d'une grammaire CF ... et de quelques précisions supplémentaires.
     La grammaire et ses annexes ont le statut d'une spécification, non d'un programme.
     L'outil en question produit un programme (en C++) compilable, puis exécutable.
     
     L'utilisation de cet outil n'a de sens que dans la perspective d'une application informatique (programme) qui va mettre en œuvre le parseur en question.
     En effet, la nature exacte du résultat produit par le parseur dépend de cette mise en œuvre :
     ce résultat sera le plus souvent un arbre syntaxique, mais de quelle sorte exactement ? Quelles informations doit-il porter ?
     Nous avons besoin de le savoir pour écrire la spécification qui sera fournie à l'outil.
     Il convient donc avant toute chose de préciser le genre d'applications pour lesquelles notre outil est conçu.
     

   • Dans quel but ?

     Une telle application est centrée sur la lecture d'un texte et sur un travail à partir du contenu de ce texte.
     Le contenu en question est obtenu à partir de l'arbre syntaxique, qui matérialise la preuve que le texte est conforme à une certaine grammaire.
     Seuls des textes grammaticalement corrects peuvent avoir un contenu, les autres sont rejetés.
     Exemples :
     
     
     • L'exemple-type est un compilateur, où le texte lu est celui d'un programme et le travail sa traduction en code exécutable.
       Le programme est censé être conforme à la grammaire du langage de programmation choisi.
       
     • Un navigateur Web qui lit un fichier HTML pour le visualiser entre aussi dans cette catégorie.
       La grammaire est celle du langage HTML, et vous pouvez observer l'arbre syntaxique avec Firefox,
       en demandant "Inspecteur DOM" dans le menu Outils.
       
     • De nombreuses applications qui exploitent des fichiers XML commencent par une phase d'analyse syntaxique construisant un arbre de syntaxe abstraite (en format DOM) et travaillent ensuite sur cet arbre

   • Par quel moyen ? la commande make et le fichier makefile

     Du point de vue de la conception du programme, nous nous plaçons dans une perpective différente de celle des exercices  de programmation que nous avons pratiqués jusqu'ici, où on écrivait essentiellement un algorithme en C++ et où la génération de l'exécutable était effectuée en une seule commande de compilation.
     Comme le code du parseur est engendré à partir de la spécification, la génération de l'exécutable se fait en deux temps :
     
     1. production du code C++
     2. compilation.
     et elle met en jeu une bonne demi-douzaine de fichiers, rassemblés dans un même répertoire.
     
     Le détail des opérations à effectuer est décrit dans un fichier appelé makefile, activé par la commande make.
     Malheureusement, ce fichier est écrit avec une syntaxe archaïque qui le rend illisible au commun des mortels,
     mais il est indispensable de connaître son existence et sa fonction.
     Dans le cas précis des expérimentations sur le présent cours, il faudra même passer par une phase préliminaire
     de génération de ce fichier par un script écrit en Perl...
     
     Nous passons donc d'un programme matérialisé par un fichier (comme ceux du cours 21) à un programme réalisé par un répertoire (voyez la notion de projet en Visual C++).
     En outre, au lieu de rédiger tout le programme (en C++), nous n'écrirons que certaines parties, tantôt en C++ et tantôt sous forme de fragments de C++ disséminés dans différents formalismes, qui sont précisément l'objet de ce cours.
     Il va donc falloir plus que jamais réfléchir avant d'écrire !

2. Choix d'une application

   Principe

   Le seul langage dont nous avons examiné la syntaxe et pour lequel nous avons une idée précise de sa sémantique est celui de expressions arithmétiques. Nous envisageons donc une application qui
   
   • lit une expression arithmétique à 3 niveaux de précédences, conforme à la grammaire vue au cours 2-5
     et construit l'abre syntaxique correspondant ;
   • imprime l'arbre en question en notations polonaises préfixée et postfixée ;
   • extrait de cet arbre la liste des variables qui apparaissent dans l'expression, et donne pour chacune le nombre de ses occurrences ;
   • procède à l'évaluation de l'expression, en demandant interactivement la valeur de chaque variable la première fois qu'elle est rencontrée.
     
     
   Plus précisément, nous souhaitons que
   
   • les variables portent des noms "raisonnables", pas nécessairement réduits à un seul caractère
   • les constantes entières soient écrites en notation décimale ordinaire, avec un nombre quelconque de zéros en tête
   • l'expression soit écrite sur une seule ligne, mais avec la licence d'y insérer ad libitum des blancs et des tabulations.
     
     

   • Exemple d'exécution

     (le nom de l'exécutable est "calc") :
     

     jfp% ./calc
long * larg + 2^(exp - (long - 3))
+ * long larg ^ 2 - exp - long 3
long larg * 2 exp long 3 - - ^ +
Liste des variables :
exp : 1 occurrences.
larg : 1 occurrences.
long : 2 occurrences.
Valeur de la variable long ?
23
Valeur de la variable larg ?
10
Valeur de la variable exp ?
22
Valeur de l'expression : 234

   • Choix de la classe des arbres

     Ces desiderata ont pour conséquence que l'arbre syntaxique devra porter des étiquettes qui seront des chaînes et non pas de caractères comme c'est le cas pour la classe ArbExp utilisée jusu'ici.
     Nous utiliserons donc une nouvelle classe ExpArb qui ne diffère de la classe ArbExp que par le type des étiquettes.
     [fichiers ExpArb.h et ExpArb.cpp]
     Notez que la définition d'une structure adéquate pour les arbres syntaxiques est un problème délicat qui n'a pas de solution universelle : notre classe ExpArb n'est qu'un pis-aller simpliste !
     

   • Le code C++ de l'application

     Nous le donnons au complet, non comme un modèle, mais pour bien marquer que la réalisation du parseur en Lex & Yacc
     est assujettie à la contrainte de devoir fonctionner dans ce cadre.
     Sur la notion de map, qui est la réalisation en C++ standard des tableaux associatifs, alias tables de hachage (les hash de Perl),
     voyez Wikipedia.
     
     fichier calc.eval.C (à renommer calc.C pour le faire fonctionner avec les instruments du cours)
     

     ---

     /*
      Fichier "calc.C".
      Mise en œuvre d'un parseur ascendant
      Liste des variables présentes et évaluation de l'expression.
*/

#include    <iostream>
#include    <sstream>
#include    <map>
#include    <cmath> // pour 'pow'
#include     "expparser.h" // interface de la classe ExpParser

using namespace std;

//===== Auxiliaires pour manipuler les ExpArb (devraient être ajoutés à la classe !)

bool estBin (ExpArb* a) { // vrai si le sommet est binaire, i.e. n'est pas une feuille
    string et =  a->etiq();
    char init = et[0];
    return ! (init > 47 && init < 58 || init > 96 && init < 123 ); //  opérateur
}

bool estVar (ExpArb* a) { // vrai si le sommet est une feuille portant une variable
    string et =  a->etiq();
    char init = et[0];
    return (init > 96 && init < 123 ); //  lettre minuscule
}

bool estConst (ExpArb* a) { // vrai si le sommet est une feuille portant une constante
    string et =  a->etiq();
    char init = et[0];
    return (init > 47 && init < 58 ); //  chiffre
}
//=====

typedef map<string, int> dict; // dict comme 'dictionnaire'

dict lvs; // pour y accumuler les variables

void listvars(ExpArb* a) { // parcourt l'arbre et dépose les variables dans le dictionnaire 'lvs'
    if( estVar(a) ){
             ++lvs[a->etiq()]; // insertion automatique
    }else{
       if( estBin(a) ){
          listvars(a->fg());
          listvars(a->fd());
       }
    }
}// listvars

dict lva; // pour y loger les associations nom-valeur

int eval(ExpArb* a) {

    if( estVar(a) ){
        string et =  a->etiq();
        if( lva.find(et) == lva.end() ){
            int val;
            cout << "Valeur de la variable " << et << " ?" << endl;
            cin >> val;
            lva.insert(pair<string, int>(et, val));
        }
        return lva[et];
    }else{
        if( estConst(a) ){ // constante entière
            string et =  a->etiq();
            int val;
            stringstream ss(et); ss >> val;
            return val;
        }else{ // estBin
            int vg = eval(a->fg());
            int vd = eval(a->fd());
            switch(a->etiq()[0]){
                case '+' : return vg+vd;
                case '-' : return vg-vd;
                case '*' : return vg*vd;
                case '/' : return vg/vd; // division entière
                case '^' : { // la fonction 'pow' est très surchargée !
                        float p = pow((float)vg, vd);
                        return (int) p;   
                }
            }
        }
    }
}// eval

int main() {
    string lu;
    getline(cin, lu); // la chaîne à analyser
   
    stringstream inlu(lu, ios_base::in);
    ExpParser    parser(inlu); // le parseur est créé pour la chaîne donnée

    int n = parser.yyparse(); // lancement de l'analyse
    // valeur signal, normalement 0

    if( n ){ // traitement d'erreur sommaire
        cerr << "syntax error in \"" << lu << "\"" << endl;
        return 1; // et c'est fini
    }
    // si n == 0, OK
    ExpArb* arb = parser.arbre; // / l'arbre construit est obtenu commme un attribut de l'objet 'parser'
   
    // et l'aplication se poursuit en traitant l'arbre obtenu/
    arb->printPref();
    cout << endl;
    arb->printPost();
    cout << endl;
    listvars(arb);
    cout << "Liste des variables :" << endl;
    for( dict::const_iterator it = lvs.begin(); it != lvs.end();  ++it ){
        cout << it->first << " : " << it->second << " occurrences." << endl;
    }
    cout << "Valeur de l'expression : " << eval(parser.arbre) << endl;
    return 0;

}// main

     

     ---

     
     

Réalisation pratique

1. Point de départ

   • Hypothèses

     On fait l'hypothèse que
     
     1. vous avez défini votre application ;
     2. vous disposez d'une classe d'arbres conforme à vos desiderata ;
     3. vous avez écrit le fichier C++ correspondant à l'application, du genre de l'exemple ci-dessus,
        et que ce fichier s'appelle calc.C
        (ce dernier point est arbitraire, mais ne limite pas vraiment votre liberté d'action) ;
     4. il ne vous reste plus qu'à engendrer le parseur (et son lexeur) pour passer aux essais.
        
        
     Pour l'écriture des deux spécifications lexicale (explexer.ll) et syntaxique (expparser.yy),
     compte-tenu des contraintes issues de votre application, reportez-vous au  cours 2-9.
     Voici les deux fichiers qui correspondent à l'application annoncée ci-dessus (second exemple du cours 2-9) :
     
     • explexer.ll
     • expparser.yy
     Nous traitons ici de la phase finale de la réalisation.

   • Données

     • Le fichier calc.C contenant le code de l'application, et les deux fichiers de spécifications expparser.yy et explexer.ll.
       
       
     • <chemin> : Le chemin d'accès  du fichier d'interface (extension ".h") de votre classe d'arbres.
       On suppose que le fichier d'implémentation est logé au même endroit et porte le même nom, avec l'extension ".cpp".
       De préférence, donnez ce chemin sous forme absolue - sinon, réfléchissez bien à ce que vous faites :
       la chaîne que vous donnez devra repérer le fichier depuis le répertoire que vous allez créer...
       
       Attention ! ce chemin doit figurer dans votre fichier expparser.yy, dans #include    " <chemin>"
       parmi les ordres d'inclusion qui figurent dans le prologue entre %{ et %}.
       C'est normal ! Il s'agit de votre programme, qui doit donc savoir où il trouve ses arbres !
       
       
     • <nom-classe> : Le nom de votre classe d'arbres (qui en C++ peut être différent du nom du fichier d'interface).
       
       
     • <projet> : Enfin, le nom du répertoire qui va contenir l'application :
       si ce nom est projet, l'exécutable sera projet/calc.
   
   

2. Création du répertoire projet

   • Principe

     Il s'agit essentiellement de reproduire un répertoire-modèle en l'adaptant à la classe d'arbres que vous avez choisie.
     Comme cette adaptation affecte le fichier makefile et les classes ExpLexer et ExpParser, dont la lecture est ardue,
     il est préférable qu'elle soit faite automatiquement à partir du modèle et des données ci-dessus :
     c'est l'affaire de quelques lignes de Perl...
     
     On suppose dans la suite que le répertoire que vous allez créer est nouveau.
     

   • Réalisation

     Le répertoire-modèle s'appelle src, le script Perl est build.pl, ils sont censés résider dans le même répertoire,
     appelons-le base.
     Choisissez votre répertoire base et téléchargez-y
     
     • le répertoire src (sous forme d'un fichier src.tar à détarer par la commande "tar xf src.tar")
     • et le script build.pl.
       
     Le répertoire "projet" va être créé dans ce même répertoire par l'action du script build.pl.
     
     Dans le répertoire base, exécutez la commande :
     perl build.pl <projet> <chemin> <nom-classe>
     

   • Complétion

     Le répertoire base/projet  ue vous venez de créer contient tout le matériel standard, y compris un fichier makefile idoine.
     Il ne manque plus que les trois fichiers qui relèvent de votre responsabilité pleine et entière, à savoir
     
     • le code de l'application calc.C
     • la spécification du parseur expparser.yy (rappel : il doit être conforme au choix du <chemin>)
     • la spécification du lexeur explexer.ll
     
     Ajoutez-les ! Pour vos premiers essais, vous pouvez vous fournir dans les notes du cours 2-9...
     Compilez - corrigez - recompilez....
     

3. Compilation et recompilation

   • Les commandes make et make clean

     La commande qui doit lancer le processus de génération/compilation est make (dans le répertoire projet)
     Il arrive qu'elle soit inopérante, parce qu'un exécutable est déjà présent (même s'il est défectueux).
     Le système répond alors :
     make: `calc' is up to date.
     Il faut donc l'éliminer, en demandant make clean
     avant de redemander make.
     
     Cette situation est normale dès qu'on procède à des modifications d'un système qui a déjà été compilé avec succès.
     

   • Exemples

     En démo live !
     

   • Pour mieux comprendre le détail des opérations,

     lisez ceci !