Índice
Introdução
O objectivo deste trabalho é o de implementar uma ferramenta que permita converter documentos em PLI-Doc para LaTeX e HTML. Assim torna-se possivel publicar um documento PLI-Doc na internet e produzir uma versão impressa.
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 na contrução de um grove e finalmente, a última consistiria na conversão para a linguagem final.
Este relatório será actualizado ao longo da realização das três fases. Neste momento apenas documentamos a parte relativa à análise léxica e sintáctica. A versão final deste relatório estará dividida em três capítulos, um para cada fase do projecto, por sua vez cada capítulo encontra-se dividido em duas partes:
-
"Discussão do problema"
-
"Método de implementação"
Na segunda 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 PLI-Doc . O objectivo desta estrutura d dados é o de permitir uma travessia que volte a gerar o documento reconhecido.
Análise léxica e sintáctica
Discussão do problema
Para a realização da análise léxica e sintática foi necessária a construção de um reconhecedor dos símbolos terminais e de um outro para reconhecer as frases válidas de uma linguagem , utilizando assim o flex e o bison (lex e yacc) para os respectivos reconhecedores.
Análise léxica
Um documento PLI-Doc é composto por texto do utilizador e um conjunto de comandos, a que chamaremos Tags, que lhe permitem formatar o texto. Uma Tag é composta por vários símbolos terminais : <, >, = e / identificador valores.
Exemplo:Exemplo de uma tag com atributos.
<REALCADO ESTILO="BOLD" > texto </REALCADO>
Neste extracto < ...> e < ...> são exempo de duas Tags. Decidimos que os identificadores que representam as Tags seriam também símbolos terminais, facilitando assim o controlo de erros e o balanceamento da Tags.
Outro problema com que deparamos na análise léxica foi o de como reconhecer o texto do utilizador. Por um lado, tinha-mos de arranjar uma expressão regular que abranjesse o maior número de caracteres. Por outro lado, esta expressão regular não podia fazer matching às tags. Para resolvermos este problema opetamos por utilizar pré-condições, ou seja, ter dois estados no analisador léxico. Um para reconhecer as tags, que era iniciado sempre que se encontrasse o símbolo '< ' e um outro para reconhecer o texto do utilizador.
Repare-se também que se o utilizador desejar colocar tags separadas por espaços ou "returns", esses caracteres seriam interpretados como caracteres. Foi por essa razão que introduzimos uma nova expressão regular ( \>[\t \n \r]*\<) que faz matching com o caracter '>' seguido de um ou mais espaços ou "returns", e por ultimo, ao caracter '<'. Assim, na acção desta regra pudemos obrigar a ser reconhecido apenas '><' em e não ' > texto <' (note-se que neste caso o texto era apena constituído por espaços e "returns"). O mesmo aconteceria no fim do ficheiro. Se este fosse composto por '<PLI-DOC>' seguido de um ou mais espaços ou até linhas em branco, estas seriam interpretadas como texto. Assim, introduzimos mais uma expressão regular: \>[ \t\n\r]*\$
Visto que um documento PLI-DOC pode variar bastante de tamanho e chegar a alguns megabytes, tivemos que assegurar que o flex não tivesse problemas a reconhecer tokens muito grandes. Note-se que bastam algumas páginas de texto para encher um array de dimensão fixa. Então, decidimos limitar um token de texto a 128 caracteres para que não houvesse problemas na alocação da memória. No entanto, e porque não podemos limitar desta forma o comprimento do texto do utilizador, colocamos uma string da biblioteca glib , (existente em http://www.gtk.org ) com o texto. Note-se que testamos a velociadade de alargamento desta string, tendo chegado aos 5 megabytes.
Mais uma vez, pensando nos problemas da implementação do analisador sintáctico, optamos por ir contando o número de linhas do texto que está a ser processado. Desta forma, podemos indicar um erro com maior precisão.
Análise sintáctica
Visto que no enunciado do problema era-nos dada a gramática, começamos por a adoptar de forma a que o "bison" --- ferramenta que utilizamos para esta fase do trabalho --- não assinalasse qualquer erro. A principal alteração consistiu na mudança da recursividade da direita para a esquerda.
Alteramos também a forma como os identificadores das tags eram reconhecidos. Em vez de termos uma regra a derivar em todas as Tags ID, colocamos cada um desses identificadores na regra respectiva. Assim, não só eliminamos alguns conflictos na gramática, como também asseguramos automáticamente o balanceamento e ordem das tags. Note-se que no caso de não termos colocado directamente as produções, teria-mos de escrever código C que assegurasse esse balanceamento. Além destas, acresceu-nos uma outra vantagem: a legibilidade.
Implementação
A implementação deste parser foi efectuada usando as ferramentas flex e bison . Além delas, utilizamos também, como já referimos, denominada glib , que implementa todas as estruturas de dados elementares. Nesta primeira fase utilizamos uma única das vantagens desta biblioteca: funções de string. As string estão implementadas de forma a alocar um espaço exponêncial, de forma a que, quanto maior o tamanho da string, menor o tempo de alocação do espaço.
Análise Léxica
Não existem muitos pormenores nesta implementação visto que os ficheiros flex são, quase sempre, elementares. No entanto, existem agumas particularidades na forma como foi implementado o nosso analisador.
Em primeiro lugar, convém salientar o uso de duas pré-condições. O parser inicia o seu trabalho sem qualquer pré-condição e vai reconhecendo texto. Durante esta fase vai guardando texto, a não ser que encontre o caracter '<'. Neste caso, inicia uma pré-condição (denominada Tag) a partir da qual vai identificar o nome da tag. Depois de ter esse nome, passa à segunda pré-condição onde reconhece, ou o fechar da tag, ou uma lista de atributos. Após esta pré-condição, volta de novo a ficar sem pré-condições. As vantagens destas pré-condições são que facilitam o reconhecimento do texto e permitem que existam atributos cujo seu identificador seja igual ao nome de uma qualquer tag.
Visto que o flex tem problemas em gerir grandes strings (encontramos algumas informações de que algumas versões do gnu flex suportam apenas 256 caracteres), decidimos ir acumulando o texto numa gstring (nome das string da bilbioteca GLib ). Assim, a expressão regular que faz matching ao texto não o retorna. Em vez disso, acumula a string até que o parser encontre o caracter '<'. Quando o encontra, verifica que a string não é nula e retorna o identificador de Texto para o Bison e volta a colocar o caracter '<' na stack. Além disto, coloca a string a nulo para que da próxima vez entre no outro braço da estrutura condicional if .
Quando na secção anterior falavamos de uma expressão regular que fazia matching ao caracter '>' seguido de espaços ou linhas em branco, e '<', nao referimos que esta regra retorna o caracter '>' e volta a colocar o caracter '<' na stack, para que da próxima vez seja reconhecido.
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.
Análise Sintáctica
A implementação da análise sintáctica é quase toda ela elementar. O único pormenor que devemos referir é o uso de gstring's para passar o texto reconhecido através das produções. Evidentemente que não vai ser este o meio de armazenar os dados relativos a um do cumento PLI-DOC, mas permite que se possa colocar algum output nesta primeira fase.
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.
Construção de um grove
Análise do Problema
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:
-
Tipo de Tag (PLI-DOC, ABERTURA, CORPO, etc.)
-
Atributos da Tag
-
Apontador para o conteúdo da Tag
-
Apontador para a próxima tag, que está no mesmo nível da actual.
Então um documento PLI-Doc é representado em memória da forma como o seguinte esquema ilustra. Note-se que as setas verticais são apontadores para o contúdo da Tag, enquanto que as setas horizontais são apontadores para nodos irmãos do que está à esquerda da seta. No caso de uma tag texto, a seta vertical aponta para um buffer de dados em memória.
Figura:Esquema da estrurura de dados
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 recursiva que "mergulhe" no conteúdo deste nodo e só passe para os nodos do lado quando já realizou o "mergulho" completo.
Implementação
Criamos então algumas funções de forma a encapsular o mais possivel este "type Casting" de forma a ser mais difícil cometer asneiras. As funções básicas de alocação e libertacção da memória, foram feitas de forma a alocar e preencher os campos das estruturas o mais rapidamente possivel. Com este objectivo, criamos as funções:
-
Elem* Elem_new(int tipo,GHashTable *hash)
-
Elem* Elem_string_new(GString *str)
-
void Elem_free(Elem *el)
Aprimeira função aloca espaço para a estrutura e coloca-lhe um tipo e um hashtable. A segunda, definida à custa da primeira, aloca espaço, coloca a hashtable e o apontador next a nulo, coloca o tipo texto e faz o "type Casting" da GString para Elem * . Por último, a função Elem-free trata de libertar a memória de determinado elemento, a sua hashtable e próximo/conteúdo elementos.
Falta-nos no entanto, uma forma facíl de colocar os apontadores dos elementos, para outros elementos. Para este fim, criamos duas funções:
-
Elem* Set_next(a, b)
-
Elem* Set_content(a, b)
A primeira relaciona o elemento "a" com o elemento "b", através do apontador next , ou seja, "a" passa a apontar para "b", pelo apontador next . Por sua vez, a segunda função é análoga, mas em relação ao apontador content . Ambas as funções devolvem o apontador de "a" depois de alterado.
Passamos a explicar a integração destas funções com o Bison . Em cada regra da gramática, excepto aquelas que fazem a iteração de listas, criamos um nodo, colocando-lhe os atributos e o tipo de tag. Posteriormente, usando a função Set_content colocamos no nodo o apontador para o seu contúdo. No caso de listas, ou de tags que se seguem como irmãs, usamos a função Set_next .
Ou seja, o funcionamento é identico ao que foi usado com as gstring s na primiera fase do trabalho!
Quanto à travessia, convém apenas referir que criamos uma função, portadora de uma enorme estrutura case, que nos converte um inteiro para o respectivo texto identificativo da tag.
Geração de Código
Análise do Problema
Depois de apresentar-mos algumas alterações que fizemos ao código da primeira e segunda parte, vamos apresentar ideia do funcionamento das funções de geração de código. Ou seja, quer a geração de código para HTML quer para LaTeX .
As alterações efectuadas no código já existente foram:
-
Alteramos o grove de forma a podermos armazenar um valor inteiro que representa a linha em que essa tag está, ou seja, a linha onde apareceu a tag a abrir. Desta forma, foi-nos possível dar algumas mensagens de erro mais completas, o que é sempre do agrado do utilizador. Para isso, tivemos que alterar a gramática. Ou melhor, não teriamos de alterar a gramática mas colocar acções semânticas no meio das produções. Assim fizemos, ou seja, após o reconhecimento da tag a abrir, criamos automáticamente um nodo do grove para aquela tag, naquela linha. Se armazenasse-mos o número da linha no fim de reconhecer a produção toda ficaria-com com a linha da tag de fecho e não da tag de abertura.
Ao fazermos isto, tivemos um problema de shift/reduce na produção referente ao autor. O que fizemos foi criar uma nova produção autor2 que faz o reconhecimento do texto que segue a abertura de tag AUTOR . Ou seja, a produção que já existia ficou a reconhecer apenas a tag de abertura.
-
Foram corrigios alguns bugs na ligação de nodos. Existia alguns problemas, como por exemplo, nos autores. Estavamos apenas a guardar o primeiro autor e a descartar todos os outros. O problema era simples, porque estavamos a colocar o resumo como next do primeiro autor, e o que deviamos fazer era colocar como next do último autor.
A ideia base assenta, como na geração de código ESIS , na travessia do grove . Sendo possível criar uma função suficientemente genérica para gerar HTML , LaTeX ou Esis , optamos por criar um módulo (na verdade um ficheiro .c ) para cada um dos casos. Assim, não só é possível uma maior facilidade na leitura de código, permitiu que se ganhasse alguma eficiencia. Para que a função fosse genérica teriamos de ter uma flag que nos indicasse o tipo de documento a gerar, o que implicaria uma estrutura condicional sempre que quisessemos gerar o código respectivo a determinada tag.
Visto que a estrutura de um documento PLI-Doc é completamente diferente da estrutura de um documento LaTeX e/ou HTML , não pudemos fazer uma conversão directa, ou seja, não pudemos fazer substituição tag por tag. Assim sendo, existem certos comandos LaTeX e HTML que não estão a ser gerados na tag mais apropriada, mas no entanto, estão no sitio que permite criar um ficheiro válido nas outras linguagens.
Assim sendo, durante a travessia do grove, vamos gerando comandos da linguagem a gerar para o standard output para que possa ser redireccionado para um ficheiro e até para que, com algumas modificações se possa a fazer conversões para HTML on-the-fly . Por convenção, erros de semântica, não abortam a geração de código, visto que a maior parte deles são inofensivos. Ou seja, os erros gerados são enviados para o Standard Error para que ao redireccionar o texto gerado, este não apanhe as mensagens de erro.
Para verificar os erros nos identificadores e referencias de tags para tags, utilizamos uma estrutura de dados auxiliar, uma tabela de hashing . Esta tabela tem como chave o nome do identificador, e como dado, um número que representa uma linha. Quando é encontrada uma referência a um identificador (a tag REF ), é colocado o número da linha em que foi encontrada a tag na tabela, com valor negativo. Caso esse identificador já tenha sido definido, não faz absolutamente nada. Por outro lado, quando é encontrado um atributo ID numa tag, é colocado o nome da tag e a respectiva linha na tabela. No entanto, no caso de esse atributo já tiver sido definido, é gerado um erro, e no caso de esse identificador já tiver sido referenciado mas ainda não declarado (tem um número negativo), passa a ter a linha actual. No fim de processar todo o documento, são percorridos todos os elementos da tabela para que, caso ainda existam valores negativos, seja impressa uma mensagem de erro a avisar de que o identificador referenciado não foi declarado. Sempre que possivel, estas mensagens de erro apresentam o número da linha em que foi declarado anteriormente, ou foi referenciado sem declarar. No entanto, por vezes, o número de linha apresenta uma imprecisão de uma ou duas unidades.
Geração de HTML
A geração de HTML foi pensada de forma a não gerar um documento super formatado, mas com um formato básico. Assim, não só permite que o utilizador o edite e perceba perfeitamente o código gerado, como também que as cores e tamanhos de letras definidos pelo utilizador no seu browser sejam usados no documento. Assim sendo, não é de estranhar que não tenhamos usado comandos como o CENTER .
Por outro lado, a geração de HTML é mais lenta, e ineficiente do que a sua dual para LaTeX . A verdade é que enquanto que o LaTeX gera automáticamente os índices, nós tivemos que gerar os links do índice em HTML para o respectivo texto. Assim sendo, e para não gastar mais memória com estruturas de dados, optamos por dar trabalho ao processador. Para a geração do índice criamos uma outra função de travessia do grove , que gera uma sequência de titulos de capítulos, secções, subsecções e assim sucessivamente, identados e com links para os respectivos capítulos. Para dar nome aos links, optamos por numeração sequencial, ou seja, não utilizamos nomes como cap1.0.2 mas sim, _indicen em que n é o número do link que está a ser gerado. Note-se que a travessia para geração do índice é apenas despoletada após a geração de todo o código da ABERTURA , e não chegamos a fazer a travessia ao FECHO . Ou seja, apenas atravessamos os filhos da tag CORPO .
Não pretendemos explicar o estilo de tradução feita, do documento original para o final. Pretendemos apenas focar alguns pontos importantes. Um exemplo desses pontos em que foi necessário dar a volta ao tradutor foi no caso da tag CORPO . Note-se que numa tradução directa, seriamos fortemente levados a traduzir para BODY . No entanto, no documento PLI-Doc os autores, data e resumo aparecem na tag ABERTURA , enquanto que em HTML não convém que seja gerado na tag HEAD , visto que assim não apareceriam visivelmente no documento final. Assim sendo, tratamos de abrir a tag BODY antes de acabar a secção ABERTURA . Muitos outros casos parecidos com este foram encontrados, no entanto, uma explicação de todos eles seria grande e muito aborrecida para o leitor.
Outro problema com que deparamos foi a traducção de acentos. Mais uma vez, optamos por uma estrutura condicional para resolver este problema. Na verdade, o que fazemos, é processar caracter a caracter. Assim sendo, para cada caracter vemos se está no formato pré-fixo, ou se está introduzido com 8-bit's. Aproveitamos a mesma função para traduzir caracteres especiais para a respectiva codificação em HTML .
O resto do código é análogo ao da geração do formato Esis , pelo que não tem interesse uma descrição detalhada. Na verdade, o segredo da geração do HTML está na função que para cada uma das tags, verifica em que tag resultado deve ser transformada.
Geração de LaTeX
Fazendo um pararelismo com a secção anterior, devemos começar por dizer que a geração do LaTeX é mais eficiente a nível do nosso programa, uma vez que ele próprio trata da construcção do índice do documento. No entanto, mesmo sendo a nossa execussão mais rápida, o utilizador irá perder tempo, de novo, ao compilar o documento em LaTeX .
Então, a função de travessia suplementar que gerava o índice foi cortada. No entanto, todas as outras funções foram preservadas. Em particular uma das funções é exactamente a da versão HTML , ou seja, a que faz o tratamento de erros no caso de identificadores referenciados não definidos. A função de tratamento de acentos tem, também, uma estrutura muito similar. No entanto, é bastante maior visto que tem de tratar muitos mais casos especiais.
Assim como na verão HTML , também tivemos que fazer algumas alterações na ordem pela qual as tags são geradas. Por exemplo, enquanto que a tag RESUMO pertence à ABERTURA , em LaTeX , o \abstract tem de ser colocado dentro do corpo do documento.
Outro malabarismo que fizemos na travessia do grove, foi na geração de capítulos, secções, subsecções e assim sucessivamente. Ou seja, qualquer um destes comandos em LaTeX tem um formato similar com \chapter{title} . No nosso caso, para que o título aparecesse correctamente posicionado tivemos que fazer uma referência directa ao título para o imprimir, e depois de imprimir a chaveta a fechar, saltamos a tag TITULO .
Um outro cuidado que tivemos de ter foi o de contar o número de nested secções (secções aninhadas) para poder escrever, sucessivamente, descendo no nível hierarquico, section , subsection , subsubsection , e assim sucessivamente.
Esta secção do relatório é pequena, não pela facilidade com que se escreveu o código, nem pelo número de linhas necessário para pôr a funcionar, mas sim porque é dual da versão HTML e tem o mesmo funcionamento da travessia para geração de código Esis .
Conclusão
Na primeira fase do trabalho pudemos concluir que existem algumas ferramentas (assim como o flex ou o bison ) que nos facilitam bastante a criação de parsers. No entanto, estas ferramentas --- nomeadamente o bison --- mesmo estando bastante optimizadas e bastante automáticas ainda têm problemas que não conseguem resolver. Exemplos destes problemas são os usuais reduce -- reduce conflicts e reduce -- shift conflicts .
Foi-nos também possivel verificar o duro trabalho que uma ferramenta como o bison executa para chegar a um autómato possivel de ser implementado e escrever o código C necessário para o implementar.
Nesta segunda fase, deparamos com algo surpreendente: poucas linhas de código permitiram armazenar toda uma estrutura deveras complicada. Julgamos que a facilidade com que isto decorreu se deveu não só à modulazização de funções que trabalham com o grove , mas também à implementação de pequenas funções que mesmorealizando tarefas muito pequenas, permitem uma grande flexibilidade.
Pudemos então concluir, que a implementação de um parser é bastante simplificada com a utilização de ferramentas como o Bison e o flex , e que não é tão dificil quanto isso a utilziação de uma estrutura de dados um pouco fora do comum, desde que se implementem funções que tornem transparente este manuseamento.
Como conclusão da terceira fase, e conclusão de todo este trabalho, verificamos que nem sempre é linear fazer a tradução entre dois tipos de documentos. Ou seja, por vezes somos obrigados a dar a volta ao documento para conseguir gerar o que achamos ser um documento idêntico ao original.
Mesmo dando muito trabalho, acho que foi bastante sensato dar um trabalho a sério. Não só permitiu verificar as nossas capacidades num projecto mais ou menos complicado, como também ganhar gosto no que estamos a fazer. As vezes deparamos com problemas, como em tudo, mas com um bocado de paciência e raciocinio chega-se sempre a uma solução, por mais deselegante que possa ser.