Analyseurs Lexicaux et Syntaxiques


    L'objectif de ces séances de travaux pratiques de compilation est de se familiariser aux commandes flex et bison, les deux outils de compilation par défaut sur les systèmes unix depuis plusieurs décennies ( déjà !). Le premier outil flex (version gnu de la commande lex) construit un analyseur lexical à partir d?un ensemble de règles/actions décrites par des expressions régulières. Le second outil bison est un compilateur de compilateur, version gnu de la célèbre commande yacc acronyme de « yet another compiler of compilers ». Il construit un compilateur d?un langage décrit par un ensemble de règles et actions d?une grammaire LARL sous une forme proche de la forme BNF de Backus-Naur.
 
 

[ manuel flex ] [ manuel bison] [ lex/yacc ] [ lex/flex ] [ yacc/bison ]



Premiers pas avec flex.

    La structure d'un programme flex est similaire à celle d'une source bison. La source d'un programme flex est découpée en 4 zones séparées par les balises  %{ , %},  %%,  %%.

    L'analyseur lexical de l'exemple ci-dessous recherche le mot le plus long tout en calculant la somme des entiers rencontrés dans le fichier. Il utilise deux variables prédéfinies :yytextet yyleng.

%{
déclarations C
#include <stdio.h>
int total = 0;
int score = 0;

%}
Déclarations lex
LETTRE   [a-zA-Z]
CHIFFRE  [0-9]
MOT      {LETTRE}+
NOMBRE   {CHIFFRE}+

%%
Règles et actions sémantiques.

    {NOMBRE}  total+= atoi( yytext );
    {MOT}     if (yyleng > score){
                score = yyleng;
                printf("\n%s", yytext );
               }
     .        printf("\nNi mot, ni nombre :%s", yytext);
    %%

    int main( void ) {

        yylex() ;
        printf("\nSomme des nombres %d\nbye...\n", total);
       }
 
    La compilation d'une source flex produit une fonction yylex(). Un appel de yylex() déclanche une analyse lexicale du flux yyin. lAu cours traitement, l'nalyseur tente de satisfaire la première règle, puis la seconde etc... Quand un motif est détecté, il est chargé dans la variable yytext, sa longueur dans yyleng.
 
[ 1 ]  Le nom d'une source flex termine obligatoirement par le suffixe .lex . Uitiliser un copier/coller pour éditer un fichier mot.lex comme ci-dessus. Lancer la commande
flex mot.lex

Si tout se passe bien, flex construit une source C  yy.lex.c.

gcc -Wall yy.lex.c -olyse

Lancer les commandes

lyse
lyse < mot.lex
cat yy.lex.c | lyse

pour tester l'exécutable  lyse.

[ 2 ] Modifier la fonction main()pour affecter la variable yyin.

         int main( int argc, char **argv )
        { ++argv, --argc; /* skip over program name */
          if ( argc > 0 )
                       yyin = fopen( argv[0], "r" );
               else
                       yyin = stdin;

          yylex();

    }

[ 2 ] Modifier mot.lex  pour préciser la ligne contenant le mot le plus long.

[ 3 ] Modifier mot.lex  pour préciser l'adresse (ligne, colonne) du mot le plus long.

 

Gestion de symboles

Dans cette partie,  il s'agit de construire un analyseur lexical pour d'eterminer les mots les plus fréquents dans un texte. On utilise les structures :
      typedef struct  symb {
                       char * nom;
                       int    cpt;
                       } INFO, *PTR;
 
Les mots trouvés au cours de l'analyse lexicale sont recherchés dans une liste de type  PTR pour maintenir à jour la fréquence des mots rencontrés. l
[ 4 ] Ecrire une fonction
void inserer( char * mot, PTR liste)
pour faire le travail, utilisez des sentinnelles.

[ 5 ]  Ecrire une fonction void Afficher( PTR liste ). Modifier votre analyseur lexical pour obtenir la liste des mots et leurs fréquences.
 

Analyse de fichier PGN

Une partie d'échecs au format PGN ( Portable Game Notation) est une suite de "tag" précisant  le cadre de la rencontre suivie des coups et du résultat.  Par exemple :
 

[Event "07.22 R03 GER Nuernberg"]
[Site "?"]
[Date "1896.??.??"]
[Round "?"]
[White "Steinitz, W.."]
[Black "Lasker, Em."]
[Result "0-1"]
[WhiteElo "2725"]
[BlackElo "2785"]
[PlyCount "88"]
[EventDate "1896.??.??"]

{source: The Brooklyn Daily Eagle, 1896.08.03.} 1. e4 e6 2. d4 d5 3. Nd2 c5 4.
dxc5 Bxc5 5. Nb3 Bb6 6. exd5 Nf6 7. Bb5+ Bd7 8. Bxd7+ Qxd7 9. c4 exd5 10. c5
Bc7 11. Nf3 Nc6 12. O-O O-O 13. Nbd4 Nxd4 14. Qxd4 Rfe8 15. Be3 Re4 16. Qd3
Rae8 17. Rad1 h6 18. a3 Qg4 19. b4 g5 20. Qc3 Qf5 21. Qd3 Qg6 22. Qb5 Qh5 23.
Qxb7 Bxh2+ 24. Nxh2 Rh4 25. f3 Rxh2 26. Qc7 Rh1+ 27. Kf2 Qh4+ 28. Qg3 Qxg3+ 29.
Kxg3 Rxf1 30. Rxf1 Rxe3 31. Rc1 Ne8 32. a4 Ra3 33. b5 Rxa4 34. Rb1 Rc4 35. b6
axb6 36. cxb6 Rc8 37. Kg4 Nd6 38. Kh5 Kg7 39. b7 Rb8 40. Rb6 Nf5 41. f4 gxf4
42. Kg4 Ne3+ 43. Kxf4 Nc4 44. Rb4 Kf6 0-1

[ 6 ] Ecrire un analyseur lexical pour parcourir un fichier de parties au format pgn pour donner le résultat des joueurs. Pour chaque joueur, on précisera le nom, le nombre d'adversaires rencontrés, le nombre de parties gagnées, de partie nulle et de défaite.

 fichier de parties

Philippe Langevin, Janvier 2002.