Cours n° 2-9, 6 mai 2010

Jean-François Perrot

Génération de parseurs par Lex & YACC

  1. Introduction
    1. But poursuivi
    2. Les outils en question

  2. Analyse lexicale
    1. Différence entre conventions lexicales et conventions syntaxiques
      1. Distinction
      2. Nature de la différence
      3. Lexing vs. Parsing
    2. Cahier des charges de l'analyse lexicale
      1. Catégories lexicales
      2. Lexèmes "singuliers"
      3. Lexèmes "génériques"
      4. Les séparateurs
    3. Travail du lexeur
      1. En principe
      2. Avec LEX plus précisément
      3. Typage de la variable lexval
    4. Réalisation du lexeur en Flex++
      1. Le lexeur est construit comme instance d'une classe ExpLexer.
      2. Comment est organisé le fichier "explexer.ll"
      3. Exemple : spécification d'un lexeur usuel pour expressions arithmétiques

  3. Analyse syntaxique
    1. Grammaires CF en format YACC
      1. Format des règles
      2. Déclaration des noms de lexèmes
      3. Règle de lancement
      4. Actions sémantiques
      5. Exemple rudimentaire
    2. Informations dans la pile
      1. Accès à la pile
      2. Type des éléments dans la pile
      3. Exemple un peu moins rudimentaire
      4. Actions d'empilement
      5. Exemple de la profondeur de l'arbre de dérivation
    3. Construction de l'arbre de syntaxe abstraite
      1. Problème de la livraison de l'arbre construit : recours à la classe ExpParser
      2. Fichiers expparser.h et calc.C
      3. Le fichier de spécification du parseur expparser.yy au complet

  4. Réalisation conjointe du lexeur et du parseur en Flex++ et bisonpp
    1. Mise en œuvre
      1. Principe
      2. Pratique
    2. Un premier exemple
    3. Un second exemple

Introduction

  1. But poursuivi

    Ce cours présente deux outils logiciels qui permettent d'engendrer un parseur ascendant à partir d'une grammaire CF.
    Pour comprendre le détail des préoccupations qui guident l'emploi de ces outils, il faut se placer dans la perspective d'une application informatique qui les met en œuvre.
    Ce point est développé plus avant au début du cours 2-10.

  2. Les outils en question

    YACC = Yet Another Compiler Compiler [S.C. Johnson, Bell Labs, 1975]
    est en fait un générateur de parseurs (et pas un compilateur de compilateurs !).
    Sa version d'origine engendrait des parseurs en C.
    Il en existe des adaptations pour la plupart des langages de programmation, par exemple en Perl.
    Nous utiliserons ici sa variante Bison, adaptée à C++ par Dirk Vermeir de la VUB (Vrije Universiteit Brussel),
    sous le nom de bisonpp, et configurée pour les systèmes Linux en usage à Nogent par Marie-Anne Moreaux.

    Comme nous allons le voir, le parseur engendré par YACC travaille non pas sur une chaîne de caractères mais sur une séquence de lexèmes,
    produite à partir du texte original par un analyseur lexical qui était à l'origine engendré par Lex (programme que nous avons déjà rencontré).
    Notre dispositif expérimental fera appel à sa variante Flex, aujourd'hui plus répandue, qui est aussi capable d'engendrer du C++.

    Pour une information complète sur ces outils, voir The Lex & Yacc Page.

Analyse lexicale

La distinction entre analyse lexicale et analyse syntaxique est spécifique aux langages des programmation.
Elle recoupe très approximativement la distinction entre morphologie et syntaxe en grammaire traditionnelle.

  1. Différence entre conventions lexicales et conventions syntaxiques

  2. Cahier des charges de l'analyse lexicale

    Répétons qu'il s'agit de langages artificiels, typiquement des langages de programmation.
    L'inventaire des lexèmes de chaque langage est une étape préliminaire à l'écriture de sa grammaire.
    La spécification du lexeur contient cet inventaire sur un mode opérationnel, c'est-à-dire accompagné
    Pour pouvoir donner des exemples il nous faut entrer dans l'analyse de ces rôles.

  3. Travail du lexeur

    Rappelons que le lexeur dispose du catalogue des lexèmes, à raison d'une expression régulière par classe de lexèmes,
    décrivant la forme de chacun des membres de cette classe (les séparateurs étant assimilés à une classe de lexèmes).

  4. Réalisation du lexeur en Flex++

    La spécification du lexeur est contenue dans un fichier portant l'extension ".ll". Par exemple "explexer.ll".
    Pour rédiger ce fichier il est utile de savoir que

Analyse syntaxique

  1. Grammaires CF en format YACC

  2. Informations dans la pile

  3. Construction de l'arbre de syntaxe abstraite


    On doit disposer d'une classe d'arbres adéquate pour le but visé par l'application.
    Dans un premier temps, nous reprendrons celle qui nous a déjà servi : ArbExp (dont les étiquettes sont des caractères).
    La construction proprement dite se fera par des actions sémantiques du même genre que celles qui effectuent le calcul de la profondeur,
    en travaillant sur le domaine des arbres au lieu de celui des entiers, comme expliqué au cours 2-8.

Réalisation conjointe du lexeur et du parseur en Flex++ et bisonpp

  1. Mise en œuvre

    Principe
    La génération de l'exécutable de l'application, qui contient le lexeur et le parseur, est une tâche complexe.
    Cette tâche est rendue encore plus compliquée par une série de détails techniques dans lesquels nous n'entrerons pas.

    Le programmeur doit founir trois fichiers :
    1. La spécification du lexeur, dans un fichier portant l'extension ".ll". Par exemple "explexer.ll".
    2. La spécification du parseur, dans un fichier portant l'extension ".yy". Par exemple "expparser.yy".
    3. Le code C++ de l'application, ici appelé "calc.C".

    Les fichiers d'interface des classes ExpLexer et ExpParser sont donnés a priori.

    La génération est effectuée par trois commandes rassemblées dans un fichier makefile.
    1. Génération du lexeur ("explexer.C") à partir de la spécification "explexer.ll"
      par la commande flex++
    2. Génération du parseur ("expparser.C") à partir de la spécification "expparser.yy"
      par la commande bisonpp
    3. Compilation de l'ensemble avec le fichier "calc.C" pour produire l'exécutable
      par la commande g++.

    Pratique
    Vu la complication byzantine du fonctionnement de Flex++ & bisonpp dans notre environnement,
    je vous propose la démarche suivante pour conduire vos expériences : voir le cours 2-10.

    1. Un premier exemple

      Les expressions arithmétiques en syntaxe traditionnelle à deux niveaux de précédences,
      comme celles que nous avons traitées au cours 2-8.
      Les arbres d'expressions sont instances de la classe ArbExp, dont les étiquettes sont des caractères.
      Le lexeur doit donc produire des caractères, comme celui de l'exemple un peu moins rudimentaire.

      Le code de l'application a été donné ci-dessus (fichier calc.C), il ne change pas.
      Voici les deux fichiers de spécifications du parseur et du lexeu:

      expparser.prec.yy (à renommer expparser.yy pour le faire fonctionner avec les instruments du cours)
      %{ /* Un parseur ascendant équivalent à AnAsc/Prec/aprec2Arb.cpp.
            Notation à précédences traditionnelle à deux niveaux.
            Les variables et les constantes et les opérateurs sont des caractères.
            On produit des ArbExp.
         */

      #include    <iostream>
      #include    "explexer.h"
      #include    "expparser.h"
      #include    "../ArbExp.h"

      %}

      %union    {
           ArbExp* expar; char nom;
      }

      %token         OpAdd OpMul Id Cte
      %type        <nom> OpAdd OpMul Id Cte
      %type        <expar> EXPAR TERME FACTEUR

      %%
      prog    : EXPAR { arbre = $1 ; } ;

      EXPAR        : EXPAR OpAdd TERME { $$ = new ArbExp($2, $1, $3); }

                  | TERME { $$ = $1; }
                  ;

      TERME    : TERME OpMul FACTEUR    { $$ = new ArbExp($2, $1, $3); }

              | FACTEUR { $$ = $1; }
              ;
             
      FACTEUR     : '(' EXPAR ')' { $$ = $2; }
             
                  | Cte { $$ = new ArbExp($1); }
             
                  | Id { $$ = new ArbExp($1); }
                  ;
             
      %%

      explexer.ll
      On prendra garde à la place du commentaire initial, en deuxième ligne contrairement à "expparser.yy" où il apparaît en première ligne.
      Une des bizarreries de Flex (héritée de Lex) est qu'il n'accepte pas de commentaire sur la même ligne que la balise "%{".
      %{
      /*
            Fichier "explexer.ll".
            un lexeur conforme aux analyseurs des cours 2-7 & 2-8
            Les variables sont les lettres x, y ou z.
            Les nombres ont 1, 2 ou 3
      */

      #undef  yyFlexLexer  // suppression de la définition de FlexLexer pour éviter la redéfinition

      #include    "explexer.h"
      #include    "expparser.h"

      %}

      %option    noyywrap

      %option    yyclass="ExpLexer"

      %%

      [xyz]       { lexval.nom = yytext[0];
                    return Id;
                  }
      [123]       { lexval.nom = yytext[0];
                    return Cte;
                  }
      [+*]        { lexval.nom = yytext[0];
                    return Op;
                  }
                 
      "("         return '(';
      ")"         return ')';

      .           return 0; // dans tous les autres cas, erreur

      %%

      Exécution :
      jfp% ./calc
      x-y/(z+3-x*y)-z/2
      --x/y-+z3*xy/z2
      xyz3+xy*-/-z2/-


    2. Un second exemple


      Les expressions arithmétiques en syntaxe traditionnelle à trois niveaux de précédences, comme celles que nous avons traitées au cours 2-5.
      On veut en outre que les noms de variables soient des chaînes de caractères, et les constantes des nombres décimaux.
      Et on souhaite pouvoir insérer des blancs et des tabulations ad libitum.

      Les arbres d'expressions sont à présent instances de la classe ExpArb, dont les étiquettes sont des chaînes, et où, en conséquence,
      les procédures d'impression polonaises séparent les étiquettes par des espaces. [fichiers ExpArb.h et ExpArb.cpp]. 

      Le lexeur va produire tantôt des caractères (pour les opérateurs), tantôt des entiers, tantôt des chaînes.

      Le fait que les étiquettes de nos arbres soient exclusivement des chaînes (et pas des entiers, par exemple), va nous obliger dans le parseur à
      convertir en chaînes les entiers livrés par le lexeur.
      Nous maintenons cette complication (au lieu d'adapter le lexeur en lui faisant produire des chaînes pour les nombres)
      de manière à pouvoir réutiliser le lexeur tel quel, en ne modifiant que le parseur,
      si on nous procure un jour des arbres de syntaxe abstraite un peu plus perfectionnés.

      Le code de l'application est celui du premier exemple,
      il ne change que par le nom de la classe d'arbres invoquée (ExpArb au lieu de ArbExp). [fichier calc.C]
      Voici les deux fichiers de spécifications :

      expparser.yy
      %{ /* Notation à précédences traditionnelle à trois niveaux.
            On produit des ExpArb.
         */

      #include    <sstream> // pour la conversion d'entier en chaîne
      #include    "explexer.h"
      #include    "expparser.h"
      #include    "../../ExpArb.h" // étiquettes string       et non plus char

      %}

      %union    {
           ExpArb* expar; const char* nom; int val; char op;
      }
      // Attention ! Pour le champ "nom" il faut "const char*" et pas "string" !

      %token       OpAdd OpMul OpExp Id Cte
      %type        <op> OpAdd OpMul OpExp
      %type        <nom> Id
      %type        <val> Cte
      %type        <expar> EXPAR TERME FACTEUR PRIMAIRE

      %%
      prog    : EXPAR { arbre = $1 ; } ;

      EXPAR       : EXPAR OpAdd TERME { $$ = new ExpArb($2, $1, $3); }

                  | TERME { $$ = $1; }
                  ;

      TERME   : TERME OpMul FACTEUR    { $$ = new ExpArb($2, $1, $3); }

              | FACTEUR { $$ = $1; }
              ;
             
      FACTEUR     : PRIMAIRE OpExp FACTEUR { $$ = new ExpArb($2, $1, $3); } // OpExp exigé par le typage : '^' impossible

                  | PRIMAIRE { $$ = $1; }
                  ;

      PRIMAIRE    : '(' EXPAR ')' { $$ = $2; }
             
                  | Cte { ostringstream oss; oss << $1; $$ = new ExpArb(oss.str()); } // conversion laborieuse
             
                  | Id { $$ = new ExpArb($1); }
                  ;
             
      %%

      explexer.ll
      %{
         /* un lexeur normal pour des expresions arithmétiques
         */

      #undef  yyFlexLexer
      #include          <iostream>
      #include          <sstream> // pour la conversion de chaîne en entier
      #include    "explexer.h"
      #include    "expparser.h"

      %}

      %option    noyywrap
      %option    yyclass="ExpLexer"

      %%

      [ \t]        ;

      [a-z][a-z0-9]*      { lexval.nom = yytext;
                            return Id;
                          }
      [0-9]+      { stringstream ss(yytext); int i; ss >> i; lexval.val = i;       // conversion laborieuse
                    return Cte;
                  }
      [+-]        { lexval.op = yytext[0];
                    return OpAdd;
                  }
      [*/]        { lexval.op = yytext[0];
                    return OpMul;
                  }
      "^"         { lexval.op = yytext[0];
                    return OpExp;
                  }
                 
      "("            return '(';
      ")"            return ')';

      %%


      Exécution :
      jfp% ./calc
      xx + y2/2^k0^( 3 * pa + 10 )
      + xx / y2 ^ 2 ^ k0 + * 3 pa 10     
      xx y2 2 k0 3 pa * 10 + ^ ^ / +

      Pour la pratique de la mise en œuvre, voir le cours 2-10.