Resumo:
Este trabalho vem no âmbito da disciplina de Processamento de Linguagens I e relata-se aqui a primeira fase desse trabalho, um reconhecedor de documentos XML.
Este trabalho prático da disciplina de Processamento de Linguagens I, engloba três fases. Este relatório é referente à primeira dessas fases, onde se pretende a construção de um processador genérico de documentos estruturados (XML). Falaremos então nos analisadores léxico e sintáctico e na construção de uma estrutura de dados não linear para armazenamento de um documento.
Tendo como base que os analisadores léxicos são normalmente implementados segundo o modelo de autómatos finitos, recorremos ao gerador lex/flex para elaborar o reconhecimento léxico.
Tendo ainda em conta o facto de existir uma especificação por meio de uma gramática, usaremos também a ferramente yacc/bison , uma vez que esta constrói automaticamente a árvore de uma frase (texto).
Por fim, falaremos nos algoritmos de geração do grove , a estrutura onde armazenamos o documento a ser analisado, e falaremos também da travessia ESIS desse mesmo grove.
Numa primeira análise ao enunciado do trabalho, e tendo como base o conteúdo das aulas téoricas e teórico práticas, sabemos que o nosso analisador léxico (lex) vai receber o nosso texto e uma descrição dos terminais, devolvendo depois os terminais que vai reconhecendo para o nosso analisador sintáctico(yacc), devendo este reconhecer o nosso como válido ou não.
Analisando a grámatica que nos foi fornecida, fizemos o levantamento dos símbolos terminais da gramática para posteriormente procedermos à elaboração do analisador léxico.
Os símbolos terminais da gramática são:
T = {texto, id, valor}
Depois de termos efectuado o levantamento dos símbolos terminais da linguagem iniciamos o percurso da automatização do reconhecimento dos símbolos, ou seja, começamos a estruturar o conjunto de regras e as respectivas acções
Sabendo que o lex/flex é um gerador de analisadores léxicos, e que este é constituído por um conjunto de expressões regulares para descrever os símbolos básicos ou lexemas da linguagem, e cujas acções semânticas respectivas devolvem os símbolos reconhecidos na análise léxica, que serão posteriormente verificados sintacticamente, como se evidencia mais abaixo.
A análise léxica ficou então assim constituída:
ID [A-Za-z][A-Za-z0-9-]*
%option yylineno
%x TAG ATRIB EXTRA
%%
\< { BEGIN(TAG); return *yytext; }
& { BEGIN(EXTRA); return *yytext; }
<EXTRA>; { BEGIN(0); return *yytext; }
<TAG>{ID} { BEGIN(ATRIB);
yylval.str = strdup(yytext);
return id; }
<ATRIB,TAG>\>[ \n\t\r]*\< { BEGIN(0);
unput('<');
return *yytext; }
<ATRIB,TAG>\>[ \n\t\r]*$ { BEGIN(0);
return *yytext; }
<ATRIB,TAG>\> { BEGIN(0); return *yytext; }
<ATRIB>\= { return *yytext; }
<ATRIB>\"[^\"]*\" { yylval.str = strdup(yytext+1);
if (yylval.str[yyleng-2] != '"') {
fprintf(stderr, "String nao terminada: linha %d\n",
yylineno);
exit(1); }
else
yylval.str[yyleng-2] = '\0';
return valor; }
<ATRIB,TAG>\/ { return *yytext; }
<ATRIB,EXTRA>{ID} { yylval.str = strdup(yytext); return id; }
<ATRIB,TAG,EXTRA>[ \t\r\n]+ ;
\n ;
<TAG,ATRIB,EXTRA>. { printf("Erro: caracter n esperado na linha %d: %s\n!", yylineno, yytext); exit(1); }
[^<&]+ { yylval.gstr = g_string_new("");
yylval.gstr = g_string_append(yylval.gstr, yytext);
return texto; }
%%
Visto que o ficheiro de especificação lex/flex é constituído por um conjunto de expressões regulares triviais, não se justifica, nem é do âmbito desta disciplina, a descrição do conjunto das regras ei acçãoi . Isto é, uma vez que ei é uma expressão regular que denota uma classe de símbolos básicos (terminais) e acçãoi é a acção semântica que será executada sempre que uma sequência de caracteres (do texto a processar) faz match com ei , acção esta que nesta situação apenas faz o transporte do código associado ao elemento léxico que concordou com ei .
Devemos, no entanto, salientar alguns aspectos do nosso ficheiro de especificação lex/flex. O primeiro prende-se com o facto de activarmos a contagem de linhas no lex %option yylineno . Este facto permitir-nos-á aceder a qualquer altura ao número da linha do ficheiro que estamos a analisar, ficando este valor armazenado na variável yylineno que será útil nas mensagens de erro.
É importante referir também que optamos por usar start-conditions para podermos fazer uma separação lógica entre texto do utilizador, tags e atributos, bem como o caso especial do tipo &id; por exemplo. Isto permite um maior controlo (a nível de detecção de erros) do texto a ser reconhecido.
Por último convém referir ainda a expressão <[ \n\t\r]*\< que elimina espaços e "returns" que de outra forma seriam considerados como texto, voltando a colocar o caracter < na stack para ser analisado.
A interacção entre o lex/flex e o yacc/bison é feita através da função yylex() , onde são enviados os códigos dos elementos léxicos encontrados no texto fonte.
Por ultimo, mas não menos importante, é o facto de ser necessário enviar itambém os valores dos símbolos terminais da nossa gramática para o yacc/bison. Isto é conseguido através da variável yylval . No caso da nossa gramática, sempre que encontramos um identificador ou um valor de um atributo o valor destes é retornado. Por sua vez, também o texto do utilizador é retornado, com a diferença de que neste caso recorremos ao tipo string da GLib que permite alocar strings em memória sem limites de tamanho, eliminado desta forma possíveis limitações do tipo string associado ao flex e ao bison.
Depois de um cuidada análise à gramática apresentada pelo docente procedemos a uma série de alterações por forma a viabilizar o seu uso com o bison e de acordo com os objectivos do trabalho.
A primeira alteração prende-se com o facto de que a gramática original não implementava de facto uma lista de elementos, mas apenas uma tag com um elememento dentro e assim sucessivamente, ou seja, o texto <p>teste<b>bb</b></p> não era válido.
Alteramos também a produção das tags pois havia duas produções a começar com o símbolo <. Uma para as tags que possuem conteúdo e outra para as tags que não possuem conteudo. Bastou-nos colocar em evidência os pontos comuns dessas produções e criar uma outra (Tail) que ramifica os dois casos.
Na terceira alteração eliminanos toda e qualquer recursividade à direita de todas as produções da gramática.
A última modificação que introduzimos já veio no sentido de uma das validações que nos era pedida para fazer, isto é, que todo o documento começasse e terminasse com a abertura e fecho de um elemento. Para tal, bastou-nos acrescentar esta informação à primeira produção da gramática.
A nossa gramática neste ponto é:
DOCUMENTO -> '<' id '>' ElemList '<' '/' id '>'
ElemList -> ElemList Elem
| &
Elem -> Text
| '&' id ';'
| '<' id AttrList Tail
Tail -> '>' ElemList '<' '/' id '>'
| '/' '>'
AttrList -> AttrList Attr
| &
Attr -> id '=' valor
Text -> texto
Restava-nos nesta altura introduzir mais uma validação. Deveríamos garantir que os elementos com conteúdo que fossem abertos fossem correctamente fechados, isto é, na ordem correcta em que foram abertos.
A forma mais simples que encontramos de implementar isto foi construíndo uma stack. Assim, de cada vez que um elemento é aberto, o seu valor é colocado no topo da stack. Desta forma, quando um elemento é fechado é feito um pop e o valor a fechar deve ser idêntico ao que se encontra no topo da stack.
Há no entanto dois aspectos a considerar. O primeiro prende-se com o facto de que os elementos sem conteúdo do género <id /> usam a mesma produção que os elementos com conteúdo aquando da sua abertura, ou seja, o seu conteúdo também é colocado na stack. Para contornar este problema, basta fazermos um pop da stack quando fechamos os elementos sem conteúdo.
Devemos considerar também o caso da primeira produção em que os elemento que engloba o documento também deve ser aberto e fechado correctamente. Aqui basta fazermos os respectivos push e pop.
Em relação à stack popriamente dita não iremos descrever aqui o seu funcionamento, qué muito trivial, bastando dizer que é uma lista ligada com inserção à cabeça, que permite uma maior simplicidade das funções e uma maior rapidez no acesso ao topo da stack. Implementamos também a função de teste à stack, bem como a respectiva função de erro.
O código completo nesta altura da gramática é:
extern char* yytext;
t_node * stack = NULL; // a stack em questão
extern int yylineno;
%}
%union {
char* str;
GString* gstr; }
%start DOCUMENTO
%%
DOCUMENTO : '<' id { stack = push(stack, yylval.str, yylineno); }
'>' ElemList '<' '/' id { teste_stack(stack, $8, yylineno); } '>'
ElemList : ElemList Elem
|
Elem : Text
| '&' id ';'
| '<' id { stack = push(stack, $2, yylineno); }
AttrList Tail
Tail : '>' ElemList '<' '/' id '>' { teste_stack(stack, $5, yylineno);
stack = pop(stack); }
| '/' '>' { stack = pop(stack); }
AttrList : AttrList Attr
|
Attr : id '=' valor
Text : texto
%%
int yyerror(char* msg) {
printf("linha: %d, %s e encontrei '%s'\n", yylineno, msg, yytext);
exit(1);
}
O código da stack é o seguinte:
/* stack.h */
typedef struct node{
char * identif;
struct node * link;
int nlinha;
}t_node;
t_node * push(t_node* stack, char * identif, int nlinha);
t_node * pop(t_node* stack);
void teste_stack(t_node * stack, char * str, int linha);
/* stack.c */
#include "stack.h"
t_node * push(t_node* stack, char * identif, int nlinha){
t_node * new_node = (t_node*)malloc(sizeof(t_node));
if (new_node == NULL) { perror("Stack overflow"); exit(1); }
else
{
new_node->identif = strdup(identif);
new_node->nlinha = nlinha;
new_node->link = stack;
identif = "tiago";
return new_node;
}
}
t_node * pop(t_node * stack) {
t_node * node_pop;
if (stack == NULL) return NULL; //stack vazia
else
{
node_pop = stack;
stack = stack->link;
free(node_pop);
return stack;
}
}
void teste_stack(t_node * stack, char * str, int linha) {
if (strcmp(stack->identif, str) != 0) {
printf("ERRO!!!\n");
printf("%s abriu na linha %d\n", stack->identif,
stack->nlinha);
printf("%s fechou na linha %d\n", str, linha);
exit(1);
}
}
Partindo do princípio que o objectivo do grove é permitir armazenar e representar a informação de um documento de entrada com base numa gramática, sem perde a semântica do documento, chegamos à conclusão que a estrutura dinâmica de dados para a nossa tabela de identificadores, que melhor se ajusta à solução do problema e que nos oferecia uma maior fiabilidade era uma árvore binária. Isto porque o seu acesso é relativamente rápido em tabelas de grande dimensão, e o facto das operações de inserção e remoção de um nodo na árvore serem bastante complexas não nos afecta pois essas operações não são necessárias para o projecto em questão.
A lógica do uso desta estrutura de dados é bastante simples. Cada nodo aponta para os seus filhos, isto é, cada elemento é representado como um nodo que possui apontadores para os outros elementos que possui dentro de si, aplicando-se esta lógica para esses elementos "filhos". Ou seja:
a sub-árvore da esquerda de um qualquer nodo corresponde sempre ao conteúdo de um nodo;
a sub-árvore da direita de um qualquer nodo corresponde sempre ao bloco seguinte desse nodo presente no documento;
o nodo raiz (aquele que engloba todo o documento) nunca terá sub-árvore da direita, uma vez que todo o conteúdo de um documento pertence a este bloco, tal como foi definido na contrução da gramática. Este mesmo raciocínio aplica-se aos elementos sem conteúdo que como nunca terão conteúdo terão sempre uma sub-árvore direita nula.
como já foi referido, vamos ter de efectuar nesta fase uma travessia do grove . Esta travessia será uma travessia PRE-ORDER, na medida em que visitamos primeiro o nodo em questão, depois a sua sub-árvore esquerda que corresponde ao seu conteúdo, e de seguida a sua sub-árvore direita que corresponde ao bloco seguinte de dados.
Tendo em conta o referido na secção anterior, isto é, que a nossa estrutura de dados é uma árvore binária, esta vai ser constituída pelos seguintes campos:
identif : este campo é um apontador para caracteres onde armazenamos os "id's" dos elementos que vamos reconhecendo. No caso especial de encontrarmos texto, este toma o valor de "texto";
cont : este campo é uma union com dois campos, sendo que usaremos um deles consoante o tipo de nodo. O primeiro campo txt é um apontador para uma GString.É usado no caso de possuirmos um nodo de texto. O tipo GString pertence à biblioteca GLib, que é usada pelas razões já apontadas. O segundo campo conteudo é usado para os outros nodos e representa a sub-árvore esquerda do nodo, ou seja, é um apontador para outro nodo do mesmo tipo.
atribs : este campo é um apontador para uma lista ligada onde se armazena os atributos do elemento no nodo. Não achamos necessários analisarmos muito detalhadamente esta implementação, bastando apenas referir que se trata de uma lista ligada comum com inserção à cauda, sendo que em cada nodo armazenamos o identificador do atributo e o seu valor.
irmaos : o último campo da nossa estrutura é o apontador para a sub-árvore direita do nodo, ou seja, um apontador para um outro nodo, que se encontra no mesmo nível.
A estrutura fica então assim definida (note-se que t_nodo é a lista ligada onde armazenamos os atributos):
typedef struct nodo {
char * atributo;
char * atr_valor;
struct nodo *next;
}t_nodo;
typedef struct g_nodo {
char * identif;
union C {
GString* txt;
struct g_nodo * conteudo;
} cont;
t_nodo * atribs;
struct g_nodo * irmaos;
} t_grove;
Por forma a acedermos mais facilmente aos vários campos da estrutura de dados e por também para facilitar a leitura do código, definimos as seguintes macros:
#define IRMAOS(g) g->irmaos #define ATRIBS(g) g->atribs #define IDENTIF(g) g->identif #define CONT_TXT(g) g->cont.txt #define CONTEUDO(g) g->cont.conteudo
Falaremos primeiro nas funções que usamos para construir as listas ligadas dos atributos:
t_nodo * new_nodo_list() {
return NULL;
}
Esta função retorna uma nova lista, o que equival a retornar um apontador nulo.
t_nodo * new_nodo(char * atributo, char * atr_valor) {
t_nodo * new = (t_nodo *)malloc(sizeof(t_nodo));
new->atributo = strdup(atributo);
new->atr_valor = strdup(atr_valor);
new->next = NULL;
return new;
}
Aqui cria-se um novo nodo da lista ligada, com a respectiva alocação de momória e preenchimento dos campos.
t_nodo * append_nodo(t_nodo * nodo_list, t_nodo * nodo) {
if (nodo_list == NULL)
nodo_list = nodo;
else
nodo_list->next = append_nodo(nodo_list->next, nodo);
return nodo_list;
}
Por fim a função de inserção na lista ligada, que como já referimos é feita na cauda.
Apresentaremos agora as funções de construção do grove:
t_grove * new_txt_grove(GString * str) {
t_grove * new = (t_grove *)malloc(sizeof(t_grove));
new->identif = "texto";
new->cont.txt = str;
new->atribs = NULL;
return new;
}
Neste caso temos uma função para criar um novo nodo da nossa árvore, especificamente um nodo do tipo texto. É feita a alocação de memória e o campo dos atributos é colocado a nulo, pois um nodo de texto não possui atributos.
t_grove * new_elem_grove(char * identif, t_nodo * atribs) {
t_grove * new = (t_grove *)malloc(sizeof(t_grove));
new->identif = strdup(identif);
new->atribs = atribs;
return new;
}
Para os restantes nodos da árvore temos esta função que armazena o valor do identificador do elemento e o apontador para a lista dos seus atributos.
t_grove * append_grove(t_grove * g, t_grove * elem) {
if ( g == NULL )
g = elem;
else
g->irmaos = append_grove(g->irmaos, elem);
return g;
}
Esta função adiciona uma sub-árvore direita a um elemento. Se este já possuir uma, esta será adicionada a essa sub-árvore, mantendo-se assim os nodos como "irmãos".
O grove vai ser contruído recorrendo às funções descritas anteriormente e, dado que os lados esquerdos das produções na gramática têm a si associados um determinado tipo de dados, vamos armazenar aí o nosso grove, declarando a nossa estrutra de dados e a nossa lista ligada para os atributos na union dos dados da gramática, por forma a podermos associar esses tipos com as produções. Ou seja:
%union {
t_grove * el; //um apontador para um nodo do grove
t_nodo * nodo_list; // lista ligada atributos
char* str;
GString* gstr; }
De seguida atribuímos o tipo ao lado esquerdo das produções consoante a sua utilização.
%type <nodo_list> AttrList %type <nodo_list> Attr %type <el> Text %type <el> Elem %type <el> ElemList %type <el> Tail
Ao declararmos os símbolos terminais da gramática, associamos também a cada um deles o respectivo tipo de dados, por forma a permitir as acções semânticas de construção do gfrove .
%token <gstr> texto %token <str> id %token <str> valor
De seguida analisaremos com detalhe o processo de construção do grove :
i)
DOCUMENTO : '<' id { stack = push(stack, yylval.str, yylineno); }
'>' ElemList '<' '/' id { teste_stack(stack, $8, yylineno); }
'>' { $<el>$ = new_elem_grove($2, NULL);
CONTEUDO($<el>$) = $5;
_travessia_esis($<el>$); }
ii)
ElemList : ElemList Elem { $$ = append_grove($1, $2); }
| { $$ = NULL; }
iii)
Elem : Text { $$ = $1; }
| '&' id ';' { $$ = new_elem_grove($2, NULL); }
| '<' id { stack = push(stack, $2, yylineno); }
AttrList Tail { $$ = new_elem_grove($2, $4);
CONTEUDO($$) = CONTEUDO($5);
free_grove($5); }
iv)
Tail : '>' ElemList '<' '/' id '>' { teste_stack(stack, $5, yylineno);
stack = pop(stack);
$$ = new_elem_grove($5, NULL);
CONTEUDO($$) = $2; }
| '/' '>' { $$ = new_elem_grove("", NULL); CONTEUDO($$) = NULL;
stack = pop(stack); }
v)
AttrList : AttrList Attr { $$ = append_nodo($1, $2); }
| { $$ = new_nodo_list(); }
vi)
Attr : id '=' valor { $$ = new_nodo($1, $3); }
vii)
Text : texto { $$ = new_txt_grove($1); }
No ponto i) criamos o primeiro nodo da árvore através da função new_elem_grove($2, NULL) . Este primeiro nodo não tem atributos e definimos o seu conteúdo, i.e., a sua sub-árvore esquerda como sendo ElemList . Isto está na linha do que tem sido dito, o primeiro elemento engloba todos os outros. Para isso usamos o comando CONTEUDO($<el>$) = $5 .
No ponto ii) procede-se à inserção dos nodos "irmãos", ou seja, o novo nodo passa a ser a sub-árvore direita do nodo mais à direita neste nível. Isto através da função append_grove já discutida.
No ponto iii) temos várias acções semânticas. O que fazemos aqui é criar os nodos para os elementos, excepto no caso dos nodos de texto que são criados noutra produção como iremos ver. É importante notar que na produção que reconhece os elementos (os que começam com uma tag), e de acordo com a gramática e com o que foi dito anteriormente, só saberemos qual o seu conteúdo na produção Tail . Deste modo e como veremos no ponto seguinte criámos um nodo "temporário" na produção Tail onde armazenamos o conteúdo para agora o usarmos CONTEUDO($$) = CONTEUDO($5) , fazendo depois a dealocação de memória desse nodo.
Neste ponto, como já foi referido no ponto anterior, criamos um nodo temporário onde apenas colocamos dados no campo do conteúdo. Para os elementos que têm conteúdo colocamos o apontador para a o seu conteúdo e um valor nulo para os elementos sem conteúdo.
No ponto v) é apenas a inserção dos atributos e dos seus valores na lista ligada e o ponto vi) a criação de um novo nodo da lista.
No último ponto temos a criação dos nodos de texto.
Uma vez que sabemos que a travessia da árvore é PRE-ORDER, basta implementar o algoritmo que é bastante simples:
void _travessia_esis(t_grove * g) {
if (g) {
if ( strcmp(IDENTIF(g), "texto") == 0)
printf("-%s\n", CONT_TXT(g)->str);
else {
print_nodo_list(ATRIBS(g));
printf("( %s\n", IDENTIF(g));
_travessia_esis(CONTEUDO(g));
printf(")/ %s\n", IDENTIF(g));
}
_travessia_esis(IRMAOS(g));
}
}
Para imprimirmos a lista de atributos usamos a função print_nodo_list :
void print_nodo(t_nodo * nodo) {
printf("A %s=%s\n", nodo->atributo, nodo->atr_valor);
}
void print_nodo_list(t_nodo * nodo) {
if (nodo != NULL) { print_nodo(nodo); print_nodo_list(nodo->next); }
}
%{
#include <glib.h>
#include "stack.h"
#include "grove.h"
#include "gramatica.tab.h"
#include <string.h>
%}
ID [A-Za-z][A-Za-z0-9-]*
%option yylineno
%x TAG ATRIB EXTRA
%%
\< { BEGIN(TAG); return *yytext; }
& { BEGIN(EXTRA); return *yytext; }
<EXTRA>; { BEGIN(0); return *yytext; }
<TAG>{ID} { BEGIN(ATRIB);
yylval.str = strdup(yytext);
return id; }
<ATRIB,TAG>\>[ \n\t\r]*\< { BEGIN(0);
unput('<');
return *yytext; }
<ATRIB,TAG>\>[ \n\t\r]*$ { BEGIN(0);
return *yytext; }
<ATRIB,TAG>\> { BEGIN(0); return *yytext; }
<ATRIB>\= { return *yytext; }
<ATRIB>\"[^\"]*\" { yylval.str = strdup(yytext+1);
if (yylval.str[yyleng-2] != '"') {
fprintf(stderr, "String nao terminada: linha %d\n",
yylineno);
exit(1); }
else
yylval.str[yyleng-2] = '\0';
return valor; }
<ATRIB,TAG>\/ { return *yytext; }
<ATRIB,EXTRA>{ID} { yylval.str = strdup(yytext); return id; }
<ATRIB,TAG,EXTRA>[ \t\r\n]+ ;
\n ;
<TAG,ATRIB,EXTRA>. { printf("Erro: caracter n esperado na linha %d: %s\n!", yylineno, yytext); exit(1); }
[^<&]+ { yylval.gstr = g_string_new("");
%{
#include "stack.h"
#include "grove.h"
#include <string.h>
#include <glib.h>
extern char* yytext;
t_node * stack = NULL;
extern int yylineno;
%}
%union {
t_grove * el;
t_nodo * nodo_list;
char* str;
GString* gstr; }
%type <nodo_list> AttrList
%type <nodo_list> Attr
%type <el> Text
%type <el> Elem
%type <el> ElemList
%type <el> Tail
%token <gstr> texto
%token <str> id
%token <str> valor
%start DOCUMENTO
%%
DOCUMENTO : '<' id { stack = push(stack, yylval.str, yylineno); }
'>' ElemList '<' '/' id { teste_stack(stack, $8, yylineno); }
'>' { $<el>$ = new_elem_grove($2, NULL);
CONTEUDO($<el>$) = $5;
_travessia_esis($<el>$); }
ElemList : ElemList Elem { $$ = append_grove($1, $2); }
| { $$ = NULL; }
Elem : Text { $$ = $1; }
| '&' id ';' { $$ = new_elem_grove($2, NULL); }
| '<' id { stack = push(stack, $2, yylineno); }
AttrList Tail { $$ = new_elem_grove($2, $4);
CONTEUDO($$) = CONTEUDO($5);
free_grove($5); }
Tail : '>' ElemList '<' '/' id '>' { teste_stack(stack, $5, yylineno);
stack = pop(stack);
$$ = new_elem_grove("", NULL);
CONTEUDO($$) = $2; }
| '/' '>' { $$ = new_elem_grove("", NULL); CONTEUDO($$) = NULL;
stack = pop(stack); }
AttrList : AttrList Attr { $$ = append_nodo($1, $2); }
| { $$ = new_nodo_list(); }
Attr : id '=' valor { $$ = new_nodo($1, $3); }
Text : texto { $$ = new_txt_grove($1); }
%%
int yyerror(char* msg) {
printf("linha: %d, %s e encontrei '%s'\n", yylineno, msg, yytext);
exit(1);
}
#include <stdio.h>
#include <string.h>
#include <glib.h>
typedef struct nodo {
char * atributo;
char * atr_valor;
struct nodo *next;
}t_nodo;
typedef struct g_nodo {
char * identif;
union C {
GString* txt;
struct g_nodo * conteudo;
} cont;
t_nodo * atribs;
struct g_nodo * irmaos;
} t_grove;
#define IRMAOS(g) g->irmaos
#define ATRIBS(g) g->atribs
#define IDENTIF(g) g->identif
#define CONT_TXT(g) g->cont.txt
#define CONTEUDO(g) g->cont.conteudo
t_nodo * new_nodo_list();
t_nodo * new_nodo(char * atributo, char * atr_valor);
t_nodo * append_nodo(t_nodo * nodo_list, t_nodo * nodo);
void print_nodo_list(t_nodo * nodo_list);
t_grove * new_grove();
t_grove * new_txt_grove(GString * str);
t_grove * new_elem_grove(char * identif, t_nodo * atribs);
t_grove * append_grove(t_grove * g, t_grove * elem);
void _travessia_esis(t_grove * g);
void free_grove(t_grove * g);
#include "grove.h"
#include "gramatica.tab.h"
t_nodo * new_nodo_list() {
return NULL;
}
t_nodo * new_nodo(char * atributo, char * atr_valor) {
t_nodo * new = (t_nodo *)malloc(sizeof(t_nodo));
new->atributo = strdup(atributo);
new->atr_valor = strdup(atr_valor);
new->next = NULL;
return new;
}
t_grove * new_txt_grove(GString * str) {
t_grove * new = (t_grove *)malloc(sizeof(t_grove));
new->identif = "texto";
new->cont.txt = str;
new->atribs = NULL;
new->irmaos = NULL;
return new;
}
t_grove * new_elem_grove(char * identif, t_nodo * atribs) {
t_grove * new = (t_grove *)malloc(sizeof(t_grove));
new->identif = strdup(identif);
new->atribs = atribs;
return new;
}
t_nodo * append_nodo(t_nodo * nodo_list, t_nodo * nodo) {
if (nodo_list == NULL)
nodo_list = nodo;
else
nodo_list->next = append_nodo(nodo_list->next, nodo);
return nodo_list;
}
void print_nodo(t_nodo * nodo) {
printf("A %s=%s\n", nodo->atributo, nodo->atr_valor);
}
void print_nodo_list(t_nodo * nodo) {
/* while(nodo) {
print_nodo(nodo);
nodo = nodo->next;
}*/
if (nodo != NULL) { print_nodo(nodo); print_nodo_list(nodo->next); }
}
t_grove * new_grove() {
return NULL;
}
t_grove * append_grove(t_grove * g, t_grove * elem) {
if ( g == NULL )
g = elem;
else
g->irmaos = append_grove(g->irmaos, elem);
return g;
}
void _travessia_esis(t_grove * g) {
if (g) {
if ( strcmp(IDENTIF(g), "texto") == 0)
printf("-%s\n", CONT_TXT(g)->str);
else {
print_nodo_list(ATRIBS(g));
printf("( %s\n", IDENTIF(g));
_travessia_esis(CONTEUDO(g));
printf(")/ %s\n", IDENTIF(g));
}
_travessia_esis(IRMAOS(g));
}
}
void free_grove(t_grove * g) {
free(g);
}
#include <stdio.h>
#include <string.h>
typedef struct node{
char * identif;
struct node * link;
int nlinha;
}t_node;
t_node * push(t_node* stack, char * identif, int nlinha);
t_node * pop(t_node* stack);
void teste_stack(t_node * stack, char * str, int linha);
#include "stack.h"
t_node * push(t_node* stack, char * identif, int nlinha){
t_node * new_node = (t_node*)malloc(sizeof(t_node));
if (new_node == NULL) { perror("Stack overflow"); exit(1); }
else
{
new_node->identif = strdup(identif);
new_node->nlinha = nlinha;
new_node->link = stack;
identif = "tiago";
return new_node;
}
}
t_node * pop(t_node * stack) {
t_node * node_pop;
if (stack == NULL) return NULL; //stack vazia
else
{
node_pop = stack;
stack = stack->link;
free(node_pop);
return stack;
}
}
void teste_stack(t_node * stack, char * str, int linha) {
if (strcmp(stack->identif, str) != 0) {
printf("ERRO!!!\n");
printf("%s abriu na linha %d\n", stack->identif,
stack->nlinha);
printf("%s fechou na linha %d\n", str, linha);
exit(1);
}
}
Para já os nossos agradecimentos vão para os docentes da cadeira e para alguns colegas por ajudarem a resolver alguns problemas.
Bibliografia: