Resumo:
Relatório de progresso do trabalho prático da cadeira de processamento de linguagens 1, ministrada pelo Departamento de Informática da Universidade do Minho. Descreve o processo de criação de analisadores léxicos, sintáticos e semânticos para armazenamento de um documento XML numa estrutura de dados (grove) e posterior travessia e representação da estrutura de dados na forma ESIS.
O objectivo desta primeira fase do trabalho era essencialmente criar uma estrutura de dados (grove) para guardar um qualquer documento XML. Neste momento não se sabe se o trabalho continuará a ser desenvolvido, pelo que o resultado final é um programa que representa um documento XML na forma ESIS.
O programa foi desenvolvido usando o conjunto de ferramentas lex e yacc (flex e byacc mais propriamente) que criaram analisadores léxicos, sintáticos e semânticos que validam o documento e geram a grove.
Posteriormente realiza-se uma travessia em profundidade à grove e representa-se a mesma na forma ESIS.
No resto deste relatório descrevem-se com mais detalhe os vários passos tomados na realização do trabalho.
A gramática implementada foi a seguinte;
Documento -> '<' "DOC" '>' ElemList '<' '/' "DOC" '>' ElemList -> ElemList Elem | Elem Elem -> text | '&' id ';' | '<' id AttrList '>' ElemList '<' '/' id '>' | '<' id AttrList '/' '>' AttrList -> AttrList Attr | Attr -> id '=' '"' VALOR '"'
Como se pode verificar esta gramática possui pequenas alterações em relação à original, a sua funcionalidade mantém-se porém.
Originalmente a gramática era orientada ao caracter, reconhecendo caracteres onde agora reconhece texto, esta alteração deve-se ao facto de estruturalmente ser muito pouco correcto armazenar caracteres individualmente devido a problemas de eficácia (em vez de termos um array unidimensional facilmente consultável, temos uma lista ligada de caracteres que exige uma carga de processamento muito maior).
A definição de atributo também foi alterada, sendo agora o seu valor obrigatoriamente envolvido por aspas ("), este pequeno pormenor permitiu simplificar o analisador léxico, pois considera-se que o valor é tudo o que está entre aspas. A aspa também serve de separador entre atributos, facilitando assim o seu parsing.
Para concretizar o analisador léxico usou-se o flex, uma ferramenta que gera programas para reconhecimento de padrões de texto (pattern-matching).
A funcão de um analisador léxico é a de retornar símbolos terminais (e o seu conteúdo se necessário) a um analisador sintático. No caso deste problema usou-se uma metodologia em que certos símbolos só são terminais em certas situações. Por exemplo o símbolo igual (=) só é terminal aquando da atribuição de um determinado valor a um atributo, de resto é considerado como fazendo parte de texto.
No entanto, neste momento, tenho grandes incertezas quanto à correçcão ou mesmo necessidade desta metodologia, pois embora esta se adeque bem à posterior análise sintática, por facilitar a diferenciação entre símbolos terminais isolados e blocos de texto que contenham os mesmos símbolos, parece-me que este papel cabe ao analisador sintático.
Este método foi implementado usando condições de contexto, que permitem definir quando uma certa combinação de símbolos pode ser associada a um determinado terminal.
A concretização do analisador sintático foi realizada em yacc e sobre esta pouco há a dizer pois consistiu unicamente em introduzir a gramática já apresentada no yacc.
Visto que esta é bastante simples e se apresenta numa forma correcta para o yacc (nomeadamente as produções com recursividade à esquerda) não houve quaisquer tipos de conflitos na construção do analisador.
Bem mais interessante foi a definição das acções semânticas descritas no próximo capítulo.
As acções semânticas foram definidas no yacc juntamente com a gramática. No nosso caso estas limitam-se, essencialmente, a construir uma estrutura de dados a que chamamos grove, que representa o documento XML. A estrutura é posteriormente usada para criar uma representação ESIS do documento XML.
A estrutura de dados usada é uma árvore binária cujos nodos são os elemento identificados. Cada nodo além dos ponteiros para os nodos seguintes (conteudo e irmao), contém o tipo de elemento presente no nodo (tipo), um ponteiro para char que armazena o nome da tag ou o próprio conteúdo do elemento caso este seja um bloco de texto ou caracter especial (tag), e um ponteiro para uma lista de atributos (atributos).
struct _elem {
unsigned char tipo; /* tipo de elemento */
char *tag;
struct _elem *conteudo;
struct _attr *atributos;
struct _elem *irmao;
};
A lista de atributos é uma lista ligada simples com nodos do tipo:
struct _attr {
char *id;
char *valor;
struct _attr *irmao;
};
Embora houve-se uma estrutura de dados proposta numa das aulas, preferi esta pois é bastante mais simples por não usar unions (e não menos eficaz por isso) e que têm como principal diferença a adição do tipo de elemento presente no nodo.
A construção da grove usando o yacc foi extremamente simples pois bastou, basicamente, associar a cada produção uma acção semântica que cria um nodo para armazenar o elemento identificado, e garantir que todos os nodos são ligados correctamente.
O único pormenor interessante a realçar é o facto de devido ao yacc usar um algoritmo bottom-up (LALR) as listas serem construidas invertidas, pelo que se criou uma função para adicionar elementos à cauda de uma lista, obtendo-se assim as listas correctas (o mesmo se fez para atributos e suas listas).
A ultima parte desta primeira fase, consistiu na criação de uma função de travessia da grove que permitisse criar uma representação ESIS da estrutura. A travessia necessária é em profundidade, pelo que antes de passar para o irmão de um dado elemento, é visitado o seu conteudo. A transformação para ESIS é bastante simples e pode ser explicada pelas seguintes regras :
As tags passam a ser representadas na forma:
(TAG conteudo )TAG
Se uma tag tiver atributos estes aparecem antes da abertura da tag, na forma:
Aid CDATA valor
Um elemento de texto é representado precedido do símbolo '-'.
Quanto aos caracteres especiais, por agora, estes são representados textualmente na forma &id;. (Não vejo de facto uma forma correcta de representar os caracteres especiais, pois devido ao facto da gramática ser tão genérica, não me parece ser possível saber à partida o símbolo a usar para um determinado identificador)
Nesta primeira fase do trabalho, houve um estudo e consequente compreensão dos programas lex e yacc (flex e byacc mais especificamente) e suas potencialidades. De facto é notável que tão rapidamente se tenha construido um programa capaz de processar qualquer documento XML.
/* Tipo de elementos */
#define E_TEXT 0
#define E_SPECIAL 1
#define E_TAG 2
#define E_EMPTYTAG 3
struct _elem {
unsigned char tipo; /* tipo de elemento */
char *tag;
struct _elem *conteudo;
struct _attr *atributos;
struct _elem *irmao;
};
struct _attr {
char *id;
char *valor;
struct _attr *irmao;
};
BLANK [ \t\r]
ID [A-Za-z][A-Za-z0-9_]*
%{
#include "y.tab.h"
extern unsigned int cline;
%}
%x tag tag_valor special
%%
"<" {BEGIN(tag); return('<');}
& {BEGIN(special); return('&');}
[^&<\n]+ {char *text = (char *) calloc(yyleng + 1, sizeof(char));
strcpy(text, yytext);
yylval.string = text;
return(TEXT);}
\n {cline++;};
<special>{BLANK}+ ;
<special>[^;\n]+ {char *id = (char *) calloc(yyleng + 1, sizeof(char));
strcpy(id, yytext);
yylval.string = id;
return(ID);}
<special>";" {BEGIN(INITIAL); return(';');}
<special>\n {cline++;}
<tag>"DOC" {return(DOC);}
<tag>{BLANK}+ ;
<tag>"/" {return('/');}
<tag>{ID} {char *id = (char *) calloc(yyleng + 1, sizeof(char));
strcpy(id, yytext);
yylval.string = id;
return(ID);}
<tag>"=" {return('=');}
<tag>\" {BEGIN(tag_valor); return('"');}
<tag>">" {BEGIN(INITIAL); return('>');}
<tag>\n {cline++;}
<tag>. {return(ERRO);}
<tag_valor>[^"\n]+ {char *valor = (char *) calloc(yyleng + 1, sizeof(char));
strcpy(valor, yytext);
yylval.string = valor;
return(VALOR);}
<tag_valor>\" {BEGIN(tag); return('"');}
<tag_valor>\n {cline++;}
%%
int yyerror(char* s) {
fprintf(stderr, "Erro:%s na linha %d antes de %s\n", s, cline, yytext);
exit(-1);
}
int yywrap() {
return(EOF);
}
%union {char *string; struct _attr *attr; struct _elem *elem;}
%token <string> TEXT ID VALOR END
%token DOC ERRO
%type <elem> Documento ElemList Elem
%type <attr> AttrList Attr
%{
#include <stdlib.h>
#include <stdio.h>
#include "grove.h"
struct _elem *new_node(unsigned char tipo, char *tag) {
struct _elem *node = (struct _elem *) calloc(1, sizeof(struct _elem));
char *ntag = (char *) calloc(1, strlen(tag) + 1);
strcpy(ntag, tag);
node->tipo = tipo;
node->tag = ntag;
node->conteudo = NULL; /* Desnecessarios enquanto o NULL for */
node->atributos = NULL; /* equivalente a 0, pois o calloc */
node->tipo = NULL; /* preenche as posicoes com 0 */
return (node);
}
unsigned int cline = 1;
void addetail(struct _elem *list, struct _elem *elem) {
if (list->irmao == NULL)
list->irmao = elem;
else
addetail(list->irmao, elem);
}
void addatail(struct _attr *list, struct _attr *attr) {
if (list->irmao == NULL)
list->irmao = attr;
else
addatail(list->irmao, attr);
}
struct _elem *grove;
%}
%%
Documento : '<' DOC '>' ElemList '<' '/' DOC '>' {
struct _elem *node = new_node(E_TAG, "DOC");
node->conteudo = $4;
node->atributos = NULL;
grove = node;
/*printf("Documento Reconhecido.\n");*/
};
ElemList : ElemList Elem {
addetail($1, $2);
$$ = $1; };
| Elem {
$1->irmao = NULL;
$$ = $1; };
Elem : TEXT {
struct _elem *node = new_node(E_TEXT, $1);
$$ = node; };
| '&' ID ';' {
struct _elem *node = new_node(E_SPECIAL, $2);
$$ = node; };
| '<' ID AttrList '>' ElemList '<' '/' ID '>' {
struct _elem *node;
if (strcmp($2, $8) != 0) { /* Erro ids diferentes */
fprintf(stderr,"Ids diferentes - Na linha %d, esperava %s encontrei %s\n",cline,$2,$8);
exit(-1);
}
node = new_node(E_TAG, $2);
node->conteudo = $5;
node->atributos = $3;
$$ = node; };
| '<' ID AttrList '/' '>' {
struct _elem *node = new_node(E_EMPTYTAG, $2);
node->conteudo = NULL;
node->atributos = $3;
$$ = node; };
AttrList : AttrList Attr {
if($1 != NULL) {
addatail($1, $2);
$$ = $1;
} else
$$ = $2;
};
| /* vazio */ {$$ = NULL; };
Attr : ID '=' '"' VALOR '"' {
struct _attr *node = (struct _attr *) calloc(1, sizeof(struct _attr));
node->id = $1;
node->valor = $4;
$$ = node;
}
%%
void liberta_attr(struct _attr *attr) {
if(attr != NULL) {
liberta_attr(attr->irmao);
free(attr->id);
free(attr->valor);
free(attr);
}
}
void liberta_elem(struct _elem *elem) {
if(elem != NULL) {
liberta_elem(elem->conteudo);
liberta_elem(elem->irmao);
liberta_attr(elem->atributos);
free(elem->tag);
free(elem);
}
}
void attr2esis(struct _attr *attr) {
if(attr != NULL) {
printf("A%s CDATA %s\n", attr->id, attr->valor);
attr2esis(attr->irmao);
}
}
void elem2esis(struct _elem *elem) {
if (elem != NULL) {
switch(elem->tipo) {
case E_TEXT:
printf("-%s\n", elem->tag);
break;
case E_SPECIAL:
printf("-&%s;\n", elem->tag);
break;
case E_TAG:
case E_EMPTYTAG:
attr2esis(elem->atributos);
printf("(%s\n", elem->tag);
elem2esis(elem->conteudo);
printf(")%s\n", elem->tag);
break;
}
elem2esis(elem->irmao);
}
}
int main() {
yyparse();
elem2esis(grove);
liberta_elem(grove);
}
Antes de mais, quero congratular os responsáveis pela cadeira de processamento de linguagens 1, pois esta aborda tópicos extremamente úteis e aplicáveis.
Desejo também congratular o Professor José João Almeida pela forma eficaz com que me orientou em certos tópicos, nomeadamente acerca do formato ESIS (que teve como consequência o agradecimento seguinte).
Agradeço aos criadores do programa nsgmls, sem o qual ter percebido a norma ISO-8879 tinha implicado pelo menos uma grande dor de cabeça.
Agradeço aos alunos Sara Alexandra Gomes Correia <mc23214@ci.uminho.pt> e Alberto Manuel Brandão Simões <mc23801@ci.uminho.pt> pois usei o seu relatório como exemplo prático de um documento PLI-DOC, e o seu programa conversor de PLI-DOC para HTML que permitiu verificar a correcção deste documento na sua forma original (PLI-DOC).
Bibliografia: