Compiladores II

Apresentação

Está é a página da disciplina Compiladores II do professor Fabio Mascarenhas, para o semestre de 2014.2. As aulas da disciplina são às terças e quintas, 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 quatro fases de um compilador:

  • Métodos generalizados de análise sintática (GLR, GLL, SGLR, PEGs)
  • Inferência de tipos em linguagens funcionais, polimorfismo paramétrico em linguagens OO (generics), e tipagem gradual em linguagens de script
  • Representação intermediária com Static Single Assignment (SSA) e otimizações usando a forma SSA.
  • Ambientes de execução gerenciados: máquinas virtuais, coleta de lixo e compilação Just-In-Time.

Avaliação

A presença é obrigatória em pelo menos 75% das aulas, ou o aluno será reprovado por falta.

A avaliação se dará 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. Os artigos são os seguintes:

OMeta: an Object-Oriented Language for Pattern Matching - uma ferramenta que generaliza o uso de PEGs para uso em dados estruturados ao invés de sequências, junto com recursos que permitem o reuso e extensão de gramáticas

Making the future safe for the past: Adding Genericity to the Java Programming Language - uma descrição da proposta do que acabou sendo a implementação de tipos genéricos ou parametrizados para a linguagem Java

Virtual-Machine Abstraction and Optimization Techniques - discussão de alto nível de várias técnicas para otimização de interpretadores, em especial em como técnicas mais antigas se comportam no hardware moderno

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 estamos abordando 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

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, otimizaçã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

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

19/08 - Lua (tabelas), código Lua

21/08 - Lua (erros, módulos, closures), código Lua

26/08 - Lua (iteradores), código Lua

28/08 - Lua (metatabelas e OO), código Lua

02/09 - sequências, scanner “genérico”

04/09 - Combinadores de parsing, código

09/09 - Combinadores de parsing (2), código

11/09 - Parsers determinísticos, PEGs, código

18/09 - PEGs - sintaxe e ações semânticas, código

23/09 - PEGs - capturas, código

25/09 - Erros em parsers determinísticos e PEGs, código

30/09 - SmallLua - sintaxe, código

09/10 - Funções por casos, código

14/10 - Verificação de tipos - tipos simples

16/10 - Verificação de tipos - sequências, código

30/10 - Verificação de tipos - sequências, código

04/11 - Verificação de tipos - polimorfismo, código

06/11 - Verificação de tipos - unificação, código

13/11 - Verificação de tipos - inferência, código

18/11 - Verificação de tipos - sobrecarga, código

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 manual de referência (versão para impressão) 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-01-31 15:51