2. Enunciado 1 - Report2007: vamos escrever relatórios
A escrita de relatórios técnicos é muito importante no contexto em que te estás a
inserir.
Neste projecto, irás desenvolver um compilador que aceitará relatórios escritos
numa determinada linguagem e gerará a respectiva versão HTML (como extra poderá
gerar também uma versão em LaTeX).
A especificação da gramática da linguagem para a escrita de relatórios é dada
abaixo (com alguns pormenores em branco). Deverás analisá-la, completá-la e
implementá-la.
Na análise da gramática tem em conta as seguintes considerações:
- Símbolos capitalizados pertencem à família dos não-terminais: Report, Abstract, TRowList, ...;
- Símbolos em maiúsculas pertencem à família dos terminais constantes (palavras reservadas ou símbolos carácter): BTITLE, EGRAPH,
...;
- Símbolos em minúsculas pertencem à família dos terminais variáveis: texto, path, ...;
- A definição de cada símbolo terminal ficará a seu cargo, a gramática apenas indica onde eles deverão aparecer (seja imaginativo,
proponha alterações, ...);
- Os não terminais marcados com "?" são opcionais e deverão ser tratados à
semelhança de "SubTitle".
- Como é suposto utilizarem o
yacc
para implementarem o compilador a gramática foi escrita com recursividade
à esquerda, alterem-na se optarem por uma metodologia de
parsing Top-Down
.
Um Relatório é composto por 3 partes: uma parte inicial, um corpo e uma parte final.
Report --> BREPORT FrontMatter Body BackMatter EREPORT
A parte inicial é constituída por um título, um subtítulo opcional, uma lista de autores, uma data, a indicação de uma instituição
opcional, uma lista de palavras-chave opcional, um resumo, uma secção opcional de agradecimentos, um índice opcional, um
índice de
figuras opcional e m índice de tabelas opcional.
FrontMatter --> BFM Title SubTitle? Authors Date Institution? Keywords?
Abstract Aknowledgements? Toc? Lof? Lot? EFM
Title --> BTITLE texto ETITLE
SubTitle --> BSUBTITLE texto ESUBTITLE
| &
Authors --> Authors Author
| Author
Author --> BAUTHOR Name Nident? Email? Url? Affilliation? EAUTHOR
Name --> BNAME texto ENAME
O resumo e a secção de agradecimentos são constituídos por uma lista de parágrafos.
Abstract --> BABS ParaList EABS
Aknowledgements --> BAKN ParaList EAKN
Toc --> TOC | &
Lof --> LOF | &
Lot --> LOT | &
O Corpo do Relatório é constituído por uma lista de capítulos e um capítulo, por sua vez, é constituído por um título e uma
lista de elementos..
Body --> BBODY ChapterList EBODY
ChapterList --> ChapterList Chapter
| Chapter
Chapter --> BCHAP Title ElemList ECHAP
Uma Secção tem um modelo semelhante ao do capítulo só que em vez do subelemento
Section
tem o subelemento
SubSection
(o mesmo acontecerá com a
SubSection
e a
SubSubSection
).
Section --> BSEC Title ElemListSec ESEC
ElemList --> ElemList Elem
| Elem
Um elemento pode ser um parágrafo, um elemento
flutuante
(tabela ou figura), uma lista (descritiva, de itens ou numerada), um bloco
de código, uma secção, um sumário.
Elem --> Paragraph
| Float
| List
| CodeBlock
| Section
| Summary
O parágrafo tem um conteúdo composto por texto onde podem aparecer livremente alguns elementos: referências, pedaços de texto
com diferentes características
de formatação (bold, itálico, ...), acrónimos, ...
Paragraph --> BPARA ParaContent EPARA
ParaContent --> ParaContent texto
| ParaContent FreeElement
| &
FreeElement --> Footnote
| Ref
| Xref
| Citref
| Iterm
| Bold
| Italic
| Underline
| InlineCode
| Acronym
Ref --> BREF target EREF
Xref --> BXREF target EXREF
Citref --> BCIT target ECIT
Iterm --> BITERM texto EITERM
Bold --> BBOLD BContent EBOLD
BContent --> BContent texto
| BContent Italic
| BContent Underline
| &
Italic --> BITALIC IContent EITALIC
IContent --> IContent texto
| IContent Bold
| IContent Underline
| &
Underline --> BUNDERLINE UContent EUNDERLINE
UContent --> UContent texto
| UContent Bold
| UContent Italic
| &
Float --> Figure | Table
Figure --> BFIG Graphic Caption EFIG
Graphic --> BGRAPH path format? EGRAPH
Caption --> BCAPTION texto ECAPTION
Table --> BTABLE Caption TRowList
TRowList --> TRowList TRow
| TRow
3. Enunciado 2 - XML WorkBench
Neste projecto, pretende-se desenvolver uma plataforma para manipulação de documentos XML.
Esta plataforma terá dois níveis: num primeiro nível é preciso reconhecer um documento XML e construir uma sua
representação em memória; num segundo nível pretende-se generalizar permitindo o carregamento de vários documentos para
memória
sobre os quais se poderão fazer várias operações: selecção de partes, geração de novos documentos a partir dos que estão
carregados, estatísticas, ...
Podemos dividir este enunciado em 3 partes que se descrevem nas secções seguintes.
3.1. Reconhecedor de Documentos Estruturados
Como já foi referido, nesta fase o alunos deverá desenvolver um parser que valide um documento XML e crie em memória uma
representação do mesmo.
A título apenas de exemplo apresenta-se uma possível gramática para um documento XML:
Documento --> ElemList '$'
ElemList --> ElemList Elem
| Elem
Elem --> char
| '&' id ';'
| '<' id AttrList '>' ElemList '<' '/' id '>'
| '<' id AttrList '/' '>'
AttrList --> Attr AttrList
| &
Attr --> id '=' valor
No reconhecimento do documento, o parser desenvolvido deverá verificar os seguintes invariantes:
- todas as anotações correspondentes a elementos com conteúdo são abertas e fechadas correctamente (não há marcas
cruzadas);
- o documento tem que obrigatoriamente começar com a abertura dum elemento (que irá englobar todo o documento).
3.2. Interpretador de Comandos
O parser desenvolvido no ponto anterior será uma peça de algo bem maior: o tal
"XML Workbench"
.
Pretende-se agora criar um ambiente de trabalho que aceite os seguintes comandos:
- LOAD "path para o documento" id
- Este comando irá usar o parser desenvolvido no ponto anterior para reconhecer e carregar um documento XML. No fim,
deverá ainda criar uma entrada numa estrutura de dados interna em que o identificador
id
fica associado ao documento reconhecido;
- LIST
- Mostra no écran a lista de documentos carregados e respectivos ids;
- SHOW id
- Mostra no écran o documento associado ao identificador id em formato ESIS;
- EXIT
- Sai do programa;
- HELP
- Imprime no écran um texto parecido com esta lista de comandos.
Pode usar a imaginação à vontade para acrescentar comandos a esta lista.
Considere ainda a seguinte gramática proposta para este interpretador (pode alterá-la à vontade):
Interp --> ComList
ComList --> Comando | ComList Comando
Comando --> LOAD fich-id id
| SHOW id
| LIST
| EXIT
| HELP
3.3. Document Query Language
Neste momento, todos grupos de trabalho deverã estar munidos dum interpretador de comandos que permite carregar documentos,
visualizá-los, fornecendo assim um primeiro conjunto de facilidades básicas num sistema documental.
Nesta fase, vamos adicionar um novo comando à lista dos já existentes:
QLE: [selector de documentos] [query-exp]
[selector de documentos] --> * "todos os docs carregados"
| id "apenas o doc com ident=id"
| id1,id2,...,idn
[query-exp] --> "definida mais à frente"
O resto do enunciado irá descrever através da apresentação de exemplos as várias facetas das expressões de query que se
pretendem suportar.
3.3.1. Interrogando os Documentos
A operação de seleccionar os elementos com os quais se quer fazer alguma coisa, ou aos quais se quer aplicar algum
processamento, tem sido, desde há algum tempo, uma preocupação das pessoas que trabalham nesta área. Começou por surgir
na transformação e na formatação: era preciso seleccionar os elementos que se queriam transformar, ou que se queriam
mapear num ou mais objectos com características gráficas (formatação). Este esforço é visível no DSSSL
[Cla96]; o
primeiro elemento das suas regras é uma expressão de "query" que selecciona os elementos aos quais será aplicado o
processamento especificado. Por último, esta necessidade surgiu ligada às linguagens de "query" para documentos
estruturados, como as que foram propostas na conferência dedicada a esse tópico
[RLS98][DeR98]
[Tom98][Wid98][CCDFPT98].
Assim se chegou, rapidamente, à conclusão de que a operação de selecção necessária para a transformação ou formatação era
muito
semelhante à necessária nos sistemas de bases de dados documentais para a realização de "queries".
Depois de algum tempo de discussão (moderada pelo W3C - World Wide Web Consortium), começa a emergir algum consenso na utilização
do
XSLT
[XSLT], uma sublinguagem de padrões presente no XSL
[XSL] - a proposta de normalização para a
especificação de estilos a associar a documentos XML. O XSLT tornou-se um standard e foi já alvo de um estudo formal
por parte de Wadler
[Wad99], apresentado na conferência mundial da área ("Markup Technologies 99"), e onde ele define a linguagem usando
semântica denotacional (formalismo de cariz funcional utilizado para especificar a sintaxe e a semântica de linguagens
-
[Paa95]).
Depois dum estudo de algumas destas linguagens (em particular todas as que já foram referidas), foi fácil constatar que o
XSLT é um denominador comum de
uma grande parte delas, aquelas que foram desenvolvidas a pensar em documentos estruturados, tratando-se portanto de
uma linguagem específica.
Houve, no entanto, uma linguagem que cativou a atenção do autor, pela sua simplicidade e recurso à teoria de conjuntos,
a linguagem proposta por
Tim Bray
[Bray98] na QL'98 - The Query Languages Workshop designada por Element Sets. Um estudo mais atento da linguagem e do seu
historial, revelou ser esta a especificação por detrás do conhecido motor de procura Pat comercializado pela OpenText
e utilizado na maior parte
dos primeiros portais da Internet.
Enquanto as linguagens do tipo XSLT assentam numa sintaxe concreta e específica, a Element Sets define uma notação abstracta
baseada em cinco operadores
da teoria de conjuntos: contido (within), contém (including), união (+), intersecção (^) e diferença (-). Bray argumenta
ser capaz de especificar uma
grande percentagem de queries que possam ser necessárias num sistema de arquivo documental à custa da combinação daqueles
cinco operadores.
Numa primeira análise e a título comparativo, apresentam-se a seguir dois exemplos, uma query simples e uma mais complicada
que irão ser especificadas
respectivamente recorrendo a XSLT e a Element Sets.
3.3.1.1. Query Simples
Pretende-se seleccionar todos os parágrafos (PARA) pertencentes à introdução (INTROD) que contenham uma ou mais notas de rodapé
(FOOTNOTE) ou
uma ou mais referências (REF) a outros elementos no documento.
Em Element Sets a query seria:
set1 = Set('PARA') within Set('INTROD')
set2 = set1 including Set('FOOTNOTE')
set3 = set1 including Set('REF')
set4 = (set2 + set3) - (set2 ^ set3)
Apesar de complexa, foi fácil especificar esta query. Bastou excluir (diferença de conjuntos) os elementos resultantes da
query anterior que
continham ambos os elementos (intersecção de conjuntos), REF e FOOTNOTE.
Temos agora, a especificação em XSLT:
INTROD/PARA[(FOOTNOTE and (not REF)) or (REF and (not FOOTNOTE))]
Do estudo comparativo realizado entre os dois tipos de linguagem, e do qual os dois exemplos acima fazem parte, podemos concluir
que, em termos da
operação de selecção, são mais ou menos equivalentes, não se tendo encontrado nenhuma situação que uma solucionasse
e a outra não. Vão diferir é no
método como fazem a selecção: o XSLT usa a árvore documental e toda a operação de selecção é feita em função dessa estrutura;
a Element Sets, por outro
lado, não usa a árvore documental, manipula o documento como um conjunto de elementos usando uma sintaxe mais universal.
Mas esta diferença existe
apenas perante o utilizador que usa a linguagem porque em termos de implementação não se pode fugir às travessias da
árvore documental.
Ao contrário do que o leitor poderia supor nesta altura, a escolha não recaiu sobre a Element Sets mas sim sobre uma linguagem
do tipo XSLT, a XQL -
XML Query Language
[RLS98]. Os motivos por detrás desta escolha são muito simples. Apesar dos paradigmas, em termos de selecção,
serem equivalentes, as linguagens do tipo XSLT vão além da selecção, permitem ter um segundo nível de selecção baseado
em restrições sobre o conteúdo.
3.3.2. A Linguagem para o Projecto
A linguagem XSLT fornece um método bastante simples para descrever a classe de nodos que se quer seleccionar. É declarativa
em lugar de procedimental.
Apenas é preciso especificar o tipo dos nodos a procurar usando um tipo de padrões simples baseado na notação de directorias
dum sistema de ficheiros
(a sua estrutura é equivalente à de uma árvore documental). Por exemplo, livro/autor, significa: seleccionar todos os
elementos do tipo autor contidos
em elementos livro.
A XQL é uma extensão do XSLT. Adiciona operadores para a especificação de filtros, operações lógicas sobre conteúdo, indexação
em conjuntos de
elementos, e restrições sobre o conteúdo dos elementos. Basicamente, é uma notação para a especificação de operações
de extracção de informação de
documentos estruturados.
Como já foi dito, vamos começar por descrever operadores relacionados com a selecção mas a linha divisória entre selecção
e restrição irá sendo
diluída ao longo do texto, confundindo-se até, para os casos em que a integração das duas é muito forte.
3.3.2.1. Padrões e Contexto
Uma expressão de selecção é sempre avaliada em função dum contexto de procura. Um contexto de procura é um conjunto de nodos
a que uma
expressão se pode aplicar de modo a calcular o resultado. Todos os nodos no contexto de procura são filhos do mesmo
nodo pai; o contexto de
procura é constituído por todos os nodos que são filhos deste nodo pai e respectivos atributos mais os atributos do
nodo pai.
As expressões de selecção poderão ser absolutas (o contexto é seleccionado em função do nodo raíz - "/"), ou relativas (o
contexto é
seleccionado em função do contexto actual - "."). Na especificação do contexto pode ainda ser usado o operador "//"
com o significado de descendência recursiva.
Exemplos:
- Seleccionar todos os elementos autor no contexto actual.
-
./autor
ou
autor
- Seleccionar o elemento raíz (report) deste documento.
-
/report
- Seleccionar todos os elementos autor em qualquer ponto do documento actual.
-
//autor
- Seleccionar todos os elementos capítulo cujo atributo tema é igual ao atributo especialidade de report.
- capítulo[/report/@especialidade = @tema]
- Seleccionar todos os elementos título que estejam um ou mais níveis abaixo do contexto actual.
- .//título
3.3.2.2. Quantificador: todos
O operador "*" quando usado numa expressão de selecção selecciona todos os elementos nesse contexto.
Exemplos:
- Seleccionar todos os elementos filhos de autor.
-
autor/*
- Seleccionar todos os elementos nome que sejam netos de report.
-
report/*/nome
- Seleccionar todos os elementos netos do contexto actual.
-
*/*
- Seleccionar todos os elementos que tenham o atributo identificador.
-
*[@identificador]
3.3.2.3. Atributos
Como já se pôde observar nalguns exemplos, o nome de atributos é precedido por "@". Os atributos são tratados como sub-elementos,
imparcialmente, sempre que possível. De notar que os atributos não podem ter sub-elementos pelo que não poderão ter
operadores de
contexto aplicados ao seu conteúdo (tal resultaria numa situação de erro sintáctico). Os atributos também não têm conceito
de ordem,
são por natureza anárquicos pelo que nenhum operador de indexação deverá ser-lhes aplicado.
Exemplos:
- Seleccionar o atributo valor no contexto actual.
-
@valor
- Seleccionar o atributo dólar de todos os elementos preço no contexto actual.
-
preço/@dólar
- Seleccionar todos os elementos capítulo que tenham o atributo língua.
-
capítulo[@língua]
- Seleccionar o atributo língua de todos os elementos capítulo.
-
capítulo/@língua
- Exemplo inválido
-
preço/@dólar/total
3.3.2.4. Filtro - sub-query
O resultado duma query pode ser refinado através de uma sub-query (restrição aplicada ao resultado da query principal),
indicada entre "[" e "]" (nos exemplos anteriores já apareceram várias sem nunca se ter explicado a sua sintaxe e semântica).
A sub-query é equivalente à cláusula SQL WHERE. O valor resultante da aplicação de uma sub-query é booleano e os elementos
para os quais o valor final seja verdadeiro farão parte do resultado final.
Há operadores nas sub-queries que permitem testar o conteúdo de elementos e atributos.
Exemplos:
- Seleccionar todos os elementos capítulo que contenham pelo menos um elemento excerto.
-
capítulo[excerto]
- Seleccionar todos os elementos título pertencentes a elementos capítulo que tenham pelo menos um elemento excerto.
-
capítulo[excerto]/titulo
- Seleccionar todos os elementos autor pertencentes a elementos artigo que tenham pelo menos um elemento excerto, e onde autor
tenha email.
-
artigo[excerto]/autor[email]
- Seleccionar todos os elementos artigo que contenham elementos autor com email.
-
artigo[autor/email]
- Seleccionar todos os elementos artigo que tenham um autor e um título.
-
artigo[autor][titulo]
Como se pode observar nalguns destes exemplos, algumas das restrições que pretendemos colocar sobre os documentos podem ser
especificadas com os
construtores e operadores já apresentados. A linha divisória entre a selecção e a restrição parece já um pouco diluída.
3.3.2.5. Expressões booleanas
As expressões booleanas podem ser usadas nas sub-queries e estas, já nos permitem especificar condições contextuais como a
restrição de valores a
um domínio. Uma expressão booleana tem a seguinte forma:
val-esquerda operador val-direita
Os operadores são normalmente binários, tomam como argumentos um valor à esquerda e um valor à direita:
or
,
and
e
not
(este é unário tomando o
valor à direita).
Com estes operadores e o agrupamento por parentesis podem especificar-se queries bastante complexas.
Exemplos:
- Seleccionar todos os elementos autor que tenham um email e um url.
-
autor[email and url]
No universo das queries, o resultado seria o conjunto de autores que tivessem email e url.
- Seleccionar todos os elementos autor que tenham um email ou um url e pelo menos uma publicação.
-
autor[(email or url) and publicação]
- Seleccionar todos os elementos autor que tenham um email e nenhuma publicação.
-
autor[email and not publicação]
- Seleccionar todos os elementos autor que tenham pelo menos uma publicação e não tenham email nem url.
-
autor[publicação and not (email or url)]
3.3.2.6. Equivalência
A igualdade é notada por
=
e a desigualdade por
!=
.
Podemos usar strings nas expressões desde que limitadas por aspas simples ou duplas.
Exemplos:
- Seleccionar todos os autores que têm o sub-elemento organização preenchido com o valor 'U.Minho'.
-
autor[organização = 'U.Minho']
- Seleccionar todos os elementos que têm o atributo língua preenchido com o valor 'pt'.
-
*[@língua = 'pt']
A linguagem possui todos os operadores relacionais habituais, cuja utilização não foi aqui exemplificada,
porém, a sua semântica é bem conhecida e este enunciado já tem complexidade qb. Fica ao critério dos grupos de trabalho
a sua implementação.