Resumo:
Este trabalho surge no Âmbito da disciplina de Processamento de Linguagens I, sendo constituida por 3 fases: Esta relatório refere-se a primeira fase, que por sua vez é constituida por 3 etapas:
-primeira etapa: Construir um analisador léxico e um analisador sintáctico, usando as ferramentas lex e yacc.
-segunda etapa: Acrescentar ao analisador construído na etapa anterior a análise semântica que faça algumas validações.
-terceira etapa: Armazenamento da informação num grove.
O objectivo desta fase é o de implementar uma ferramenta que permita processar documentos estruturados genericos XML que validará a boa formação dos documentos e que guardará a sua informação num grove . A utilização do XML pode ser justificada pela crescente importância deste, visto que a tendência actual é da subtituição do HTML pelo XML como linguagem de criação de paginas WEB.
Este relatório será actualizado ao longo da realização das três fases. Neste momento apenas documentamos a parte relativa á primeira fase. A versão final deste relatório estará dividida em três capítulos, um para cada fase do projecto, por sua vez cada capítulo encontra-se dividido em duas partes:
"Discussão do problema"
"Método de implementação"
Para a realização da análise léxica e sintática foi necessária a construção de um reconhecedor dos símbolos terminais e de um outro para reconhecer as frases válidas de uma linguagem , utilizando assim o flex e o yacc (lex e yacc) para os respectivos reconhecedores.
Um documento xml é composto por texto do utilizador e um conjunto de comandos, a que chamaremos Tags, que lhe permitem formatar o texto. Uma Tag é composta por vários símbolos terminais : <, >, =, / , identificadores, atributos e valores destes.
Exemplo:<REALCADO ESTILO="BOLD" > texto </REALCADO>
Neste extracto < ...> e < ...> são exemplo de duas Tags. Decidimos que os identificadores que representam as Tags seriam também símbolos terminais, facilitando assim o controlo de erros e o balanceamento da Tags.
Para implementarmos o analisador léxico, criamos uma variável global (in) que contêm o estado do análise léxica ( se está dentro ou fora de uma tag, e se estiver dentro se está a reconhecer o valor de um atributo).
Definimos Texto como sendo uma sequência de caracteres excepto < e o '&', os identificadores com uma palavra sem espaços e cujo 1º caracter é uma letra e os seguintes são letras, digitos ou '_','.' e '-', um valor é uma qualquer sequência de texto excepto '"'.
Quando estamos a reconhecer uma tag ou uma referência (entenda-se por referência '&' ID ';'), estamos no estado IN, este estado reconhece os símbolos terminais '/', '=', '<', '>', ';' e IDENTIFICADOR (os espaços são filtrados), no caso de encontrar:
[/=] -> Neste caso apenas retorna o símbolo correspondente.
'"' -> Aqui o estado é actualizado para reconhecer um Valor e retorna '"'.
[>;] -> Retorna ao estado OUT e retorna o símbolo correspondente.
IDENTIFICADOR -> Coloca na union o valor correspondente e retorna ID para identificar o IDENTIFICADOR.
Depois do analisador léxico reconhecer o caracter '>' ou ';' (fim de uma tag ou de uma referência), o estado muda para OUT (a variavel in = 0;). Neste estado reconhece-se os símbolos terminais '&', '<', que vai voltar a recolhecer os símbolos do estado IN (descritos no paragrafo acima!). O analisador léxico também vai recolhecer como simbolo terminal TEXTO , que vai ser constituido por todos os caracters menos os caracters '&', '<'; (inicio de tag e referência), os espaços são filtrados.
[<&] -> passa-se para o estado IN e retorna o símbolo correspondente.
[TEXTO] -> Coloca na union o valor correspondente e retorna o símbolo CHAR.
Existe ainda um terceiro estado, estado Valor (quando in = 2), sendo esencial para o analisador reconhecer o valor de uma tag. Este estado é activado quando o analisador vai reconhecer o símbolo '"', passa-se ao reconhecimento do símbolo terminal VALOR vai ser constituido por todos os caracters menos o símbolo '"', quando é reconhecido '"' pela segunda vez, o estado passa de novo para IN (in = 1).
Quando o analisador reconhecer o símbolo <<EOF>>, a variavel global eof passa a 1 e retorna o símbolo '$' (fim de ficheiro), é usado a variavel eof, para tratar de um erro que ocorria, quando se corria a aplicação sobre um ficheiro válido, a aplicação mostrava que o ficheiro xml era valido, e depois imprimia que houve um erro de sintase. No ficheiro da analise sintática, quando ocorre um erro sintatico, antes de imprimir a mensagem de erro, vai haver um teste para verificar se o ficheiro dado como parametro ao programa esta no fim ou não, se estiver, não sera dada nenhum mensagem de erro.
NOTA: Pode-se notar que alguns ficheiros xml podem ter um tamanho consideravel (varios MB) e que podem existir textos com varios KB de dimenção, convinha assegurar que o analisador lexico não tivesse problemas a reconhecer estes grandes textos. Pretende-se assim, implementar na segunda fase uma solução para este problema de maneira que se pudesse ler textos com pelo menos alguns megabytes. Testamos esta versão, e verificou-se que consegue ler textos de 20K.
Partindo da gramática fornecida, procedemos à sua implementação em yacc, a gramática dada não presisava de ser adaptada de forma alguma pois corria sem alterações, no entanto para que se implementassem as funcionalidades pedidas, foi necessário proceder à sua alteração.
Começamos por alterar a recursividade da direita para a esquerda, na produção AttrList, procedemos tambêm ainda nessa produção a reconhecer como caracteres terminais as '"' para ser mais fácil a leitura de VALOR, visto que em XML todos os valores estão entre '"'. Para apenas permitir que um documento XML começe e acabe obrigatoriamente por uma tag, acrescentamos uma produção Elem que tem a abetura da tag, uma lista de Elementos e o fecho dessa tag, sendo que a produção inicial DOCXML deriva em Elem.
A segunda etápa do trabalho consistia em verificar se as tag's de abertura e de fecho tinham identificadores iguais e se não existiam referências cruzadas. Para tal foi-nos proposto a utilização de uma stack para esse efeito, no entanto nós achamos desnecessária a sua utilização, pois o yacc permite-nos comparar directamente os identificadores das tag's, logo o código que tivemos de acrescentar para essa verificação foi mínimo, foi apenas acrescentar à produção Elem uma acção semântica que compara o identificador da tag de abertura com o identificador da tag de fecho.
Nota: A utilização de uma stack, talvez traga vantagens na detecção e correcção de erros, no entanto como nesta fase ainda não implentamos quase nenhum código de tratamento de erros, optamos por esta solução mais simples, não descartando a possibilidade de, em versões futuras criarmos uma stack para nos ajudar no tratamento de erros.
A estrutura de dados utilizada para o grove baseia-se na estrutura proposta pelo professor, uma árvore genérica, mas com adaptações para a glib , uma bibioteca com diversas estruturas de dados já implementadas.
A utilização da glib justifica-se pelas funções já existentes para o manuseamento da estrutura, desde funções de inserção de elementos até funções de travessia.
De seguida é apresentada a estrutura de dados que armazena a informação (os apontadores da árvore, como já foi referido são implementados pela estrutura GNode do glib ):
GNode *grove;
typedef union text{
char *txt;
int size;
} Text;
typedef struct attrib{
char *nome;
char *valortext;
struct attrib *next;
}Attrib;
typedef struct data{
char *nome;
union op {
Text *txt;
Attrib *attr;
}op;
}Data;
Pensamos que a interpretação desta estrutura, é fácil pelo que não a explicaremos em detalhe, salientamos apenas que a union Text, tem dois campos pois existem dois modos de guardar em memória os textos de um ficheiro XML, ou guardamos em memória central, ou criamos um ficheiro temporário que armazena em ficheiro esses textos.
Para construir a árvore, tinhamos duas opções :
"UP-BOTTOM" - construir a árvore da raiz para as folhas, utilizando as funções de inserção usuais
"BOTTOM-UP" - construir a árvore das folhas para a raíz
Optamos por fazer uma construção "BOTTOM-UP", apesar de um pouco mais complexa, é bastante compensadora pois permite-nos construir uma árvore bastante mais rapidamente, visto que não temos de procurar na árvore o local onde o elemento deve ser inserido.
Funções relevantes na construção do grove:
Data *new_data(char *nome,void *op,int type);
GNode *new_brother(GNode *grove,GNode *new);
GNode *new_content(GNode *grove,GNode *new);
A função new_data cria um elemento de acordo com o tipo passado como argumento:
1 - TAG ELEM ENDTAG
2 - TEXTO
3 - REF
4 - TAG UNICA
O argumento nome é o identificador do elemento. O primeiro caracter de nome é um número de 1 a 4, respectivamente o tipo desse elemento, para que assim possamos distinguir os elementos, os restantes caracteres têm o nome do identificador, excepto para TEXTO, onde os restantes caracteres correspondem à string "TEXTO". O parametro op corresponde a um apontador para uma string se o elemento for do tipo texto, a um apontador para Atributos se for do tipo 1 ou 4 ou a NULL se for do tipo 3.
A função new_brother recebe um apontador para uma "lista" de elementos irmãos e acrescenta no fim dessa lista, o novo elemento.
A função new_content recebe um apontador para uma "lista" de irmãos e "dá-lhes" um pai, ou seja esta função sobe o nível da árvore (lembrar que esta construção é BOTTOM-UP).
A melhor maneira de esplicar como implementamos o formato ESIS no trabalho, é de explicar o ficheiro funcoes, que contem o código que diz respeito ao formato ESIS, este ficheiro vai conter 2 funções principais:
int show (GNode *grove), esta função vai ser responsável pela recursividade, vai usar a função g_node_traverse da Glib, que vai por sua vez chamar a função show_gorve para cada nodo da arvore genérica. A função g_node_traverse vai usar a traversia PRE_ORDER, iniciando no inicio da arvore generica que é dado pelo apontador grove(parametro de show). A função show, também vai verificar se a flag de SECURE_MODE esta ou não activa, se estiver vai se utilizar a função rewind, que vai posicionar para o inicio do ficheiro tmp, este ficheiro vai conter os textos do grove.
gboolean show_grove (Gnode *gr,gpointer st), vai ser a função responsavel pela criação da noação ESIS. Ao se iniciar a função, vai ser verificado qual o tipo de dados é o nodo dado como parametro, a através de um switch, vai ser escolhido qual das 4 maneira diferentes de imprimir o nodo é a certa. Verificando sempre se a flag (ASCII_TEXT) para imprimir só o texto esta activa ou não. Foi preciso usar uma stack para esta função, para se poder guardar as tag's que foram abertas e não foram fechadas. Para se poder saber se já se podia fechar ou não uma tag, utilizamos o seguinte processo: Verifica-se se o nodo tem nodo filhos, se tiver que dizer que vai ter que ser fechado mais tarde, por isto guarda-se o nome da tag na stack. Se não tiver filhos, verifica-se se o nodo é o ultimo dos irmões, se for, vai retirar-se da stack o nome da tag e imprima-se e continua-se até encontrar um nodo que não seja o ultimo irmão ou até que acaba os elementos da stack. De notar que um nodo só tem filhos se for do tipo 1.
Nesta fase implementamos algumas opções para permitir uma maior flexibilidade à ferramenta. Se chamarmos o programa sem parâmetros este lê a informação do standart input, podemos tambêm passar como argumento ao programa o nome do ficheiro que queremos processar.
Os argumentos que o programa pode receber na linha de comandos são:
'-s' (SECURE_MODE) - Neste modo, os textos de um ficheiro são armazenados num ficheiro temporário para que se possa consumir menos memória central. Esta opção é de considerar quando queremos fazer o parsing de ficheiros com bastante informação (da ordem dos MB). Com esta opção sacrificamos um pouco a velocidade, mas ganhamos segurança contra a falta de memória.
'-v' (VALIDATION_MODE) - Este opção verifica apenas se um ficheiro é XML válido ou não.
'-a' (ASCII_MODE) - Esta opção imprime no standart output apenas o texto de um ficheiro XML. Sem uma análise sêmantica correcta das tags, não é possível mostrar de uma forma formatada o texto, mas mesmo assim serve para verificarmos o conteúdo de um ficheiro XML.
Se não dermos argumentos ao programa ele imprime no standart output a notação ESIS da entrada
Utilizando um processador PII a 350MHZ e 128MB de RAM, fizemos alguns testes ao nosso programa para verificar a sua velocidade de execução e memória utilizada.Os testes foram feitos utilizando as ferramentas time e top
Os resultados obtidos foram:
Utilizando o ficheiro doc2.pli, multiplicamos várias vezes o seu conteúdo até atingirmos um tamanho aproximado de 18.7 MB.
Utilizando '-s -v' demorou 17.41s a processar o ficheiro, consumindo 65560 KB
Utilizando '-v' demorou 18.25s a processar o ficheiro e utilizou 79700KB
Utilizando o ficheiro VME_HOWTO que tinha inicialmente 28.8 KB, colocamos uma tag no inicio e outra no fim e multiplicamos várias vezes o seu conteúdo até atingirmos um tamanho aproximado de 14.7 MB.Este ficheiro difere do anterior porque a grande maior parte dele é texto.
Utilizando '-s -v' demorou 9.57s a processar o ficheiro, consumindo 620KB
Utilizando '-v' demorou 4.5s a processar o ficheiro e utilizou 14682KB
Nesta primeira fase a conclusão a que podemos chegar é que a utilização de ferramentas como o lex e o yacc simplifica bastante a construção de um parser.
Pensamos que a nossa solução é uma solução bastante robusta e eficaz, alêm disso consegue dar uma grande flexibilidade ao utilizador pois possibilita que se escolha uma solução para o grove toda implementada em memória central, ou então uma solução mista em que o texto é guardado em ficheiro.
Agradecemos à equipa do glib, e aos alunos do ano passado que nos possíbilitaram esta ferramenta para criação de relatórios.
Bibliografia: