UFJF - Universidade Federal de Juiz de Fora

Plano de ensino

Disciplina: DCC045 - TEORIA DOS COMPILADORES

Créditos: 4

Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE

Ementa -Introdução
-Análise léxica
-Análise sintática
-Análise semântica
-Ambientes de execução
-Geração de representação intermediária
-Geração de código de máquina para MIPS ou PENTIUM
Conteúdo 1) Introdução
A estrutura dos compiladores modernos: front-end, middle-end, back-end. Compiladores de um, dois e três passos.

2) Análise léxica
Operações com expressões regulares. Reconhecimento de linguagens regulares com autômatos finitos. Construção de autômatos finitos deterministas a partir de expressões regulares. Geradores de varredores léxicos.

3) Análise sintática
Sintaxe livre de contexto. Formas de derivação de strings e a árvore de sintaxe concreta. Precedência em expressões aritméticas. Eliminação de ambigüidade e de recursão à esquerda. Gramáticas LL(1) e LR(1). Derivação top-down. Derivação preditiva: fatoração à esquerda. Derivação recursiva: descendente e por tabelas de derivação. Recuperação de erros: o conjunto SYNCH. Gramáticas LL(K). Derivação bottom-up. Formas sentencias à esquerda e definição de manipuladores. Implementação por pilha: derivadores shift-reduce. Gramáticas LR(K). Construção de tabelas LR(0), SLR(1), LR(1), LALR(1)

4) Análise semântica
Problemas sensíveis ao contexto. Ações semânticas em derivadores LL e LR. Gramáticas de atributos. Grafo de dependência de atributos. Estrutura e organização de tabelas de símbolos. Aninhamento léxico e regras de escopo. Descritores de tipos: formas de compatibilidade. Verificação e conversão de tipos em expressões. L-values e R-values. Representação intermediária para análise semântica: árvore de sintaxe abstrata.

5) Ambientes de execução
Classes de armazenamento e acesso a dados não locais. Registros de ativação. Funções de mais alta ordem . Pilha de execução: criação e manipulação de registros de ativação.

6) Geração de representação intermediária
Tipos de representação intermediária: árvores de sintaxe abstrata, grafo acíclico direcionado, grafo de controle do fluxo, código de três endereços. Regras semânticas para geração de código intermediário: atribuição e expressões, desvio de controle, declarações. Tradução em árvores de sintaxe abstrata. Reorganização do código intermediário: árvores canônicas, blocos básicos, aglomerados seqüenciais.

7) Geração de código de máquina para MIPS ou PENTIUM
Seleção de instruções. Análise de tempo de vida: grafos de fluxo do controle, grafos de interferência. Alocação de registradores: coloração de grafos, coalescência. Exemplo de otimização de laços.
Bibliografia - ANDREW, W. A.; PALSBERG, J. Modern Compiler Implementation in Java, Cambridge University Press, 2002
- AHO, A.; SETHI, R.; ULMAN J. Compilers: Principles Techniques and Tools. Addison-Wesley, 1995. (versão em inglês)
Bibliografia (continuação)
Bibliografia complementar
Voltar