O programa apresentado supõe entrada e saída no formato do problema "ET Phone Home". O arquivo de teste original pode ser baixado de http://www.ime.usp.br/~cef/Xmaratona/problems/io/. Entretanto, o código apresentado aqui não é uma solução adequada, por ser muito lento.
O código abaixo é uma adaptação direta do algorítimo, sem grandes otimizações. Uma lista ligada é usada para implementar os conjuntos de estados. Isto tem a vantagem de simplificar as atividades de inserir e percorrer os conjuntos, porém deixa muito ineficiente a verificação da presença de um estado no conjunto. Um levantamento rápido acusou que cerca de 40% do tempo de processamento é executando a função Presente, que faz uma busca sequencial no conjunto.
As regras para cada não terminal também são armazenadas como uma lista ligada, sem impacto significativo no desempenho.
O define DEBUG controla a listagem dos estados. Esta listagem serve tanto para depuração do código como para permitir examinar o funcionalmento do algorítimo, listando os estados que estão sendo analisados e os novos estados acrescentados por Completer, Predictor e Scanner.
// Earley Parsing
// Daniel Quadros, 2011
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FALSE 0
#define TRUE 1
// define para mostrar mensagens de acompanhamento
#define DEBUG
// Dimensionamento (problema "ET Phone Home")
#define N_NT 27 // @A..Z
#define T_REGRA 2 // tamanho do texto da regra após "-> "
#define T_TEXTO 50 // tamanho máximo do texto a analisar
// terminais
char term [96]; // "caracteres imprimíveis" (0x21 a 0x7E)
// não terminais
char nt [N_NT]; // não terminais
// regras
typedef struct _regra
{
char dest; // NT descrito pela regra
int tam; // tamanho do texto da regra
char texto[T_REGRA]; // texto da regra
char nt [T_REGRA]; // nt[i] indica se texto[i] é NT
struct _regra *prox; // para a lista ligada de regras
} REGRA;
REGRA *tbRegra [N_NT]; // regras para os não terminais
// tbRegra[0] é a regra para a raiz
// state
typedef struct _state
{
REGRA *pRegra; // ponteiro para a regra sendo aplicada
int ponto; // posição onde estamos na regra
int inicio; // posição no texto onde começa o reconhecimento
struct _state *prox; // para lista ligada
} STATE;
STATE *S [T_TEXTO+2]; // um conjunto de estados para cada posição no texto
// Libera a memória alocada para as regras
void LimpaRegras (void)
{
REGRA *pRegra, *prox;
int i;
for (i = 0; i <= N_NT; i++)
{
prox = tbRegra[i];
while (prox != NULL)
{
pRegra = prox;
prox = pRegra->prox;
free (pRegra);
}
tbRegra[i] = NULL;
}
}
// Libera a memória alocada para os estados
void LimpaStates (void)
{
STATE *pSt, *prox;
int i;
for (i = 0; i <= (T_TEXTO+1); i++)
{
prox = S[i];
while (prox != NULL)
{
pSt = prox;
prox = pSt->prox;
free (pSt);
}
S[i] = NULL;
}
}
// Carrega as regras, que devem estar no formato do
// problema "ET Phone Home"
int CarregaRegras (void)
{
char cNT;
char szRegra [T_REGRA+6]; // "X -> texto\0"
REGRA *pRegra;
int i;
// elemento raiz
if (scanf ("%c\n", &cNT) != 1)
return FALSE;
// cria a regra @ -> raiz <vazio>
pRegra = (REGRA *) malloc (sizeof (REGRA));
pRegra->dest = '@';
pRegra->tam = 1;
pRegra->texto[0] = cNT;
pRegra->nt[0] = TRUE;
pRegra->prox = NULL;
tbRegra[0] = pRegra;
// não terminais (não inclui o @)
gets (nt);
// terminais
gets (term);
// regras
for (;;)
{
gets (szRegra);
if (szRegra [0] == '#')
break; // "# -> #" indica fim das regras
cNT = szRegra [0] - '@'; // não terminal sendo definido
pRegra = (REGRA *) malloc (sizeof (REGRA));
pRegra->dest = szRegra [0];
pRegra->tam = strlen (szRegra) - 5;
for (i = 0; i < pRegra->tam; i++)
{
pRegra->texto[i] = szRegra[i+5];
pRegra->nt[i] = strchr (term, szRegra[i+5]) == NULL;
}
pRegra->prox = tbRegra [cNT];
tbRegra [cNT] = pRegra;
}
return TRUE;
}
// Lista um estado para depuração
void DumpState (char *prefixo, STATE *pSt)
{
#ifdef DEBUG
REGRA *pReg = pSt->pRegra;
char regra [100];
int i, j, t;
t = pReg->tam + 6; // X <- xxx.xxx
regra[0] = pReg->dest;
regra[1] = ' ';
regra[2] = '<';
regra[3] = '-';
regra[4] = ' ';
for (i = 0, j = 5; j < t; i++)
{
if (i == pSt->ponto)
regra[j++] = '.';
if (i < pReg->tam)
regra[j++] = pReg->texto[i];
}
regra[t] = 0;
printf ("%s%s,%d\n", prefixo, regra, pSt->inicio);
#endif
}
// Verifica se um estado já está em um conjunto
int Presente (STATE *pSt, int i)
{
STATE *pSt2 = S[i];
while (pSt2 != NULL)
{
if ((pSt2->inicio == pSt->inicio) && (pSt2->ponto == pSt->ponto) &&
(pSt2->pRegra == pSt->pRegra))
return TRUE;
pSt2 = pSt2->prox;
}
return FALSE;
}
// Verifica se uma palavra obedece à gramática
int Analisa (char *palavra)
{
int i, n;
STATE *pSt, *pSt2, *pSt3;
n = strlen(palavra);
// coloca o estado inicial
pSt = (STATE *) malloc (sizeof (STATE));
pSt->pRegra = tbRegra[0];
pSt->ponto = 0;
pSt->inicio = 0;
pSt->prox = NULL;
S[0] = pSt;
// cria os conjuntos de estados
for (i = 0; i <= n; i++)
{
#ifdef DEBUG
printf ("> Conjunto %d\n", i);
#endif
pSt = S[i];
while (pSt != NULL)
{
DumpState (" Analisando: ", pSt);
if (pSt->ponto == pSt->pRegra->tam)
{
// Completer: reconheceu a regra
// testar se acabou
// se não, colocar no set atual as regras antigas avançando o ponto
if ((i == n) && (pSt->pRegra == tbRegra[0]) && (pSt->inicio == 0))
return TRUE;
pSt3 = S[pSt->inicio];
while (pSt3 != NULL)
{
int pto = pSt3->ponto;
char rec = pSt->pRegra->dest;
if (pSt3->pRegra->nt[pto] && (pSt3->pRegra->texto[pto] == rec))
{
pSt2 = (STATE *) malloc (sizeof (STATE));
pSt2->pRegra = pSt3->pRegra;
pSt2->ponto = pSt3->ponto + 1;
pSt2->inicio = pSt3->inicio;
if (Presente (pSt2, i))
free (pSt2);
else
{
pSt2->prox = pSt->prox;
pSt->prox = pSt2;
DumpState (" Completer: ", pSt2);
}
}
pSt3 = pSt3->prox;
}
}
else if (pSt->pRegra->nt[pSt->ponto])
{
// Predictor: tentar reconher o NT
// colocar no set atual as regras do NT
REGRA *pReg = tbRegra [pSt->pRegra->texto[pSt->ponto] - '@'];
while (pReg != NULL)
{
pSt2 = (STATE *) malloc (sizeof (STATE));
pSt2->pRegra = pReg;
pSt2->ponto = 0;
pSt2->inicio = i;
if (Presente (pSt2, i))
free (pSt2);
else
{
pSt2->prox = pSt->prox;
pSt->prox = pSt2;
DumpState (" Predictor: ", pSt2);
}
pReg = pReg->prox;
}
}
else if (pSt->pRegra->texto[pSt->ponto] == palavra[i])
{
// Scanner: avançou um terminal na regra, colocar no Set seguinte
pSt2 = (STATE *) malloc (sizeof (STATE));
pSt2->pRegra = pSt->pRegra;
pSt2->ponto = pSt->ponto + 1;
pSt2->inicio = pSt->inicio;
if (Presente (pSt2, i+1))
free (pSt2);
else
{
pSt2->prox = S[i+1];
S[i+1] = pSt2;
DumpState (" Scanner: ", pSt2);
}
}
pSt = pSt->prox;
}
if (S[i+1] == NULL)
return FALSE; // não sobrou opção
}
return FALSE;
}
// Programa Principal
// Processa entrada no formato do problema "ET Phone Home"
int main (void)
{
int iCaso = 1;
char palavra [51];
while (CarregaRegras())
{
printf ("Instancia %d\n", iCaso);
scanf ("%s\n", palavra);
while (palavra[0] != '#')
{
if (Analisa (palavra))
printf ("%s e uma palavra valida\n", palavra);
else
printf ("%s nao e uma palavra valida\n", palavra);
LimpaStates ();
scanf ("%s\n", palavra);
}
printf ("\n");
LimpaRegras ();
iCaso++;
}
return 0;
}
Nenhum comentário:
Postar um comentário