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 :
DFA 2.4.
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