Compiladores II

Apresentação

Está é a página da disciplina Compiladores II do professor Fabio Mascarenhas, para o semestre de 2016.2. As aulas da disciplina são às segundas e quartas, das 10 às 12 horas, na sala DCC.

Objetivo e Ementa

O objetivo do curso é estudar alguns tópicos mais avançados em cada uma das fases principais de um compilador:

  • Métodos generalizados de análise sintática
  • Inferência de tipos em linguagens funcionais, polimorfismo paramétrico em linguagens OO (generics), e tipagem gradual em linguagens de script
  • Ambientes de execução gerenciados: máquinas virtuais, coleta de lixo e compilação Just-In-Time.

Avaliação

A participação nas aulas é obrigatória, e durante as aulas serão feitos exercícios em estilo coding Dojo. O aluno que tiver mais que 25% de reprovação será reprovado por falta. A presença e participação nas aulas valem 5,0 (cinco pontos) na média final

O segundo componente da avaliação, também valendo 5,0 (cinco pontos) na média final, será dada por um seminário em que cada aluno fará uma apresentação oral de 30 minutos sobre um artigo escolhido pelo aluno dentre um pool de artigos dado pelo professor.

Lista de Discussão

Estaremos reusando o grupo no Facebook de Compiladores I para perguntas e avisos sobre essa matéria. Acessem aqui.

Bibliografia

Os artigos abaixo cobrem alguns dos assuntos que são abordados no curso, embora eu muitas vezes modifique a ordem na qual os assuntos são apresentados:

Monadic Parsing in Haskell - combinadores de parsing “clássicos”

Parsec: Direct Style Monadic Parser Combinators For The Real World - combinadores de parsing determinísticos

Parsing Expression Grammars: A Recognition-based Syntactic Foundation - o artigo que introduz PEGs

On the Relation between Context-Free Grammars and Parsing Expression Grammars - uma formulação alternativa de PEGs, mais próxima de CFGs

A Text Pattern-Matching Tool based on Parsing Expression Grammars - PEGs para casamento de padrões, com a noção de capturas que vimos

Error Reporting in Parsing Expression Grammars - estratégias de detecção de erros em PEGs e combinadores de parsing determinísticos

Basic Polymorphic Typechecking - polimorfismo paramétrico e inferência de tipos, com uma implementação imperativa

Virtual Machines and Managed Runtimes - um curso com farto material online que entra em mais detalhes na implementação de linguagens através de máquinas virtuais

The Case for Virtual Register Machines e Virtual Machine Showdown: Stack Versus Registers - dois artigos que comparam a eficiência de uma máquina virtual de pilha versus de registradores, no contexto de uma JVM, e obtêm resultados similares.

Os três livros abaixo dão uma visão mais aprofundada de cada uma das grandes etapas de um compilador: análise sintática, verificação de tipos, geração de código.

“Parsing Techniques: A Practical Guide”, 2a. edição, de Dick Grune e Ceriel Jacobs.

“Types and Programming Languages”, de Benjamin Pierce.

“Engineering a Compiler”, 2a. edição, de Keith D. Cooper e Linda Torczon.

Finalmente, o livro abaixo dá uma série de dicas pragmáticas voltadas para a implementação de interpretadores para linguagens simples, voltado para quem não tem nenhum treinamento formal em construção de compiladores e linguagens de programação.

“Language Implementation Patterns”, de Terence Parr.

Notas de Aula

29/08 - Introdução, código Lua

31/08 - Tabelas, código Lua

05/09 - Erros, Módulos, Iteradores, código Lua

12/09 - Metatabelas, código Lua

14/09 - OO, código Lua

19/09 - Combinadores I, código Lua

21/09 - Combinadores II, código Lua

26/09 - Combinadores III, código Lua

28/09 - Combinadores e PEGs, código Lua

03/10 - PEGs em PEGs, código Lua

05/10 - Erros de Sintaxe, código Lua

10/10 - SmallLua - Parser, código Lua

24/10 - Tipos Estáticos, código Lua

26/10 - Tipos de Sequências, código Lua

31/10 - Polimorfismo Paramétrico, código Lua

07/11 - Unificação e Inferência, código Lua

09/11 - Inferência e Sobrecarga, código Lua

16/11 - Máquinas Virtuais, código C/Lua

21/11 - Funções Simples em VMs, código C/Lua

23/11 - Escopo Léxico com Árvores de Ambientes, código C/Lua

28/11 - Escopo Léxico com Displays, código C/Lua

Trabalhos

Coletor de Lixo

Compilador JIT

Lua

Vários algoritmos vistos no curso serão apresentados em Lua, uma linguagem de script simples e muito fácil de aprender. Essa página faz um resumo da linguagem que é útil para quem já tem boa desenvoltura em programação (especialmente em outra linguagem de script como Python, Ruby ou JavaScript). As notas de aula de um curso de Lua dão um material mais detalhado, e o manual de referência e o livro Programming in Lua vão mais a fundo.

Se você está em Windows, pode baixar um interpretador Lua (um executável, uma DLL, e uma bibilioteca para linkar com código C) aqui. Descompacte e chame lua.exe no prompt de comando. Todas as distribuições Linux têm interpretadores Lua disponíveis nos seus gerenciadores de pacotes.


Última Atualização: 2016-12-05 17:40