TP de Compilation : une solution de l'exercice 2 du TP 4
2.1.
Yacc affiche :
4 rules never reduced
conflicts: 6 reduce/reduce
Avec l'option -v, Yacc crée un fichier y.output contenant
notamment les informations suivantes :
...
4: reduce/reduce conflict (red'ns 10 and 4 ) on \n
state 4
...
13: reduce/reduce conflict (red'ns 10 and 13 ) on \n
13: reduce/reduce conflict (red'ns 10 and 4 ) on \n
state 13
...
15: reduce/reduce conflict (red'ns 7 and 14 ) on \n
15: reduce/reduce conflict (red'ns 7 and 1 ) on \n
state 15
...
18: reduce/reduce conflict (red'ns 7 and 4 ) on \n
...
Rule not reduced: H : a
Rule not reduced: J : b
Rule not reduced: I : a b
Rule not reduced: I : b a
...
2.2.
Cet analyseur reconnait le langage sur {a,b} ayant un nombre pair de
'a' et un nombre impair de 'b'.
2.3.
Un exemple, le premier conflit :
4: reduce/reduce conflict (red'ns 10 and 4 ) on \n
est dû à la présence des trois règles :
J→bG
J→b
G→ε
qui donnent deux dérivations (J→bG ; G→ε) et (J→b)
pour un même mot "b", Yacc privilégiant la première dérivation.
Par conséquent, la règle J→b ne sera jamais utilisée
(never reduced).
2.4.
Le langage à reconnaitre est rationnel, il est reconnu par le DFA
suivant :
On en déduit une grammaire pour Yacc :
%%
MOT : S '\n' {printf("mot accepté\n"); return 0;}
| error '\n' {printf("mot refusé\n"); return 1;}
;
S : 'b' T
| 'a' W
;
T : 'a' U
| 'b' S
|
;
U : 'a' T
| 'b' W
;
W : 'a' S
| 'b' U
;
%%
int yylex()
{char c=getchar(); if (c=='a' || c=='b' || c=='\n') return(c);
else exit(-1);}
yyerror(){;}
N.B. On pouvait aussi s'inspirer de ce qui a été fait pour
Lex en contournant la difficulté par l'utilisation de deux variables :
%{
int a=0;
int b=0;
%}
%%
MOT : S '\n' {if ((a%2==0)&&(b%2==1))
printf("mot accepté\n");
else printf("mot refusé\n");
a=0; b=0; return 0;}
;
S : 'a' S {a++;}
| 'b' S {b++;}
|
;
© 2000, 2017 – A. Sigayret