Í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;
typedef struct _lista_tags_ {
char * tag_id; // nome da tag
int num_ocor; // numero de ocorrencias
struct _lista_tags_ * next; // proxima status_cel
} status_cel;
typedef struct _list_id_ {
char * id; /* String que contem o nome do identificador */
char * ficheiro; /* String que contem o nome do ficheiro */
tag * grove; /* Grove final aqui pendurado */
struct _list_id_ * next;
} id_cell;
Funções sobre o grove
#include "grove.h"
/*
***********************************************************
* *
* As seguintes funçoes sao as funçoes que tomam conta da *
* parte de construçao do grove final... *
* *
***********************************************************
*/
/* funçao que cria um grove */
tag * newgrovenode (char * nome, attr * la) {
tag * g = (tag *) malloc (sizeof(tag));
g->tag_id = nome;
g->atributos = la;
g->next = NULL;
return (g);
}
/* funçao que cria uma celula atributo */
attr * newatribnode(char * n, char * v) {
attr * al = (attr *) malloc (sizeof(attr));
al->nome = n;
al->valor = v;
al->next = NULL;
return (al);
}
/*
* Esta funçao faz a travessia duma lista de atributos e poe no stdout
* o conteudo da lista.
*
*/
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;
}
}
/* funçoes de auxilio a construçao do grove na gramatica */
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);
}
/*
*************************************************************
* *
* Esta funçao faz a travessia de um grove e envia para o *
* stdout o conteudo em formato ESIS. *
* *
*************************************************************
*/
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;
}
}
}
/*
********************************************************************
* *
* Aqui comeca a parte do tratamento do comando STATUS. Estao aqui: *
* -> listas *
* -> criaçao de celulas *
* -> verificaçao de existencia *
* -> etc. *
* *
********************************************************************
*/
status_cel * new_status_cel(char * tag_id) {
status_cel * cel = (status_cel *) malloc(sizeof(status_cel));
cel->tag_id = (char *) strdup(tag_id);
cel->num_ocor=1;
return cel;
}
status_cel * existe_cel(char * tag_id, status_cel * lista) {
status_cel * aux = lista;
while(aux) {
if(!strcmp(aux->tag_id, tag_id)) return aux;
aux=aux->next;
}
return 0;
}
status_cel * insert_status_cel(char * tag_id, status_cel * lista) {
status_cel * new_cel = new_status_cel(tag_id);
new_cel->next = lista;
return new_cel;
}
status_cel * constroi_list_status(tag * grove, status_cel * lista) {
tag * aux = grove;
status_cel * lista_aux = lista;
status_cel * aux_sc=NULL;
while(aux) {
if(aux_sc = existe_cel(aux->tag_id, lista_aux)) {
aux_sc->num_ocor++;
if(strcmp("_rtext-id_", aux->tag_id))
lista_aux = constroi_list_status(aux->conteudo.filho, lista_aux);
} else {
lista_aux = insert_status_cel(aux->tag_id, lista_aux);
if(strcmp("_rtext-id_", aux->tag_id))
lista_aux = constroi_list_status(aux->conteudo.filho, lista_aux);
}
aux=aux->next;
}
return lista_aux;
}
void list_status(status_cel * lista) {
status_cel * aux = lista;
while(aux) {
printf("Etiqueta -> %s [ %d ]\n", aux->tag_id, aux->num_ocor);
aux=aux->next;
}
}
/*****************************************************************
* *
* Esta funçao diz respeito ao comando ID. Faz a travessia de *
* um grove e coloca no stdout o nome das etiquetas. *
* *
*****************************************************************/
void list_com(tag * grove) {
tag * aux = grove;
while(aux) {
if(!strcmp(aux->tag_id, "_rtext-id_"))
printf("Etiqueta -> %s\n", aux->tag_id);
else {
printf("Etiqueta -> %s\n", aux->tag_id);
list_com(aux->conteudo.filho);
}
aux=aux->next;
}
}
/*
*****************************************************
* *
* Aqui comeca a parte das listas de identificadores *
* *
*****************************************************
*/
id_cell * new_id_cell(char * id, char * ficheiro, tag * grove) {
id_cell * celula = (id_cell *) malloc(sizeof(id_cell));
/*
OS MALLOCS PARA AS STRINGS SAO FEITAS NO
LEX COM A FUNÇAO strdup
*/
celula->id = id;
celula->ficheiro = ficheiro;
celula->grove = grove;
return celula;
}
/*
**********************************************************
* *
* Esta funçao retorna o apontador para uma celula. Se *
* o identificador existir na lista e' retornada a celula *
* que o contem. Se nao existir devolve ZERO. *
* *
**********************************************************
*/
id_cell * existe_id_lista(char * id, id_cell * lista) {
id_cell * aux = lista;
while(aux) {
if(!strcmp(aux->id,id)) return aux;
else aux=aux->next;
}
return 0;
}
id_cell * existe_fich_lista(char * fich, id_cell * lista) {
id_cell * aux = lista;
while(aux) {
if(!strcmp(aux->ficheiro,fich)) return aux;
else aux=aux->next;
}
return NULL;
}
/*
**********************************************************
* *
* Esta e a funçao de inserçao do identificador na lista. *
* Se ele existir, pergunta se que substituir. *
* *
**********************************************************
*/
id_cell * insert_id(char * id, char * ficheiro, tag * grove, id_cell * lista) {
id_cell * aux;
char c;
if(lista) {
if(aux = existe_id_lista(id, lista)) {
do {
printf("Identificador já existente. Deseja substituir [S/n]? ");
c = getc(stdin);
if(c=='s' || c=='S' || c=='\n') {
aux->ficheiro=ficheiro;
aux->grove = grove;
return lista;
}
else if( c == 'n' || c == 'N' ) return lista;
} while(c!='\n'&& c!='s' && c!='N' && c!='S' && c!='s');
}
else {
aux = new_id_cell(id, ficheiro, grove);
aux->next = lista;
return aux;
}
}
else {
aux = new_id_cell(id, ficheiro, grove);
return aux;
}
}
/*
*********************************************************************
* *
* Esta funçao coloca no stdout os identificadores e os ficheiros *
* associados. *
* *
*********************************************************************
*/
void print_id_list(id_cell * lista) {
id_cell * aux = lista;
if(aux) {
while(aux) {
printf("Identificador: %s\t\tFicheiro: %s\n",aux->id, aux->ficheiro);
aux=aux->next;
}
}
else printf("Nao existem ficheiros carregados!");
printf("\n");
}
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); }
O Problema (2ª fase)
Nesta fase, foi-nos pedido para criarmos um interpretador (uma shell) para receber comandos que trabalhassem os documentos escritos em XML. Os comandos propostos tinham como funções: ler ficheiros, fazer travessias, ...
Este interpretador, como não podia deixar de ser, foi implementado usando um analizador léxico (criado pelo lex), e uma gramática por trás a "arrumar" a casa, por assim dizer.
A linha de comandos
Como em todas as linhas de comandos, esta teria a função de interpretar aqueles para os quais estaria preparada para o fazer. Deste modo, e analizador teria de distinguir comandos válidos e outros lexemas específicos (identificadores, nomes de ficheiros, etc) de situações de erro. Esta foi a solução encontrada para o tratamento de erros. Assim todos os lexemas válidos seriam retornados para o YACC, com o seu token associado, e para tudo o resto seria retornado um token ERRO. Para atingir este objectivo, tivemos que ser um pouco meticulosos na escrita do analizador léxico, para contemplar todas as hipóteses possíveis.
De realçar ainda que criamos mais 4 comandos, que são os seguintes: STATUS, CLEAR, ID, WRITE. O comando STATUS, mostra o nome das etiquetas e o numero de vezes que elas ocorrem no grove final, depois de carregado o ficheiro. O comando ID mostra-nos o nome das etiquetas segundo uma travessia Depth-First. WRITE, escreve para um ficheiro a travessia ESIS do identificador requerido. E como não podia deixar de ser o comando CLEAR limpa o ecrã.
Os dois parsers em conjunto
Outro aspecto que temos de referir é que neste interpretador estão dois parsers gerados, pelo LEX+YACC, a serem utilizados em conjunto. Para ser possível esta utilização quase em simultâneo, tivemos que renomear os parsers gerados de maneira a que não existíssem conflitos de nomenclatura (terem ambos os mesmos prefixos -> yy). Assim, tivemos que alterar o prefixo utilizado na geração do código por parte do LEX e do YACC. Isto foi conseguido, no momento de invocação das ferramentas, utilizando as flags : "-Pxml" e "-Pinterp", no LEX, "-p xml" e "-p interp" no YACC.
Desta maneira teremos o parser interpparse a ser chamado primeiro, e que ficará á espera dos comandos. O parser de xml (xmlparse) só será invocado ao executarmos o comando LOAD, gerando assim o grove do documento que será guardado numa lista. Temos assim dois parsers em convivio pacífico.
Analizador léxico do interpretador
%{
int flag = 1;
int err_flag = 0;
%}
branco [ \t\r]
id [a-zA-Z0-9]+
not_id [^a-zA-Z0-9\n]+
fich_id [^\n\"\*\+\?]+
pal [^ \t\r\n]+
%x fn ids load
%option noyywrap
%%
if(flag) printf("\nixpr ]$ ");
{branco} ;
^({branco}*)LOAD { flag = 0; BEGIN(load); return LOAD; }
^({branco}*)SHOW { flag = 0; BEGIN(ids); return SHOW; }
^({branco}*)WRITE { flag = 0; BEGIN(load); return WRITE; }
^({branco}*)LIST{branco}*.* return LIST;
^({branco}*)EXIT{branco}*.* return EXIT;
^({branco}*)HELP{branco}*.* return HELP;
^({branco}*)STATUS{branco}*.* return STATUS;
^({branco}*)CLEAR{branco}*.* return CLEAR;
^({branco}*)ID{branco}*.* return ID;
<ids>{id} { yylval.str=(char *) strdup(yytext); err_flag = 1; BEGIN(0); return id; }
<ids>{branco}+|\n ;
<ids>{not_id} { BEGIN(0); return(ERRO); }
<load>\" BEGIN(fn);
<load>\n|{branco}+ ;
<load>[^\"\n]+ { BEGIN(0); return(ERRO); }
<fn>{fich_id}\" { yytext[strlen(yytext)-1] = '\0';
yylval.str=(char *) strdup(yytext);
BEGIN(ids);
return fich_id; }
<fn>{fich_id}\n { BEGIN(0); return(ERRO_STRING); }
^{branco}*\n printf("ixpr ]$ ");
\n { err_flag = 0; }
{pal} { return(ERRO); }
%%
Gramática final do interpretador
Interp -> ComList
ComList -> Comando
| ComList Comando
Comando -> LOAD fich_id id
| SHOW id
| WRITE fich_id id
| ID
| STATUS
| EXIT
| CLEAR
| LIST
| HELP
| ERRO
| LOAD ERRO
| WRITE ERRO
| LOAD fich_id ERRO
| WRITE fich_id ERRO
| LOAD ERRO_STRING
| WRITE ERRO_STRING
| SHOW ERRO
Outros Aspectos
Os restantes casos, como guardar os ficheiros carregados, etc., foram resolvidos utilizando listas ligadas. No caso do comando LOAD, o ficheiro é carregado seguidamente construimos um grove com o xmlparse(), e finalmente guardamos toda esta informação numa estrutura que tem como campos, char * id; char * ficheiro; tag * grove, e o apontador para o próximo elemento da lista.
De referir ainda, que talvez saindo um pouco do âmbito desta cadeira, construimos uma versão deste interpretador para o X-Windows. Para este efeito foram utilizadas as bibliotecas gráficas GTK. Ainda não está completamente acabado por esta altura mas estará num futuro próximo.
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.
No que diz respeito á segunda fase do trabalho, o que se apresentou como tarefa mais "incómoda", foi a parte de ser "mesquinho" e filtrar todas as hipoteses no analizador léxico. O resto foi de certa forma fácil, e assim ficou demonstrada de outra forma a utilidade de ferramentas geradoras de parsers.