Resumo:
Este é um projecto que surge no âmbito da disciplina de Processamento de Linguagens 1, cujo objectivo é tornar-se um processador genérico de documentos estruturados (XML).
Este trabalho tem por objectivo desenvolver uma ferramente que, processando um documento no formato XML, valide a sua estrutura e guarde a informação num grove , permitindo assim a construção de documentos com o mesmo conteúdo, em vários formatos.
O projecto divide-se em 3 fases, cada uma com várias etapas. Este relatório contém, actualmente, informação sobre a primeira fase, e será actualizado conforme for necessário.
Nesta fase, o único output é no formato ESIS.
A análise léxica e sintáctica implica uma forma de reconhecer símbolos terminais e uma forma de distinguir frases válidas na linguagem. Utilizei o flex para o reconhecedor de símbolos terminais e o bison para o reconhecedor de frases.
Um documento em XML é composto por texto normal, no qual se introduzem comandos num formato predefinido, a que se chamam tags . Uma tag é formada por vários símbolos terminais e por identificadores textuais. Existe também uma forma particular de tag que permite introduzir caracteres especiais, de diferentes alfabetos, que não merece muita atenção, pela sua simplicidade.
Um problema com que me deparei na análise léxica foi a necessidade de reconhecer certos tokens apenas em certos contextos. É, por exemplo, o caso dos tokens ID, que só deverao ser reconhecidos dentro de uma tag, ou na especificaçao de um caracter especial (&ID;).
O caso dos valores dos atributos merece também alguma atençao. Com efeito, pode revelar-se útil a possibilidade de atribuir valores com mais do que uma palavra. Mas esse tipo de tokens também só faz sentido aquando da atribuiçao de um valor a um atributo. Por outro lado, ao reconhecer texto, convinha encontrar o maior bloco de texto possível, sem que as tags fossem englobadas nesse bloco.
Tornou-se assim necessário definir diferentes estados para o analisador léxico:
O estado "inicial", em que o maior conjunto de caracteres (que não contenha '&' ou '<' ) é retornado como um bloco de texto.
O estado "tag", que é activado ao encontrar o símbolo terminal '<' e que representa a leitura de informaçao de uma tag. Neste estado sao retornados tanto tokens ID como caracteres, que valem eles próprios como símbolos terminais. O símbolo terminal ' > ' retoma o estado inicial.
O estado "valor", que é activado ao encontrar o símbolo terminal '=' quando no estado "tag". Neste estado retornam-se tokens do tipo STR, que podem ser um grupo de caracteres alfanuméricos ou um qualquer conjunto de caracteres entre "". A leitura de qualquer token neste estado retoma o estado "tag".
O estado "caracter", que é activado ao encontrar o caracter '&' quando no estado inicial. Neste estado retornam-se tanto tokens ID como caracteres, (cujo significado sintático é o do próprio caracter). Termina com a leitura do caracter ';', voltando ao estado inicial.
A gramática proposta inicialmente foi ligeiramente alterada. Algumas das modificaçoes foram efectuadas apenas para aumentar a legibilidade, outras para extender um pouco a própria sintaxe. Segue-se a nova gramática, com breves comentários:
document --> bck
Este é o ponto de entrada para a gramática. Definindo blk separadamente de elem torna-se simples forçar um documento a começar com a abertura e fecho de uma tag (um bloco, ver mais abaixo).
blk --> blk_start elem_list blk_end | blk_start blk_end
Uma tag em bloco é, uma tag que abre um novo conteúdo e termina com o fecho da mesma tag. A tag que é fechada em blk_end está ao mesmo nível de blk_start , já que o balanceamento é feito pela recursividade de elem_list . Na implementação foi necessário escrever código para comparar os nomes das tag de blk_start e blk_end . Se forem diferentes é emitido um erro que indica o mau fecho da tag em bloco. De notar que se fosse importante restringir as tags a certos nomes, poderia alterar-se essa função para que não permitisse certas tags ou para que permitisse apenas certas tags, recorrendo a uma simples lookup table.
blk_start --> '<' ID attr_list '>' | '<' ID '>' blk_end: '<' '/' ID '>'
Estas regras correspondem respectivamente à abertura e ao fecho de uma tag em bloco.
tag --> '<' ID '/' '>'
| '<' ID attr_list '/' '>'
Uma tag do tipo simples, que não contem corpo, com ou sem atributos
schar --> '&' ID ';'
Um caracter especial.
elem_list --> elem | elem_list elem
Uma lista de elementos, recursividade à esquerda, não sofreu alteraçoes.
elem --> text | schar | tag | blk
Um elemento do corpo de uma tag em bloco, que pode ser texto, um caracter especial, uma tag simples ou uma outra tag em bloco.
attr_list --> attr | attr_list attr
Uma lista de atributos. Recursividade alterada para a esquerda.
attr --> ID '=' STR
Um atributo e o seu valor. De notar que ao encontrar o símbolo terminal '=', o analisador léxico entra num estado diferente que lhe permite retornar um token do tipo STR.
A construção da grove assenta numa estrutura de que pode ser descrita como uma árvore de numero de nodos(ramos) variável, em que os nodos do mesmo nível se encontram numa lista ligada. Cada nodo contém assim um apontador para o próximo elemento do mesmo nível e um identificador de tipo, que classifica a informação residente no nodo. Esta pode ser:
Texto
Um nodo deste tipo contém um apontador para uma string.
Caracter especial
Um nodo deste tipo contém um apontador para uma string, que é o identificador do caracter especial.
Tag
Um nodo deste tipo contém: um apontador para uma string, que é o nome da tag; um apontador para a lista de atributos; um apontador para um nodo que é o conteúdo da tag, e que pode ser nulo (se a tag não tiver conteúdo).
GROVE_NODE é uma estrutura que contém informação sobre um nodo.
GROVE_TYPE é uma enumeração que pode ser GRV_TXT (texto), GRV_CHR (caracter especial) ou GRV_TAG (uma tag com conteudo)
ATTR_DATA é uma estrutura que armazena a informação sobre um atributo
Para aceder aos campos de um um nodo, estão definidas as seguintes macros (com GROVE_NODE * g ):
G_TYPE( g ) um valor que identifica o tipo de nodo ( do tipo GROVE_TYPE). G_NEXT( g ) o próximo nodo do mesmo nível ( do tipo GROVE_NODE *) Válido apenas se ( G_TYPE( g ) == GRV_TXT ). G_TEXT( g ) o conteúdo textual do nodo ( do tipo char * ). Válido apenas se ( G_TYPE( g ) == GRV_CHR ). G_CHAR( g ) o texto do identificador do caracter especial ( do tipo char * ). Válido apenas se ( G_TYPE( g ) == GRV_TAG ). G_NAME( g ) o texto do identificador da grove ( do tipo char * ). G_ATTR( g ) o primeiro atributo ( do tipo ATTR_DATA * ). G_CONT( g ) o conteúdo ( do tipo GROVE_NODE *, pode ser NULL ).
De notar que nenhuma string é alocada nestas funções. Os apontadores de strings passados às funções são duplicados, mas não o seu conteúdo. Isto torna-se útil uma vez que o analisador léxico já alocou memória para as strings, e seria inútil duplicar esse processo.
Outra nota importante é o facto de o analisador sintáctico ter sido criado com a flag %pure_parser, o que implica que não acede a variáveis globais, e pode ser utilizado de forma reentrante. A função yyparse() toma como argumento um apontador do tipo void *. Neste caso, yyparse() recebe a referência a um apontador para um nodo. Depois da chamada a yyparse(), esse apontador terá o endereço do nodo mais topo de nível da grove lida.
GROVE_NODE * grove_new() , cria um novo nodo. Não é utilizada directamente, mas sim pelas 3 funções seguintes.
GROVE_NODE * grove_new_tag( char * name, ATTR_DATA * a, GROVE_NODE * c ) , cria um nodo para uma tag, com nome, atributos e conteúdo.
GROVE_NODE * grove_new_chr( char * id ) , cria um nodo para um caracter especial.
GROVE_NODE * grove_new_txt( char * txt ) , cria um nodo para um bloco de texto.
void grove_free( GROVE ** g ) , liberta memória para uma grove e todos os seus nodos.
void grove_print_esis( GROVE ** g ) , faz a travessia da grove, gerando output no formato ESIS. Muito simplesmente, percorre a lista de nodos no mesmo nível e imprime o seu conteúdo. Para nodos que contém tags, é invocada (recursivamente) para o nodo de conteúdo.
ATTR_DATA * attr_new( char * name, char * val ) , cria um novo atributo, dados o seu nome e o valor.
ATTR_DATA * attr_add( ATTR_DATA ** l, ATTR_DATA * a ) , acrescenta um atributo à lista passada por referência. Os atributos são ordenados por ordem alfabética.
void attr_free( ATTR_DATA ** a ) , liberta memória para toda uma lista de atributos.
Estão também definidas as seguintes macros, que facultam algumas opções:
STR_INDENT , uma string que é impressa para cada nível de indentaçao do formato ESIS. Inicialmente consiste em " " (3 espaços), mas poderia ser modificada, por exemplo, para "\t" para que cada indentaçao fosse feita com um tab, ou para "" para que nao haja indentaçao.
CAPITALIZE , nome da função que é chamada para "tratar" os nomes das tags. Pode ser: cap_all_upper , que converte todos os caracteres para maiusculas; cap_all_lower , que converte todos os caracteres para minusculas; cap_first_upper , que converte o primeiro caracter para maiúscula e os outros para minúsculas. Poderia ainda ser definida como ; , para que nenhuma função seja chamada.
Para exemplo, pensei em invocar o parser sobre este mesmo relatório, recursivamente... mas tomei uma decisão mais sensata, utilizando um pequeno ficheiro de exemplo.
Tomando assim em consideração, o seguinte texto:
<doc> <title font="Times New Roman" fontsize=5>Chapter 1</title> <body fontsize=3> <P/> This is the first chapter of the great big 'something'. It is <B>obviously</B> clear that I don't really know what I'm typing, but it's kind of <I>OK</I>. </body> <footer> <flash freq=3>Flashy footer, lá lá lá, page <pagen fontsize=2/></flash> </footer> </doc>
Obtem-se o seguinte resultado (com CAPITALIZE definido como cap_all_upper):
(DOC
(TITLE
A font=Times New Roman
A fontsize=5
-Chapter 1
) /TITLE
(BODY
A fontsize=3
(P
) /P
-This is the first chapter of the great big 'something'. It is
(B
-obviously
) /B
- clear that I don't really know what I'm typing, but it's kind of
(I
-OK
) /I
-.
) /BODY
(FOOTER
(FLASH
A freq=3
-Flashy footer, l&á l&á l&á, page
(PAGEN
A fontsize=2
) /PAGEN
) /FLASH
) /FOOTER
) /DOC
A minha anterior experiência com flex e bison tinha sido um pouco diferente, consistindo em desenvolver um interpretador para uma linguagem com a sintaxe de C. A comparação com este trabalho é inevitável, por utilizar as mesmas ferramentas. Por um lado, este trabalho é bem mais simples em termos de estruturas de dados, mas complica-se um pouco ao nível de conflitos na gramática.
Onde as diferenças se realçam é na facilidade de apresentação e recuperação de erros. Numa sintaxe como a de C, existem vários pontos de sincronização óbvios, como o ';' e os demarcadores de bloco '{' e '}'. Numa linguagem como esta, nem sempre é tão óbvia a forma óptima de recuperar a partir de um erro, e menos simples ainda é a manutenção da memória de forma a que toda a memória alocada seja libertada após um erro. Isto pode não ter muita importância num programa em que a única função é fazer o parsing, mas é de suprema importância num projecto mais complexo.
Qualquer pessoa que já tenha tentado escrever, por exemplo, um bom interpretador de expressões matemáticas em C, sem recorrer a ferramentas como Lex/Yacc ou Mox não pode deixar de sorrir quando aprende essas mesmas ferramentas. A simplicidade é tal que se torna de certa forma ridículo todo o esforço que em tempos se fez. É como tentar pregar pregos com uma esponja e de repente descobrir que existem martelos. Obviamente que a pergunta que se forma é algo semelhante a "mas porque é que nunca ninguém me tinha dito que existiam martelos?!?".