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.