Descrição do processo de implementação

Introdução

Nesta fase, começámos por testar a gramática definida na aula prática, que foi sendo modificada ao longo da implementação, para corrigir os erros que iam sendo encontrados.

O analisador léxico foi implementado em flex . Inicialmente era bastante simples e não reconhecia os textos de teste na perfeição, dando por vezes erro com certos caracteres e tendo certos problemas com alguns espaços em branco. Estes problemas foram resolvidos quando passámos a utilizar start-conditions no flex , que simplificaram, e muito, o desenvolvimento do analisador. Devemos mencionar que, as start-conditions utilizadas são exclusivas, embora neste caso isso seja indiferente, pois não existe nenhuma produção no analisador léxico que não esteja sujeita a uma start-condition .

Para a implementação do analisador sintático utilizámos o yacc . A gramática foi modificada várias vezes, até à versão final que, em virtude da simplificação operada no analisador léxico aquando da introdução de start-conditions , ficou praticamente igual à versão criada na aula prática em que foi apresentado o trabalho. As únicas diferenças residem na produção inicial, que foi modificada para garantir que o documento é iniciado com uma tag, e no facto de estarmos a utilizar recursividade à esquerda nas produções recursivas.

A estrutura criada para o grove consiste numa lista ligada de estruturas com apontadores para nome do nodo, filhos (ou no caso de ser um nodo de texto ou de macro, um apontador para o texto ou para o nome da macro, respectivamente), irmãos, e lista de atributos, tal como foi pedido na aula prática. Temos no entanto de referir que, devido à maneira como os nodos do grove são criados, e ao facto de estarmos a utilizar recursividade à esquerda, a lista de nodos irmãos de um nodo qualquer fica ligada pela ordem inversa à que é introduzida no texto, o mesmo acontecendo com a lista de atributos de uma tag. Quanto ao ESIS, criamos uma função travessia para o gerar, função esta que leva em conta a inversão da lista de nodos referida anteriormente, mas não a inversão da lista de atributos, que pensamos não afectar o reconhecimento, pelo menos nesta fase do trabalho.

Analisador Léxico - Código Fonte

ESPACO [\ \t\n]+
PALAVRA [a-zA-Z][a-zA-Z0-9]*
%x INTAG INAND
%%


<INITIAL>\< {
            BEGIN INTAG;
            return *yytext; 
          } 

<INITIAL>\<\/ { 
       BEGIN INTAG;
       return ETAGOPEN; 
     }

<INTAG>\> {
            BEGIN INITIAL;
            return *yytext; 
          } 

<INTAG>\/\> { 
              BEGIN INITIAL;
              return CLOSETAG;
            }

<INTAG>\=   { 
              return *yytext;
            }

<INTAG>{PALAVRA} { 
	yylval.t=strdup(yytext);
	return(ID); 
      }

<INTAG>\"[^\"]*\" { 
             yytext[strlen(yytext)-1]=0;
             yylval.t=yytext+1;
             return(VALOR); 
           }

<INTAG>{ESPACO} ;

<INITIAL>\& {BEGIN INAND; return AND;}

<INITIAL>[^&<]+ { 
	     yylval.t=strdup(yytext);
             return(CHAR); 
           }

<INAND>{PALAVRA} {
	           yylval.t=strdup(yytext);
                   return ID; 
                 }

<INAND>\; { 
            BEGIN INITIAL;
            return ENDAND; 
          }

Analisador Sintático, grove e ESIS - Código Fonte

%{ 
  #include<string.h>
 
  typedef struct attrNode {
    char *name;
    char *value;
    struct attrNode *next;
  } aNode;

  typedef struct groveNode {
    char *name;
    union { 
      char *text; 
      struct groveNode *son;
    } content;
    struct groveNode *brother;
    struct attrNode *attrList;
  } gNode;

  typedef enum{NODO,TEXTO,AND} gNodeType;

  gNode *grove, *gtest;
  aNode *atest;

  void travessia(gNode *grv);
  gNode *addGNode(gNodeType tp, char *name, void *cont, gNode *bro, aNode *at);
%}

%token ID ETAGOPEN CLOSETAG VALOR ESPACO AND ENDAND CHAR

%union{ 
  char *t;
  aNode *att;
  gNode *grv;
}     

%type <t> ID ESPACO VALOR CHAR
%type <att> Attr AttrList
%type <grv> Elem ElemList Doc

%%

Doc: '<' ID AttrList '>' ElemList ETAGOPEN ID '>'
     { 
       if (!strcmp($2,$7)) {
	 printf("*******AXIOMA RECONHECIDO!!!!*******\n"); 
	 
         grove=$$=addGNode(NODO, $2, $5, NULL, $3);
	 printf("\n");
	 return;
       }
       else exit(-1);
     }
  ;

ElemList: /*empty*/
          { $$=NULL; }
        | ElemList Elem
          {
            $2->brother=$1;
            $$=$2;
          }
        ;

Elem: CHAR
      {
        $$=addGNode(TEXTO, NULL, $1, NULL, NULL);
      }
    | AND ID ENDAND 
      {
        $$=addGNode(AND, NULL, $2, NULL, NULL);
      }
    | '<' ID AttrList '>' ElemList ETAGOPEN ID '>' 
      {
        if (strcmp($2,$7) != 0) {
          printf("TAGS NAO COINCIDEM!!!!\n");
          return;
        }
        $$=addGNode(NODO, $2, $5, NULL, $3);
      } 
    | '<' ID AttrList CLOSETAG
      {
        $$=addGNode(NODO, $2, NULL, NULL, $3);
      }
    ;

AttrList: /*empty*/         
          { $$=NULL; }
        | AttrList Attr 
          {
            $2->next=$1;
            $$=$2; 
          }
        ;

Attr: ID '=' VALOR 
      {
         if ( ($$=(aNode*)malloc(sizeof(struct attrNode)))==NULL)  
           exit(-1);
	 $$->name=strdup($1);
	 $$->value=strdup($3);
	 $$->next=NULL;
      }
    ;

%%

#include "scanner.c"

int  main() { 
  yyparse();
  travessia(grove);
  printf("\n");
  return 0;
}

void yyerror(char *text) { printf("Erro: %s\n",text); }

void travessia(gNode *grv) {
  if (strcmp(grv->name,"TEXTO")==0) {
    if (grv->brother!=NULL) travessia(grv->brother);
    printf("- %s\n",grv->content.text);
  }
  else if (strcmp(grv->name,"AND")==0) {
    if (grv->brother!=NULL) travessia(grv->brother);
    printf("&(%s)\n",grv->content.text);
  }
  else {
    aNode *attrAux=grv->attrList;

    if (grv->brother!=NULL) travessia(grv->brother);
    while(attrAux!=NULL) {
      printf("A %s %s\n", attrAux->name, attrAux->value);  
      attrAux=attrAux->next;
    }
    printf("(%s\n",grv->name);
    if (grv->content.son!=NULL) 
      travessia(grv->content.son);
    printf(")%s\n",grv->name);
  }
}


gNode *addGNode(gNodeType tp, char *name, void *cont, gNode *bro, aNode *at)
{
  gNode *grv;
  
  if ( (grv=(gNode*)malloc(sizeof(struct groveNode)))==NULL) {
    printf("Erro na aloca,c~ao dum nodo do grove.\n"); 
    exit(-1);
  }

  if (tp==AND) {
    grv->name=strdup("AND");
    grv->content.text=strdup((char *)cont);
  }
  else if (tp==TEXTO) {
    grv->name=strdup("TEXTO");
    grv->content.text=strdup((char *)cont);
  }
  else {
    grv->name=strdup(name);
    grv->content.son=(gNode *)cont;
  } 
  grv->brother=bro;
  grv->attrList=at;

  return(grv);
}

Makefile

PROCDEPS= y.tab.c
YACCDEPS= fase1.y scanner.c
FLEXDEPS= fase1.l


fase1: $(PROCDEPS)
	gcc -o fase1 $< -lfl -ggdb

y.tab.c: $(YACCDEPS)
	yacc -v fase1.y

scanner.c: $(FLEXDEPS)
	lex -oscanner.c $< 

clean: scanner.c y.tab.c y.output
	rm scanner.c
	rm y.output
	rm y.tab.c

Devemos agradecer aos professores Pedro Henriques e José Ramalho pela ajuda dispensada, sempre que solicitada. Agradecemos ainda ao nosso colega Marco Monteiro pelas dicas que nos deu, principalmente por nos ensinar a usar start-conditions no flex .

• [crespo98 ]Processadores de linguagens - da concepção à implementação, Rui Gustavo Crespo, IST Press, 1998
• [manlexyacc ]Man pages do flex e do yacc