Resumo:
Este trabalho tem como objectivo a realização de um processador genérico de documentos estruturados (XML) que validará a boa formação dos documentos e que guardará a sua informação num grove.
Apresentamos aqui um relatório sucinto relativamente à primeira fase do trabalho prático por nós realizado.
Este relatório tem como objectivo acompanhar a primeira fase do trabalho prático da disciplina de Processamento de Linguagens I, de modo a facilitar a sua compreensão, funcionamento, estrutura interna e composição.
O objectivo global deste trabalho prático é a construção de uma ferramenta para verificação e transformação de documentos estruturados anotados segundo a gramática que se apresenta em apêndice a qual foi alterada consoante as opções por nós tomadas como se verá na análise.
Nesta primeira fase construir-se-á um analisador léxico e sintáctico que reconheça léxica e sintacticamente um documento do tipo do da gramática que nos foi apresentada.
Esta implementação dos analisadores léxico e sintáctico foi feita com o auxílio das ferramentas LEX (ou flex) e YACC as quais têm maior divulgação neste tipo de trabalhos.
Após o reconhecimento léxico e sintáctico da gramática que nos foi apresentada, e o qual nos era pedido na primeira e segunda etapa, pretendemos nesta última etapa da primeira fase, a criação de uma estrutura de dados que permita o armazenamento do documento - Grove .
Nos ficheiros que enviamos em anexo são também facultadas a codificação dos analisadores léxico e sintáctico, contendo este último a implementação do Grove, o guião da gramática que deve ser reconhecida e o exemplo a reconhecer.
No final encontrará uma pequena conclusão com que damos por terminada a primeira fase do nosso trabalho.
"Discussão do problema"
No final desta fase tinhamos como objectivo principal a construção de um Grove , ou seja, uma estrutura de dados para armazenar toda a estrutura de um documento. O objectivo desta estrutura de dados é o de permitir uma travessia que volte a gerar o documento reconhecido.
A primeira decisão, e a qual influenciará o tratamento da gramática, surgiu quando tivemos de optar pelo uso de ferramentas adequadas para efectuarmos a análise léxica e sintáctica de um documento desse tipo. Como já referimos na introdução optámos pela ferramenta LEX e YACC.
Na análise léxica declaramos uma variável estado , a qual ao longo das diversas partes que se referem ao reconhecimento léxico diz se nessa parte é possível existir texto ou não. Essa variável comporta-se como um booleano, que no caso de poder aceitar texto toma o valor 1 senão toma o valor 0, o qual lhe está associado no inicio pois não poderá aparecer qualquer texto antes de uma marca.
Tal como o Lex o formato de um ficheiro de especificação de Yacc tem uma estrutura própria.
O axioma da gramática, aquele que se encontra do lado esquerdo da primeira regra sintáctica é declarado na zona de definições através da regra %start inserida na primeira coluna.
A definição do código dos elementos léxicos é feita também no inicio do ficheiro através da regra %token.
O Yacc permite que sejam associados valores a símbolos quer terminais quer não terminais. Os tipos a serem associados a símbolos devem ser declarados no inicio do ficheiro através da instrução %union.
Após as declarações segue-se a parte de gramática que irá reconhecer o texto ou não. Caso o analisador sintáctico gerado pelo Yacc detecte um erro sintáctico pára a análise e regressa ao programa que o chamou.
Esta é a parte principal da codificação a qual fará o reconhecimento das expressões que são passadas pelo Lex após o matching que este efectua com aquilo que vai lendo do ficheiro a processar.
Para termos a certeza de que o texto está a ser todo reconhecido mandamos várias mensagens de reconhecimento das produções que foram reconhecidas.
A análise semântica consiste em acrecentar ao analisador constrúido algumas validações. Em primeiro lugar teriamos de verificar se todas as anotações correspondentes a elementos com conteúdo são abertas e fechadas correctamente isto é, as primeiras a fechar são as últimas que foram abertas. E em segundo todo o documento tem que começar obrigatóriamente com a abertura de uma marca e acabar com fecho dessa mesma marca. Para além disso toda a marca aberta tem o respectivo fecho.
A estrutura de dados por nós escolhida para o Grove , foi uma árvore irregular. Consideramos que cada elemento é constituido por quatro campos:
Identificador do elemento
Apontador para atributos do elemento
Apontador para o conteúdo do elemento
Apontador para o próximo elemento, que está no mesmo nível do actual.
Consideramos também que cada atributo é constituido por três campos:
Identificador do atributo
Valor do atributo
Apontador para o próximo atributo
Por último consideramos que cada abertura é constituido por dois campos:
Identificador da abertura
Apontador para atributos da abertura
Assim sendo, é-nos possivel realizar uma travessia de forma a manter a estrutura do documento através de uma função pre_order e pos_order que percorre o conteúdo de cada nodo passando para os nodos do lado após ter realizado o percurso completo desse mesmo nodo. Essa é invocada logo a seguir ao yyparse() gerando o documento no formato ESIS.
Para guardar a informação no grove houve a necessidade de criar funções que inserissem a informação na estrutura de dados. Assim criámos funções de inserir um elemento numa lista de elementos(função ins), inserir um atributo numa lista de atributos(função insatr),e inserir um caracter numa lista de caracteres(função inscar).
Para as funções de inserir um elemento e atributo, criámos mais duas funções auxiliares para o caso de a lista não ser vazia dar-nos a última posição da lista para inserir o novo elemento no fim da lista já existente.
A função que imprime o documento no formato ESIS tem como argumento o grove e caso ele seja diferente de vazio escreve o identificador da marca que abriu antecipada por (, em seguida os atributos caso existam, imprimindo um A para indicar que é atributo seguido de um par contendo a informação do identificador do atributo e do respectivo valor. Após a escrita do texto imprime ),e de seguida imprime o identificador da marca. Para melhor elucidação recomenda-se a visualização do ficheiro em anexo que contém os exemplos.
Neste primeira fase do trabalho damos por concluídos os objectivos a que nos propusemos na introdução.
Construímos o analisador léxico e sintáctico cujo resultado da sua interacção é o reconhecimento de um determinado texto consoante esteja, ou não, em consonância com a gramática que nos foi proposta e à qual fizemos alterações que nós achamos convenientes após a observação da análise.
Após conclusão desta primeira parte tomamos consciência de que a fase que se segue dependerá em muito desta primeira fase.
Para terminar seguem-se os apêndices, entre quais serão encontrados a gramática base que deu origem ao trabalho, bem como listagem dos ficheiros onde este se encontra e ainda um exemplo de um texto a ser processado.
Ficheiro gramatica.l
%{
#include <string.h>
#define ERRO -1
%}
%x estado1 fim
%%
"<" {BEGIN estado1; return('<');}
"&" {BEGIN estado1; return('&');}
\n {BEGIN(fim);}
<fim><<EOF>> {yyterminate();}
<fim>. {BEGIN(INITIAL);yyless(INITIAL);yylval.carac=yytext[0];return(car);}
. {yylval.carac=yytext[0];return(car);}
<estado1>">" {BEGIN(INITIAL); return('>');}
<estado1>";" {BEGIN(INITIAL); return(';');}
<estado1>"=" {return('=');}
<estado1>"/" {return('/');}
<estado1>[a-zA-Z][a-zA-Z0-9]* {yylval.valor=strdup(yytext);return(id);}
<estado1>\"[^"]*\" {yylval.valor=strdup(yytext);return(str);}
<estado1>[0-9]+ {yylval.valor=strdup(yytext);return(num);}
<estado1>[ \t\n] ;
<estado1>. {return(ERRO);}
%%
%{
#include "gramatic.h"
#include <string.h>
%}
%start Documento
%token <carac> car
%token <valor> id num str
%union {
char * valor;
char carac;
tgrove g;
tAptAtr at;
tAbre ab;
}
%type <g> Elems Elem Documento
%type <at> Atributos Atrib
%type <valor> Txt Fecho Valor
%type <ab> Abertura AbreFecho
%%
Documento : Abertura Elems Fecho
{ $$=(tcelgrove *) malloc(sizeof(tcelgrove));
$$->idElem=$1->idAbr;
$$->contVar.tnodo.atributos=$1->atribu;
$$->contVar.tnodo.conteudo=$2;
$$->seg=NULL;
grove=$$;
if(strcmp($1->idAbr,$3)!=0) printf("ERRO!! As marcas sao diferentes!\n\n ->%s\n ->%s\n\n",$1->idAbr,$3);
else printf("Documento valido!!\n");}
;
Elems : Elem
{ $$=$1;
printf("Reconheci Elems como Elem.\n");}
| Elems Elem
{ $$=ins($1,$2);
printf("Reconheci Elems como Elems Elem.\n");}
;
Elem : Txt
{ $$=(tcelgrove *)malloc(sizeof(tcelgrove));
$$->idElem="TEXTO";
$$->contVar.txt=$1;
$$->seg=NULL;
printf("Reconheci Elem como Txt.\n");}
| Abertura Elems Fecho
{ if(strcmp($1->idAbr,$3)!=0) printf("ERRO !! As marcas sao diferentes\n");
else {printf("Documento valido!!\n");
printf("Reconheci Elem como Abertura Elems Elem.\n");}
$$=(tcelgrove *)malloc(sizeof(tcelgrove));
$$->idElem=$1->idAbr;
$$->contVar.tnodo.conteudo=$2;
$$->contVar.tnodo.atributos=$1->atribu;
$$->seg=NULL;}
| AbreFecho
{ $$=(tcelgrove *)malloc(sizeof(tcelgrove));
$$->idElem=$1->idAbr;
$$->contVar.tnodo.atributos=$1->atribu;
$$->contVar.tnodo.conteudo=NULL;
$$->seg=NULL;
printf("Reconheci Elem como AbreFecho.\n");}
| '&' id ';'
{ $$=(tcelgrove *)malloc(sizeof(tcelgrove));
$$->idElem="ENTESP";
$$->contVar.txt=$2;
$$->seg=NULL;
printf("Reconheci Elem como '&' id ';'.\n");}
;
Txt : car
{ $$=inscar(NULL,$1);
printf("Reconheci Txt como 1 car.\n");}
| Txt car
{ $$=inscar($1,$2);
printf("Reconheci Txt como Txt 2 car.\n");}
;
Abertura : '<' id Atributos '>'
{ $$=(tcelAbre *)malloc(sizeof(tcelAbre));
$$->idAbr=$2;
$$->atribu=$3;
printf("Reconheci Abertura.\n");}
;
Fecho : '<' '/' id '>'
{ $$=$3;
printf("Reconheci Fecho.\n");}
;
AbreFecho : '<' id Atributos '/' '>'
{ $$->idAbr=$2;
$$->atribu=$3;
printf("Reconheci AbreFecho.\n");}
;
Atributos :
{ $$=NULL;
printf("Reconheci Atributos como vazio.\n");}
| Atributos Atrib
{ $$=insatr($1,$2);
printf("Reconheci Atributos como Atributos Atrib.\n");}
;
Atrib : id '=' Valor
{ $$=(tAtr *)malloc(sizeof(tAtr));
$$->idAtrib=$1;
$$->valor=$3;
$$->seg=NULL;
printf("Reconheci Atrib como id '='valor.\n");}
;
Valor : id
{ $$=strdup($1);
printf("Reconheci Valor como id.\n");}
| num
{ $$=$1;
printf("Reconheci Valor como num.\n");}
| str
{ $$=$1;
printf("Reconheci Valor como str.\n");}
;
%%
#include "lex.yy.c"
#include <stdio.h>
#include <string.h>
#include "gram.c"
int yyerror(char *s)
{
printf("ERRO! Documento nao valido!\n");
}
main()
{
yyparse();
funcao_esis(grove);
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
tAptAtr ultimoAtr(tAptAtr l)
{
while(l->seg!=NULL)
{
l=l->seg;
}
return(l);
}
tAptAtr insatr(tAptAtr l,tAptAtr x)
{
tAptAtr aux;
if(l!=NULL)
{
aux=(tAptAtr)ultimoAtr(l);
aux->seg=x;
}
else
{
l=x;
}
return(l);
}
tgrove ultimoElem(tgrove l)
{
tgrove aux;
if(l->seg!=NULL)
aux=ultimoElem(l->seg);
else
aux=l;
return(aux);
}
tgrove ins(tgrove l,tgrove x)
{
tgrove aux;
aux=(tgrove)ultimoElem(l);
aux->seg=x;
return(l);
}
char * inscar(char *s,char c)
{
int i=0;
int comp;
char * aux=NULL;
if(s!=NULL)
{
comp=strlen(s);
aux=(char *)malloc(comp+2);
while(i<comp)
{
aux[i]=s[i];
i++;
}
aux[i++]=c;
aux[i]='\0';
}
else
{
comp=1;
aux=(char *)malloc(comp+1);
aux[0]=c;
aux[1]='\0';
}
free(s);
printf("%s\n",aux);
return(aux);
}
void mostra_atrib(tAptAtr at)
{
if(at!=NULL)
{
printf("A %s %s \n",at->idAtrib,at->valor);
mostra_atrib(at->seg);
}
}
void funcao_esis(tgrove g)
{
if(g!=NULL)
{
if(strcmp(g->idElem,"TEXTO")!=0 && strcmp(g->idElem,"ENTESP")!=0)
{
printf("( %s\n",g->idElem);
mostra_atrib(g->contVar.tnodo.atributos);
funcao_esis(g->contVar.tnodo.conteudo);
printf(")%s\n",g->idElem);
}
else
{
printf("-%s\n",g->contVar.txt);
}
funcao_esis(g->seg);
}
}
typedef struct atrib {
char * idAtrib;
char * valor;
struct atrib * seg;
}tAtr, *tAptAtr;
typedef struct elem {
char * idElem;
union{
struct x{
struct elem * conteudo;
tAptAtr atributos;
}tnodo;
char * txt;
}contVar;
struct elem * seg;
}tcelgrove, * tgrove;
typedef struct Abert {
char * idAbr;
tAptAtr atribu;
}tcelAbre, * tAbre;
tgrove grove;
EXEMPLOS DE EXECUÇAO Exemplo1 <data> hoje e dia 21 </data1> Resultado: Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. h Reconheci Txt como Txt 2 car. ho Reconheci Txt como Txt 2 car. hoj Reconheci Txt como Txt 2 car. hoje Reconheci Txt como Txt 2 car. hoje Reconheci Txt como Txt 2 car. hoje e Reconheci Txt como Txt 2 car. hoje e Reconheci Txt como Txt 2 car. hoje e d Reconheci Txt como Txt 2 car. hoje e di Reconheci Txt como Txt 2 car. hoje e dia Reconheci Txt como Txt 2 car. hoje e dia Reconheci Txt como Txt 2 car. hoje e dia 2 Reconheci Txt como Txt 2 car. hoje e dia 21 Reconheci Txt como Txt 2 car. hoje e dia 21 Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Fecho. ERRO!! As marcas sao diferentes! ->data ->data1 ( data - hoje e dia 21 )data Exemplo2 <marca> bla blahfugjhfuytyuyu 6 <figura nome = "ficheiro" /> bla bla </marca> Resultado: Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla b Reconheci Txt como Txt 2 car. bla bl Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. bla blah Reconheci Txt como Txt 2 car. bla blahf Reconheci Txt como Txt 2 car. bla blahfu Reconheci Txt como Txt 2 car. bla blahfug Reconheci Txt como Txt 2 car. bla blahfugj Reconheci Txt como Txt 2 car. bla blahfugjh Reconheci Txt como Txt 2 car. bla blahfugjhf Reconheci Txt como Txt 2 car. bla blahfugjhfu Reconheci Txt como Txt 2 car. bla blahfugjhfuy Reconheci Txt como Txt 2 car. bla blahfugjhfuyt Reconheci Txt como Txt 2 car. bla blahfugjhfuyty Reconheci Txt como Txt 2 car. bla blahfugjhfuytyu Reconheci Txt como Txt 2 car. bla blahfugjhfuytyuy Reconheci Txt como Txt 2 car. bla blahfugjhfuytyuyu Reconheci Txt como Txt 2 car. bla blahfugjhfuytyuyu Reconheci Txt como Txt 2 car. bla blahfugjhfuytyuyu 6 Reconheci Txt como Txt 2 car. bla blahfugjhfuytyuyu 6 Reconheci Txt como Txt 2 car. bla blahfugjhfuytyuyu 6 Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Atributos como vazio. Reconheci Valor como str. Reconheci Atrib como id '='valor. Reconheci Atributos como Atributos Atrib. Reconheci AbreFecho. Reconheci Elem como AbreFecho. Reconheci Elems como Elems Elem. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla b Reconheci Txt como Txt 2 car. bla bl Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elems Elem. Reconheci Fecho. Documento valido!! ( marca - bla blahfugjhfuytyuyu 6 ( figura A nome "ficheiro" )figura - bla bla )marca Exemplo3 <marca cod = 3>bla bla </marca> Resultado: Reconheci Atributos como vazio. Reconheci Valor como num. Reconheci Atrib como id '='valor. Reconheci Atributos como Atributos Atrib. Reconheci Abertura. b Reconheci Txt como 1 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla b Reconheci Txt como Txt 2 car. bla bl Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Fecho. Documento valido!! ( marca A cod 3 -bla bla )marca Exemplo4 <marca> bla bla <nova> & identi ; </nova> ola <marca1> Hoje esta um dia terrivel </marca1> </marca> Resultado: Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla b Reconheci Txt como Txt 2 car. bla bl Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Elem como '&' id ';'. Reconheci Elems como Elems Elem. Reconheci Txt como 1 car. Reconheci Elem como Txt. Reconheci Elems como Elems Elem. Reconheci Fecho. Documento valido!! Reconheci Elem como Abertura Elems Elem. Reconheci Elems como Elems Elem. Reconheci Txt como 1 car. o Reconheci Txt como Txt 2 car. ol Reconheci Txt como Txt 2 car. ola Reconheci Txt como Txt 2 car. ola Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elems Elem. Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. H Reconheci Txt como Txt 2 car. Ho Reconheci Txt como Txt 2 car. Hoj Reconheci Txt como Txt 2 car. Hoje Reconheci Txt como Txt 2 car. Hoje Reconheci Txt como Txt 2 car. Hoje e Reconheci Txt como Txt 2 car. Hoje es Reconheci Txt como Txt 2 car. Hoje est Reconheci Txt como Txt 2 car. Hoje esta Reconheci Txt como Txt 2 car. Hoje esta Reconheci Txt como Txt 2 car. Hoje esta u Reconheci Txt como Txt 2 car. Hoje esta um Reconheci Txt como Txt 2 car. Hoje esta um Reconheci Txt como Txt 2 car. Hoje esta um d Reconheci Txt como Txt 2 car. Hoje esta um di Reconheci Txt como Txt 2 car. Hoje esta um dia Reconheci Txt como Txt 2 car. Hoje esta um dia Reconheci Txt como Txt 2 car. Hoje esta um dia t Reconheci Txt como Txt 2 car. Hoje esta um dia te Reconheci Txt como Txt 2 car. Hoje esta um dia ter Reconheci Txt como Txt 2 car. Hoje esta um dia terr Reconheci Txt como Txt 2 car. Hoje esta um dia terri Reconheci Txt como Txt 2 car. Hoje esta um dia terriv Reconheci Txt como Txt 2 car. Hoje esta um dia terrive Reconheci Txt como Txt 2 car. Hoje esta um dia terrivel Reconheci Txt como Txt 2 car. Hoje esta um dia terrivel Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Fecho. Documento valido!! Reconheci Elem como Abertura Elems Elem. Reconheci Elems como Elems Elem. Reconheci Txt como 1 car. Reconheci Elem como Txt. Reconheci Elems como Elems Elem. Reconheci Fecho. Documento valido!! ( marca - bla bla ( nova - -identi - )nova - ola ( marca1 - Hoje esta um dia terrivel )marca1 - )marca Exemplo5 <marca> bla bla <falha> & agora </falha> bla bla </marca> Resultado: Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla b Reconheci Txt como Txt 2 car. bla bl Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. bla bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. Reconheci Elem como Txt. Reconheci Elems como Elem. ERRO! Documento nao valido! Exemplo6 <marca1> bla <marca2> bla </marca1> bla </marca2> Resultado: Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Atributos como vazio. Reconheci Abertura. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elem. Reconheci Fecho. ERRO !! As marcas sao diferentes Reconheci Elems como Elems Elem. Reconheci Txt como 1 car. b Reconheci Txt como Txt 2 car. bl Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. bla Reconheci Txt como Txt 2 car. Reconheci Elem como Txt. Reconheci Elems como Elems Elem. Reconheci Fecho. ERRO!! As marcas sao diferentes! ->marca1 ->marca2 ( marca1 - bla ( marca2 - bla )marca2 - bla )marca1
Agradecemos ao professor Pedro Henriques pela sua simpatia e disponibilidade para tirar-nos algumas dúvidas sobre o trabalho. Caso contrário, ainda estaríamos a tirar os erros. O nosso muito obrigado.
Bibliografia: