Introdução

O objectivo deste trabalho é a utilização das ferramentas lex e yacc para fazer o reconhecimento de ficheiros XML.

Nesta primeira fase do trabalho foram criados dois ficheiros: um em lex e outro em yacc, respectivamente o analisador léxico e sintáctico. Além disso, implementámos a estrutura (grove) que deverá guardar a informação, ficando esta armazenada em memória principal.

Análise Léxica e Sintáctica

Análise Léxica

O analisador léxico não trouxe grandes problemas ao nível da implementação. Aquilo que optámos por fazer foi separar dois casos. Um deles é o caracter < simbolizando a abertura de uma nova tag. Neste caso, aquilo que fizemos foi entrar numa condição de contexto condicionando assim o que poderia suceder àquele caracter. O outro caso é o do caracter ">" que simboliza o fim de uma tag. Neste caso, voltamos ao ínicio através de um BEGIN(0). Tomámos a opção de não considerar o '&' ao contrário do que vem especificado na gramática, porque não estaria de acordo com a estrutura de dados que adoptámos, e a sua identificação não era necessária. Esta escolha foi discutida com o Prof. Ramalho, que concordou com a nossa decisão. Como futuro desenvolvimento, pretendemos incluir um contador de linhas de forma a detectarmos a linha onde ocorreu o erro e corrigir a forma como detectamos o texto, já que, quando o texto atinge um determinado número de caracteres, é dividido em blocos.

Análise Sintáctica

No analisador sintáctico, em primeiro lugar, alterámos a gramática inicialmente proposta. Criámos uma que "exigisse" a existência de uma abertura e um fecho idênticos, para "identificar" o tipo de documento (ex: XML, PLI-DOC, HTML, etc). Verificámos também que todas as tags fechavam pela ordem inversa à que abriam. Fizemos isto sem recorrer a uma stack, comparando os identificadores à medida que aparecem. Também aqui reconhecemos como texto dados com o formato "&aaa;", tal como na análise léxica.

Estrutura de dados

Implementação

Em relação à estrutura de dados, criàmos duas struct's. Uma delas para os atributos, e a outra para os nodos. Os nodos guardam a informação relativa às tags, ou ainda texto. Neste último caso, o campo do identificador fica com o valor "#TXT", de maneira a sabermos qual o campo da union a usar. No caso de esse campo ser diferente de "#TXT", usamos o campo cont que representa o conteúdo deste nodo. Caso contrário, usamos o campo txt que contém o texto. Para além do identificador,em cada nodo temos ainda um apontador para a lista de atributos, e outro para os seus irmãos. Os atributos têm apenas dois campos de informação contendo o tipo de atributo e o seu valor, e um apontador para o próximo atributo.

Estrutura de dados

	typedef struct a{
		char *nome;
		char *valor;
		struct a *next;
	} *Atributo;

	typedef struct n{
		char* id;
		union {
			struct n* cont;
			char* txt;
		} z;
		Atributo attr;
		struct n* next;
	} *Nodo;	

Listagem do código

Analisador léxico

ID [A-Za-z][A-Za-z0-9\-\_]*
TXT [^<]+
VALOR ["][^ \n\t]+["]
VARIOS [=/]

%x abrir
%%

^<abrir,INITIAL>[ \t\n]+ ;

\^< {BEGIN(abrir);return(*yytext);}

<abrir>{ID} {yylval.id=(char*)strdup(yytext);return(ID);}

<abrir>{VARIOS} {return(*yytext);}

<abrir>{VALOR} {yylval.valor=(char*)strdup(yytext);return(VALOR);}

<abrir>\> {BEGIN(0);return(*yytext);}

{TXT} {yylval.txt=(char*)strdup(yytext);return(TXT);}


%%

Analisador sintáctico

%{
#include <string.h>
#include "grove.h"

Nodo grove;
%}

%token VALOR ID TXT
%start DOCXML
%union{
	char *id;
	char *valor;
	char *txt;
	Nodo n;
	Atributo attr;
}

%type <id> ID FECHO
%type <valor> VALOR
%type <txt> TXT
%type <n> ABERTURA ELEM ELEMS ABREFECHO
%type attr> ATRIBS ATRIB

%%
DOCXML:ABERTURA ELEMS FECHO 	{grove=$1;
				 grove->z.cont=$2;
				 if (strcmp(grove->id,$3)) yyerror("erro de tags");
					else printf ("\nReconheci um documento estruturado!\n\n");};

ABERTURA:'<' ID ATRIBS '>' 	{$$=criaNodo($2,$3);};

ATRIBS: ATRIB               	{$$=$1;};
      | ATRIBS ATRIB		{fa($1,$2);$$=$1;};
      | ;                       {$$=NULL;};

ATRIB: ID '=' VALOR       	{$$=criaAtrib($1,$3);};

ELEMS:ELEM			{$$=$1;};
     |ELEMS ELEM		{f($1,$2);
				 $$=$1;};

ELEM:TXT			{$$=criaTxt($1);};
    |ABREFECHO			{$$=$1;};
    |ABERTURA ELEMS FECHO  	{($1)->z.cont=$2;
				 $$=$1;
				 if (strcmp($1->id,$3)) yyerror("erro de tags");};

FECHO:'<' '/' ID '>' 		{$$=$3;};

ABREFECHO:'<' ID ATRIBS '/' '>'	{$$=criaNodo($2,$3);};
%%

#include "lex.yy.c"

int yyerror(char *s) {
	printf("\nSomething´s wrong...:((( -> %s\n\n",s);
	exit(1);
}

int main(){
	yyparse();
	travessia(grove);
}

yywrap(){}

Estrutura de dados (Grove)

#include <stdio.h>
#include <stdlib.h>


typedef struct a{
	char *nome;
	char *valor;
	struct a *next;
} *Atributo;

typedef struct n{
	char* id;
	union {
		struct n* cont;
		char* txt;
	} z;
	Atributo attr;
	struct n* next;
} *Nodo;

Nodo criaTxt(char *txt){

	Nodo n;

	n=(Nodo)calloc(1, sizeof(Nodo));
	n->id="#TXT";
	n->z.txt=strdup(txt);
	n->attr=NULL;
        n->next=NULL;
	return n;             	
}


Atributo criaAtrib(char *id, char *valor) {

	Atributo a;

	a=(Atributo)calloc(1,sizeof(Atributo));
	a->nome=strdup(id);
	a->valor=strdup(valor);
	a->next=NULL;
	return a;
}


Nodo criaNodo(char *id, Atributo atribs){

	Nodo n;

	n=(Nodo)calloc(1,sizeof(Nodo));		
        n->id=strdup(id);
	n->attr=atribs;
	n->z.cont=NULL;
	n->next=NULL;
	return n;
}


void ver_atr(Atributo a) {

	if(a) {

		printf("A %s %s\n",a->nome,a->valor);
		ver_atr(a->next);	
	}
}


void f(Nodo n1, Nodo n2) {

	Nodo n3=n1;
	while(n3->next) n3=n3->next;
	n3->next=n2;
}

void fa(Atributo n1, Atributo n2) {

	Atributo n3=n1;
	while(n3->next) n3=n3->next;
	n3->next=n2;
}

void travessia(Nodo n) {

	if(n) {
		if (!strcmp(n->id,"#TXT")) {
			printf("-%s\n",n->z.txt);
		}

		else {  ver_atr(n->attr);
			printf("(%s\n",n->id);
			travessia(n->z.cont);
			printf(")%s\n",n->id);
      		}

		travessia(n->next);
 	}	
}

Queremos agradecer ao professor José Carlos Ramalho e ao professor Pedro Henriques por esclarecerem as dúvidas que foram surgindo ao longo desta primeira fase.

• [man ]Manuais do linux relativos às ferramentas lex e yacc.