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