Usamos cookies para medir audiência e melhorar sua experiência. Você pode aceitar ou recusar a qualquer momento. Veja sobre o iMasters.
Boa noite pessoal,
É meu primeiro post no fórum, havia descoberto ele há alguns dias procurando sobre o mesmo assunto do título, e acho que vocês poderiam me ajudar. O seguinte código representa um AFD simples para o reconhecimento de constantes reais com exponenciação.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
int testePalavra(int contador, char palavra[]);
int testePosicao(int e, int estadoFinal[]);int main() {
char palavra[] = "+32E-52E";
int estadoFinal[] = {3, 5, 9};
int estadoIncial = 0;
int i;
//+ //- //. //E //Digito
int tabelaTransicoes[10][5] = {{1, 1, 2, -1, 3}, //q0
{-1, -1, 2, -1, 3}, //q1
{-1, -1, -1, -1, 5}, //q2
{-1, -1, 4, 6, 3}, //q3
{-1, -1, -1, -1, 5}, //q4
{-1, -1, -1, 6, 5}, //q5
{ 8, 8, -1, -1, 9}, //q6
{-1, -1, -1, -1, 9}, //q8
{-1, -1, -1, -1, 9}}; //q9
int e = estadoIncial;
printf("Estado Inicial q%d\n", e);
int contador = 0;
for (i = 0; i < strlen(palavra); i++) {
char c = palavra[i];
int coluna;
if (c == '+') {
printf("Caractere lido: %c\n", c);
coluna = 0;
} else if (c == '-') {
printf("Caractere lido: %c\n", c);
coluna = 1;
} else if (c == '.') {
printf("Caractere lido: %c\n", c);
coluna = 2;
} else if (c == 'E') {
printf("Caractere lido: %c\n", c);
coluna = 3;
} else if (isdigit(c)) {
printf("Caractere lido: %c\n", c);
coluna = 4;
} else {
printf("Caractere lido: %c\n", c);
coluna = -1;
printf(" Transicao invalida: Caractere nao aceito!\n");
break;
}
e = tabelaTransicoes[e][coluna];
if (e != -1) {
contador++;
printf(" Transicao para q%d", e);
if (testePosicao(e, estadoFinal))
printf(" | Estado Final");
else
printf(" | Estado Nao-Final");
printf("\n");
}
else{
printf(" Transicao invalida: Erro de leitura!\n");
break;
}
}
if ((testePalavra(contador, palavra)) && (testePosicao(e, estadoFinal))) {
printf("\nA palavra %s foi aceita pelo AFD!", &palavra);
} else{
printf("\nA palavra %s foi recusada pelo AFD!", &palavra);
}
return 0;
}int testePalavra(int contador, char palavra[]){ //Teste para verificar se a
if (contador == strlen(palavra))
return 1;
else
return 0;
}int testePosicao(int e, int estadoFinal[]){ //Teste para verificar se a posição em que a palavra terminou é estado final
int i;
int status = 0;
for(i = 0; i < sizeof(estadoFinal); i++){
if (e == estadoFinal[i]){
status = 1;
break;
}
}
return status;
}int tabelaTransicoes[10][5] = {{1, 1, 2, -1, 3}, //q0
{-1, -1, 2, -1, 3}, //q1
{-1, -1, -1, -1, 5}, //q2
{-1, -1, 4, 6, 3}, //q3
{-1, -1, -1, -1, 5}, //q4
{-1, -1, -1, 6, 5}, //q5
{ 8, 8, -1, -1, 9}, //q6
{ 0, 0, 0, 0, 0}, //q7
{-1, -1, -1, -1, 9}, //q8
{-1, -1, -1, -1, 9}}; //q9
//EDIT 2: Problema corrigido apenas por inserir um novo array na matriz, "q7", com todos os valores 0.
//O porquê eu não sei hahahaha ainda estou em dúvida! Se alguém souber responder, agradeço!
#Estou fazendo um trabalho da faculdade, em que foi pedido um AFD para reconhecimento de constantes reais com exponenciação, e acabei de concluí-lo, porém estou #com um erro totalmente sem sentido, que ainda não consegui compreender o que é.
#A palavra que estou usando como teste demonstra o erro, segundo a tabela de transições, quando eu chego no estado q9 eu não posso mais sair dele (e isso está explícito #na matriz que eu declarei), porém de alguma forma ela está voltando para q5, o que possibilita inserir um E após os dígitos.
#Preciso da resposta urgente, quem puder me ajudar agradeço!
Problema acima corrigido, agora preciso saber o porquê de essa alteração ter resolvido..
>
Em 2017-6-21 at 12:40, _Isis_ disse:
->Altere aquele sizeof no loop. O sizeof te dá o tamanho do array em bytes. Se você precisa do tamanho como quantidade de elementos presentes no array, precisa dividir o tamanho em bytes do array pelo tamanho em bytes do tipo do array (sizeof(estadoFinal)/sizeof(int))
Agradeço pela explicação! Não sabia deste detalhe, ou talvez não lembrasse, estou meio enferrujado em C hahaha..
>
Em 2017-6-21 at 12:40, _Isis_ disse:
Então a única alteração que fiz no código foi inserir um break no if
-> Não esqueça que existe um loop lendo a palavra. Para uma palavra válida o estado final corresponde ao final da palavra (último caractere lido, a princípio... não me parece que você está trabalhando com transições "vazias") então isso vai corresponder ao final do loop (a condição do for vai ser falsa e o loop, interrompido). Mas para uma palavra inválida, cujo estado final pode estar já no início da palavra, esse loop precisa ser interrompido "no braço".
Agora, um pequeno adendo aqui, segundo o AFD pelo problema proposto, a palavra pode tanto sair de alguns estados finais, quanto retornar a eles, o importante é que o último caractere lido pelo mesmo seja um estado final, portanto poderia chegar a um estado final no meio da palavra e ir para um estado não-final e voltar a assumir um estado final novamente ao fim da palavra.
Perceba (pela matriz) que a palavra pode transitar do estado q3 (final) para o estado q6 (não final), e deste para o q9 (final novamente), e ser aceita (válida). Apenas invertendo a ordem do que você escreveu "Para uma palavra válida, o final da palavra corresponde a um estado final".
Não sei se você fez a alteração apenas por teste, mas a ideia aqui é justamente não ter um break.
Como que ficou teu autômato no papel? Tava tentando lembrar como era a gramática do C p/ constante com exponenciação, mas não achei o documento técnico.
https://goo.gl/photos/9YdLNgkxCAXfEXdN7
(Faltou a transição do q0 p/ q6 caso você informe qq coisa diferente de +,- ou dígito)
Entenda o asterisco como "qualquer coisa que não tenha uma transição especificada".
>
1 hora atrás, _Isis_ disse:
Como que ficou teu autômato no papel? Tava tentando lembrar como era a gramática do C p/ constante com exponenciação, mas não achei o documento técnico.
https://goo.gl/photos/9YdLNgkxCAXfEXdN7
(Faltou a transição do q0 p/ q6 caso você informe qq coisa diferente de +,- ou dígito)
Entenda o asterisco como "qualquer coisa que não tenha uma transição especificada".
Segue o diagrama de transições do AFD
/applications/core/interface/imageproxy/imageproxy.php?img=https://image.prntscr.com/image/ub_VgH2_QkmcITBx3Bm1eQ.png&key=182bf3f7679d9d783d632bb7478521ef31a6b88cfec09168f1ecb7e8b730742e" />
Isso te ajuda? Não tentei simplificar o autômato.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
const int ESTADOS_FINAIS[] = {6,8,9};
const int ESTADOS_ERRO[] = {9};int indexOf(const int * arr, int size, int element) {
int i;
for(i=0; i<size && element != arr[i]; i++);
return (i >= size)? -1 : i;
}int isErro(int estado) {
return (indexOf(ESTADOS_ERRO, sizeof(ESTADOS_ERRO)/sizeof(int), estado) != -1);
}int isFinal(int estado) {
return (indexOf(ESTADOS_FINAIS, sizeof(ESTADOS_FINAIS)/sizeof(int), estado) != -1);
}int localizar_estado(char c, int estado_atual) {
int proximo_estado = 9; // define o estado de erro como padrão.
if (c == '+') {
proximo_estado = AFD[estado_atual][0];
} else if (c == '-') {
proximo_estado = AFD[estado_atual][1];
} else if (c == '.') {
proximo_estado = AFD[estado_atual][2];
} else if (isdigit(c)) {
proximo_estado = AFD[estado_atual][3];
} else if (c == 'e') {
proximo_estado = AFD[estado_atual][4];
} else {
proximo_estado = AFD[estado_atual][5];
}
return proximo_estado;
}int main(void) {
const char * palavra = "+3.389E-10.8";
int estado_atual = 0;
int i;
for(i = 0; i < strlen(palavra) && !isErro(estado_atual); i++) {
printf("-- Estado atual: %d --\n", estado_atual);
printf("Processando caractere: %c\n", palavra[i]);
estado_atual = localizar_estado(tolower(palavra[i]), estado_atual);
}
if (i >= strlen(palavra) && !isFinal(estado_atual)) {
printf("Palavra \t%s\t não aceita.", palavra);
} else {
if (isFinal(estado_atual)) {
printf("Palavra \t %s \t %saceita.\n", palavra, isErro(estado_atual)? "não ":"");
} else {
printf("Palavra \t %s \t não aceita.\n");
}
}
return 0;
}>
37 minutos atrás, _Isis_ disse:
Isso te ajuda? Não tentei simplificar o autômato.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
const int ESTADOS_FINAIS[] = {6,8,9};
const int ESTADOS_ERRO[] = {9};int indexOf(const int * arr, int size, int element) {
int i;
for(i=0; i<size && element != arr[i]; i++);
return (i >= size)? -1 : i;
}int isErro(int estado) {
return (indexOf(ESTADOS_ERRO, sizeof(ESTADOS_ERRO)/sizeof(int), estado) != -1);
}int isFinal(int estado) {
return (indexOf(ESTADOS_FINAIS, sizeof(ESTADOS_FINAIS)/sizeof(int), estado) != -1);
}int localizar_estado(char c, int estado_atual) {
int proximo_estado = 9; // define o estado de erro como padrão.
if (c == '+') {
proximo_estado = AFD[estado_atual][0];
} else if (c == '-') {
proximo_estado = AFD[estado_atual][1];
} else if (c == '.') {
proximo_estado = AFD[estado_atual][2];
} else if (isdigit(c)) {
proximo_estado = AFD[estado_atual][3];
} else if (c == 'e') {
proximo_estado = AFD[estado_atual][4];
} else {
proximo_estado = AFD[estado_atual][5];
}
return proximo_estado;
}int main(void) {
const char * palavra = "+3.389E-10.8";
int estado_atual = 0;
int i;
for(i = 0; i < strlen(palavra) && !isErro(estado_atual); i++) {
printf("-- Estado atual: %d --\n", estado_atual);
printf("Processando caractere: %c\n", palavra[i]);
estado_atual = localizar_estado(tolower(palavra[i]), estado_atual);
}
if (i >= strlen(palavra) && !isFinal(estado_atual)) {
printf("Palavra \t%s\t não aceita.", palavra);
} else {
if (isFinal(estado_atual)) {
printf("Palavra \t %s \t %saceita.\n", palavra, isErro(estado_atual)? "não ":"");
} else {
printf("Palavra \t %s \t não aceita.\n");
}
}
return 0;
}
Ajuda sim, muito obrigado!
Mas no caso, já solucionei o problema, conforme escrevi no post original, o único que ficou faltando foi a inserção do q7, a qual realizei depois, e solucionou o problema de ele (de alguma forma que eu não compreendi) estar no estado q9 e ir para o q5 (o que seria impossível, pois q9 não tem transição para q5)Sim, mas se você montar o autômato seguindo a tua tabela de transição, ele não vai fazer sentido nenhum porque a princípio, q7 é um estado inalcançável. Eu alterei os estados e a matriz de transição (ao invés de pular o q7 e ter somente o q8 e q9, mudei p/ q7 e q8) e alterei a condição do for do testeFinal (for(i = 0; i <= sizeof(estadoFinal)/sizeof(int) ; i++)).
Ele ainda processa o 'E' que está no expoente, mas atinge o -1 e recusa. O comportamento está certo.
Agora, se você quer um autômato LR(1) a coisa vai ser mais complicada.
int estadoFinal[] = {3, 5, 8};
int estadoIncial = 0;
int i;
//+ //- //. //E //Digito
int tabelaTransicoes[9][5] = {{1, 1, 2, -1, 3}, //q0
{-1, -1, 2, -1, 3}, //q1
{-1, -1, -1, -1, 5}, //q2
{-1, -1, 4, 6, 3}, //q3
{-1, -1, -1, -1, 5}, //q4
{-1, -1, -1, 6, 5}, //q5
{ 7, 7, -1, -1, 8}, //q6
{-1, -1, -1, -1, 8}, //q7
{-1, -1, -1, -1, 8}}; //q8>
Citar
Estado Inicial q0
Caractere lido: 3
Transicao para q3 | Estado Final
Caractere lido: E
Transicao para q6 | Estado Nao-Final
Caractere lido: 2
Transicao para q8 | Estado Final
Caractere lido: E
Transicao invalida: Erro de leitura!
A palavra 3E2E foi recusada pelo AFD!
Eu fiz aqui um teste de mesa com o que você passou no código e ao chegar no primeiro dígito da palavra ele já não aceita (apesar de seguir em frente) porque o novo valor de e corresponde a um dos estados finais. Então a única alteração que fiz no código foi inserir um break no if:
if (testePosicao(e, estadoFinal)) {