Resumo:
Neste documento, apresenta-se o relatório da primeira parte do trabalho práctico de Processamento de Linguagens I .
Trabalho esse em que se pretende implementar um processador genérico de documentos estruturados.
Foi-nos pedido para criarmos um reconhecedor genérico de documentos XML que fizesse a validação da estrutura dos mesmos e guardasse toda a informação num grove.
A solução para o problema passou por criar um parser bottom-up , utilizando para o efeito as mesmas Ferramentas que utilizamos nas aulas prácticas.
No capítulo Ferramentas apresentaremos as ferramentas que irão ser utilizadas no desenvolvimento da solução, no capítulo Gramática apresenta-se a gramática da linguagem em causa e no capítulo Estrutura de Dados irá ser descrita a estrutura de dados( grove ) utilizada para guardar o documento.
As ferramentas utilizadas para as tarefas descritas na Introdução foram as mesmas utilizadas nas aulas práticas
lex (flex) - Gerador de Analisadores Léxicos.
O lex é uma ferramenta, integrada no sistema operatico Unix (Linux) , que tem por finalidade criar analizadores léxicos, isto é, programas, ou parte de programas (como no nosso caso), que reconhecem padrões léxicos em textos. O lex recebe a descrição na forma de pares de expressões regulares e código C , chamados regras. E gera um ficheiro com código C , no qual está definida uma função yylex() que analisa o input à procura de expressões regulares. Quando encrontra uma executa o código C correpondente.
yacc - Gerador de Analisadores Sintácticos.
O Yacc lê um ficheiro com a especificação da gramática e gera um parser LR(1) para esta. O parser consiste num conjunto de tabelas de parsing e um função escrita em C, yyparse() , que lê os tokens retornados pelo lex e procede com a análise sintática dos mesmos.
A gramatica que utilizamos para descrever a linguagem XML foi a sugerida pelo professor com umas ligeiras, mas indispensáveis, alterações.
Documento : Envelope '$' ;
Envelope : '<' id AttrList '>' ElemList '<' '/' id '>' ;
ElemList : ElemList Elem
|
;
Elem : Envelope
| texto
| '&' id ';'
| '<' id AttrList '/' '>'
;
AttrList : AttrList Attr
|
;
Attr : id '=' valor ;
A estrutura de dados que utilizamos para guardar o documento foi um módulo de àrvores genéricas, existente na biblioteca do Glib. A informação nos nodos da àrvore é do tipo Info que está definido da seguinte forma:
typedef struct _info {
int flag;
union C { // é o conteudo
char* text; // para nodos texto
struct _tag { // para os outros nodos
char *ident;
GSList *atributos;
} tag;
} conteudo;
} Info;
/* Flags possíveis */
#define TEXTO 0 /* Texto!!! */
#define TAG1 1 /* <id id="valor" ...> ... </id> */
#define TAG2 2 /* <id id="valor" ... /> */
#define TAG3 3 /* &id; */
Para o caso do conteúdo ser uma TAG utiliza-se ainda um outro módulo, de listas ligadas, também da biblioteca do Glib, para guardar os atributos dessa TAG. Os atributos são guardados na lista numa estrutura do tipo Atributo , definida do seguinte modo:
typedef struct _atributo {
char* nome;
char* valor;
} *Atributo;
O nosso programa é constituido por 5 módulos:
lex.yy.c - o ficheiro gerado pelo lex , analizador léxico.
gramatica.tab.[c|h] - ficheiros gerados pelo Yacc , analizador sintático.
tagstack.[c|h] - módulo que implementa uma stack, utilizado para verificar o correcto aninhamento das TAG's.
grove.[c|h] - módulo que implementa o grove ( Estrutura de Dados), que é utilizado para guardar o documento.
main.[c|h] - basicamente, contém a função main() (é um módulo individual só pela questão da modularidade).
O programa resultante da compilação destes módulos é capaz de analizar um texto (documento XML), guardar o seu conteúdo num grove e enviar para o standard output o resultado da travessia ESIS deste. Pode ainda receber um parâmetro opcional [ -g ] na linha de comandos que fará com que o programa envie para stderr informações sobre todos os passos executados.