Trabalho Prático II
Processamento de Linguagens e Compiladores (PLC2008)
José Carlos Ramalho
José João Almeida
2008-05-07
Criada a segunda versão com o segundo enunciado completo.
2008-04-22
Criada a primeira versão.
Palavras-chave: Compiladores, Trabalho Prático, C, Lex, Yacc
Este documento descreve os vários temas disponiveis para a realização do trabalho prático que os alunos a fazer a disciplina em epígrafe têm de realizar de forma a obter uma avaliação prática à disciplina.
Ao longo de várias semanas, irá evoluindo e sofrendo alterações.
Esteja atento às datas de revisões e aos comentários sobre as alterações introduzidas.
Dos vários enunciados disponiveis, cada grupo de trabalho deverá escolher um que desenvolverá e submeterá para avaliação no fim do semestre.
Este trabalho vale 2/3 da nota prática.
Índice
Capítulo 1
Capítulo 2
Capítulo 3
Secção 3.1
Secção 3.2
Secção 3.3
Subsecção 3.3.1
Subsubsecção 3.3.1.1
Subsecção 3.3.2
Subsubsecção 3.3.2.1
Subsubsecção 3.3.2.2
Subsubsecção 3.3.2.3
Subsubsecção 3.3.2.4
Subsubsecção 3.3.2.5
Subsubsecção 3.3.2.6
Capítulo 4



1. Objectivos de formação e resultados de aprendizagem

Este projecto tem como objectivos principais a formação genérica e específica de estudantes em fundamentos de computação na área do processamento de linguagens.
Os objectivos de formação genérica incluem: (i) a pesquisa, análise e selecção de informação, (ii) o treino na resolução de problemas, (iii) o desenvolvimento da capacidade de análise, e (iv) o desenvolvimento da capacidade de comunicação escrita e oral.
Os objectivos de formação específica incluem: (i) a análise da especificação e do problema, (ii) o desenvolvimento de algoritmos e consequente programação numa linguagem imperativa, (iii) a execução e realização de testes de conformidade.
A avaliação dos resultados esperados de aprendizagem irão verificar se as/os estudantes conseguem demonstrar ter adquirido o seguinte conjunto de competências genéricas e específicas:

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:
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:
  1. todas as anotações correspondentes a elementos com conteúdo são abertas e fechadas correctamente (não há marcas cruzadas);
  2. 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.

4. Enunciado 3 - Yet Another Top-Down Parser Generator

Neste projecto, pretende-se que o aluno construa um gerador de parsers segundo a filosofia Top-Down. Nesse sentido, será necessário definir uma linguagem para a especificação de gramáticas e todos os algoritmos que verificam se uma gramática especificada pode ser processada pela ferramenta (se é LL(1)), e neste caso gerem o código necessário para implementar o parser.
Alternativamente poderão usar uma abordagem Bottom-Up com as devidas validações: LR0, SLR1, LALR.

Bibliografia

Bray98
RDF and Metadata, Tim Bray, Seybold and O'Reilly Publicatons, June 1997.
Cla96
"DSSSL - Document Style and Semantics Specification Language", Editado por James Clark em 1996: http://www.jclark.com/dsssl
CCDFPT98
XML-GL: A Graphical Language for Querying and Reshaping XML Documents, Stefano Ceri, Sara Comai, Ernesto Damiani, Piero Fraternali, Stefano Paraboschi, e Letizia Tanca, QL'98 - The Query Languages Workshop, December 5, 1998.
DeR98
XQuery: A unified syntax for linking and querying general XML documents, Steven DeRose, QL'98 - The Query Languages Workshop, December 5, 1998.
Paa95
Attribute Grammars Paradigms: A High-Level Methodology in Language Implementation, Jukka Paakki, ACM Computing Serveys, 27, 2, June 1995.
RLS98
XML Query Language (XQL), Jonathan Robie, Joe Lapp, e David Schach, QL'98 - The Query Languages Workshop, December 5, 1998.
Tom98
Providing flexible access in a query language for XML, Frank Tompa, QL'98 - The Query Languages Workshop, December 5, 1998.
Wad99
A formal semantics of patterns in XSLT, Philip Wadler, Markup Technologies'99, Philadelphia - USA, Dec. 1999.
Wid98
Querying XML with Lore, Jennifer Widom, QL'98 - The Query Languages Workshop, December 5, 1998.
XSL
"Extensible Stylesheet Language (XSL) Version 1.0" - World Wide Web Consortium Working Draft 18-August-1998.
XSLT
"XSL Transformations (XSLT) - Version 1.0" - World Wide Web Consortium Recommendation 16-November-1999.