Resumo:
O objectivo da primeira fase deste trabalho é a construção de um processador genérico de documentos escritos no formato XML. Pretende-se validar a "boa formação de documentos" e armazenar a informação e estrutura dos mesmos num grove.
Este relatório descreverá as três fases propostas para o desenvolvimento desta fase. Assim, em cada capítulo, para além de uma explicação relativa à resolução do problema proposto, encontrar-se-á também a respectiva evolução do código.
Esta primeira fase do trabalho encontra-se dividida em várias etapas. A primeira consiste na construção de um analisador léxico e sintáctico, usando as ferramentas "Lex" e "Yacc" para a gramática que traduz a estrutura de documentos em XML.
Na segunda etapa, foi pedido que se acrescentasse ao analisador construído anteriormente a análise semântica. Este analisador deveria permitir realizar validações no documento reconhecido pela gramática.
Na terceira e última, era pedido o armazenamento da informação, ou seja, a criação de um grove. Aqui fica guardada a estrutura bem como o conteudo dos documentos.
Como já foi referido, esta etapa consiste na construção de um analisador léxico, e um analisador sintáctico (Parser). A tarefa foi parcialmente facilitada, na medida em que foi facultada a gramática que traduz a estrutura de um documento em XML. No entanto, foram introduzidas pequenas alterações determinantes para facilitar o reconhecimento léxico e sintáctico da gramática.
Em primeiro lugar procedeu-se à adaptação da gramática ao formato do yacc. Esta transformação é simples e linear, pelo que não houve grande problema. De seguida, foi necessário um analisador léxico que fornecesse os tokens ao analisador sintáctico.
Com a ferramenta Lex foi construído o analisador que é constituído por três estados: um inicial e dois relativos a marcas. No estado inicial pode-se transitar para uma marca através dos símbolos "menor" e "e comercial", sendo os restantes caractéres entendidos como texto.
Dentro das marcas, poder-se-á ter identificadores, números ou strings, tendo também significado especial os caractéres: "<", "=", ";" ">". Os dois últimos funcionam como final de marca, transitando de imediato para o estado inicial.
%{
#include "y.tab.h"
int linhas=0;
%}
num [0-9]+
id [a-zA-Z][a-zA-Z0-9]*
str \"[^"]*\"
%x MARCA
%%
"<" { BEGIN(MARCA);
return(MENOR);}
"\e" { BEGIN(MARCA);
return(E);}
\t ;
. { yylval.frase = strdup(yytext);
return(CAR);}
\n { linhas++;}
<MARCA>{num} { return(NUM);}
<MARCA>{id} { return(ID);}
<MARCA>">" { BEGIN(INITIAL);
return(MAIOR);}
<MARCA>"=" return(IGUAL);
<MARCA>"/" return(BARRA);
<MARCA>";" { return(PTOVIRG);
BEGIN(INITIAL);}
<MARCA>{str} { return(STR);}
<MARCA>. ;
%%
yywrap(){
return(EOF);
}
%{
#include "lista.h"
%}
%token ID CAR STR NUM MAIOR MENOR E IGUAL BARRA PTOVIRG
%%
docxml: abertura elems fecho
;
elems:
| elems elem {$$ = insereG($1,$2);}
;
elem: txt
| E ID PTOVIRG
| docxml
| abreFecho
;
abertura: MENOR ID atribs MAIOR
;
abreFecho: MENOR ID atribs BARRA MAIOR
;
fecho: MENOR BARRA ID MAIOR
;
atribs:
| atribs atrib
;
atrib: ID IGUAL valor
;
valor: ID
| NUM
| STR
;
txt: CAR
| txt CAR
;
%%
#include"lex.yy.c"
int yyerror(char *msg){
printf("Na linha %d da o erro '%s' em '%s'\n", linhas, msg, yytext);}
int main() {
yyparse();
}
O objectivo desta segunda etapa é acrescentar, ao analisador construido, a parte semântica, ou seja, a realização de validações que permitem a "boa" estruturação de um documento em XML.
Podemos dividir estas validações em dois tipos. Uma que verifique se as anotações correspondentes a elementos com conteúdo são abertas e fechadas correctamente. Outra que verifique se um documento está todo contido entre uma abertura e um fecho.
Para proceder a estas validações foram necessárias algumas alterações ao código já escrito. Na parte sintáctica passa a ser necessária uma comparação entre os identificadores das aberturas e dos fechos. Esta alteração é conceguida no Yacc através dos registos.
Assim, para verificar se a produção docxml: abertura elems fecho é válida, é suficiente ver se $1 = $3 , desde que $1 contenha o identificador da abertura e $3 o identificador do fecho.
Esta informação é retirada das produções respectivas à abertura e ao fecho.
No entanto, esta alteração por si só não chega. É necessário alterar a parte léxica para que os tokens correspondentes aos identificadores contenham os respectivos nomes. Isto é conseguido, acrescentando ao analisador léxico a instrução yylval.frase = strdup(yytext) , sempre que este encontre informação relevente.
Esta instrução não faz mais que colocar num canal de comunicação, entre o Lex e o Yacc (yylval), a informação desejada.
%{
#include "y.tab.h"
int linhas=0;
%}
num [0-9]+
id [a-zA-Z][a-zA-Z0-9]*
str \"[^"]*\"
%x MARCA
%%
"<" { BEGIN(MARCA);
return(MENOR);}
"\e" { BEGIN(MARCA);
return(E);}
\t ;
. { yylval.frase = strdup(yytext);
return(CAR);}
\n { linhas++;}
<MARCA>{num} { yylval.frase = strdup(yytext);
return(NUM);}
<MARCA>{id} { yylval.frase = strdup(yytext);
return(ID);}
<MARCA>">" { BEGIN(INITIAL);
return(MAIOR);}
<MARCA>"=" return(IGUAL);
<MARCA>"/" return(BARRA);
<MARCA>";" { return(PTOVIRG);
BEGIN(INITIAL);}
<MARCA>{str} { yylval.frase = strdup(yytext);
return(STR);}
<MARCA>. ;
%%
yywrap(){
return(EOF);
}
%{
#include "lista.h"
%}
%union { char* frase;}
%type <frase> abertura fecho valor
%token <frase> ID STR NUM
%token MAIOR MENOR E IGUAL BARRA PTOVIRG
%%
docxml: abertura elems fecho
{ if (strcmp($1,$3))
yyerror("Abertura diferente de Fecho\n");
}
;
elems:
| elems elem
;
elem: txt
| E ID PTOVIRG
| docxml
| abreFecho
;
abertura: MENOR ID atribs MAIOR { $$ = $2; }
;
abreFecho: MENOR ID atribs BARRA MAIOR
;
fecho: MENOR BARRA ID MAIOR { $$ = $3; }
;
atribs:
| atribs atrib
;
atrib: ID IGUAL valor
;
valor: ID { $$ = $1; }
| NUM { $$ = $1; }
| STR { $$ = $1; }
;
txt: CAR
| txt CAR
;
%%
#include"lex.yy.c"
int yyerror(char *msg){
printf("Na linha %d da o erro '%s' em '%s'\n", linhas, msg, yytext);}
int main() {
yyparse();
}
Esta última etapa, tinha como objectivo o armazenamento da informação, isto é, a criação de um grove que permitisse guardar o documento com uma determinada estrutura. O grove não é nada mais do que uma árvore irregular que armazena os vários elementos que um documento contém.
Assim sendo, cada célula da árvore, tem a informação relativa à identificação de um elemento, seus atributos (se for caso disso), o seu conteúdo (texto ou outra célula) e um apontador para as células seguintes.
Foi criada uma biblioteca (lista.h) onde foram definidas as estruturas de dados, bem como as funções necessárias à inserção de elementos, tanto no grove como na lista de atributos (insereG e insereA respectivamente). Também consta desta biblioteca a função geradora do ESIS - mostraGrove, que envia a informação directamente para o standard output. Caso seja necessário a escrita do grove num ficheiro basta redireccionar o resultado do parser.
A função mostraGrove é invocada a seguir ao yyparse(), com um parametro g que não é mais do que uma variável global que guarda o grove após a última produção da gramática ser verificada.
typedef struct Tcelatrib{ char* nomeAtrib; char* valorAtrib; struct Tcelatrib* seguinte; } atributos; typedef struct Tcelgrove{ char* nomeElem; struct Tcelatrib* atribs; union C { char* texto; struct Tcelgrove* conteudo; } cont; struct Tcelgrove* seguinte; } grove;
%{
#include "y.tab.h"
int linhas=0;
%}
num [0-9]+
id [a-zA-Z][a-zA-Z0-9]*
str \"[^"]*\"
%x MARCA
%%
"<" { BEGIN(MARCA);
return(MENOR);}
"\e" { BEGIN(MARCA);
return(E);}
\t ;
. { yylval.frase = strdup(yytext);
return(CAR);}
\n { linhas++;}
<MARCA>{num} { yylval.frase = strdup(yytext);
return(NUM);}
<MARCA>{id} { yylval.frase = strdup(yytext);
return(ID);}
<MARCA>">" { BEGIN(INITIAL);
return(MAIOR);}
<MARCA>"=" return(IGUAL);
<MARCA>"/" return(BARRA);
<MARCA>";" { return(PTOVIRG);
BEGIN(INITIAL);}
<MARCA>{str} { yylval.frase = strdup(yytext);
return(STR);}
<MARCA>. ;
%%
yywrap(){
return(EOF);
}
%{
#include "lista.h"
grove* g;
%}
%union { char* frase;
grove *nodogrove;
atributos *nodoatrib;}
%type <frase> fecho txt valor
%type <nodogrove> elems elem abertura docxml abreFecho
%type <nodoatrib> atribs atrib
%token <frase> ID CAR STR NUM
%token MAIOR MENOR E IGUAL BARRA PTOVIRG
%%
docxml: abertura elems fecho
{ if (strcmp($1->nomeElem,$3))
yyerror("Abertura diferente de Fecho\n");
$$ = CONS_TCELGROVE;
$$->nomeElem = $1->nomeElem;
$$->atribs = $1->atribs;
$$->seguinte = $1->seguinte;
$$->cont.conteudo = $2;
g = $$;
}
;
elems: {$$ = NULL;}
| elems elem {$$ = insereG($1,$2);}
;
elem: txt { $$ = CONS_TCELGROVE;
$$->nomeElem = "TXT";
$$->cont.texto = $1;
$$->atribs = NULL;
$$->seguinte = NULL;
}
| E ID PTOVIRG
{ $$ = CONS_TCELGROVE;
$$->nomeElem = $2;
$$->cont.conteudo = NULL;
$$->atribs = NULL;
$$->seguinte = NULL;
}
| docxml { $$ = $1; }
| abreFecho { $$ = $1; }
;
abertura: MENOR ID atribs MAIOR
{ $$ = CONS_TCELGROVE;
$$->nomeElem = $2;
$$->atribs = $3;
$$->cont.conteudo = NULL;
$$->seguinte = NULL;
}
;
abreFecho: MENOR ID atribs BARRA MAIOR
{ $$ = CONS_TCELGROVE;
$$->nomeElem = $2;
$$->atribs = $3;
$$->cont.conteudo = NULL;
$$->seguinte = NULL;
}
;
fecho: MENOR BARRA ID MAIOR { $$ = $3; }
;
atribs: { $$ = NULL;}
| atribs atrib { $$ = insereA($1,$2); }
;
atrib: ID IGUAL valor
{ $$ = CONS_TCELATRIB;
$$->nomeAtrib = $1;
$$->valorAtrib = $3;
$$->seguinte = NULL;
}
;
valor: ID { $$ = $1; }
| NUM { $$ = $1; }
| STR { $$ = $1; }
;
txt: CAR { $$ = $1;}
| txt CAR { $$ = strcat($1,$2);}
;
%%
#include"lex.yy.c"
int yyerror(char *msg){
printf("Na linha %d da o erro '%s' em '%s'\n", linhas, msg, yytext);}
int main() {
yyparse();
mostraGrove(g);
printf("\n\n");
}
A listagem seguinte refere-se a um documento valido.
<PLI-DOC>
<ABERTURA>
<TITULO>
Primeira Fase do Trabalho Prático de Processamento de Linguagens I
</TITULO>
<DATA> Universidade do Minho - 12 de Abril de 2000 </DATA>
<AUTOR> <NOME>Célia Margarida Ribeiro </NOME>
<EMAIL>celia_margarida@portugalmail.pt</EMAIL>
</AUTOR>
</ABERTURA>
</PLI-DOC>
Com o respectivo grove.
(PLI-DOC (ABERTURA (TITULO Primeira Fase do Trabalho Prático de Processamento de Linguagens I )TITULO (DATA Universidade do Minho - 12 de Abril de 2000 )DATA (AUTOR (NOME Célia Margarida Ribeiro )NOME (EMAIL celia_margarida@portugalmail.pt )EMAIL )AUTOR )ABERTURA )PLI-DOC
A seguir apresenta-se um documento com um erro
<PLI-DOC>
<ABERTURA>
<TITULO>
Primeira Fase do Trabalho Prático de Processamento de Linguagens I
</TITULO>
<DATA> Universidade do Minho - 12 de Abril de 2000 </DATA>
<AUTOR> <NOME>Célia Margarida Ribeiro</NOME>
<EMAIL>celia_margarida@portugalmail.pt</EMAIL>
</AUTOR>
</ABERTURA identificador>
</PLI-DOC>
Ao fazer o parse deste documento surge a mensagem:
Na linha 11 da o erro 'syntax error' em 'identificador'
Este erro surge, pois o documento contem um erro de sintaxe. A gramatica nao permite a existencia de mais de um identificador nas marcas de fecho.
Obs: Optou-se por incluir na funcao yyerror a indicaçao da linha, do tipo de erro e da palavra que lhe deu origem.
Outro exemplo de um documento invalido
<TITULO>
Primeira Fase do Trabalho Prático de Processamento de Linguagens I
</TITULO>
<DATA> Universidade do Minho - 12 de Abril de 2000 </DATA>
<AUTOR> <NOME>Célia Margarida Ribeiro</NOME>
<EMAIL>celia_margarida@portugalmail.pt</EMAIL>
</AUTOR>
Este documento e invalido pois nao esta inserido entre uma marca de abertura e uma de fecho. Surge assim, a seguinte mensagem de erro:
Na linha 4 da o erro 'syntax error' em '<'
Por ultimo um exemplo de um documento em que surge um erro semantico.
<PLI-DOC> <ABERTURA> <TITULO> Primeira Fase do Trabalho Prático de Processamento de Linguagens I </FIM_DE_TITULO> <DATA> Universidade do Minho - 12 de Abril de 2000 </DATA> </ABERTURA> </PLI-DOC>
Naturalmente surge o erro:
Na linha 6 da o erro 'Abertura diferente de Fecho' em ''
Apos a realizacao deste trabalho achamos ter alcancado uma visao mais clara da materia leccionada nesta cadeira. De facto, apos aplicar os conceitos aprendidos, com ferramentas que produzem resultados concretos, apercebemo-nos das potencialidades desta abordagem. Na realidade, para este tipo de problemas (analise lexica, sintactica e semantica) este e, de facto, o melhor metodo.
Gostariamos de ter melhorado alguns aspectos no trabalho. No entanto acabamos por gastar mais tempo do que o previsto na realizacao do relatorio. Assim nao foi possivel investir em alteracoes que pudessem se traduzir num melhor desempenho.
Esperamos que este relatorio nao tenha sido pura perda de tempo, uma vez que nao foi possivel verificar se e valido dentro da gramatica apresentada para o PLI-DOC. Sabemos que verifica a nossa! Alias foi o teste final.
AO JCR por ter CORRIGIDO este RELATÓRIO que NÃO ESTAVA de acordo com o plidoc.
Bibliografia: