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 dun 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 ]



Démarrage.

    Pour mesurer l'efficacité de ces outils,vous allez commencer par écrire « à la main » un interpréteur d'expressions algébriques capable  de traiter des programmes de la forme :
A = 3*5; C = (A - 5) * 7 + 3; ? C;
c'est-à-dire une suite d'instructions séparées par un ;  Les  espaces seront ignorés, les nombres réduits à un chiffre,  et les identificateurs réduits à une lettre, une instruction d'affichage,  une affectation, 4 opérateurs et des expressions parenthèsées.

[ 1 ] Identifiez bien le rôle des différents lexèmes, les priorités, les ordres d'associations.

[ 2 ] Ecrire une fonction récursive int execute( char * prog) qui  exécute  la suite de calculs spécifiée par une chaine de caractère prog. Notez bien que pour cette approche, une  analyse descendante est préférable.   La fonction utilisera une autre fonction récursive int evaluation( char * exp) qui calcule la valeur d'une expression.


 

Premiers pas avec bison.


Nous allons faire la même chose avec bison. On commence  par quelque chose de trés élémentaire : le langage des  expressions  (non parenthésées) construites à partir de  trois symboles terminaux NB, PLUS, FOIS, un symbole  non-terminal EXP et des règles

EXP := NB | EXP PLUS EXP | EXP FOIS EXP

 Pour construire un analyseur syntaxique avec la commande bison on édite un fichier de suffixe .y, disons fichier mini.y incluant la définition d'un analyseur lexical, obligatoirement identifié par  yylex(), la description des lexèmes ( tokens ) et des règles. Les actions sémantiques écrites en langage C entre accolades calculent l'attribut du père, représenté par $$, en fonction des attributs des  fils de gauche à droite représentés par $1, $2, ...
 

%{
int yylval ;
%}
 
%token NB PLUS FOIS FIN
    préciser la priorité des opérateurs
%start AXIOME
%%
AXIOME : EXP FIN { printf("%d", $1 ) }
EXP    : NB { $$ = $1 }
       | EXP PLUS EXP { $$ = $1 + $2 }
       | EXP FOIS EXP { $$ = $1 * $2 }
       ;
    %%
    int main( void ) {
        yyparse() ;
       }
    int yylex( ) { à définir }
 
    int yyerror(char *msg) {
        printf("\n%s\n", msg);
    }
 
    Le main du programme est réduit à sa plus simple expression : un appel de l'analyseur syntaxique yyparse() qui utilise implicitement la variable yylval et l'analyseur lexical  yylex(), une fonction qui renvoie la valeur du lexème  ( token) courant dont l'attribut est transmis par la variable  yylval.. Les erreurs de syntaxes provoque l'appel de la fonction  yyerror(). Ci-dessous, un exemple d'analyseur lexical rudimentaire que vous ne manquerez pas d'améliorer!
int yylex( ) {
    int car ;
    car = getchar() ;
    if ( car == EOF ) return 0 ;
    if ( isdigit(car) ) {
        yylval = car - '0';
        return NB;
        }
    switch ( car ) {
        case '+' : return PLUS;
        case '*': return FOIS;
        case '=': return FIN;
        }
          }
 
[ 3 ] Lancer la commande bison mini.y. L'analyseur échoue :-< ...
La présence de conflit  « décalage/reduction » montre que la grammaire ne peut pas être traitée par bison. Seule les grammaire LARL sont admises par bison. Dans notre cas, il s'agit d'un problème d'ambiguité relatif au caractères associatifs des opérateurs.  Une déclaration :
    %left PLUS
    %left FOIS
 
indique que l'opérateur  FOIS  est associatif à gauche, de priorité supérieure à l'opérateur PLUS (associatif à gauche) à cause de l'ordre des déclarations.
[ 4 ] Modifier mini.y jusqu'à ce que l'exécution :
bison mini.y
se passe correctement.
Vous devez obtenir un fichier C mini.tab.c qu'il faut compiler par
gcc mini.tab.c -o lysa
et préférablement
gcc -Wall mini.tab.c -o lysa
pour obtenir un analyseur nommé lysa, prévoir un Makefile? Essayer  lysa un analyseur sensé évaluer une formule terminée par  un point d'exclamation. Est-ce bien le cas ?
[ 5 ] Améliorer l'analyseur lexical pour filtrer les espaces et tabulations.
 
[ 7 ] Modifier la grammaire et mini.y pour gérer les autres opérations : division, soustraction, puissance, opposé.
 
[ 8 ] Gérer les parenthèses.
 
[ 9 ] Utiliser le symbole prédéfini error pour faire de la récupération d'erreur.

 

Calculette

[ A ] Modifier yylex() pour manipuler des nombres de plusieurs chiffres : la fonction ungetchar() est particulièrement utile !

 

[ B]  Ajouter des règles syntaxiques pour effectuer des calculs séparés par des « ; »
 

On souhaite manipuler des suites d'instructions un peu plus complexes à base de 26 registres mémoires A, B, ..., Z. Pour écrire des programmes comme ci-dessous :

    A := 3 ; B := 5*6 ; ( A- B) *(A+B) ;

[ C ] Ajouter un lexème MEM dont les attributs possibles seront A, B, ... dans l'analyseur lexical. Incorporer les règles syntaxiques pour gérer les expressions contenant des variables.
 

[ E ] Ajouter un lexème AFFECT . Incorporer les règles syntaxiques pour reconnaître les affectations MEM := EXP.
 

[ F ] Modifier les actions sémantiques pour afficher l'arbre syntaxique de l'expression.

Philippe Langevin, Janvier 2002.