Programação de Sistemas
Anúncios:
·
11-7-2003: As notas globais (frequência, trabalhos, e
exame de época de recurso) já estão disponíveis.
1.
Parabéns para
os grupos que conseguiram desenvolver um mini-compilador
ou um interpretador!
1.
Como houve
trabalhos muito bons, foi bastante difícil escolher os trabalhos para a
atribuição do bónus de 10% (melhor interpretador e melhor compilador).
Parabéns!
·
11-7-2003: Notas da
avaliação por exame de época normal.
·
10-7-2003: As notas do exame de época normal serão colocadas
amanhã de manhã no site. Serão também disponibilizadas as notas finais do
último trabalho prático (incluindo os bónus).
·
10-7-2003: Os alunos que queiram ver o exame podem fazê-lo
durante a manhã de sexta-feira, dia 11-7-2003.
·
18-6-2003: Notas da avaliação por frequência que
indicam os alunos que obtiveram aprovação.
·
Os alunos que pretendam melhorar ou que ainda não
apresentaram o último trabalho podem fazê-lo até ao dia 2 de Julho de 2003
(deverão combinar com o Prof. João Cardoso a data da apresentação).
·
14-6-2003: Exame de época normal: dia 20-6-2003, 9H30,
salas: CP 2.11, CP 2.5, CP 2.7, e CP 2.9.
·
14-6-2003: Os alunos que queiram fazer melhoria de nota no
exame de época normal podem fazê-lo. Contudo a entrega do exame (não
desistência) anula a nota da frequência.
·
14-6-2003: Notas do 2º trabalho.
·
14-6-2003: Discussão/Apresentação dos trabalhos (dias 16,
17, e 18) na sala 1.60
·
11-6-2003: Notas da frequência.
·
4-6-2003: segmentos de código para manusear Hashtables do Java.
·
2-6-2003: Entrega e apresentação do trabalho final nos dias
16, 17, e 18 de Junho de 2003 [requer inscrição].
·
28-5-2003: A folha de exercícios sobre gramáticas tinha um lapso
na tabela sintáctica. Tem de ser: M[s7][$] = Reduce(1).
Foi corrigido.
·
28-5-2003: As transparências disponíveis englobam a matéria
dada nas aulas teóricas que pode sair na frequência. Só depois da frequência é
que haverá adição das transparências das restantes aulas teóricas.
·
Frequência: dia 2 de Junho de 2003, 17h-19h30, salas B1 e
J17.
·
Folha de exercícios sobre gramáticas disponível.
·
Nota da componente prática da disciplina: 20% 1º trabalho;
20% 2º trabalho; 60% 3º trabalho.
·
22-5-2003: circula pelas aulas teóricas a folha de
inscrições para entrega e apresentação do trabalho (as datas são 16, 17, e
18-5-2003).
·
21-5-2003: houve pequenas correcções na gramática ualg do enunciado do último trabalho prático. Por favor,
voltem a fazer download do enunciado.
·
9-5-2003: O enunciado do trabalho final já se encontra
disponível.
·
7-5-2003: As notas
do primeiro trabalho já se encontram disponíveis. Os alunos com um asterisco
devem falar com o Prof. João Cardoso.
·
10-4-2003: Na semana de 21-4-2003 a 25-4-2003
não haverá aulas teóricas.
·
7-4-2003: Aula teórica de compensação (Aulas Nº
11 e 12) para ESC será realizada amanhã (8-4-2003) na sala 3.11 do CP das
15h30-17h30 (não foi possível arranjar sala para as 15h).
·
2-4-2003: 2º Trabalho prático (1º exercício da AULA Nº 5):
1.
Obrigatória a entrega em disquete (colocar no
cacifo da professora Margarida Moura até ao dia 22-4-2003)
2.
Devem entregar o código Java e as classes
previamente compiladas para resolver a alínea (c) da
ficha (AVISO: podem utilizar um array bidimensional
ou uma função utilizando um switch para a
implementação da tabela de transições que define o vosso DFA)
3.
Devem colocar um ficheiro README onde indicam os
nomes e números dos alunos que realizaram o trabalho.
·
2-4-2003: Obrigatória a entrega do primeiro
trabalho em disquete (colocar no cacifo dos professores João Cardoso ou
Margarida Moura até ao dia 4-4-2003)
·
31-3-2002: Amanhã, 1-4-2003, não há a aula de
recuperação para os alunos de ESC
·
31-3-2002: Exame trabalhador/estudante com a
matéria de PS do ano anterior (especial favor da Prof.ª
Ana Paula):
1.
Horário para esclarecer dúvidas sobre a matéria:
28/04/03, segunda-feira, das 14h30 às 16h30, no gabinete 2.57.
2.
Realização do exame: 30/04/03, quarta-feira, às
10h, no gabinete 2.57.
·
19-3-2003: Makefile exemplo da
primeira aula TP
·
19-3-2003: 1º Trabalho prático (2º exercício da AULA Nº 2):
entrega até ao dia 28 de Março.
Envio para: mmadeira@adeec.fct.ualg.pt
De: 1. Código java (incluindo a identificação dos autores nos comentários
do programa)
2. Ficheiro de teste
3. Makefile
contemplando as regras/alvos:
3.1. Compilação
3.2. Eliminar classes
anteriormente compiladas
3.3. Execução
3.4. Comparar o ficheiro
original com o alterado pela "Paródia".
Notar bem: É pedida apenas a
implementação das regras a negrito.
·
27-2-2003: Já está disponível a documentação
relativa à 4ª aula teórica e à 2ª e 3ª aulas teórico-práticas.
·
26-2-2003: De 1 a 16 de Março de 2003
não se realizam aulas teóricas (aulas de substituição serão oportunamente
marcadas)
·
23-2-2003: Frequência da disciplina em 2
de Junho de 2003 (salas e hora a marcar)
·
21-2-2003: Já está disponível a documentação
relativa às primeiras 3 aulas teóricas e à primeira aula teórico-prática.
3º
ano, 2º semestre para EI (Ensino de Informática) e IG (Informática, ramo de
Gestão).
2º
ano, 2º semestre para ESC (Eng.ª de Sistemas e Computação)
2 h (T); 3 h (TP) / 6 ECTS
João
M. P. Cardoso (email: jmcardo@ualg.pt)
Horário de atendimento (gab. 2.65):
Segundas: 15:30-18:00
Quartas: 10:00-11:30;
Margarida
M. Moura (email: mmadeira@ualg.pt)
Esta disciplina tem como objectivo a aprendizagem dos
conceitos fundamentais da geração de código a ser executado num
microprocessador a partir de um programa descrito numa linguagem de programação
imperativa.
Estudo dos componentes de um compilador, com o
projecto de um compilador para uma linguagem simples, incluindo os módulos de
análise lexical, sintáctica e semântica, além do gerador e optimizador
de código final. São realizados trabalhos práticos que focam as diversas etapas
de um compilador.
Enquanto
os tópicos I a VI são abordados na perspectiva de “como se faz e como se implementa?” os restantes tópicos (VII e
VIII), sendo tópicos mais avançados e por isso normalmente constarem em
disciplinas posteriores sobre compiladores, são abordados na perspectiva: “o que são e quais os efeitos da sua
aplicação?”.
I.
Introdução
Ø
Objectivos de um Compilador
Ø
Anatomia de um Compilador
Ø
Aplicação de Conceitos a outras Ferramentas
Ø
Interpretadores
Ø
Factos históricos
II.
Análise
lexical
Ø
Do texto do programa aos tokens
Ø
Expressões regulares
Ø
Autómatos finitos deterministas e não deterministas (NFAs, DFAs, conversão NFA ®
DFA)
Ø
Criação de analisadores léxicos
Ø
Construção automática de analisadores léxicos
III.
Análise
Sintáctica
Ø
Dos tokens
à árvore sintáctica
Ø
Gramáticas livres do contexto
Ø
Análise sintáctica preditiva
Ø
Análise sintáctica LR
Ø
Árvores de sintaxe concretas
Ø
Árvores de Sintaxe Abstractas (ASTs)
Ø
Recuperação de erros
Ø
Criação automática de analisadores sintácticos
IV.
Análise
Semântica
Ø
Tabelas de símbolos
Ø
Verificações de tipos em expressões
Ø
Verificações de tipos em declarações
V.
Tradução
para código intermédio
Ø
Árvores de representação intermédias
Ø
Estruturas de dados
Ø
Tradução para árvores (expressões, variáveis escalares e arrays,
condicionais, ciclos, etc.)
Ø
Declarações
VI.
Geração
de código final
Ø
Geração de código para blocos básicos
Ø
Análise de fluxo de dados para determinação do tempo de vida
de variáveis
Ø
Afectação de registos por coloração de grafos
Ø
Geração do código máquina
Ø
Assemblers, Linkers, e loaders
VII.
Optimização
de código
Ø
Análise de fluxo de dados
Ø
Eliminação de sub-expressões
comuns
Ø
Substituição de expressões com constantes
Ø
Propagação de constantes
Ø
Simplificações algébricas
Ø
Redução da força de operadores
Ø
Transformações em ciclos
Ø
Escalonamento
VIII.
Tópicos
avançados
Ø
Pipelining de Software
Ø
Paralelização
Ø
Gestão de Memória
Ø
Compilação de linguagens orientadas por objectos
Ø
Utilização de algumas opções de optimização do compilador gcc para avaliar o impacto dessas optimizações no tamanho
do código produzido e no desempenho do mesmo. Ferramentas de software para
apoio ao desenvolvimento de aplicações (makefiles).
Ø
Introdução à linguagem de programação Java: sintaxe,
tecnologia, documentação, etc. Exercícios relacionados com alguns aspectos da linguagem
Java e que focam tratamento de texto.
Ø
Exercício para determinar os procedimentos recursivos a partir de um grafo de chamadas (Call Graph).
Resolução com um algoritmo iterativo.
Ø
Aula de exercícios sobre expressões regulares, DFAs, NFAs, e gramáticas.
Ø
Implementação de um reconhecedor
de números reais e números inteiros. Versão construída manualmente; Versão
construída utilizando o gerador de parsers JavaCC.
Ø
As outras aulas serão posteriormente adicionadas...
Qualquer
um dos seguintes livros retrata as matérias que aprofundaremos (e claro, muitos
conceitos que não abordaremos):
Ø Andrew W. Appel. Modern
Compiler Implementation in Java, Cambridge University Press, 1998.
Ø Alfred V. Aho, Ravi Sethi,
Jeffery D. Ullman. Compiler - Principles, Techniques, and Tools, Addison-Wesley, 1986.
[existe uma versão brasileira]
Ø
Dick Grune,
Henri E. Bal, Ceriel J. H. Jacobs, and Koen G. Langendoen, Modern Compiler Design, John Wiley &
Sons, Ltd, 2000.
Ø
Rui Gustavo Crespo. Processadores
de Linguagens. IST Press. 2001. http://istpress.ist.utl.pt/lprocess.html
O
livro seguinte aborda essencialmente tópicos mais avançados:
Ø Steven S. Muchnick. Advanced
Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997.
Época
Normal: [1º momento] 1
frequência (60%) + trabalhos práticos (40%)
[2º momento]
1 Exame
Época
de Recurso: [3º momento] 1 Exame
Um
aluno tem avaliação positiva na disciplina se alcançar pelo menos 10 valores
num dos momentos de avaliação. Avisam-se os alunos que tenham tido avaliação
positiva durante este ano lectivo, e pretendam voltar a ser avaliados num dos
exames, que a nota final será a última das notas (quer seja superior ou
inferior a 10 valores)
Nota: existe a possibilidade das notas
obtidas com os trabalhos práticos também contarem com 40% nos exames (nesse
caso a nota atribuída num exame é 60% da nota do exame + 40% da notas dos
trabalhos).
Como
nas aulas práticas utilizaremos a linguagem de programação Java e embora os
conhecimentos necessários para a disciplina sejam inseridos por fases, é sempre
útil termos documentos onde possamos esclarecer dúvidas ou aprender mais sobre
Java:
São aconselhados
os seguintes tópicos: Trails
Covering the Basics: Your First Cup of Java; Detailed instructions to help you
run your first program; Getting Started; Learning the Java Language; Essential
Java Classes.
O documento com a especificação da linguagem Java
pode ser encontrado em:
Para geração semi-automática de analisadores lexicais
e sintácticos serão utilizadas ferramentas disponíveis gratuitamente. A
ferramenta que iremos utilizar é o JavaCC e foi concebida para geração de parsers programados na linguagem
Java. Se necessitássemos de construir automaticamente parsers em código C/C++ teríamos
que, por exemplo, utilizar uma das duplas lex/yacc ou flex/bison
(GNU).
Os
trabalhos da disciplina que incidem na geração de código assembly
utilizarão o SPIM (assembler e simulador do MIPS):
·
Para os utilizadores do sistema operativo Microsoft
Windows (95/98, NT, 2000) basta fazerem o download: http://www.cs.wisc.edu/~larus/SPIM/pcspim.zip
·
Utilizadores de outros sistemas operativos devem
consultar a página do simulador spim: http://www.cs.wisc.edu/~larus/spim.html
·
Documentação do spim: Morgan Kaufmann disponibiliza uma
versão on-line do Apêndice A do livro: Computer
Organization and Design: The Hardware/Software Interface (Adobe PDF file).
·
Documentação do interface windows
do spim: postscript
ou Adobe PDF file.
https://imap.ualg.pt/wws/info/fct-progsist
Para
subscrever: fct-progsist@ualg.pt