Resumo:
O objectivo deste trabalho é o de implementar uma ferramenta que processará documentos anotados XML e que permitirá fazer queries em CQL (Context Query Language) .
Este trabalho será desenvolvido em 3 fases, sendo este relatório um relatório de progresso alusivo à primeira fase, que por sua vez foi dividida em três etapas.A primeira etapa referia-se à análise léxica e sintáctica, a segunda consistia na análise semântica e por fim, a última, que era a construção de uma estrutura para armazenar a informação do documento anotado.
Passando à análise da gramática, concluímos que, se a alterássemos seria mais simples resolver ceertos tipos de confiltos que nos surgiram com a gramática inicialmente proposta.Assim, resolvemos adoptar a gramática construída nas aulas práticas.
Para a análise léxica tivemos que identificar os valor terminais e encontrar uma expressão regular que os identificasse. O principal problema com que nos deparamos foi como identificar o texto do utilizador; optámos por reconhecer o texto caracter a caracter. A implementação do analisador léxico foi construída usando a ferramenta flex .
A análise sintáctica resumiu-se praticamente à passagem da gramática para a forma usada pelo yacc , ficou um único conflito de shift/reduce por resolver.Na análise sintáctica o analisador sintáctico recebe do analisador léxico um sequência de "palavras" e verifica se pertencem à linguagem definida pela gramática usada.
Quanto à semântica, era apenas obrigar a que os identificadores das tags dos elementos fizessem match e que o identificador que inicia o documento também o termina.
Para a contrução do grove, usamos a estrutura sugerida pelo prof. e ainda outras auxiliares que consideramos necessárias.
Assim, consideramos que um documento em XML é constituido por elementos a que chamá-nos nodos com a seguinte forma:
um identificador da tag;
o conteúdo, que pode ser uma lista de atributos e outro elemento que está a um nível inferior, ou somente texto;
um apontador para o elemento seguinte;
Os atributos são da forma ID=Valor, portanto, contituídos por:
um identificador;
um valor, que pode ser um Num, um ID ou uma Str, logo, e apesar de nesta fase não fazermos uso dela, acrescentamos uma flag a esta estrutura, para indicar qual é o tipo do valor, pois ele é guardado como um char*;
um apontador para o atributo seguinte;
Para o texto, como não é possível limitar o texto que o utilizador vai escrever, decidimos usar uma lista de caracteres para armazenar o texto. Sabemos que há um desperdicio de memória pois, para cada caracter exige um apontador para o caracter seguinte.
Quanto às estruturas auxiliares, deparámos com a necessidade de usar algumas estruturas mais simples do que os nodos durante a construção do grove. É apenas uma simplificação do nodo, menos específicos.
Com as estruturas anteriores, guardamos o nosso grove numa espécie de àrvore, i.e., pode crescer em duas direcções: para o lado (pelo apontador para o elemento seguinte quando cresce ao mesmo nível) ou para baixo (pelo apontador para conteúdo, quando cresce para o seu descendente, i.e., quando surge um novo elemento antes de fechar a tag do elemento anterior).
Repare-se que tudo são nodos: qualquer elemento do documento excepto os atributos, é armazenado como sendo um nodo, seja ele texto, tags...
O grove é construído durante a análise sintáctica, portanto é construído em profundidade, da mesma forma com que a função de parse percorre o documento.
Após a armazenagem do documento no grove, gera-se o Esis, que mostra a estrutura interna do documento. A nossa função tem como parâmetro o grove. O seu funcionamento é o seguinte: imprime o "(" e o identificador do primeiro elemento, após o que chama uma função que gera o Esis para os atributos, caso eles existam. Em seguida verifica a tag do conteúdo: caso a tag seja "TEXTO", chama a função que gera o Esis para o texto, caso seja "&", imprime o conteúdo do nodo. Somente quando verifica que o conteúdo dos elementos é vazio passa para o elemento seguinte, portanto a travessia do grove também ocorre em profundidade.
Durante a execução deste relatório e enquanto testávamos com parte do relatório o nosso grove, reparámos que ao fazermos enter , este era reconhecido como texto, gerando no Esis uma linha com apenas a indicação que se segue texto.
Para resolver este problema apenas teremos de alterar o analisador léxico, o que faremos nos próximos dias.
Exemplo de funcionamento do programa
<SECCAO><TITULO>Estrutura de dados</TITULO> <PARA>Para a contru,c~ao do grove, usamos a estrutura sugerida pelo prof. e ainda outras auxiliares que consideramos necess'arias. </PARA> <PARA>Assim, consideramos que um documento em <REALCADO ESTILO="italico">XML</REALCADO> 'e constituido por elementos a que cham'a-nos nodos com a seguinte forma: </PARA> <LISTA> <ITEM><PARA>um identificador da tag;</PARA></ITEM> <ITEM><PARA>o conte'udo, que pode ser uma lista de atributos e outro elemento que est'a a um n'ivel inferior, ou somente texto;</PARA></ITEM> <ITEM><PARA>um apontador para o elemento seguinte;</PARA></ITEM> </LISTA> <PARA>Os atributos s~ao da forma ID=Valor, portanto, contitu'idos por:</PARA> <LISTA> <ITEM><PARA>um identificador;</PARA></ITEM> <ITEM><PARA>um valor, que pode ser um Num, um ID ou uma Str, logo, e apesar de nesta fase n~ao fazermos uso dela, acrescentamos uma flag a esta estrutura, para indicar qual 'e o tipo do valor, pois ele 'e guardado como um char*;</PARA></ITEM> <ITEM><PARA>um apontador para o atributo seguinte;</PARA></ITEM> </LISTA> <PARA>Para o texto, como n~ao 'e poss'ivel limitar o texto que o utilizador vai escrever, decidimos usar uma lista de caracteres para armazenar o texto. Sabemos que h'a um desperdicio de mem'oria pois, para cada caracter exige um apontador para o caracter seguinte. </PARA> <PARA>Quanto `as estruturas auxiliares, depar'amos com a necessidade de usar algumas estruturas mais simples do que os nodos durante a construção do grove. 'E apenas uma simplifica,c~ao do nodo, menos espec'ificos. </PARA> </SECCAO>
( SECCAO ( TITULO -Estrutura de dados )TITULO - ( PARA -Para a contru,c~ao do grove, usamos a estrutura sugerida pelo prof. e ainda outras auxiliares que consideramos necess'arias. )PARA - ( PARA -Assim, consideramos que um documento em ( REALCADO ( atributos ESTILO "italico" )atributos -XML )REALCADO - 'e constituido por elementos a que cham'a-nos nodos com a seguinte forma: )PARA - ( LISTA - ( ITEM ( PARA -um identificador da tag; )PARA )ITEM - ( ITEM ( PARA -o conte'udo, que pode ser uma lista de atributos e outro elemento que est'a a um n'ivel inferior, ou somente texto; )PARA )ITEM - ( ITEM ( PARA -um apontador para o elemento seguinte; )PARA )ITEM - )LISTA - ( PARA -Os atributos s~ao da forma ID=Valor, portanto, contitu'idos por: )PARA - ( LISTA - ( ITEM ( PARA -um identificador; )PARA )ITEM - ( ITEM ( PARA -um valor, que pode ser um Num, um ID ou uma Str, logo, e apesar de nesta fase n~ao fazermos uso dela, acrescentamos uma flag a esta estrutura, para indicar qual 'e o tipo do valor, pois ele 'e guardado como um char*; )PARA )ITEM - ( ITEM ( PARA -um apontador para o atributo seguinte; )PARA )ITEM - )LISTA - ( PARA -Para o texto, como n~ao 'e poss'ivel limitar o texto que o utilizador vai escrever, decidimos usar uma lista de caracteres para armazenar o texto. Sabemos que h'a um desperdicio de mem'oria pois, para cada caracter exige um apontador para o caracter seguinte. )PARA - ( PARA -Quanto `as estruturas auxiliares, depar'amos com a necessidade de usar algumas estruturas mais simples do que os nodos durante a construção do grove. 'E apenas uma simplifica,c~ao do nodo, menos espec'ificos. )PARA - )SECCAO
%{
//#include "y.tab.h"
#include <string.h>
%}
%x opentag fim
%%
"<" {BEGIN(opentag);return('<');}
"&" {BEGIN(opentag);return('&');}
\n {BEGIN(fim);}
. {yylval.caracter=yytext[0];return(Car);}
<opentag>">" {BEGIN(INITIAL); return('>');}
<opentag>";" {BEGIN(INITIAL);return(';');}
<opentag>"/" {return('/');}
<opentag>"=" {return('=');}
<opentag>[+-]?[0-9]+ {yylval.valor=strdup(yytext);return(Num);}
<opentag>[a-zA-Z][a-zA-Z0-9]* {yylval.valor=strdup(yytext);return(Id);}
<opentag>\"[^"]*\" {yylval.valor=strdup(yytext);return(Str);}
<fim><<EOF>> {yyterminate();}
<fim>. {BEGIN(INITIAL);
yyless(INITIAL);yylval.caracter=yytext[0];return(Car);}
%%
%{
#include "grove.c"
%}
%token <valor> Id Num Str
%token <caracter> Car
%union
{
Lchar txt;
char *valor;
grove nodao;
Latribs atrib;
char caracter;
nodinho aux;
tValor flag;
}
%type <valor> Fecho
%type <flag> Valor
%type <txt> Txt
%type <aux> Abert AbertFecho
%type <nodao> DocXml Elems Elem
%type <atrib> Atrib Atribs
%Start DocXml
%%
DocXml: Abert Elems Fecho {
$$=(nodo *)malloc (sizeof(nodo));
$$->ident=$1.ident;
$$->cont.normal.atribs=$1.atribs;
$$->cont.normal.conteudo=$2;
$$->next=NULL;
g=$$;
if (strcmp($1.ident,$3)!=0) {
printf("Tags diferentes:%s!=%s\n",$1.ident,$3);
yyterminate();}
}
;
Abert:'<' Id Atribs '>' {$$.ident=$2;
$$.atribs=$3;
/* printf("inseri Abert %s\n", $2);*/}
;
Atribs : {$$=NULL;}
|Atribs Atrib {$$=insAtrib($1,$2);}
;
Atrib: Id '=' Valor {$$=(Latribs) malloc (sizeof(atributo));
$$->nome=$1;
$$->flag=$3.flg;
$$->valor=$3.val;
$$->next=NULL;
}
;
Valor: Id {$$.flg="i";$$.val=$1;}
|Num {$$.flg="n";$$.val=$1;}
|Str {$$.flg="s";$$.val=$1;}
;
Elems: Elem {$$=$1;/*printf("Inseri Elem\n");*/}
| Elems Elem {insereNodo($1,$2);
$$=$1;/*printf("Inseri Elems Elem\n");*/}
;
Elem: Txt {$$=(grove)malloc (sizeof(nodo));
$$->ident="TEXTO";
$$->cont.texto=$1;
$$->next=NULL;/*printf("INSERI ELEMS COMO TXT\n");*/
;}
| '&' Id ';' {$$=(grove)malloc (sizeof(nodo));
$$->ident="&";
$$->cont.texto=$2;
$$->next=NULL;/* printf("reconheci &ID\n");*/
}
| AbertFecho {$$=(grove)malloc (sizeof(nodo));
$$->ident=$1.ident;
$$->cont.normal.atribs=$1.atribs;
$$->cont.normal.conteudo=NULL;
$$->next=NULL;
}
| Abert Elems Fecho {$$=(grove)malloc (sizeof(nodo));
$$->ident=$1.ident;
$$->cont.normal.atribs=$1.atribs;
$$->cont.normal.conteudo=$2;
$$->next=NULL;
if (strcmp($1.ident,$3)!=0) {
printf("Tags diferentes:%s !=%s\n",$1,$3);
yyterminate();}
}
;
Txt: Car {Lchar aux=(Lchar)malloc(sizeof(charNodo));
aux->car=$1;
aux->next=NULL;
$$=aux;}
| Txt Car {insereChar($1,$2);$$=$1;}
;
Fecho: '<' '/' Id '>' {$$=$3;}
;
AbertFecho: '<' Id Atribs '/''>' {$$.ident=$2;
$$.atribs=$3;
}
;
%%
#include "lex.yy.c"
int yyerror(char *s)
{
printf("%s\n",s);
}
int main()
{
yyparse();
geraEsis(g);
}
#include <stdio.h>
#include <string.h>
#include <malloc.h>
typedef struct Anodo
{ char* nome;
char* valor;
char flag;
struct Anodo* next;
} atributo;
typedef atributo* Latribs;
typedef struct Gnodo
{ char* ident;
union C
{ char* texto;
/* para nodos _texto */
struct X
/* para os outros nodos */
{ struct Gnodo* conteudo;
Latribs atribs;
} normal;
} cont;
struct Gnodo* next;
} nodo;
typedef nodo *grove ;
typedef struct aux
{ char *ident;
Latribs atribs;
nodo *conteudo;
struct aux *next;
}nodinho;
typedef struct lchar
{ char car;
struct lchar *next;
}charNodo;
typedef charNodo* Lchar;
typedef struct fValor
{ char *val;
char flg;
}tValor;
grove g;
Latribs insAtrib(Latribs lista,Latribs atr)
{
Latribs aux;aux=lista;
if (aux==NULL)
lista=atr;
else
{
while(aux->next!=NULL)
aux=aux->next;
aux->next=atr;
}
return lista;
}
Lchar insereChar(Lchar lista, char c)
{
Lchar aux=(Lchar)malloc(sizeof(charNodo));
aux->car =c;
aux->next=NULL;
if(lista==NULL){
lista=aux;
return lista;
}
else
{
lista->next=insereChar(lista->next, c);
return lista;
}
}
grove insereNodo(grove g, grove a)
{
if (g==NULL)
g=a;
else
g->next=insereNodo(g->next,a);
return g;
}
void geraTexto(Lchar texto)
{
if(texto!=NULL)
{
printf("%c",texto->car);
geraTexto(texto->next);
}
}
void geraAtribsAux(Latribs lista)
{
if(lista!=NULL)
{
printf("%s %s ", lista->nome, lista->valor);
geraAtribsAux(lista->next);
}
}
void geraAtribs(Latribs lista)
{
if(lista!=NULL)
{
printf("( atributos\n");
geraAtribsAux(lista);
printf("\n)atributos\n");
}
}
void geraEsis(grove g)
{
if(g!=NULL)
{
if(strcmp(g->ident,"TEXTO")!=0 && strcmp(g->ident,"&")!=0)
{
printf("( %s\n", g->ident);
geraAtribs(g->cont.normal.atribs);
geraEsis(g->cont.normal.conteudo);
printf(")%s\n",g->ident);
}
else
{
if (g->ident=="TEXTO")
{
printf("-");
geraTexto(g->cont.texto);
printf("\n");
}
else
printf("& %s\n",g->cont.texto);
}
geraEsis(g->next);
}
}