« Les expressions correctes sont constituées d'un nombre quelconque mais non nul de 'a', suivi d'un 'b', suivi d'un nombre quelconque éventuellement nul de 'c'.»
Exercice : Faire le même travail que précédemment.
<expression> ::= <groupe a> «b» <liste c>
<groupe a> ::= «a» <suite a>
<suite a> ::= <groupe a>
::=
<liste c> ::= «c» <liste c>
::=
Cet analyseur syntaxique pur répond par « Bon » ou « Mauvais » .
#include <stdio.h>
char s[512];
char **ss;
int expression(){
if (groupea()==1)
if (*ss == 'b'){
ss++;
return listec();
}
return 0;
}
int groupea(){
if (*ss == 'a'){
s++;
return suitea();
}
return 0;
}
int suitea(){
if (groupea() == 0)
return 1;
return 1;
}
int listec(){
if (*ss == '\0')
return 1;
else
if (*ss == 'c'){
ss++;
listec();
} else
return 0;
}
int main(){
printf("Une expression à analyser ? \n");
scanf("%s",s);
ss = s;
if (expression()==1)
if (*ss == '\0')
printf("Bon \n");
else
printf("Mauvais\n");
else
printf("Mauvais\n");
}
int groupea(){
if (*ss == 'a'){
s++;
return suitea();
} else {
printf("L'expression doit commencer par a \n");
return 0;
}
}
int suitea(){
if (*ss == 'a'){
ss++;
return suitea();
}
return 1;
}
int main(){
printf("Une expression a analyser ? \n");
scanf("%s",s);
ss = s;
if (expression()==1)
if (*ss == '\0')
printf("Bon \n");
else
printf("Il n'y a que des c après le b\n");
}
int expression(){
if (groupea()==1)
if (*ss=='b'){
ss++;
return listec();
} else {
printf("Apres le(s) a il doit y avoir un b");
}
return 0;
}
#include <stdio.h> // déclaration des fonctions et structures char s[512]; char *ss; struct Expression{ int zero; int un; }; struct Expression expression(){ struct Expression a; a.zero = groupe0(); if (a.zero !=0) a.un = groupe1(); return a; }; int groupe0(){ if (*ss == '0'){ ss++; return 1+suite0(); } printf("L'expression doit commencer par 0\n"); return 0; } int suite0(){ if (*ss == '0'){ ss++; return 1+suite0(); } return 0; } int groupe1(){ if (*ss == '1'){ ss++; return 1+suite1(); } return 0; } int suite1(){ if (*ss == '1'){ ss++; return 1+suite1(); } return 0; } // programme principal int main(){ printf("Une expression a analyser ? \n"); scanf("%s",s); ss = s; struct Expression E = expression(); if (*ss == '\0'){ printf("Bon \n"); printf("Nombre de 0 :%d, de 1 :%d\n",E.zero, E.un);} else if (*ss == '0') printf("Un 0 ne peut suivre des 1."); else printf("Caractère interdit : %c\n",*ss); }
Les expressions algébriques à analyser sont constituées :
Exemple :
a+b+c*(d+e*(f+g))*((h+i)*j+k*l)+(m+n+o)*(p+q)*r
On souhaite ici faire le même travail que précédemment, tout en sachant que la grammmaire devra tenir compte des deux opérateurs hiérarchisés.
Les règles sont les suivantes :
<somme> ::= <terme> <finSomme>
<finSomme> ::= «+» <somme>
::=
<terme> ::= <facteur> <finProduit>
<finProduit> ::= «*» <terme>
::=
<facteur> ::= <variable>
::= «(» <somme> «)»
<variable> ::= «a» ... «z» (notation non BNF)
Exercice : Écrire l'analyseur syntaxique pur.
On pensera à inclure la bibliothèque ctype, permettant la reconnaissance de caractères.
#include <stdio.h>
#include <ctype.h>
char s[512];
char *ss;
int somme(){
if (terme() == 1)
return finSomme();
return 0;
}
int finSomme(){
if (*ss == '+'){
ss++;
return somme();
}
return 1;
}
int terme(){
if (facteur() == 1;
return finProduit();
return 0;
}
int finProduit(){
if (*ss == '*'){
ss++;
return terme();
}
return 1;
}
int facteur(){
if (variable ==1)
return 1;
if (*ss == '('){
ss++;
if (somme() == 1)
if (*ss ==')'){
ss++;
return 1;
}
return 0;
}
}
int variable(){
if (isalpha(*ss)){
ss++;
return 1;
}
return 0;
}
int main(){
printf("\n Une expression à analyser ? ");
scanf("%s»,s);
ss=s;
if (somme() == 1)
if (*ss == '\0')
printf("Bon\n");
else
printf("Mauvais\n");
else
printf("Mauvais\n")
Exercice : Adaptez la grammaire pour qu'elle gère la soustraction et la division.
<somme> ::= <terme> <finSomme>
<finSomme> ::= <operateurAdditif> <somme>
::=
<operateurAdditif> ::= «+»
::= «-»
<terme> ::= <facteur> <finProduit>
<finProduit> ::= <operateurMultiplicatif> <terme>
::=
<operateurMultiplicatif> ::= «*»
::= «/»
<facteur> ::= <variable>
::= «(» <somme> «)»
<variable> ::= «a» ... «z»
#include <stdio.h>
#include <ctype.h>
char s[512];
char *ss;
int somme(){
if (terme() == 1)
return finSomme();
return 0;
}
int finSomme(){
if (*ss == '+' || *ss == '-'){
ss++;
return somme();
}
return 1;
}
int terme(){
if (facteur() == 1;
return finProduit();
return 0;
}
int finProduit(){
if (*ss == '*' || *ss == '/'){
ss++;
return terme();
}
return 1;
}
int facteur(){
if (*ss == '('){
if (*ss == '-' || *ss == '+') ss++;
ss++;
if (somme() == 1)
if (*ss ==')'){
ss++;
return 1;
}else{
printf("Il manque une parenthèse fermante.\n");
return 0;
}
}else{
if (*ss == '-' || *ss == '+') ss++;
if (isalpha(*ss)){
ss++;
return 1;
}else{
printf("\n\n ATTENTION :\n");
if (*ss == '+' || *ss == '-' || *ss == '/' || *ss == '*')
printf("Deux opérateurs ne peuvent pas se suivre");
else
if (*ss == '\0')
printf("L'expression ne peut pas se terminer par un opérateur");
else
printf("Ce caractere ne fait pas partie de la grammaire : %c \n.", *ss);
return 0;
}
}
}
int variable(){
if (isalpha(*ss)){
ss++;
return 1;
}
return 0;
}
int main(){
printf("\n Une expression à analyser ?");
scanf("%s",s);
ss=s;
if (*ss == '*' || *ss '/'){
printf("Ne peut pas commencer par un opérateur binaire");
return c;
}
if (somme() == 1)
if (*ss == '\0')
printf("Bon\n");
else{
printf("Attention\n");
if (isalpha(*ss))
printf("Deux variables ne peuvent se suivre.\n");
else if (*ss == '(' || *ss == ')')
printf("Caractère mal placé : %c", *ss);
else
printf("Ce caractère ne fait pas parti de la grammaire : %c \n",*ss);
}
}
printf("\n");
return 1;
}
On utilise les arbres : a+b+c devient
+
\
+ c
/ \
a b
et -a+b :
+
/ \
- b
|
a
On est en effet obligé d'associer à gauche pour la soustraction (sinon on change l'expression).
Exercice : Programmez cette structure d'arbre, puis la version sémantique.
typedef enum {FEUILLE, UNAIRE, BINAIRE} Tnoeud;
typedef struct arbre{
Tnoeur selecteur;
union{
char var;
struct{
char operateur;
struct arbre* fs;
} un;
struct{
char operateur;
struct arbre* fd;
struct arbre* fg;
} bin;
} type;
} arbre;
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define amalloc (arbre*)malloc (sizeof(arbre))
#define ANULL (arbre*) NULL
arbre* feuille(char var){
arbre* a = ANULL;
if ((a = amalloc) != ANULL{
a->selecteur = FEUILLE;
a->t.var = var;
}
return a;
}
arbre* unaire(char op, arbre* fs){
arbre* a = ANULL;
if (fs != ANULL)
if ((a=amalloc) != ANULL){
a->sel.UNAIRE;
a->t.un.op=op;
a->t.un.fs=fs;
}
return a;
}
arbre* binaire(char op, arbre* fg, arbre* fd){
arbre* a = ANULL;
if (fg != ANULL && fd != ANULL)
if ((a=amalloc) != ANULL){
a->sel.BINAIRE;
a->t.un.op=op;
a->t.un.fg=fg;
a->t.un.fd=fd;
}
return a;
}
void printa(arbre* a){
switch (a->sel){
case FEUILLE : printf("%c",a->t.var);
break;
case UNAIRE : printf("%c(",a->t.un.op);
printa(a->t.un.fs);
printf(")");
break;
case BINAIRE : printf("%c(",a->t.bin.op);
printa(a->t.bin.fg);
printf(",");
printa(a->t.bin.fd);
printf(")");
break;
}
}
void print_arbre(arbre* a){
if (a != NULL)
printa (a);
else
printf("Arbre vide\n");
printf("\n");
}
#define cmalloc(n) (char*)malloc((n)*sizeof(char))
#define crealloc(ptr,n) (char*)realloc(ptr,(n)*sizeof(char))
#define CNULL (char*)NULL
#define BLOC 16
char* lire_chaine(){
char *s, *ss, *ssmax;
int taille, c;
if ((s = cmalloc(BLOC))==CNULL){
fprintf(stderr,»Memoire saturee\n");
exit(43);
}
ss=s;
taille = BLOC;
smax = s + taille;
while ((c=getchar()) != '\n'){
*ss++ = (char)c;
if (ss == smax){
if ((s=crealloc(c,taille+BLOC))==CNULL){
fprintf(stderr,»Memoire saturee\n")
exit(44);
}
ss=s+taille;
taille += BLOC;
smax = s+taille;
}
}
*ss++ = '\0';
return crealloc(s,ss-s);
}
On souhaite rajouter le - unaire ; son analyse intervient au niveau du facteur :