BCC328
Construção de Compiladores I
José Romildo Malaquias
Sala 21 – DECOM – ICEB III
Instituto de Ciências Exatas e Biológicas
Universidade Federal de Ouro Preto
malaquias@ufop.edu.br
2018/2
Sumário
1 Dados gerais
|
|
| Departamento | Computação |
|
|
| Unidade | Instituto de Ciências Exatas e Biológicas |
|
|
| Carga horária semanal | 4 teóricas |
|
|
| Duração | 18 semanas |
|
|
| Carga horária semestral | 72 horas-aula |
|
|
| Pré-requisitos | POO, Teoria da Computação |
|
|
| Cursos | Ciência da Computação: obrigatória 6o período |
|
|
| |
2 Ementa
- Implementação de linguagens de programação: compilação e interpretação
- Análise léxica
- Análise sintática
- Análise semântica
3 Bibliografia
-
[1]
-
Torben Ægidius Mogensen. Introduction to Compiler Design. Inglês. 2a ed. Springer, 2017. isbn:
978-3-319-66965-6.
-
[2]
-
Andrew W Appel. Modern Compiler Implementation in Java. Inglês. 1a ed. Cambridge University
Press, 1997. isbn: 0-521-58388-8. Livro-texto.
-
[3]
-
Alfred V Aho, Monica S Lam, Ravi Sethi e Jeffrey D Ullman. Compiladores: Princípios, Técnicas
e Ferramentas. Português. 2a ed. Pearson, 2007. isbn: 9788588639249.
-
[4]
-
Compiler Design: Syntactic and Semantic Analysis. Inglês. Springer, 2013. isbn: 978-3642175398.
4 Objetivos
Ao final do curso é esperado que o aluno:
- possua uma visão geral sobre o processo de compilação sob o ponto de vista de implementação
- saiba especificar aspectos léxicos e sintáticos de linguagens através de expressões regulares e
gramáticas livres de contexto
- conheça as principais técnicas e ferramentas de apoio usadas na construção de compiladores,
sabendo usá-las na especificação e implementação de linguagens de programação
5 Metodologia de Ensino
- Aulas expositivas sobre o conteúdo da disciplina.
- Aulas práticas com aplicação das técnicas de compilação na construção de compiladores para
linguagens de programação simples.
6 Atividades Discentes
- Exercícios para
- estudo mais detalhado de aspectos teóricos da compilação
- aplicação das técnicas na construção de um compilador
- Trabalhos práticos
7 Avaliações
A avaliação será feita por um conjunto de provas escritas e um conjunto de trabalhos práticos. A tabela a
seguir enumera as atividades de avaliação previstas, com os respectivos pesos na formação da nota final, e a
data de realização da avaliação.
|
|
|
|
|
| Avaliação | Peso | Data | | Assuntos |
|
|
|
|
|
| Prova 1 |
70% | 24/09/2018 | segunda-feira | Introdução, gramáticas livre de contexto, análise léxica |
|
| | | | |
|
|
| |
|
|
|
| Prova 2 | | 29/10/2018 | segunda-feira | Análise sintática 1 |
|
| | | | |
|
|
| |
|
|
|
| Prova 3 | | 12/12/2018 | quarta-feira | Análise sintática 2, análise semântica |
|
|
|
|
|
| Trabalhos | 30% | | | |
|
|
|
|
|
| Exame especial | | 19/12/2018 | quarta-feira | De acordo com a resolução CEPE 2.880 |
|
|
|
|
|
| |
- A nota final dos trabalhos será dada pela média aritmética das notas dos trabalhos individuais.
- A nota final será dada pela média ponderada das atividades avaliativas, segundo a tabela acima.
As atividades deverão ser submetidas através da plataforma Moodle da UFOP:
https://www.moodlepresencial.ufop.br/course/view.php?id=21713
8 Código de honra do aluno
Este assunto deve ser muito simples. Não entregue trabalhos de outra pessoa como sendo seus, e não
compartilhe suas soluções com outros alunos.
Você deve se sentir livre para discutir os problemas propostos e os projetos de programação com os colegas,
mas todo trabalho que você submeter ao professor deve ser de sua própria autoria. Ou seja, você deve
elaborar suas próprias soluções para os problemas e implementar seus projetos de programação você
mesmo.
Se você discutir suas idéias com outros estudantes, não tem problema, mas faça uma observação sobre o
mesmo na submissão do seu trabalho.
As atividades propostas são para trabalho individual.
9 Grupo de discussão
Existe um grupo de discussão sobre o conteúdo do curso no Google Groups que deverá ser utilizado ativamente
pelos alunos e professor durante o curso. O professor poderá propor questões para discussão no grupo, bem
como problemas para serem resolvidos.
Caberá aos alunos discutir as questões e problemas propostos, apontando soluções básicas e/ou soluções
alternativas ou comentando o assunto. Os alunos poderão também propor algum problema ou levantar alguma
questão para discurtir que julgar interessante.
O endereço do grupo de discussão é http://groups.google.com/group/bcc328.
Cada aluno deverá se inscrever imediatamente no grupo e começar a participar das discussões.
10 Ferramentas
Nas aulas será utilizada a linguagem Java para implementação das técnicas de construção de compiladores.
Também serão utilizadas ferramentas auxiliares na implementação das diversas fases da compilação, como
geradores de analisadores léxicos (JFlex), geradores de analisadores sintáticos (Java CUP), e geradores de
código (LLVM).
Para desenvolvimento dos projetos recomenda-se a IDE IntelliJ IDEA.
11 Aulas
|
|
|
|
|
|
| # | Data | Assuntos | Atividades |
|
|
|
|
|
|
| 01 | 13/08 | Seg | Apresentação da disciplina | |
|
|
|
|
|
|
| 02 | 15/08 | Qua | Compilação e interpretação
Introdução | |
|
|
|
|
|
|
| 03 | 20/08 | Seg | Gramáticas | |
|
|
|
|
|
|
| 04 | 22/08 | Qua | Análise léxica: introdução | |
|
|
|
|
|
|
| 05 | 27/08 | Seg | Análise léxica: ad hoc
Exemplo | |
|
|
|
|
|
|
| 06 | 29/08 | Qua | Análise léxica: expressões regulares
CS143 Lexical Analysis | |
|
|
|
|
|
|
| 07 | 03/09 | Seg | Análise léxica: autômatos finitos | |
|
|
|
|
|
|
| 08 | 05/09 | Qua | Análise léxica: geradores
Aula prática: Análise Léxica | |
|
|
|
|
|
|
| 09 | 10/09 | Seg | Análise léxica: projeto | |
|
|
|
|
|
|
| 10 | 12/09 | Qua | Análise sintática: introdução | |
|
|
|
|
|
|
| 11 | 17/09 | Seg | Análise sintática: análise descendente recursiva | |
|
|
|
|
|
|
| 12 | 19/09 | Qua | (Continuação) | |
|
|
|
|
|
|
| 13 | 24/09 | Seg | Prova 1 | |
|
|
|
|
|
|
| 14 | 26/09 | Qua | Análise sintática: análise ascendente: autômato de pilha | |
|
|
|
|
|
|
| 15 | 01/10 | Seg | Análise sintática: análise ascendente: tabela LR(0) | |
|
|
|
|
|
|
| 16 | 03/10 | Qua | Análise sintática: análise ascendente: tabela SLR | |
|
|
|
|
|
|
| 17 | 08/10 | Seg | Análise sintática: análise ascendente: tabela LR(1) | |
|
|
|
|
|
|
| 18 | 10/10 | Qua | Análise sintática: análise ascendente: tabela LALR(1) | |
|
|
|
|
|
|
| 19 | 15/10 | Seg | Análise sintática: análise ascendente: hierarquia de gramáticas | |
|
|
|
|
|
|
| 20 | 17/10 | Qua | Análise sintática: análise ascendente: resolução de conflitos | |
|
|
|
|
|
|
| 21 | 22/10 | Seg | Análise sintática: gerador | |
|
|
|
|
|
|
| 22 | 24/10 | Qua | Análise sintática: projeto | |
|
|
|
|
|
|
| 23 | 29/10 | Seg | Prova 2 | |
|
|
|
|
|
|
| 24 | 31/10 | Qua | Árvores de sintaxe abstrata | |
|
|
|
|
|
|
| 25 | 05/11 | Seg | Análise semântica: introdução | |
|
|
|
|
|
|
| 26 | 07/11 | Qua | Análise semântica: tabelas de símbolo | |
|
|
|
|
|
|
| 27 | 12/11 | Seg | Análise semântica: tipagem | |
|
|
|
|
|
|
| 28 | 14/11 | Qua | Análise semântica: regras de análise semântica | |
|
|
|
|
|
|
| 29 | 19/11 | Seg | Análise semântica: escopo | |
|
|
|
|
|
|
| 30 | 21/11 | Qua | Análise semântica: projeto | |
|
|
|
|
|
|
| 31 | 26/11 | Seg | Geração de código: introdução | |
|
|
|
|
|
|
| 32 | 28/11 | Qua | Geração de código: LLVM | |
|
|
|
|
|
|
| 33 | 03/12 | Seg | (Continuação) | |
|
|
|
|
|
|
| 34 | 05/12 | Qua | (Continuação) | |
|
|
|
|
|
|
| 35 | 10/12 | Seg | (Continuação) | |
|
|
|
|
|
|
| 36 | 12/12 | Qua | Prova 3 | |
|
|
|
|
|
|
| | 19/12 | Qua | Exame especial | |
|
|
|
|
|
|
| |
12 Trabalhos
|
|
|
| Assunto | Trabalho | Data entrega |
|
|
|
| Análise léxica
| Implementar um analisador
léxico para a linguagem de
programação apresentada por
Torben
em seu livro de compiladores, no
capítulo 4 (gramática 4.1).
Você pode usar a seguinte
estrutura de projeto:
https://github.com/romildo/torben-java/tree/5e04d18234f519520690cf977a37ceeb27f2913b,
bastanto implementar as regras
de análise léxica, testes, e
documentação.
Na documentação é essencial
descrever a estrutura léxica da
linguagem.
Você deverá criar um projeto no
github contendo a documentação
e a implmentação do analisador
léxico.
| 16/09/2018 (domingo) |
|
|
|
| Análise sintática
descendente recursiva
| Implementar um analisador
sintático preditivo para
a linguagem de programação
apresentada por Torben em seu
livro de compiladores,
no capítulo 4 (gramática 4.1),
usando o o analisador léxico do
trabalho anterior.
Na documentação é essencial
descrever a estrutura sintática
da linguagem. Inclua também o
procedimento desenvolvido para
obter o analisador sintático
(tabelas do nullable, first, follow,
e LL(1)).
Você
deverá atualizar o seu projeto no
github contendo a documentação
e a implmentação do analisador
sintático.
| 29/10/2018 (segunda) |
|
|
|
| Interpretador
| Implementar um interpretador
para
a linguagem de programação
apresentada por Torben em
seu livro de compiladores, no
capítulo 4 (gramática 4.1), aqui
chamada de Picnic.
Você deverá implementar
o interpretador a partir do
projeto disponibilizado em
https://github.com/romildo/picnic-java.
Estenda Picnic com:
- o tipo text para cadeias de
caracteres
- o tipo real para números
em ponto flutuante
- o tipo void, cujo único
valor é nil
- uma biblioteca padrão com
as funções:
- print, para imprimir
um texto
- printbool, para
imprimir um
booleano
- printint, para
imprimir um inteiro
- printreal, para
imprimir um número
em ponto flutuante
- real, para converter
um número inteiro
para ponto flutuante
- round, para
arredondar
um número em ponto
flutuante
- ceil, para
arredondar
um número em ponto
flutuante para cima
- floor, para
arredondar
um número em ponto
flutuante para baixo
- size, para obter o
tamanho de um texto
- char, para obter um
caracter de um texto
em uma dada posição
- subtext, para obter
um pedaço de um
texto
- concat, para
concater dois textos
- expressões literais reais
- expressões literais de texto
- expressão literal nil
- expressão de atribuição
- expressão de repetição
- expressão sequência
- expressão parentetizada
- funções com lista de
argumentos vazia
- a função main deve ter uma
lista de argumentos vazia, e
um resultado inteiro.
Documente:
- as regras léxicas, sintáticas
e semânticas das extensões
- as regras de execução de
Picnic
| 12/10/2018 (quarta) |
|
|
|
| |
Equipes de estudo:
13 Avaliações de semestres anteriores
14 Notas e frequências
Resultados de avaliações e frequências
Última atualização: 2018-12-03 16:13:53 por José Romildo Malaquias.