INF1715 - Compiladores

Hisham Muhammad
2014.1 - Segundas (RDC512) e quintas (L450), 09:00 às 11:00
h@hisham.hm
LabLua, (21)3527-1500 ramal 4523

Índice

Material das aulas

11/02- Aula 0- W.O.
13/02- Aula 1- Apresentação da disciplina
18/02- Aula 2- Análise léxica, expressões regulares, Lex
20/02- Aula 3- Análise léxica manual; introdução a gramáticas
25/02- Aula 4- Análise sintática: gramáticas
27/02- Aula 5- Análise sintática top-down: LL(1), First, Follow
06/03- Aula 6- Análise sintática top-down: analisador preditivo recursivo
11/03- Aula 7- Análise sintática bottom-up: parsers LR, análise shift-reduce
13/03- Aula 8- Análise sintática bottom-up: Yacc (GNU Bison), conflitos shift-reduce
18/03- Aula 9- Análise sintática bottom-up: conflitos reduce-reduce, parsing GLR
20/03- Aula 10- Ações semânticas na árvore sintática
25/03- Aula 11- Árvore sintática abstrata: design e construção
27/03- Aula 12- Construindo uma árvore sintática abstrata na prática
01/04- Aula 13- Tabelas de símbolos: declarações de variáveis e tipos
08/04- Aula 14- Verificação de tipos: regras de derivação
15/04- Aula 15- Construindo uma tabela de símbolos na prática
24/04- Aula 16- Sistemas de tipos: conversibilidade de tipos, coerção, overflow, regras para Mini-0
29/04- Aula 17- Representações intermediárias: introdução, código de três endereços
06/05- Aula 18- Código de três endereços para Mini-0
13/05- Aula 19- Discussão sobre o trabalho
15/05- Aula 20- Gramática do formato de código intermediário
20/05- Aula 21- Construindo código intermediário na prática
22/05- Aula 22- Geração de código: Blocos básicos
27/05- Aula 23- Geração de código: Informação de próximo uso, seleção de registradores (pt.1)
29/05- Aula 24- Geração de código: Seleção de registradores (pt.2)
03/06- Aula 25- Geração de código: Assembly x86: Introdução, Mecanismos de controle
05/06- Aula 25- Geração de código: Assembly x86: Procedimentos, Variáveis locais; dicas para usar gcc 32-bits no Ubuntu

Existe um repositório da disciplina no Github com os exemplos passados em aula. Para baixar a primeira vez, digite: 

git clone https://github.com/hishamhm/inf1715

Isto vai gerar um diretório inf1715. Para baixar atualizações posteriores, entre no diretório inf1715 e digite: 

git pull

Avaliação

A avaliação da disciplina se dará através de uma série de trabalhos passados ao longo do curso, que podem ser individuais ou em dupla.

Linguagem de implementação: Os trabalhos podem ser implementados nas linguagens C, Lua ou Python. Recomenda-se fazer os trabalhos em C, que será a linguagem utilizada nas aulas. No caso de trabalhos em linguagens dinamicamente tipadas (Lua ou Python), as estruturas de dados devem estar documentadas tal qual seriam na declaração de structs em C (isto é, devem haver comentários explicando a hierarquia de estrutura das estruturas de dados construídas, sejam em tabelas Lua ou em listas, dicionários e classes Python). Consulte o professor se quiser fazer em alguma outra linguagem (ela pode ou não ser liberada).

Github: Todos os alunos devem criar contas no site github.com e os trabalhos devem ser armazenados como repositórios nas suas contas.

O registro do desenvolvimento do trabalho é parte da avaliação. O trabalho não pode ser armazenado no repositório em um único commit: a série de commits deve representar o processo de desenvolvimento (não se preocupe com comitar somente código "pronto", a ideia é justamente registrar o trabalho incompleto em andamento).

Trabalhos em dupla: No caso de trabalho em dupla, cada aluno deve ter sua própria conta e fazer seus commits como o seu próprio usuário, de modo que no histórico do repositório fique registrado quais partes foram implementadas por cada aluno; um único repositório deve ser o repositório "master" onde ambos os alunos da dupla devem fazer commits.

Atenção: Se o funcionamento da turma em relação aos trabalhos for satisfatório ao desenvolver os trabalhos dessa forma, não haverá necessidade de realizar prova ao final do semestre.

Trabalho 1 - Análise Léxica

Você deve fazer um analisador léxico para programas escritos na linguagem Mini-0, especificada abaixo.

Crie um repositório chamado inf1715 na sua conta do Github. Para facilitar sua vida, clique em "Initialize this repository with a README". Depois disso você pode fazer:

git clone https://github.com/seu_username/inf1715
cd inf1715
mkdir trab1
cd trab1
...e mãos à massa!...

A cada passo que você der no trabalho, faça um commit para ir registrando o histórico. Não se preocupe que ele esteja incompleto, a ideia é exatamente essa. Não economize commits. A maneira mais simples é assim, onde você já entra uma mensagem de log para registro:

git commit -a -m "Expressão regular para comentários"      # por exemplo

Note que ao fazer git commit você só salvou o histórico localmente. Envie o seu código em andamento periodicamente para o servidor, com o comando:

git push

Quando você terminar o trabalho, marque a versão no servidor como a final: 

git tag trab1
git push --tags      # se você não passar esta flag, a tag não vai pro servidor!

Quaisquer dúvidas na operação com git (ou sobre o trabalho de maneira geral), contacte o professor!

Prazo: 26/02/2014, 23:59. Será considerado como o trabalho entregue o conteúdo do seu repositório com a tag trab1. Não deixe para o último minuto (isto é, não assuma que você vai estar com internet funcionando neste horário exato; Murphy é implacável.)

Trabalho 2 - Análise Sintática

Você deve fazer um parser para programas escritos na linguagem Mini-0, especificada abaixo.

Assim como no Trabalho 1, o programa deve ser desenvolvido no seu repositório inf1715 do Github.

Quando você terminar o trabalho, marque a versão no servidor como a final: 

git tag trab2
git push --tags      # se você não passar esta flag, a tag não vai pro servidor!

Quaisquer dúvidas na operação com git (ou sobre o trabalho de maneira geral), contacte o professor!

Prazo: 04/04/2014, 23:59. Será considerado como o trabalho entregue o conteúdo do seu repositório com a tag trab2. Novamente, não deixe para o último minuto!

Trabalho 3 - Árvore Sintática Abstrata

Você deve construir uma árvore sintática abstrata para programas escritos na linguagem Mini-0, especificada abaixo.

Assim como nos trabalhos anteriores, o programa deve ser desenvolvido no seu repositório inf1715 do Github.

Quando você terminar o trabalho, marque a versão no servidor como a final: 

git tag trab3
git push --tags      # se você não passar esta flag, a tag não vai pro servidor!

Quaisquer dúvidas na operação com git (ou sobre o trabalho de maneira geral), contacte o professor!

Prazo: 16/04/2014, 23:59. Será considerado como o trabalho entregue o conteúdo do seu repositório com a tag trab3. Novamente, não deixe para o último minuto!

Trabalho 4 - Tabela de Símbolos e Verificação de Tipos

Você deve realizar a verificação de tipos de programas escritos na linguagem Mini-0 especificada abaixo, utilizando para isso uma tabela de símbolos como estrutura de dados interna.

Assim como nos trabalhos anteriores, o programa deve ser desenvolvido no seu repositório inf1715 do Github.

Quando você terminar o trabalho, marque a versão no servidor como a final: 

git tag trab4
git push --tags      # se você não passar esta flag, a tag não vai pro servidor!

Quaisquer dúvidas na operação com git (ou sobre o trabalho de maneira geral), contacte o professor!

Prazo: 30/04/2014, 23:59. Será considerado como o trabalho entregue o conteúdo do seu repositório com a tag trab4. Novamente, não deixe para o último minuto!

Trabalho 5 - Código intermediário

Você deve gerar código intermediário a partir de programas escritos na linguagem Mini-0 especificada abaixo, utilizando para isso a árvore sintática abstrata anotada que você produziu nos trabalhos anteriores.

Assim como nos trabalhos anteriores, o programa deve ser desenvolvido no seu repositório inf1715 do Github.

Quando você terminar o trabalho, marque a versão no servidor como a final: 

git tag trab5
git push --tags      # se você não passar esta flag, a tag não vai pro servidor!

Quaisquer dúvidas na operação com git (ou sobre o trabalho de maneira geral), contacte o professor!

Prazo: 27/05/2014, 02:00. Será considerado como o trabalho entregue o conteúdo do seu repositório com a tag trab5. Novamente, não deixe para o último minuto!

Trabalho 6 - Geração de Assembly Nativo

Neste trabalho você vai fazer o backend do compilador, que receberá como entrada código no formato de representação intermediária (conforme gerado pelo Trabalho 5) e produzirá como saída código assembly x86. Esta saída poderá então ser montada e linkada gerando um binário executável.

Critérios que serão empregados para avaliação:

  1. Repartição em blocos básicos - 1 ponto
  2. Levantamento de variáveis vivas ("próximo-uso") - 2 pontos
  3. Endereços de parâmetros e locais na pilha - 1 ponto
  4. Alocação de registradores - 2 pontos
  5. Geração de código referente às instruções - 3 pontos
  6. Tratamento de globais e strings nas instruções de mov - 1 ponto
  7. Análise e geração de instruções de spill - 1 ponto

(sim, o total dá 11)

Uma implementação do trabalho em Haskell está disponível como "pseudocódigo de referência".

Assim como nos trabalhos anteriores, o programa deve ser desenvolvido no seu repositório inf1715 do Github.

Quando você terminar o trabalho, marque a versão no servidor como a final: 

git tag trab6
git push --tags      # se você não passar esta flag, a tag não vai pro servidor!

Quaisquer dúvidas na operação com git (ou sobre o trabalho de maneira geral), contacte o professor!

Prazo: 20/06/2014, 23:59. Será considerado como o trabalho entregue o conteúdo do seu repositório com a tag trab6. Novamente, não deixe para o último minuto!

Linguagem Mini-0

A linguagem Mini-0 é uma linguagem bastante pequena, mas com um conjunto razoável de recursos para manipulação básica de inteiros, caracteres, booleanos e vetores. Ela oferece estruturas de controle if/else/end e while/loop; variáveis; funções com parâmetros e retorno de valores.

Além disso, nossa implementação gerará código objeto compatível com C, o que permitirá que programas Mini-0 possam chamar funções das bibliotecas padrão de C.

Léxico

Sintaxe

Descrição da sintaxe em formato EBNF, sem especificar precedência de operadores. Terminais estão listados em MAIÚSCULAS (quando representam tipos de tokens) ou como 'literais' quando representam a si mesmos. Em notação EBNF, [ x ] significa que x é opcional; { x } significa que x pode aparecer zero ou mais vezes. 

programa  → { NL } decl { decl }
decl      → funcao | global
nl        → NL { NL }
global    → declvar nl
funcao    → 'fun' ID '(' params ')' [ ':' tipo ] nl
               bloco
            'end' nl
bloco     → { declvar nl }
            { comando nl }
params    → /*vazio*/ | parametro { ',' parametro }
parametro → ID ':' tipo
tipo      → tipobase | '[' ']' tipo
tipobase  → 'int' | 'bool' | 'char' | 'string'
declvar   → ID ':' tipo
comando   → cmdif | cmdwhile | cmdatrib | cmdreturn | chamada 
cmdif     → 'if' exp nl
               bloco
            { 'else' 'if' exp nl
               bloco
            }
            [ 'else' nl
               bloco
            ]
            'end'
cmdwhile  → 'while' exp nl
               bloco
            'loop'
cmdatrib  → var '=' exp
chamada   → ID '(' listaexp ')'
listaexp  → /*vazio*/ | exp { ',' exp }
cmdreturn → 'return' exp | 'return'
var       → ID | var '[' exp ']'
exp       → LITNUMERAL
          | LITSTRING
          | TRUE
          | FALSE
          | var
          | 'new' '[' exp ']' tipo
          | '(' exp ')'
          | chamada
          | exp '+' exp
          | exp '-' exp
          | exp '*' exp
          | exp '/' exp
          | exp '>' exp
          | exp '<' exp
          | exp '>=' exp
          | exp '<=' exp
          | exp '=' exp
          | exp '<>' exp
          | exp 'and' exp
          | exp 'or' exp
          | 'not' exp
          | '-' exp

Observações

Bibliografia

Estou usando as edições mais novas dos livros na organização das aulas, mas as edições antigas talvez sejam mais facilmente encontradas nas bibliotecas da PUC e se mantêm geralmente relevantes.