Índice
Introdução
O objectivo desta 1ª fase do trabalho é o de implementar um ferramenta que permita reconhecer documentos em XML. Além do reconhecimento, foi já implementado um grove que permite guardar os dados á medida que vão sendo processados. Finalmente a estrutura pode ser percorrida por uma função que faz a travessia e que gera em linguagem ESIS a representação dos dados reconhecidos.
O Problema (1ª fase)
O problema proposto consistia na criação de um reconhecedor de textos num formato que obedecia a uma determinada gramática, gramática essa, que descreve a sintaxe do XML. Posteriormente foi-nos pedido que guardássemos os dados num grove, isto é, que encontrassemos uma estrutura de dados que permitisse representar todo o documento respeitando a sua estrutura inicial. Foram-nos dados 3 prazos para acabar 3 etapas de resolução do reconhecimento. A primeira etapa consistiu na validação da sintaxe de frases XML, a segunda consistiu na validação semântica, e a terceira consistiu no armazenamento da informação.
1ª etapa
Nesta etapa tinhamos a tarefa de implementar um analisador léxico. Para tal efeito, usamos as ferramentas Lex e Yacc em conjunto. O Lex foi utilizado para reconhecer os diferentes padrões dos documentos. Depois de reconhecidos, esses padrões eram enviados ao Yacc, que tinha a função de verificar se a ordem pela qual apareciam respeitava a gramática, por outras palavras, se a sequência de símbolos encontrados pelo Lex pertencia á Linguagem gerada pela gramática. A análise léxica não foi passiva. Por uma questão de economia e respeitando sempre a integridade da informação, foram filtrados todos os espaços em branco que existiam entre tags. Desta forma evitamos a existencia de blocos de texto em branco na estrutura de dados.
Na implementação da gramaática no Yacc, obtivemos alguns shift/reduce conflicts . Estes conflitos foram resolvidos alterando a recursividade numa das produções para a esquerda, quando ela, no inicio, estava á direita. Também por uma questão de optimização alteramos uma das produções, de maneira a não receber um caracter de cada vez, mas sim blocos de texto. Desta maneira optimizamos a retenção da informação no grove, pois assim temos listas de textos e/ou tags, e não listas de caracteres e/ou tags.
2ª etapa
Tinhamos agora a tarefa de verificar se todas as tags abertas eram fechadas, e se respeitavam a ordem pela qual iam aparecendo (a última a ser aberta seria a primeira a ser fechada). Para resolver este problema, no Yacc, bastou-nos comparar os campos dos identificadores de uma abertura e de um fecho de tag. A gramática por sua vez obrigava a que todas as tags que fossem abertas, posteriormente viessem a ser fechadas. Além disso a gramática obriga também que todo o texto do documento esteja entre tags.
3ª etapa
Nesta última etapa procedeu-se á implementação de um grove que guarda a informação processada. A estrutura do grove assemelha-se a um bloco de campos, 4 mais especificamente, os quais guardam apontadores para a informação. Assim temos:
-
campo que contem o nome da tag ou um identificador reservado para guardar texto livre.
-
campo que contem o apontador para o conteúdo deste grove específico. Assim podemos ter um apontador para tags filhas ou texto livre aqui pendurados.
-
campo que contem o apontador para a lista de atributos no caso de se estar a tratar uma tag. No caso de se estar a tratar texto este apontador é nulo (NULL).
-
campo que contem o apontador para os blocos de informação irmãos.
Para melhor visualização, fornecemos aqui uma imagem que de certa maneira representa do grove, assim como a sua estrutura interna.
Figura:Esquema da estrurura de dados
Para armazenar o texto livre do documento, usamos o campo laranja, para armazenar tags filhas da tag inicial, usamos um apontador para um novo bloco azul, como está demonstrado no esquema.
Recorremos ás Glibs para guardar o texto. Assim o campo texto é na realidade uma GString. Com as GString temos um conjunto de funções disponíveis para melhor e mais fácil manuseamento de strings.
Gramática - versão final
Doc -> '<' id AttrList '>' ElemList '<' '/' id '>'
ElemList -> ElemList Elem
| &
Elem -> texto
| '&' id ';'
| '<' id AttrList '/' '>'
| '<' id AttrList '>' ElemList '<' '/' id '>'
AttrList -> AttrList Attr
| &
Attr -> id '=' valor
Código
Código do grove
typedef struct _attr_ { // struct que define a estrutura de um atributo
char * nome; // nome do atributo
char * valor; // valor do atributo
struct _attr_ * next; // apontador para o atributo seguinte
} attr;
typedef struct _tag_ { // struct que contem os campos a utilizar para guardar toda a infomrmacao necessaria
char * tag_id; // identificador de tag
union _cont_ { // o conteudo da esrutura
GString * texto; // ou e texto
struct _tag_ * filho; // ou e um apontador para os filhos
} conteudo; // a union chama-se conteudo
attr * atributos; // lista de atributos
struct _tag_ * next; // apontador para a next tag
} tag;
Funções sobre o grove
#include "grove.h"
tag * newgrovenode (char * nome, attr * la) {
tag * g = (tag *) malloc (sizeof(tag));
g->tag_id = nome;
g->atributos = la;
g->next = NULL;
return (g);
}
attr * newatribnode(char * n, char * v) {
attr * al = (attr *) malloc (sizeof(attr));
al->nome = n;
al->valor = v;
al->next = NULL;
return (al);
}
void printatribs (attr * al) {
char * s1;
while (al) {
s1 = strdup((al->valor)+sizeof(char));
s1[(strlen(s1)-sizeof(char))]='\0';
printf("A %s %s\n", al->nome, s1);
al = al->next;
}
}
tag * update_texto(tag * t, GString * s) {
t->conteudo.texto = s;
return(t);
}
tag * update_filho(tag * t, tag * t_filho) {
t->conteudo.filho = t_filho;
return(t);
}
tag * last(tag * t) {
tag * aux = t;
if(aux) {
while (aux->next) aux=aux->next;
}
return(aux);
}
void travessia (tag * g){
tag * aux = g;
int flag = 0;
while(aux) {
if (strcmp(aux->tag_id, "_rtext-id_")==0 ) {
if(flag) printf("%s",aux->conteudo.texto->str);
else printf ("\n-%s", aux->conteudo.texto->str);
aux = aux->next;
flag=1;
}
else {
printf("\n");
flag=0;
printatribs(aux->atributos);
printf("( %s", aux->tag_id);
travessia(aux->conteudo.filho);
printf("\n)/ %s",aux->tag_id);
aux=aux->next;
}
}
}
Analisador Léxico
%{
#include <glib.h>
#include <string.h>
int n_lines=1, tag_n=1;
GString * gstr=NULL;
%}
id [a-zA-Z][a-zA-Z0-9\-]*
branco [ \t]*
valor \"[^\"]+\"
texto [^<&]+
%x TAG ACC
%%
& { if (gstr) {
yylval.string=gstr;
gstr=NULL;
unput('&');
return(texto);
} else { BEGIN(ACC); return(*yytext); }
}
\< { if (gstr) {
yylval.string=gstr;
gstr=NULL;
unput ('<');
return(texto);
} else { BEGIN(TAG); tag_n++; return(*yytext); }
}
<ACC>; { BEGIN(0); return(*yytext); }
<TAG>{branco} ;
<TAG>{id} { yylval.str = (char *) strdup(yytext); return(id); }
<TAG>{valor} { yylval.str = (char *) strdup(yytext); return(valor); }
<TAG>> { BEGIN(0); return(*yytext); }
<TAG>>[ \n\t\r]+< { BEGIN(0); // Limpa os espaços brancos entre tags
unput('<');
return(*yytext);
}
<TAG>[\/=] return(*yytext);
<TAG>\n n_lines++;
<TAG,ACC>{id} { yylval.str = (char *) strdup(yytext); return(id); }
{texto} { if (conta(yytext)) { n_lines+=conta(yytext); tag_n=0; }
if (!gstr) gstr=g_string_new("");
gstr = g_string_append(gstr,yytext);
}
%%
Analisador Semântico
%{
#include <glib.h>
#include <stdio.h>
#include <stdlib.h>
#include "grove.h"
/* Variaveis globais auxiliares */
int warnings=0;
attr * lista_atribs=NULL;
attr * la_aux=NULL;
tag * tag_aux=NULL;
tag * idoc=NULL;
GString * straux=NULL;
gchar * s;
/* Contador de linhas */
extern int n_lines;
/* Funcao que conta o numero de linhas */
int conta(char* line) {
char* a;
int c=0;
a=line;
while(*line)
{
if(*line=='\n') c++;
line++;
}
return c;
}
%}
%token <str> id valor
%token <string> texto
%union {
char * str;
attr * la;
tag * t;
GString * string;
char c;
}
%type <la> Attr AttrList
%type <t> Elem ElemList
%start Doc
%%
Doc : '<' id AttrList '>' ElemList '<' '/' id '>'
{
tag_aux = newgrovenode($2,$3);
tag_aux->conteudo.filho = $5;
idoc = tag_aux;
if(strcmp($2,$8)!=0) {
warnings++;
printf("Warning: line %d: Tag number %d: Tag names mismatch!!!\t( Expected Tag name : %s )\n",n_lines,tag_n,$2);
}
if(warnings) printf("Total Warnings: %d\n",warnings);
else printf("Ok!!\n\n");
travessia(idoc);
}
;
ElemList : ElemList Elem {
if ($1!=NULL) {
last($1)->next = $2;
$$=$1; }
else $$=$2;
}
| { $$ = NULL;}
;
Elem : texto {
tag_aux = newgrovenode("_rtext-id_", NULL);
tag_aux = (tag *) update_texto(tag_aux,$1);
$$ = tag_aux;
}
| '&' id ';' {
s = g_strconcat("&",$2,";");
tag_aux = newgrovenode("_rtext-id_", NULL);
tag_aux = (tag *) update_texto(tag_aux,g_string_new(s));
$$ = tag_aux;
}
| '<' id AttrList '/' '>' { tag_aux = newgrovenode($2, $3);
tag_aux->conteudo.filho = NULL;
$$ = tag_aux;
}
| '<' id AttrList '>' ElemList '<' '/' id '>'
{
if(strcmp($2,$8)!=0) {
warnings++; printf("Warning: line %d: Tag number %d: Tag names mismatch!!!\t( Expected Tag name : %s )\n",n_lines,tag_n,$2);
}
tag_aux = newgrovenode($2,$3);
tag_aux->conteudo.filho = $5;
$$ = tag_aux;
}
;
AttrList : AttrList Attr {
if ($1!=NULL) {
la_aux=$1;
while(la_aux->next!=NULL) {la_aux=la_aux->next;}
la_aux->next = $2;
$$=$1;
}
else $$=$2;
}
| { $$ = NULL; }
;
Attr : id '=' valor { lista_atribs = newatribnode($1,$3);
$$ = lista_atribs;
}
;
%%
#include "xml.fl.c"
yyerror( char * s ) { printf("%s: linha numero %d!!\n",s,n_lines); }
Conclusão
A conclusão desta primeira fase permite-nos, não só tomar consciência de que existem formas de automatizar a construção de analisadores de documentos estruturados, como ter uma visão diferente de um parte muito particular de problemas, que é a de trabalhar com texto como tipo de dados.
De realçar ainda que o que nos parecia algo difícil, como guardar o documento num grove, tornou-se surpreendentemente bastante mais fácil. Este problema foi resolvido utilizando funções simples e fáceis de implementar, pois o trabalho propriamente dito foi feito pelo Yacc, que utilizando estas funções nas suas acções semânticas, foi construindo o grove final.