teste

Algoritmo para exclusão de símbolos inúteis

Algoritmo apresentado para a cadeira de automatos na UFMA para obtenção da 3ª nota.
Algoritmo de exclusão de símbolos inúteis



#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>


int main(){
    char o,m[26][300],aux[200];
    int i,j,k,l,v,t,elem,pro,dg[26][200],contcoluna=0;
 
    //Apresentação//
    printf("-----------------------------------------------------\n");
    printf("|       Programa em linguagem C para:               |\n");
    printf("|       Exclusao de simbolos inuteis                |\n");
    printf("-----------------------------------------------------\n");
 
    printf("-----------------------------------------------------\n");
    printf("|               Kassio Romulo                       |\n");
    printf("|                CP09126-81                         |\n");
    printf("-----------------------------------------------------\n");
    o=getchar();

    system("cls");
   
//Pega a quantidade inicial de símbolos variáveis//
printf("Qual a quantidade de simbolos variaveis: \t");
scanf("%d",&v);

//Zera a matriz de ocorrências das produções//
for(i=0;i<200;i++){
for(j=0;j<v;j++){
dg[j][i]=0;
m[j][0] = '\0';
}
}
//2 for's para ler as produções da gramática
for(i=0;i<v;i++){
printf("Quantos elementos tem a linha %d:\t",i+1);
scanf("%d",&elem);

for(j=0;j<elem;j++){
printf("Qual o tamanho da producao %d: \t",j+1);
scanf("%d",&pro);

dg[i][j] = pro;
scanf("%s",aux);
strcat(m[i],aux);

}
}
//Limpa a tela
system("cls");
//------------------------------------------------------------------------------//
printf("\t\tG : (V,T,P,S)\n\n");
//Imprime todas as produções em suas respectivas linhas
for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
printf("%c",m[i][k]);
k++;
}
printf(" ");
}
printf("\n");
}
/*
a) Garante que qualquer símbolo é atingível a partir do símbolo inicial. Diretamente e indiretamente.
Contrução de v1
*/
//Primeiramente adiciona as variáveis que setem diretamente para terminais em V1
int cont=0; int flagt=0;
char aux2; char v1[200];

for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
if(m[i][k] >= 'A' && m[i][k]<='Z'){
flagt=1;
}
k++;
}
//Verifica se a variável já pertence a v1, se é a produção inicial sendo testada
for(l=0;l<cont;l++){
if(v1[l] == m[i][0]){flagt=1;}
}
if(flagt == 0){
v1[cont] = m[i][0];
cont++;
}
flagt=0;
}
}


//Agora adiciona as variáveis que setam indiretamente aos terminais
int contador1=strlen(v1)-1, flag=0;

while(contador1 != strlen(v1)){
contador1 = strlen(v1);

for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
if(m[i][k] >= 'A' && m[i][k]<='Z'){
for(l=0;l<cont;l++){
if(v1[l] == m[i][k]){flag=1;}
//Se encontrar um variável de v1 igual ao variável em questão flag=1
}
//Verifica se a variável já pertence a v1, se é a produção inicial sendo testada
for(l=0;l<cont;l++){
if(v1[l] == m[i][0]){flag=0;}
}
//Aqui faz a inclusão do novo símbolo variável a V1
if(flag == 1){
v1[cont] = m[i][0];
cont++;
}
flag=0;
}
k++;
}printf(" ");
}
}

}
printf("\n");

//Agora exclui-se as produções que não setam para nenhuma variável, não pertemcem
//Caso encontre algum variável entre as produções, que não pertença a gramática
//ele será retirado de P e a matriz de ocorrências será reorganizada, gerando então p1
int contaux=0; int contcolunaaux=0; flag=0;
for(i=0;i<v;i++){
k=1;contcoluna=1;
for(j=0;dg[i][j]!=0;j++){
contaux=k;
contcoluna=contcoluna+dg[i][j];
contcolunaaux = contcoluna-1;
while(k<contcoluna){
if(m[i][k] >= 'A' && m[i][k]<='Z'){
for(l=0;l<strlen(v1);l++){
if(v1[l] == m[i][k]){flag=1;}
}
if(flag == 0){
for(l=contaux-1; contcolunaaux < strlen(m[i]); l++){
m[i][l] = m[i][contcolunaaux];
contcolunaaux++;
}
contaux=dg[i][j];
for(l=j;dg[i][l]!=0;l++){
dg[i][l] = dg[i][l+1];
}

}
flag=0;
}
k++;
}printf(" ");
}
}
printf("\n");
//Imprime o vetor V1
printf("V1: ");
for(i=0;i<strlen(v1);i++){
printf("- %c ",v1[i]);
}
printf("\n\n");

//Imprime todas as produções em suas respectivas linhas
for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
printf("%c",m[i][k]);
k++;
}
printf(" ");
}
printf("\n");
}
printf("\n");

/*
b) Garante que qualquer símbolo é alcançavel a partir do incial (S).
Contrução de v2 e T2
*/
char v2[200];
v2[0]='S'; contador1=strlen(v2)-1; flag=0; cont=1;

while(contador1 != strlen(v2)){
contador1 = strlen(v2);

for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
if(m[i][k] >= 'A' && m[i][k]<='Z'){
for(l=0;l<cont;l++){
if(v2[l] == m[i][0]){flag=1;}
//Se encontrar um variável de v2 igual ao variável em questão flag=1
}
//Verifica se a variável já pertence a v2, se for não precisa ser inserida em V2
for(l=0;l<cont;l++){
if(v2[l] == m[i][k]){flag=0;}
}
//Aqui faz a inclusão do novo símbolo variável a V2
if(flag == 1){
v2[cont] = m[i][k];
cont++;
}
}
flag=0;
k++;
}printf(" ");
}
}

}

char t2[200];
int cont2=0, flag2=0; contador1=strlen(t2)-1;
//Construindo T2
while(contador1 != strlen(t2)){
contador1 = strlen(t2);

for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
if(m[i][k] >= 'a' && m[i][k]<='z'){
//Verifica se a variável ja está contida em T2, se for, flag2 = 0
for(l=0;l<cont2;l++){
if(t2[l] == m[i][k]){flag2=0;}
}
//Verifica se a variável pertence a v2, se for que o terminal é inserido em T2
if(flag2==1){
for(l=0;l<cont;l++){
if(v2[l] == m[i][0]){flag2=2;}
}
if(flag2 == 2){
t2[cont2]=m[i][k];
cont2++;
}
}
flag2=1;
}

k++;
}printf(" ");
}
}

}

printf("\n");
//Imprime o vetor V2
printf("V2: ");
for(i=0;i<strlen(v2);i++){
printf("- %c ",v2[i]);
}
printf("\n");
//Imprime o vetor T2
printf("T2: ");
for(i=0;i<strlen(t2);i++){
printf("- %c ",t2[i]);
}
printf("\n");
printf("\n");


//Imprime todas as produções em suas respectivas linhas do resultado final!
flag=0;
for(i=0;i<v;i++){
k=0;contcoluna=0;
for(j=0;dg[i][j]!=0;j++){
contcoluna=contcoluna+dg[i][j];
while(k<contcoluna){
for(l=0;l<strlen(v2);l++){
if(v2[l] == m[i][0]){flag=1;}
}
if(flag==1){
printf("%c",m[i][k]);
}
k++;
flag=0;
}
printf(" ");
}

printf("\n");
}
printf("\n");


printf("\n");
system("pause");

}