Trabalho Pr'atico de Processamento de Linguagens I Universidade do Minho 30/5/99 Sara Alexandra Gomes Correia mc23214@ci.uminho.pt Alberto Manuel Brand~ao Sim~oes mc23801@ci.uminho.pt Este trabalho surge no ^ambito da disciplina de Processamento de Linguagens I, e consiste na implementa,c~ao de um sistema tradutor de um subconjunto da linguagem DocBook (PLI-Doc) para LaTeX e/ou HTML. Introdu,c~ao O objectivo deste trabalho 'e 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~ao impressa. A realiza,c~ao deste projecto foi proposta em tr^es fases, a primeira deveria consistir na an'alise l'exica e sint'atica do problema, a segunda na contru,c~ao de um grove e finalmente, a 'ultima consistiria na convers~ao para a linguagem final. Este relat'orio ser'a actualizado ao longo da realiza,c~ao das tr^es fases. Neste momento apenas documentamos a parte relativa `a an'alise l'exica e sint'actica. A vers~ao final deste relat'orio estar'a dividida em tr^es cap'itulos, um para cada fase do projecto, por sua vez cada cap'itulo encontra-se dividido em duas partes: "Discuss~ao do problema" "M'etodo de implementa,c~ao" Na segunda fase deste trabalho tinhamos como objectivo principal a constru,c~ao 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 'e o de permitir uma travessia que volte a gerar o documento reconhecido. An'alise l'exica e sint'actica Discuss~ao do problema Para a realiza,c~ao da an'alise l'exica e sint'atica foi necess'aria a constru,c~ao de um reconhecedor dos s'imbolos terminais e de um outro para reconhecer as frases v'alidas de uma linguagem , utilizando assim o flex e o bison (lex e yacc) para os respectivos reconhecedores. An'alise l'exica Um documento PLI-Doc 'e composto por texto do utilizador e um conjunto de comandos, a que chamaremos Tags, que lhe permitem formatar o texto. Uma Tag 'e composta por v'arios s'imbolos terminais : <, >, = e / identificador valores. Exemplo de uma tag com atributos. <REALCADO ESTILO="BOLD" > texto </REALCADO> Neste extracto < ...> e < ...> s~ao exempo de duas Tags. Decidimos que os identificadores que representam as Tags seriam tamb'em s'imbolos terminais, facilitando assim o controlo de erros e o balanceamento da Tags. Outro problema com que deparamos na an'alise l'exica foi o de como reconhecer o texto do utilizador. Por um lado, tinha-mos de arranjar uma express~ao regular que abranjesse o maior n'umero de caracteres. Por outro lado, esta express~ao regular n~ao podia fazer matching `as tags. Para resolvermos este problema opetamos por utilizar pr'e-condi,c~oes, ou seja, ter dois estados no analisador l'exico. Um para reconhecer as tags, que era iniciado sempre que se encontrasse o s'imbolo '< ' e um outro para reconhecer o texto do utilizador. Repare-se tamb'em que se o utilizador desejar colocar tags separadas por espa,cos ou "returns", esses caracteres seriam interpretados como caracteres. Foi por essa raz~ao que introduzimos uma nova express~ao regular ( \>[\t \n \r]*\<) que faz matching com o caracter '>' seguido de um ou mais espa,cos ou "returns", e por ultimo, ao caracter '<'. Assim, na ac,c~ao desta regra pudemos obrigar a ser reconhecido apenas '><' em e n~ao ' > texto <' (note-se que neste caso o texto era apena constitu'ido por espa,cos e "returns"). O mesmo aconteceria no fim do ficheiro. Se este fosse composto por '<PLI-DOC>' seguido de um ou mais espa,cos ou at'e linhas em branco, estas seriam interpretadas como texto. Assim, introduzimos mais uma express~ao 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~ao tivesse problemas a reconhecer tokens muito grandes. Note-se que bastam algumas p'aginas de texto para encher um array de dimens~ao fixa. Ent~ao, decidimos limitar um token de texto a 128 caracteres para que n~ao houvesse problemas na aloca,c~ao da mem'oria. No entanto, e porque n~ao 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,c~ao do analisador sint'actico, optamos por ir contando o n'umero de linhas do texto que est'a a ser processado. Desta forma, podemos indicar um erro com maior precis~ao. An'alise sint'actica Visto que no enunciado do problema era-nos dada a gram'atica, come,camos por a adoptar de forma a que o "bison" --- ferramenta que utilizamos para esta fase do trabalho --- n~ao assinalasse qualquer erro. A principal altera,c~ao consistiu na mudan,ca da recursividade da direita para a esquerda. Alteramos tamb'em 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~ao s'o eliminamos alguns conflictos na gram'atica, como tamb'em asseguramos autom'aticamente o balanceamento e ordem das tags. Note-se que no caso de n~ao termos colocado directamente as produ,c~oes, teria-mos de escrever c'odigo C que assegurasse esse balanceamento. Al'em destas, acresceu-nos uma outra vantagem: a legibilidade. Implementa,c~ao A implementa,c~ao deste parser foi efectuada usando as ferramentas flex e bison . Al'em delas, utilizamos tamb'em, como j'a referimos, denominada glib , que implementa todas as estruturas de dados elementares. Nesta primeira fase utilizamos uma 'unica das vantagens desta biblioteca: fun,c~oes de string. As string est~ao implementadas de forma a alocar um espa,co expon^encial, de forma a que, quanto maior o tamanho da string, menor o tempo de aloca,c~ao do espa,co. An'alise L'exica N~ao existem muitos pormenores nesta implementa,c~ao visto que os ficheiros flex s~ao, quase sempre, elementares. No entanto, existem agumas particularidades na forma como foi implementado o nosso analisador. Em primeiro lugar, conv'em salientar o uso de duas pr'e-condi,c~oes. O parser inicia o seu trabalho sem qualquer pr'e-condi,c~ao e vai reconhecendo texto. Durante esta fase vai guardando texto, a n~ao ser que encontre o caracter '<'. Neste caso, inicia uma pr'e-condi,c~ao (denominada Tag) a partir da qual vai identificar o nome da tag. Depois de ter esse nome, passa `a segunda pr'e-condi,c~ao onde reconhece, ou o fechar da tag, ou uma lista de atributos. Ap'os esta pr'e-condi,c~ao, volta de novo a ficar sem pr'e-condi,c~oes. As vantagens destas pr'e-condi,c~oes s~ao 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,c~oes de que algumas vers~oes do gnu flex suportam apenas 256 caracteres), decidimos ir acumulando o texto numa gstring (nome das string da bilbioteca GLib). Assim, a express~ao regular que faz matching ao texto n~ao o retorna. Em vez disso, acumula a string at'e que o parser encontre o caracter '<'. Quando o encontra, verifica que a string n~ao 'e nula e retorna o identificador de Texto para o Bison e volta a colocar o caracter '<' na stack. Al'em disto, coloca a string a nulo para que da pr'oxima vez entre no outro bra,co da estrutura condicional if. Quando na sec,c~ao anterior falavamos de uma express~ao regular que fazia matching ao caracter '>' seguido de espa,cos 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'oxima vez seja reconhecido. Al'em desta gest~ao da stack, criamos uma fun,c~ao que permite contar o n'umero de linhas de determinada string. Assim, podemos manter uma vari'avel com o n'umero da linha actual. An'alise Sint'actica A implementa,c~ao da an'alise sint'actica 'e quase toda ela elementar. O 'unico pormenor que devemos referir 'e o uso de gstring's para passar o texto reconhecido atrav'es das produ,c~oes. Evidentemente que n~ao 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'em ainda referir que a fun,c~ao de tratamento de erro foi alterada de forma a que indicasse o n'umero da linha onde o erro sucedeu. Constru,c~ao de um grove An'alise do Problema A estrutura de dados que escolhemos para o grove , foi uma mistura de 'arvore bin'aria-lista ligada. Assim consideramos cada tag como sendo um elemento, em que cada elemento 'e constituido por quatro campos: Tipo de Tag (PLI-DOC, ABERTURA, CORPO, etc.) Atributos da Tag Apontador para o conte'udo da Tag Apontador para a pr'oxima tag, que est'a no mesmo n'ivel da actual. Ent~ao um documento PLI-Doc 'e representado em mem'oria da forma como o seguinte esquema ilustra. Note-se que as setas verticais s~ao apontadores para o cont'udo da Tag, enquanto que as setas horizontais s~ao apontadores para nodos irm~aos do que est'a `a esquerda da seta. No caso de uma tag texto, a seta vertical aponta para um buffer de dados em mem'oria. Esquema da estrurura de dados Assim sendo, 'e-nos possivel realizar uma travessia de forma a manter a estrutura do documento. Basta para isso a cria,c~ao de uma fun,c~ao recursiva que "mergulhe" no conte'udo deste nodo e s'o passe para os nodos do lado quando j'a realizou o "mergulho" completo. Implementa,c~ao Criamos ent~ao algumas fun,c~oes de forma a encapsular o mais possivel este "type Casting" de forma a ser mais dif'icil cometer asneiras. As fun,c~oes b'asicas de aloca,c~ao e libertac,c~ao da mem'oria, foram feitas de forma a alocar e preencher os campos das estruturas o mais rapidamente possivel. Com este objectivo, criamos as fun,c~oes: Elem* Elem_new(int tipo,GHashTable *hash) Elem* Elem_string_new(GString *str) void Elem_free(Elem *el) Aprimeira fun,c~ao aloca espa,co para a estrutura e coloca-lhe um tipo e um hashtable. A segunda, definida `a custa da primeira, aloca espa,co, coloca a hashtable e o apontador next a nulo, coloca o tipo texto e faz o "type Casting" da GString para Elem *. Por 'ultimo, a fun,c~ao Elem-free trata de libertar a mem'oria de determinado elemento, a sua hashtable e pr'oximo/conte'udo elementos. Falta-nos no entanto, uma forma fac'il de colocar os apontadores dos elementos, para outros elementos. Para este fim, criamos duas fun,c~oes: Elem* Set_next(a, b) Elem* Set_content(a, b) A primeira relaciona o elemento "a" com o elemento "b", atrav'es do apontador next, ou seja, "a" passa a apontar para "b", pelo apontador next . Por sua vez, a segunda fun,c~ao 'e an'aloga, mas em rela,c~ao ao apontador content. Ambas as fun,c~oes devolvem o apontador de "a" depois de alterado. Passamos a explicar a integra,c~ao destas fun,c~oes com o Bison . Em cada regra da gram'atica, excepto aquelas que fazem a itera,c~ao de listas, criamos um nodo, colocando-lhe os atributos e o tipo de tag. Posteriormente, usando a fun,c~ao Set_content colocamos no nodo o apontador para o seu cont'udo. No caso de listas, ou de tags que se seguem como irm~as, usamos a fun,c~ao Set_next. Ou seja, o funcionamento 'e identico ao que foi usado com as gstrings na primiera fase do trabalho! Quanto `a travessia, conv'em apenas referir que criamos uma fun,c~ao, 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~ao Na primeira fase do trabalho pudemos concluir que existem algumas ferramentas (assim como o flex ou o bison ) que nos facilitam bastante a cria,c~ao de parsers. No entanto, estas ferramentas --- nomeadamente o bison --- mesmo estando bastante optimizadas e bastante autom'aticas ainda t^em problemas que n~ao conseguem resolver. Exemplos destes problemas s~ao os usuais reduce -- reduce conflicts e reduce -- shift conflicts. Foi-nos tamb'em possivel verificar o duro trabalho que uma ferramenta como o bison executa para chegar a um aut'omato possivel de ser implementado e escrever o c'odigo C necess'ario para o implementar. Nesta segunda fase, deparamos com algo surpreendente: poucas linhas de c'odigo permitiram armazenar toda uma estrutura deveras complicada. Julgamos que a facilidade com que isto decorreu se deveu n~ao s'o `a modulaziza,c~ao de fun,c~oes que trabalham com o grove , mas tamb'em `a implementa,c~ao de pequenas fun,c~oes que mesmorealizando tarefas muito pequenas, permitem uma grande flexibilidade. Pudemos ent~ao concluir, que a implementa,c~ao de um parser 'e bastante simplificada com a utiliza,c~ao de ferramentas como o Bison e o flex, e que n~ao 'e t~ao dificil quanto isso a utilzia,c~ao de uma estrutura de dados um pouco fora do comum, desde que se implementem fun,c~oes 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. Em primeiro lugar temos que agradecer aos professor José Carlos Ramalho por nos ter tirado algumas dúvidas sobre como implementar este conversor. Temos também que agradecer ao professor José João Almeida por nos ter explicado como retornar valores de acções semânticas no meio de produções. Ainda, devemos agradecer à equipa responsável pela bilbioteca glib por a terem criado. Caso contrário, teriamos que implementar muitas estruturas de dados. glibDocumentação on-line da biblioteca GLIB, Open Source Software Foundation yacclexTony Mason and Doug Brown, Lex and Yacc, O'reilly and Assocites, Inc.