TP de compilation : une solution de l'exercice 3 du TP 5

3.1.
La grammaire telle qu'elle est proposée donne lieu à quatre conflits shift/reduce lors de l'analyse par Yacc. Pour résoudre cette difficulté, on peut choisir, très classiquement, une associativité à gauche pour l'addition et la multiplication ainsi qu'une priorité de la multiplication sur l'addition.

fichier-lex:
%{
#include "y.tab.h"
%}
%s ANOMALIE
%%
^\n          {exit(0);}
<INITIAL>1   {return un;}
<INITIAL>0   {return zero;}
<INITIAL>"+" {return plus;}
<INITIAL>"*" {return mult;}
<INITIAL>"(" {return ouvrante;}
<INITIAL>")" {return fermante;}
\n           { BEGIN(INITIAL);
               return finligne; }
<INITIAL>.   { printf("%s: inconnu\n",yytext);
               BEGIN(ANOMALIE); }
<ANOMALIE>.  ;
fichier-yac:
%token un zero
%token ouvrante fermante
%token finligne
%token errlex
%left plus
%left mult
%%
S : E finligne { printf("OK\n");
                 return 0; }
  | error finligne { printf("erreur\n");
                      return 2; }
  ;
E : E plus E
  | E mult E
  | ouvrante E fermante
  | un
  | zero
  ;
%%
yyerror(){;}
main() {while (yyparse()>=0) ;}

Cet analyseur est robuste et relativement convivial : il précise si une ligne contient une erreur (si l'erreur est lexicale, le caractère ayant donné cette erreur est affiché) puis passe à la ligne suivante sans que son fonctionnement soit perturbé. L'arrêt du programme est géré par l'analyseur lexical avec la saisie d'une ligne vide. On pourrait être plus convivial, en précisant quel type d'erreur (lexical ou syntaxique) a été commise et à quel endroit. Que proposer pour cela ?
Remarque :
On pouvait bien évidemment (voir le cours) utiliser une grammaire LALR équivalente à celle de l'énoncé mais qui ne nécessitait pas de préciser les priorités ni l'associativité :
E → E+T|T
T → T*F|F
F → (E)|0|1

3.2.
fichier-lex:
%{
#include "y.tab.h"
%}
%s ANOMALIE
%%
^\n           {exit(0);}
<INITIAL>[0-9]+
              { if (yyleng<=6) return nombre;
                else { BEGIN(ANOMALIE); return errlex; } }
<INITIAL>"+"  {return plus;}
<INITIAL>"*"  {return mult;}
<INITIAL>"("  {return ouvrante;}
<INITIAL>")"  {return fermante;}
\n            { BEGIN(INITIAL); return finligne; }
<INITIAL>.    { printf("%s: inconnu\n",yytext); BEGIN(ANOMALIE); }
<ANOMALIE>.    ;
ficher-yacc:
%token nombre
%token ouvrante fermante
%token finligne
%token errlex
%left plus
%left mult
%%
S : E finligne {printf("OK\n"); return 0;}
  | error finligne { printf("erreur\n"); return 2; }
  ;
E : E plus E
  | E mult E
  | ouvrante E fermante
  | nombre
  ;
%%
yyerror(){;}
main() {while (yyparse()>=0) ;}

3.3.
Le langage anbncn n'est pas algébrique, et donc pas déterministe ; il ne peut donc être reconnu par un analyseur LALR sans actions ajoutées. Voici deux solutions alternatives utilisant soit un fichier-lex, soit un fichier-yac.

1°) Avec seulement un fichier-lex
%{
int na, nb, nc ;
%}
%s modeA
%s modeB
%s modeC
%s ANOMALIE
%%
^\n            {exit(0);}
<INITIAL>a     { BEGIN(modeA); na=1; }
<modeA>a       {na++;}
<modeA>b       { BEGIN(modeB); nb=1; }
<modeB>b       {nb++;}
<modeB>c       { BEGIN(modeC); nc=1; }
<modeC>c       {nc++;}
.              {BEGIN(ANOMALIE);}
<modeC>\n      { if ((na==nb)&&(nb==nc)) printf("OK\n");
                 else printf("erreur\n");
                 BEGIN(INITIAL);
                 na=0; nb=0; nc=0; }
\n             { printf("erreur\n");
                 BEGIN(INITIAL);
                 na=0; nb=0; nc=0; }

2°) Avec seulement un fichier-yac
%{
int na=0;
int nb=0;
int nc=0;
%}
%%
L : S '\n'     { if ((na==nc)&&(na==nb)) printf("mot accepté\n");
                 else printf("mot refusé\n");
                 na=0; nb=0; nc=0; return 0; }
  | error '\n' { printf("mot refusé\n");
                 na=0; nb=0; nc=0; return 1; }
  ;
S : 'a' S  {na++;}
  | T
  ;
T : 'b' T  {nb++;}
  | U
  ;
U : 'c' U  {nc++;}
  |
  ;
%%
int yylex() {
 char k=getchar();
  if ((k=='a')||(k=='b')||(k=='c')||(k=='\n')) return(k);
  else exit(-1);
}
yyerror() {;}
main() {while (yyparse()>=0);}

3.4.
Voici une grammaire pour les palindromes sur {a..z} ayant exactement un x. Ce caractère 'x' est donc au centre du mot ce qui rend le langage déterministe.
S→ aSa | bSb | ... | wSw | ySy | zSz | x

3.5.
On ne peut pas ici utiliser un token différent pour chaque lettre de l'alphabet car on dépasserait largement cinq tokens. On peut s'en sortir en choisissant un unique token pour toutes les lettres différentes de 'x' et en transmettant la valeur de ces lettres grâce à yylval.
fichier-lex:
%{
#include "y.tab.h"
extern int yylval;
char c;
%}
%s ANOMALIE
%%
^\n              {exit(0);}
<INITIAL>x       {return milieu;}
<INITIAL>[a-wyz] { c=yytext[0]; yylval=c;
                   /* éviter yylval=yytext[0] !!! */
                   return lettre; }
\n               { BEGIN(INITIAL); return finligne; }
<INITIAL>.       { printf("%s: inconnu\n",yytext); BEGIN(ANOMALIE); }
<ANOMALIE>.      ;
fichier-yac:
%token finligne
%token errlex
%left lettre milieu
%%
S : E finligne { if ($1==0) printf("OK\n");
                 else printf("erreur\n");
                 return 0; }
  | error finligne { printf("erreur\n"); return 2; }
  ;
E : lettre E lettre {$$=$2; if ($1!=$3) $$=$2+1;}
  | milieu          {$$=0;}
  ;
%%
yyerror() {;}
main() {while (yyparse()>=0) ;}

3.6.
Si on veut que l'analyseur de la question 2 réalise réellement les calculs, il faut rajouter dans le fichier-lex les instructions permettant à l'analyseur lexical de transmettre les valeurs des nombres à l'analyseur syntaxique et rajouter dans le ficher-yacc les instructions permettant d'effectuer ces calculs. Voici ce qu'on pourrait réaliser :
fichier-lex:
%{
#include "y.tab.h"
extern int yylval;
%}
%s ANOMALIE
%%
^\n           {exit(0);}
<INITIAL>[0-9]+
              { if (yyleng<=6) { yylval=atoi(yytext); return nombre; }
                else { BEGIN(ANOMALIE); return errlex; } }
<INITIAL>"+"  {return plus;}
<INITIAL>"*"  {return mult;}
<INITIAL>"("  {return ouvrante;}
<INITIAL>")"  {return fermante;}
\n            { BEGIN(INITIAL); return finligne; }
<INITIAL>.    { printf("%s: inconnu\n",yytext); BEGIN(ANOMALIE); }
<ANOMALIE>.    ;
ficher-yacc:
%token nombre
%token ouvrante fermante
%token finligne
%token errlex
%left plus
%left mult
%%
S : E finligne     { printf("%d\n",$1); return 0; }
  | error finligne { printf("erreur\n"); return 2; }
  ;
E : E plus E             {$$=$1+$3;}
  | E mult E             {$$=$1*$3;}
  | ouvrante E fermante  {$$=$2;}
  | nombre               {$$=$1;}
  ;
%%
yyerror() {;}
main() {while (yyparse()>=0) ;}

© 2000, 2017 – A. Sigayret