Resumo:
Este trabalho surge no âmbito da disciplina de Processamento de Linguagens I, e consiste na implementação de um analizador léxico e sintático da linguagem XML .
O objectivo deste trabaho é o de fazer a introdução aos alunos de um conjunto de ferramentas muito utilizadas na criação de compiladores e interpretadores: lex e yacc .
A realização deste projecto foi proposta em três fases: a primeira deveria consistir na análise léxica e sintática do problema, a segunda num teste de semântica às tags e a terceira na contrução de um grove , bem como na travessia do mesmo.
Na terceira fase deste trabalho tinhamos como objectivo principal a construção de um grove , ou seja, uma estrutura de dados para armazenar toda a estrutura de um documento XML . O objectivo desta estrutura de dados é o de permitir uma travessia que volte a gerar o documento reconhecido.
A implementação deste parser foi efectuada usando as ferramentas flex e yacc . Foram codificadas algumas funções para fazerem o tratamento das strings , bem como na manipulação do grove.
Nesta fase, foi utilizado o utilitário flex , sendo a sua explicação desnecessária, já que esta ferramenta já foi analisada, no âmbito de Métodos de Programação III. Convém dizer que foram utilizados três estados: estado 0 (para reconhecimento de texto), estado TAG (para o reconhecimento das tags) e o estado AtrLst (para o reconhecimento das atribuições).
Foi utilizado um stack para fazer o controlo das tags em aberto. Foram criadas as funções para manipular o mesmo .
Além desta gestão da stack, criamos uma função que permite contar o número de linhas de determinada string. Assim, podemos manter uma variável com o número da linha actual. Este número servirá para um melhor tratamento de erros. Convém ainda referir que a função de tratamento de erro foi alterada de forma a que indicasse o número da linha onde o erro sucedeu.
A estrutura de dados que escolhemos para o grove , foi uma mistura de árvore binária-lista ligada. Assim consideramos cada tag como sendo um elemento, em que cada elemento é constituido por quatro campos:
Nome da Tag
Atributos da Tag
Apontador para o conteúdo da Tag / Apontador para o texto
Apontador para a próxima tag, que está no mesmo nível da actual.
Assim sendo, é-nos possivel realizar uma travessia de forma a manter a estrutura do documento. Basta para isso a criação de uma função tipo Deep-First , recursiva que "mergulhe" no conteúdo deste nodo e só passe para os nodos do lado quando já realizou o "mergulho" completo.
Na resolução deste trabalho, foram precisos vários conceitos que foram abordados nas aulas. A primeira parte deste trabalho vem no seguimento da disciplina Métodos de Programação III. Em nossa opinião ficaram cumpridos todos os objectivos desta primeira fase.
%{
#include "stack.h"
#include "grove.h"
elem stack;
int nlines;
char *id1,*id2,*errstr;
%}
%token DOC
%token <id> ID
%token <valor> VALOR
%token <texto> CHAR
%start DOCUMENTO
%union {
char* texto;
char* id;
char* valor;
nodo nod;
atrib at;
}
%type <nod> Elem
%type <nod> ElemList
%type <at> AttrList
%%
DOCUMENTO: '<' DOC '>' ElemList '<' '/' DOC'>'; {printf("A frase pertence a linguagem!\n"); shownodo($4); exit(0); };
ElemList: ElemList Elem {$$ = conc($1,$2);}
| Elem
Elem: CHAR {
$$=(nodo) malloc(sizeof(struct _nodo));
$$->tagname="TEXTO";
$$->atributos=NULL;
$$->cont = (conteudo) malloc(sizeof(struct _conteudo));
$$->cont->texto = (char *) strdup((char * ) strtrim(yylval.texto));
$$->next=NULL;
}
| '&' ID ';' {
pop(&(stack));
$$=(nodo) malloc(sizeof(struct _nodo));
$$->tagname="TEXTO";
$$->atributos=NULL;
$$->cont = (conteudo) malloc(sizeof(struct _conteudo));
$$->cont->texto = (char *) malloc(sizeof(yylval.id)+4);
snprintf($$->cont->texto,sizeof(yylval.id)+4,"&%s;",(char *) strdup(yylval.id));
$$->next=NULL;
}
| '<' ID AttrList '>' ElemList '<' '/' ID '>' {
id1=(char *) pop(&(stack));
id2=(char *) pop(&(stack));
if(strcasecmp(id1,id2)!=0)
{
errstr=(char *) malloc(40+strlen(id1)+strlen(id2));
snprintf(errstr,39+strlen(id1)+strlen(id2),"TAG ERROR:abertura com \"%s\" e fecho \"%s\"",id2,id1);
yyerror(errstr);
}
$$=(nodo) malloc(sizeof(struct _nodo));
$$->tagname=(char *) strdup($2);
$$->atributos=$3;
$$->cont=(conteudo) malloc(sizeof(struct _conteudo));
$$->cont->filho=$5;
$$->next=NULL;
}
| '<' ID AttrList '/' '>' {
pop(&(stack));
$$=(nodo) malloc(sizeof(struct _nodo));
$$->tagname=(char *) strdup($2);
$$->atributos=$3;
$$->cont = (conteudo) malloc(sizeof(struct _conteudo));
$$->cont->filho = NULL;
$$->next=NULL;
}
AttrList: AttrList ID '=' VALOR {
$$=insereatrib($1,(char *) strdup($2),(char *) strdup($4));
}
| {$$=NULL;}
%%
#include "lex.yy.c"
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "ansi.h"
usage(char *prog)
{
cls();
azul_escuro();
gotoxy(10,10);
printf("# # # # #");
gotoxy(10,11);
printf(" # # # # # # #");
gotoxy(10,12);
printf(" # # # #");
gotoxy(10,13);
printf(" * # # # #");
gotoxy(10,14);
printf("* # # # ######");
gotoxy(32,15);
vermelho_pisca();
printf("PARSER");
normal();
gotoxy(0,18);
bold();
printf("USAGE:");
normal();
gotoxy(0,20);
printf("%s nome_do_ficheiro_a_processar\n\n",prog);
}
main(int argc, char **argv)
{
int fd;
char *file=NULL;
stack=NULL;
if(argc>2) {
usage(argv[0]);
exit(-1);
}
if(argc==2)
{
file=(char *) strdup(argv[1]);
fd=open(file, O_RDONLY);
if(fd!=-1)
{
dup2 (fd,0);
yyparse();
close(fd);
}
else
{
perror(argv[1]);
exit(-1);
}
}
if(argc==1)
yyparse();
}
yyerror(char *s)
{
printf("line %d:%s\n",nlines+1,s);
exit(0);
}
Exemplo:
%{
extern int nlines;
%}
WHITE [\n\t ]+
ID [a-zA-Z][a-zA-Z\-\_\:0-9]*
CHAR [^\<\&]+
%x TAG ATRLIST VALORST
%%
<TAG>[dD][oO][cC] {
/*printf("DOC\n");*/
return(DOC);
}
<TAG,ATRLIST>[\/\=] {
/*printf("__%c\n",*yytext);*/
return(*yytext);
}
<TAG,ATRLIST>[\>\;] {
BEGIN(0);
/*printf("__%c\n",*yytext);*/
return(*yytext);
}
[\<\&] {
BEGIN(TAG);
/*printf("__%c\n",*yytext);*/
return(*yytext);
}
<TAG>{ID} {
/*printf("ID->|%s|\n",yytext);*/
BEGIN(ATRLIST);
yylval.id = (char *) strdup(yytext);
stack=(elem) push(stack,yytext);
return(ID);
}
<ATRLIST>\"[^\"]*\" {
/*printf("VALOR->|%s|\n",yytext);*/
nlines+=conta(yytext);
yylval.valor=(char *) strdup(yytext);
return(VALOR);
}
<ATRLIST>{ID} {
/*printf("ID->|%s|\n",yytext); */
yylval.id=(char *) strdup(yytext);
return(ID);
}
<*>{WHITE} {
nlines+=conta(yytext);
/*printf("WHITE\n");*/
}
{CHAR} {
/*printf("CHAR\n");*/
nlines+=conta(yytext);
yylval.texto=(char *) strdup(yytext);
return(CHAR);
}
%%
Exemplo:
typedef struct _atrib {
char * nome;
char * valor;
struct _atrib *next;
} *atrib;
typedef union _conteudo {
char *texto;
struct _nodo *filho;
} *conteudo;
typedef struct _nodo {
char *tagname;
atrib atributos;
conteudo cont;
struct _nodo *next;
} *nodo;
atrib insereatrib(atrib lst, char *nome, char *valor);
nodo inserenodo(char * tagname, atrib atributos,conteudo cont,nodo irmao);
void shownodo(nodo nod);
void showatrib(atrib nod);
nodo conc(nodo lst, nodo last);
char *strtrim(char *s);
int conta(char* line);
Exemplo:
#include "grove.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
atrib insereatrib(atrib lst,char *nome, char *valor)
{
atrib novo,temp=lst;
if(nome==NULL || valor==NULL) return lst;
if (temp!=NULL)
while(temp->next!=NULL)
temp=temp->next;
novo = (atrib) malloc(sizeof(struct _atrib));
novo->nome = (char *) strdup(nome);
novo->valor = (char *) strdup(valor);
if (lst!=NULL)
{
temp->next=novo;
return lst;
}
else
return novo;
}
void shownodo(nodo nod)
{
int tipo=1;
/*
* 1 - Texto
* 2 - <ID AttrList/>
* 3 - <ID AttrList>ElemList</ID>
* */
if(nod==NULL) return;
if(strcmp("TEXTO",nod->tagname)==0)
tipo=1;
else if (nod->cont->filho==NULL)
tipo=2;
else
tipo=3;
switch (tipo) {
case 1: printf("-%s\n",nod->cont->texto);break;
case 2: {
printf("( %s\n",nod->tagname);
showatrib(nod->atributos);
printf(")/ %s\n",nod->tagname);
break;
}
case 3: {
printf("( %s\n",nod->tagname);
showatrib(nod->atributos);
shownodo(nod->cont->filho);
printf(")/ %s\n",nod->tagname);
break;
}
othrewise: break;
}
shownodo(nod->next);
}
void showatrib(atrib nod)
{
while(nod!=NULL)
{
printf("A %s %s\n",nod->nome,nod->valor);
nod=nod->next;
}
}
nodo conc(nodo lst, nodo last){
nodo temp=lst;
if (lst==NULL) return last;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=last;
return lst;
}
char *strtrim(char *t)
{
int i;
int fim_start;
char *s=(char *) strdup(t);
fim_start=0;
if(s==NULL) return(NULL);
i=0;
while(((s[i]!=0) && (!fim_start)))
{
if(s[i]==10 /*char \n */ || s[i]=='\t' || s[i]==' ')
{
s++;
}
else
fim_start=1;
}
i=strlen(s)-1;
while(i>0 && (s[i]==10 /*char \n */ || s[i]=='\t' || s[i]==' '))
i--;
s[i+1]=0;
return(s);
}
int conta(char* line) {
char* a;
int c=0;
a=line;
while(*line)
{
if(*line=='\n') c++;
line++;
}
return c;
}
Exemplo:
#include <stdio.h>
typedef struct _elem {
char *str;
struct _elem *next;
} *elem;
void show(elem lst);
elem push(elem lst, char *str);
char *pop(elem *pt);
char *peek(elem lst);
Exemplo:
#include "stack.h"
#include <stdlib.h>
#include <string.h>
elem push(elem lst, char *str)
{
elem novo;
novo = (elem) malloc(sizeof(struct _elem));
novo->next=lst;
novo->str=(char *) strdup(str);
return(novo);
}
char *pop(elem *pt)
{
elem this=*pt;
char *ret;
if(pt==NULL) return NULL;
if(*pt==NULL) return NULL;
*pt=(*pt)->next;
ret=(char *) strdup(this->str);
free(this);
return(ret);
}
char *peek(elem lst)
{
if(lst==NULL) return NULL;
return(lst->str);
}
void show(elem lst)
{
int i=0;
if(lst==NULL) return;
while(lst!=NULL)
{
printf("%d: %s\n",i,lst->str);
i++;
lst=lst->next;
}
}
Exemplo:
#include <stdio.h>
#define gotoxy(x,y) (printf("\033[%d;%dH",y,x))
#define bold() (printf("\033[1m"))
#define reverse() (printf("\033[7m"))
#define normal() (printf("\033[0m"))
#define cls() (system("clear"))
#define branco() (printf("\033[29m"))
#define preto() (printf("\033[30m"))
#define vermelho() (printf("\033[31m"))
#define verde() (printf("\033[32m"))
#define amarelo() (printf("\033[33m"))
#define azul_escuro() (printf("\033[34m"))
#define rosa() (printf("\033[35m"))
#define azul_claro() (printf("\033[36m"))
#define f_verm() (printf("\033[41m"))
#define f_verd() (printf("\033[42m"))
#define f_amar() (printf("\033[43m"))
#define f_az_esc() (printf("\033[44m"))
#define f_rosa() (printf("\033[45m"))
#define f_az_claro() (printf("\033[46m"))
#define branco_pisca() (printf("[1;5;29m"))
#define preto_pisca() (printf("[1;5;30m"))
#define vermelho_pisca() (printf("[1;5;31m"))
#define verde_pisca() (printf("[1;5;32m"))
#define amarelo_pisca() (printf("[1;5;33m"))
#define azul_escuro_pisca() (printf("[1;5;34m"))
#define rosa_pisca() (printf("[1;5;35m"))
#define azul_claro_pisca() (printf("[1;5;36m"))
#define f_verm_pisca() (printf("[1;5;41m"))
#define f_verd_pisca() (printf("[1;5;42m"))
#define f_amar_pisca() (printf("[1;5;43m"))
#define f_az_esc_pisca() (printf("[1;5;44m"))
#define f_rosa_pisca() (printf("[1;5;45m"))
#define f_az_claro_pisca() (printf("[1;5;46m"))
#define upperborder " "
#define sideborder " "
void window(int xi, int yi, int xf, int yf) {
int meio=xf-xi;
int xinter,yinter,xx;
for (yinter=yi;yinter<(yf+1);yinter++) {
if (yinter==yi || yinter == yf) {
for (xinTer=xi;xinter<(xf+1);xinter++) {
gotoxy(xinter,yinter);
reverse();
printf(upperborder);
normal();
}
}
else {
for (xinter=xi;xinter<(xf+1);xinter++) {
gotoxy(xinter,yinter);
if (xinter==xi || xinter == xf) {
reverse();
printf(sideborder);
normal();
}
else printf(" ");
}
}
}
}
Exemplo:CC=gcc CFLAGS=-O3 -ansi -g -pipe -W CLIBS=-lfl LEX=flex YACC=yacc STRIP=`which strip` main: y.tab.c lex.yy.c $(CC) $(CFLAGS) -o main y.tab.c stack.c grove.c $(CLIBS) `glib-config --libs` $(STRIP) main y.tab.c: $(YACC) -v main.y lex.yy.c: $(LEX) main.l clean: rm -f *.o y.tab.c lex.yy.c y.output y.tab.h stack.o y.output all: clean main
Agradecimentos...
Bibliografia: