%%
S : M '\n' {printf("j'accepte le mot\n"); return 0; }
;
M : 'a' M 'b' {printf("A->a A b\n");}
|
{printf("A->epsilon\n");}
;
%%
int yylex() {
char c=getchar();
if ((c=='a')||(c=='b')||(c=='\n')) return(c) ;
else {printf("%c: caractere inconnu\n",c); exit(-1);}
}
1.1.
Placer le texte ci-dessus dans un fichier tp4exc1.yac et créer l'analyseur
correspondant avec les commandes :
yacc tp4exc1.yac
gcc y.tab.c -ly
Exécuter. Comment sait-on qu'un mot est accepté ou refusé ?
Quel langage cet analyseur reconnait-il ?
1.2.
Ajouter à la fin du fichier-yacc ci-dessus la ligne :
yyerror(){;}
puis créer le nouvel analyseur. Quelle différence de comportement
par rapport au précédent ?
1.3.
Modifier la première règle de production qui devient :
S : M '\n' {return 0;}
| error '\n' {printf("erreur!\n"); return 1;}
;
puis rajouter en fin de fichier :
main() {
if (yyparse()==0)
printf("mot accepté\n");
else printf("mot refusé\n");
Observer à nouveau les différences de comportement de l'analyseur.
1.4.
Modifier l'analyseur précédent pour
fonctionne en continu (il doit vérifier autant de mots qu'on veut
au lieu de s'arrêter après un mot), et s'arrête quand il rencontre
un caractère inconnu.
N.B. On peut supprimer les affichages intermédiaires des règles de
productions.
Exercice 2
%%
MOT : J '\n'
{printf("j'accepte le mot\n"); return 0;}
;
G : 'a' H
| 'b' J
|
;
H : 'a' G
| 'b' I
| 'a'
;
J : 'a' I
| 'b' G
| 'b'
;
I : 'a' J
| 'b' H
| 'a' 'b'
| 'b' 'a'
;
%%
int yylex() {
char car=getchar();
if (car=='a' || car=='b' || car=='\n') return(car);
else
{ printf("%c: je ne connais pas ce caractere!\n",car); exit(-1);}
}
int yyerror() { printf("je refuse le mot\n"); }
D'après Sophie GIRE, Université de Brest :-)
2.1.
Lancer Yacc sur un fichier-yacc contenant le texte
ci-dessus et noter les messages de conflits.
N.B. On pourra observer l'organisation de l'automate créé en utilisant
l'option -v de Yacc (voirl e cours de compilation).
2.2.
Faire tourner cet analyseur : quel langage reconnaît-il ?
2.3.
Rechercher l'origine des conflits indiqués par Yacc.
Modifier la grammaire en conséquence pour reconnaitre le même langage sans
conflits.
Exercice 3
Créer un analyseur lexico-syntaxique convivial (voir exercice 1, question 4)
pour chacun des langages suivants.
3.1.
Langage des mots bien parenthésés sur l'alphabet {a,b,(,)}.
3.2.
Le langage sur {a,b,c,d} accepté par la grammaire :
S−>AB
A−>a|aTa
B−>b|bTb
T−>c|d|S
Exercice 4
(d'après examen 2003)
Le langage des habitants de la planète One semble simple.
Il y a un nom ('O'), un verbe ('E') et une négation ('N').
Une phrase simple est composée d'un nom suivi d'un verbe,
une unique négation pouvant s'intercaler entre les deux.
Une phrase complexe peut être obtenue en remplaçant le nom ou le verbe
par une phrase (simple ou complexe) entre parenthèses.
Ainsi, les phrases suivantes sont correctes :
"OE", "ONE", "(OE)NE", "O(ONE)", "(ONE)(OE)", "(ONE)N(OE)", "(O((OE)NE))NE",
tandis que les phrases suivantes ne le sont pas :
"EO", "OOE", "NE", "ONNE", "(ONE)OE".
On pourra, au choix accepter ou refuser les parenthésages redondants
comme dans "((OE))N(E)".
Construire un fichier pour Yacc permettant de réaliser un
analyseur reconnaissant le langage "onien", chaque ligne saisie
correspondant à une phrase à analyser.
NB : on utilisera comme fonction yylex() d'analyse lexicale la
fonction suivante qui sera placée dans le code au bon endroit :
int yylex() {
char c=getchar();
if ((c=='O')||(c=='N')||(c=='E')||(c=='(')||(c==')')||(c=='\n'))
{return(c);}
else {printf("%c: inconnu\n",c); exit(-1);}
}