Bonjour,
je veux ecrire un programme qui permet de transformer n'importe quelle grammaire en une grammaire simple,en passant bien sur par les etapes suivantes:
-> rendre la grammaire sous forme de grammaire réduite :
- Productive
- Accessible
-> rendre la grammaire sous forme de grammaire propre :
- Eliminer les £-règles (les règles vides )
- Eliminer les règles unitaires.
j'ai developpé un code en c il compile mais il ne s'éxécute pas pouvez vous m'aider svp?
voila le code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <math.h>
struct regle
{
char A;
char termin[16];
struct regle* next;
};
typedef struct regle RGL;
struct grammaire
{
char nntrmn[16];
char trmn[16];
RGL *r;
char S ;
};
typedef struct grammaire GRM ;
//ajout d'une production
RGL *ajout ( RGL *p, char A,char B[])
{
RGL *p_new;
p_new= (RGL*) malloc (sizeof( *p_new));
if (p_new != NULL)
{
p_new->A=A;
strcpy(p_new->termin,B);
p_new->next = NULL;
if (p == NULL)
{
p = p_new;
}
else
{
RGL *q = p;
while (q->next != NULL)
{
q = q->next;
}
q->next = p_new;
}
}
return p;
}
//saisie d'une grammaire
void saisie()
{
//saisie d'une grammaire
GRM *m;
char NT[16];
char T [16];
char P[80];
char A;
int i, pos, s, e, i1, j;
RGL *p = NULL;
strcpy(NT, argv[1]);
printf("Donner les symboles non terminaux de votre grammaire : %s\n", NT);
// scanf("%s",NT);
strcpy(T, argv[2]);
printf("Donner les symboles terminaux de votre grammaire : %s\n", T);
// scanf("%s",T);
A = argv[3][0];
printf("Donner votre axiome : %c\n", A);
// scanf("%s",A);
strcpy(P, argv[4]);
printf("Veuillez entrer vos regles de productions ( Marquez un ; a la fin de chaque regle et separez votre partie droite de celle gauche par -)\n"
"%s\n", P);
// scanf("%s",P);
for(i = 1; i < strlen(P); i++)
{
if(P[i]=='-')
{
char k[16];
char * kk = k;
for(j = i + 1; P[j] != ';'; j++)
kk += sprintf(kk, "%c", P[j]);
sprintf(kk, "%c", 0);
p = ajout(p, P[i - 1], k);
}
else if(P[i]=='|')
{
char l[16];
char * ll;
pos=0;
char c[16];
char * cc;
ll = l;
cc = c;
for(s = i; P[s] != '-'; s--)
;
pos=s-1;// pour chercher la position du non terminal
for(e = pos + 2; P[e] != '|'; e++)
{
ll += sprintf(ll,"%c",P[e]);
}
sprintf(ll, "%c", 0);
p = ajout(p,P[pos],l);//je récupère la partie droite de la production avant le | et je la mets ds une production
for(i1 = i + 1; P[i1] != ';'; i1++)
{
cc += sprintf(cc,"%c",P[i1]);
}
sprintf(cc, "%c", 0);
p = ajout(p,P[pos],c);//je récupère la partie gauche de la production après le | et je la mets ds une production
}
}
//affichage de la liste des productions
affichage(p);
system("pause");
return 0;
}
// Algorithme1
//suppression d'une production
void supprim_noeud (RGL *r, char x)
{
RGL *m = NULL;
if (r && r->A== x)
{
m = r->next;
r->next = m->next;
free ( m);
m= NULL;
}
}
// fonction existe
int existe(char b[],char t[])
{
int k=0;
int i;
for(i=0;i<strlen(b);i++)
{ if( strchr(t,b[i]) != NULL )
k++;
}
if (k=strlen(b)) return 1;
else return 0;
}
//fonction existance
int existance (char b[],char t[], char prod[])
{
int k=0;
int i;
for( i=0;i<strlen(b);i++)
{ if( (strchr(t,b[i])!= NULL ) || (strchr(prod,b[i])!= NULL ))
k++;
}
if (k=strlen(b)) return 1;
else return 0;
}
// FONCTION calcul prod
void calcul_prod( GRM *m )
{
char prod[16];
char tab[16];
int i,j=0;
RGL *mr;
mr=m->r;
for( ;mr; mr=mr->next)
{
while(existe(mr->termin ,m->trmn))
{
prod[i]= mr->A;
i=i+1;
}
}
for(;mr;mr=mr->next)
{
if (existance(mr->termin, prod,m->trmn))
{
tab[j]=mr->A;
j++;
strcat(prod,tab);
}
}
for(;mr;mr=mr->next)
{
if ( strchr(prod,mr->A)== NULL )
{
supprim_noeud(mr,mr->A); // supprime le noeud
}
}
}
// affichage de la nouvelle liste chainée
//affichage de la liste des productions
void affichage (RGL *p)
{
RGL *q = p;
while (q != NULL)
{
printf ("%s -> %s ", q->A ,q->termin);
q = q->next;
}
printf ("NIL\n");
}
// algo2
// fonction calcul des non terminaux
void calcul_nontermin_accessibles(GRM* m )
{
RGL *mr;
char acc[16];
char h[16];
char v[16];
int i,j,k=0,e=0;
mr=m->r;
acc[0]=m->S ;
for(;mr ;mr=mr->next)
{
if ( strchr(acc,mr->A ) )
{
for (i=0; i< strlen(mr->termin); i++)
{
if(strchr(m->nntrmn,mr->termin[i])!= NULL)
{
h[k]=mr->termin[i];
k++;
}
}
for(j=0; j<strlen(h) ;j++)
{
if ( strchr(acc,h[j] )==NULL)
{
v[e]=h[j];
e++ ;
}
}
strcat (acc,v);
}
else
{
supprim_noeud(mr,mr->A); // supprime noeud
}
}
}
//ALGO 3
void supprem_eps_production (GRM *m )
{
char t[16];
char v[16];
int i=0,j=0;
RGL *mr;
mr= m->r;
for(;mr ;mr=mr->next)
{
if (mr-> termin[0] =='£')
{
t[i]=mr->A ;
i++;
}
}
for(;mr && strchr(t,mr->A)==NULL;mr=mr->next)
{
if (existe (mr->termin, m->nntrmn))
{
if ( existe (mr->termin ,t))
{
v[j]=mr->A;
}
strcat(t,v);
}
}
}
//algo4
// fonction elimination productions unitaires
void product_unitaire(GRM *m )
{
RGL *mr;
RGL *r;
mr=m->r;
char tab[16];
char v[16];
int i=0 ,j,k;
for(;mr ;mr=mr->next)
{
if(strlen(mr->termin) ==1)
{
if(strchr(m->trmn,mr->termin[0]))
{
tab[i]=mr->termin[0];
i++;
v[i]=mr->A;
i++;
}
}
}
for(;mr ;mr=mr->next)
{
for (j=0;j<strlen(tab);j++)
{
if (mr->A== tab[j])
{
mr->A=v[j];
}
}
for(k=0;k<strlen(v);k++)
{
if (mr->A== v[k] && mr->termin[0]==tab[k])
{
supprim_noeud(mr,mr->A); //SUPPRIME NOEUD;
}
}
}
}
//fonction principale
int main(int argc,char argv[])
{
RGL *mr;
RGL *r;
GRM *m;
mr=m->r;
saisie();
calcul_prod( m );
affichage( m->r);
calcul_nontermin_accessibles(m );
affichage( m->r);
product_unitaire(m );
affichage( m->r);
}
