Instructions
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 4
Linguagens Formais e Aut´omatos
Trabalho Pr´atico
Departamento de Electr´onica, Telecomunica¸c˜oes e Inform´atica
Universidade de Aveiro
2017–2018, 2osemestre
1 Introdu¸c˜ao
Um compilador pode ser encarado como sendo um tradutor da linguagem fonte (i.e. da
linguagem a compilar), para uma linguagem destino. A linguagem destino pode ser pr´oxima
da linguagem fonte, ou muito distante (por exemplo, assembly ou linguagem m´aquina).
Neste processo de tradu¸c˜ao o compilador deve n˜ao s´o garantir a validade sint´actica do
programa, com tamb´em a sua correc¸c˜ao semˆantica (i.e. uma utiliza¸c˜ao com significado das
instru¸c˜oes da linguagem).
2 Objectivos
O trabalho a desenvolver deve envolver, pelo menos, duas linguagens: uma para um compi-
lador (com a linguagem objectivo do trabalho) e outra para ler informa¸c˜ao estruturada (por
exemplo, um ficheiro de configura¸c˜ao, ou uma linguagem de especifica¸c˜ao complementar `a
linguagem principal).
O desenvolvimento do compilador deve envolver, tanto quanto poss´ıvel, todas as fases
de constru¸c˜ao de linguagens de programa¸c˜ao:
1. Concep¸c˜ao e defini¸c˜ao de uma linguagem de programa¸c˜ao (sintaxe e semˆantica).
2. Implementa¸c˜ao em ANTLR4 da an´alise l´exica e da an´alise sint´actica de um compilador
para a linguagem;
3. Defini¸c˜ao das regras semˆanticas a aplicar `a linguagem, e sua implementa¸c˜ao no con-
texto do ponto anterior.
4. Escrever um documento que descreva a linguagem (instru¸c˜oes existentes e o seu
significado; exemplos de programas; etc.).
1
5. Escolha criteriosa de uma linguagem destino, onde se possa implementar a s´ıntese
(backend) do compilador.
6. Defini¸c˜ao dos padr˜oes de gera¸c˜ao de c´odigo para as instru¸c˜oes da linguagem.
7. Implementa¸c˜ao completa do compilador.
3 Temas
O tema para a linguagem de programa¸c˜ao a desenvolver pode ser proposto pelos alunos
(sendo que, neste caso, antes de ser aceite ter´a de passar pelo “crivo” do docente das
pr´aticas). Alternativamente, pode ser escolhido um tema da seguinte lista:
1. Linguagem para manipula¸c˜ao de tabelas (adapta¸c˜ao do problema do bloco 3 para
um compilador). Gerar c´odigo em Java.
2. Linguagem para criptografia (ver sec¸c˜ao 3.1).
3. Linguagem para manipula¸c˜ao de figuras gr´aficas (desenho, composi¸c˜ao, . . . ). Gerar
c´odigo em Java,PostScript, ou pdf.
4. Linguagem para an´alise dimensional (f´ısica). A especifica¸c˜ao das unidades (metros,
segundos, nano, micro, . . . ) pode ser feita numa linguagem separada, sendo o com-
pilador aplic´avel a uma linguagem de programa¸c˜ao que se aproxime qb. de uma
linguagem de uso gen´erico.
5. Linguagem para manipula¸c˜ao de imagens (processamento de imagem, zoom, crop, de-
tec¸c˜ao de contornos, . . . ). Gerar c´odigo em OpenCV, ou noutra biblioteca/linguagem
que suporte minimamente as funcionalidades pretendidas.
As escolhas a tomar no desenvolvimento das linguagens e respectivas gram´aticas s˜ao li-
vres (e sujeitas a avalia¸c˜ao). Sugere-se a implementa¸c˜ao de algumas das seguintes opera¸c˜oes:
•Defini¸c˜ao de vari´aveis;
•Opera¸c˜oes interactivas com o utilizador;
•Defini¸c˜ao de express˜oes que definam uma ´algebra sobre elementos da linguagem
(n´umeros, figuras, tabelas, imagens, . . . );
•Instru¸c˜oes iterativas;
•Express˜oes booleanas (predicados) e instru¸c˜oes condicionais;
•Fun¸c˜oes.
Para al´em do documento que descreve as linguagens desenvolvidas, tem de fazer parte
da entrega do trabalho um conjunto adequado de programas (funcionais) de exemplo das
linguagens.
2
3.1 Linguagem para criptografia
As cifras s˜ao fun¸c˜oes de transformam dados ditos em claro em algo inintelig´ıvel (cripto-
grama), e vice-versa, usando para o efeito um algoritmo bem conhecido e um valor secreto,
designado por chave. Os dados em claro, os criptogramas e as chaves s˜ao tratadas pelo
algoritmo como conjuntos de bits com um comprimento fixo. Estes conjuntos de bits s˜ao
processados pelo algoritmo usando opera¸c˜oes que operam sobre blocos de bits de v´arias
dimens˜oes. Essas opera¸c˜oes incluem, por exemplo, rota¸c˜oes, deslocamentos, permuta¸c˜oes,
concatena¸c˜oes, substitui¸c˜oes, etc. Normalmente estas opera¸c˜oes s˜ao muito fastidiosas de
programar, tanto em linguagens de alto n´ıvel como em linguagem m´aquina, o que complica
o desenvolvimento de novos algoritmos.
Pretende-se com este trabalho desenvolver uma linguagem para descrever a opera¸c˜ao de
um algoritmo de cifra (e decifra). A linguagem dever´a suportar a defini¸c˜ao de operandos
com dimens˜ao, de forma a permitir uma valida¸c˜ao semˆantica e a balizar os tipos necess´arios
na gera¸c˜ao de c´odigo. Para obter uma lista de operadores a concretizar, pode-se ver como
exemplo os algoritmos do DES,IDEA,AES,SHA-1,SHA-2,SHA-3 eA5.
Existem tamb´em os chamados modos de cifra, que s˜ao formas gen´ericas de aplica¸c˜ao de
cifras a volumes de dados arbitr´arios. Estes modos tamb´em permitem definir novas cifras
`a custa de outras cifras. Neste sentido, a linguagem dever´a permitir o desenvolvimento de
uma cifra recorrendo a outra.
Outro aspeto interessante ´e a defini¸c˜ao, atrav´es de uma linguagem, de padr˜oes de
teste de um algoritmo. Por exemplo, certas cifras produzem sequˆencias de bits que se
assemelham a sequˆencias aleat´orias (em termos estat´ısticos), outras possuem o chamado
efeito de avalanche: a mudan¸ca de 1 bit no input causa uma altera¸c˜ao na sa´ıda que seguir´a
uma distribui¸c˜ao Gaussiana, centrada nos 50%. Outras ainda podem ter valores internos
que ter˜ao desejavelmente uma distribui¸c˜ao normal.
Outro aspeto interessante ´e a defini¸c˜ao, atrav´es de uma linguagem, do modelo de
aplica¸c˜ao de uma cifra a dados estruturados, onde se pode definir que dados permane-
cem alterados, que dados devem ser cifrados e que envelope se d´a aos dados cifrados para
serem corretamente interpretados pelo receptor. Esse envelope tipicamente indica o cripto-
grama e meta-informa¸c˜ao relativa a sua gera¸c˜ao (quais o(s) algoritmo(s) usado(s), o modo
de cifra, o alinhamento, etc.). Existem v´arias formas padr˜ao de realizar este empacota-
mento (e.g. PKCS #7,PKCS #12), os quais poder˜ao ser sumariamente concretizados com a
linguagem a desenvolver (est´a fora de quest˜ao a realiza¸c˜ao completa destes padr˜oes).
4 Grupos
O trabalho deve ser realizado por grupos de 4/5 elementos. Os grupos devem ser formados
preferencialmente por elementos da mesma turma. Poder˜ao ser consideradas excep¸c˜oes
desde que previamente sancionadas pelos docentes envolvidos. Ser˜ao criados projetos na
plataforma code.ua para suporte da atividade dos grupos, sendo o c´odigo colocado num
reposit´orio em git. Os projetos ser˜ao criados pelo docente durante as aulas pr´aticas.
3
Alerta-se desde j´a que as atualiza¸c˜oes feitas ao reposit´orio devem ser executadas por quem
desenvolve o c´odigo, usando mensagens adequadas. Ser˜ao mal toleradas situa¸c˜oes do tipo
“tive que pedir ao meu colega para o fazer”.
A entrega do trabalho ser´a feita recorrendo a estes reposit´orios.
5 Avalia¸c˜ao
A avalia¸c˜ao ter´a em considera¸c˜ao o trabalho desenvolvido pelo grupo. Ser˜ao realizadas
reuni˜oes com cada grupo com a presen¸ca de dois docentes onde se far´a uma avalia¸c˜ao
pr´atica com o trabalho realizado (onde se espera que o grupo demonstre o trabalho feito e
responda a eventuais d´uvidas e quest˜oes).
No que diz respeito `a distribui¸c˜ao da nota pelos elementos do grupo, cada grupo ter´a de
distribuir o trabalho feito pelos elementos do grupo (se o grupo tiver 5 elementos, existir˜ao
500 pontos a ser distribu´ıdos pelos elementos do grupo). Esta distribui¸c˜ao de pontos tem
ser definida aquando da entrega do trabalho (no pr´oprio email que formaliza a entrega).
Na avalia¸c˜ao v˜ao pesar a qualidade da solu¸c˜ao desenvolvida e os objetivos parcelares
por ela cobertos. Fazem parte dos objectivos parcelares os seguintes pontos:
1. Concep¸c˜ao da linguagem. A simplicidade e expressividade da linguagem definida
ser˜ao aspectos a valorizar.
2. Gram´aticas desenvolvidas.
3. An´alise semˆantica.
4. Gest˜ao de erros.
5. Legibilidade do c´odigo e documenta¸c˜ao.
6. Gera¸c˜ao de c´odigo (ser´a valorizada o uso de uma linguagem destino mais “baixo
n´ıvel”).
O grau de ambi¸c˜ao do trabalho desenvolvido, confrontado com os resultados obtidos,
ser´a tamb´em tido em conta.
6 Execu¸c˜ao do trabalho e prazos de entrega
As aulas pr´aticas que decorrem at´e ao fim do semestre ser˜ao dedicadas ao trabalho pr´atico.
No entanto, ´e expect´avel que n˜ao sejam suficientes (principalmente aos grupos que preten-
dem uma melhor classifica¸c˜ao). Espera-se por isso que uma parte do trabalho seja feita
fora das aulas.
O prazo limite de entrega do trabalho ser´a uma semana antes da data do exame da
´epoca de exames respectiva (11 de junho na ´epoca normal e 28 de junho para recurso).
Relembra-se que, como definido no gui˜ao da unidade curricular no in´ıcio do semestre, o
trabalho pr´atico tem uma ´unica entrega (ou para a ´epoca normal ou para recurso).
4
