Minhas Aventuras com "Parsing": Implementando o Earley Parser

Passada a "Semana ZX81", é hora de retomar esta série de posts, apresentando uma implementação em C do algorítimo Earley Parser.

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.

view plaincopy to clipboardprint?

1. // Earley Parsing  
2. // Daniel Quadros, 2011  
3.   
4. #include <stdio.h>  
5. #include <stdlib.h>  
6. #include <string.h>  
7.   
8. #define FALSE   0  
9. #define TRUE    1  
10.   
11. // define para mostrar mensagens de acompanhamento  
12. #define DEBUG  
13.   
14. // Dimensionamento (problema "ET Phone Home")  
15.   
16. #define N_NT    27      // @A..Z  
17. #define T_REGRA 2       // tamanho do texto da regra após "-> "  
18. #define T_TEXTO 50      // tamanho máximo do texto a analisar  
19.   
20. // terminais  
21. char term [96];     // "caracteres imprimíveis" (0x21 a 0x7E)  
22.   
23. // não terminais  
24. char nt [N_NT];       // não terminais  
25.   
26. // regras  
27. typedef struct _regra  
28. {  
29.     char   dest;            // NT descrito pela regra  
30.     int    tam;             // tamanho do texto da regra  
31.     char   texto[T_REGRA];  // texto da regra  
32.     char   nt   [T_REGRA];  // nt[i] indica se texto[i] é NT  
33.     struct _regra *prox;    // para a lista ligada de regras  
34. } REGRA;  
35.   
36. REGRA *tbRegra [N_NT];      // regras para os não terminais  
37.                             // tbRegra[0] é a regra para a raiz   
38.   
39. // state  
40. typedef struct _state  
41. {  
42.     REGRA *pRegra;          // ponteiro para a regra sendo aplicada  
43.     int   ponto;            // posição onde estamos na regra  
44.     int   inicio;           // posição no texto onde começa o reconhecimento  
45.     struct _state *prox;    // para lista ligada  
46. } STATE;  
47.   
48. STATE *S [T_TEXTO+2];       // um conjunto de estados para cada posição no texto  
49.   
50.   
51. // Libera a memória alocada para as regras  
52. void LimpaRegras (void)  
53. {  
54.     REGRA *pRegra, *prox;  
55.     int i;  
56.   
57.     for (i = 0; i <= N_NT; i++)  
58.     {  
59.         prox = tbRegra[i];  
60.         while (prox != NULL)  
61.         {  
62.             pRegra = prox;  
63.             prox = pRegra->prox;  
64.             free (pRegra);  
65.         }  
66.         tbRegra[i] = NULL;  
67.     }  
68. }  
69.   
70.   
71. // Libera a memória alocada para os estados  
72. void LimpaStates (void)  
73. {  
74.     STATE *pSt, *prox;  
75.     int i;  
76.   
77.     for (i = 0; i <= (T_TEXTO+1); i++)  
78.     {  
79.         prox = S[i];  
80.         while (prox != NULL)  
81.         {  
82.             pSt = prox;  
83.             prox = pSt->prox;  
84.             free (pSt);  
85.         }  
86.         S[i] = NULL;  
87.     }  
88. }  
89.   
90.   
91. // Carrega as regras, que devem estar no formato do  
92. // problema "ET Phone Home"  
93. int CarregaRegras (void)  
94. {  
95.     char cNT;  
96.     char szRegra [T_REGRA+6];   // "X -> texto\0"  
97.     REGRA *pRegra;  
98.     int i;  
99.   
100.   
101.     // elemento raiz  
102.     if (scanf ("%c\n", &cNT) != 1)  
103.         return FALSE;  
104.   
105.     // cria a regra @ -> raiz <vazio>  
106.     pRegra = (REGRA *) malloc (sizeof (REGRA));  
107.     pRegra->dest = '@';  
108.     pRegra->tam = 1;  
109.     pRegra->texto[0] = cNT;  
110.     pRegra->nt[0] = TRUE;  
111.     pRegra->prox = NULL;  
112.     tbRegra[0] = pRegra;  
113.   
114.     // não terminais (não inclui o @)  
115.     gets (nt);  
116.   
117.     // terminais  
118.     gets (term);  
119.   
120.     // regras  
121.     for (;;)  
122.     {  
123.         gets (szRegra);  
124.         if (szRegra [0] == '#')  
125.             break;                  // "# -> #" indica fim das regras  
126.         cNT = szRegra [0] - '@';    // não terminal sendo definido  
127.         pRegra = (REGRA *) malloc (sizeof (REGRA));  
128.         pRegra->dest = szRegra [0];  
129.         pRegra->tam = strlen (szRegra) - 5;  
130.         for (i = 0; i < pRegra->tam; i++)  
131.         {  
132.             pRegra->texto[i] = szRegra[i+5];  
133.             pRegra->nt[i] = strchr (term, szRegra[i+5]) == NULL;  
134.         }  
135.         pRegra->prox = tbRegra [cNT];  
136.         tbRegra [cNT] = pRegra;  
137.     }  
138.     return TRUE;  
139. }  
140.   
141.   
142. // Lista um estado para depuração  
143. void DumpState (char *prefixo, STATE *pSt)  
144. {  
145.     #ifdef DEBUG  
146.     REGRA *pReg = pSt->pRegra;  
147.     char regra [100];  
148.     int i, j, t;  
149.   
150.     t = pReg->tam + 6;   // X <- xxx.xxx  
151.     regra[0] = pReg->dest;  
152.     regra[1] = ' ';  
153.     regra[2] = '<';  
154.     regra[3] = '-';  
155.     regra[4] = ' ';  
156.     for (i = 0, j = 5; j < t; i++)  
157.     {  
158.         if (i == pSt->ponto)  
159.             regra[j++] = '.';  
160.         if (i < pReg->tam)  
161.             regra[j++] = pReg->texto[i];  
162.     }  
163.     regra[t] = 0;  
164.   
165.     printf ("%s%s,%d\n", prefixo, regra, pSt->inicio);  
166.     #endif  
167. }  
168.   
169. // Verifica se um estado já está em um conjunto  
170. int Presente (STATE *pSt, int i)  
171. {  
172.     STATE *pSt2 = S[i];  
173.     while (pSt2 != NULL)  
174.     {  
175.         if ((pSt2->inicio == pSt->inicio) && (pSt2->ponto == pSt->ponto) &&  
176.             (pSt2->pRegra == pSt->pRegra))  
177.             return TRUE;  
178.         pSt2 = pSt2->prox;  
179.     }  
180.     return FALSE;  
181. }  
182.   
183. // Verifica se uma palavra obedece à gramática  
184. int Analisa (char *palavra)  
185. {  
186.     int i, n;  
187.     STATE *pSt, *pSt2, *pSt3;  
188.   
189.     n = strlen(palavra);  
190.   
191.     // coloca o estado inicial  
192.     pSt = (STATE *) malloc (sizeof (STATE));  
193.     pSt->pRegra = tbRegra[0];  
194.     pSt->ponto = 0;  
195.     pSt->inicio = 0;  
196.     pSt->prox = NULL;  
197.     S[0] = pSt;  
198.   
199.     // cria os conjuntos de estados  
200.     for (i = 0; i <= n; i++)  
201.     {  
202.         #ifdef DEBUG  
203.         printf ("> Conjunto %d\n", i);  
204.         #endif  
205.         pSt = S[i];  
206.         while (pSt != NULL)  
207.         {  
208.             DumpState ("  Analisando: ", pSt);  
209.             if (pSt->ponto == pSt->pRegra->tam)  
210.             {  
211.                 // Completer: reconheceu a regra  
212.                 //            testar se acabou  
213.                 //            se não, colocar no set atual as regras antigas avançando o ponto  
214.                 if ((i == n) && (pSt->pRegra == tbRegra[0]) && (pSt->inicio == 0))  
215.                     return TRUE;  
216.                 pSt3 = S[pSt->inicio];  
217.                 while (pSt3 != NULL)  
218.                 {  
219.                     int pto = pSt3->ponto;  
220.                     char rec = pSt->pRegra->dest;  
221.   
222.                     if (pSt3->pRegra->nt[pto] && (pSt3->pRegra->texto[pto] == rec))  
223.                     {  
224.                         pSt2 = (STATE *) malloc (sizeof (STATE));  
225.                         pSt2->pRegra = pSt3->pRegra;  
226.                         pSt2->ponto = pSt3->ponto + 1;  
227.                         pSt2->inicio = pSt3->inicio;  
228.                         if (Presente (pSt2, i))  
229.                             free (pSt2);  
230.                         else  
231.                         {  
232.                             pSt2->prox = pSt->prox;  
233.                             pSt->prox = pSt2;  
234.                             DumpState ("   Completer: ", pSt2);  
235.                         }  
236.                     }  
237.                     pSt3 = pSt3->prox;  
238.                 }  
239.             }  
240.             else if (pSt->pRegra->nt[pSt->ponto])  
241.             {  
242.                 // Predictor: tentar reconher o NT  
243.                 //            colocar no set atual as regras do NT  
244.                 REGRA *pReg = tbRegra [pSt->pRegra->texto[pSt->ponto] - '@'];  
245.                 while (pReg != NULL)  
246.                 {  
247.                     pSt2 = (STATE *) malloc (sizeof (STATE));  
248.                     pSt2->pRegra = pReg;  
249.                     pSt2->ponto = 0;  
250.                     pSt2->inicio = i;  
251.                     if (Presente (pSt2, i))  
252.                         free (pSt2);  
253.                     else  
254.                     {  
255.                         pSt2->prox = pSt->prox;  
256.                         pSt->prox = pSt2;  
257.                         DumpState ("   Predictor: ", pSt2);  
258.                     }  
259.                     pReg = pReg->prox;  
260.                 }  
261.   
262.             }  
263.             else if (pSt->pRegra->texto[pSt->ponto] == palavra[i])  
264.             {  
265.                 // Scanner: avançou um terminal na regra, colocar no Set seguinte  
266.                 pSt2 = (STATE *) malloc (sizeof (STATE));  
267.                 pSt2->pRegra = pSt->pRegra;  
268.                 pSt2->ponto = pSt->ponto + 1;  
269.                 pSt2->inicio = pSt->inicio;  
270.                 if (Presente (pSt2, i+1))  
271.                     free (pSt2);  
272.                 else  
273.                 {  
274.                     pSt2->prox = S[i+1];  
275.                     S[i+1] = pSt2;  
276.                     DumpState ("   Scanner: ", pSt2);  
277.                 }  
278.             }  
279.             pSt = pSt->prox;  
280.         }  
281.         if (S[i+1] == NULL)  
282.             return FALSE;       // não sobrou opção  
283.     }  
284.   
285.     return FALSE;  
286. }  
287.   
288.   
289. // Programa Principal  
290. // Processa entrada no formato do problema "ET Phone Home"  
291. int main (void)  
292. {  
293.     int iCaso = 1;  
294.     char palavra [51];  
295.   
296.     while (CarregaRegras())  
297.     {  
298.         printf ("Instancia %d\n", iCaso);  
299.         scanf ("%s\n", palavra);  
300.         while (palavra[0] != '#')  
301.         {  
302.             if (Analisa (palavra))  
303.                 printf ("%s e uma palavra valida\n", palavra);  
304.             else  
305.                 printf ("%s nao e uma palavra valida\n", palavra);  
306.             LimpaStates ();  
307.             scanf ("%s\n", palavra);  
308.         }  
309.         printf ("\n");  
310.         LimpaRegras ();  
311.         iCaso++;  
312.     }  
313.     return 0;  
314. }  

// 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;
}