Informações

Pré-requisito: Linguagens de Programação e Linguagens Formais e Autômatos

Ementa

Estrutura de um compilador; Análise léxica; Análise sintática; Análise semântica; Recuperação de erros; Geração de código intermediário.

Objetivos

Ao final da disciplina o aluno deve:

  • Compreender a teoria e as técnicas usadas na construção de compiladores;
  • Projetar e testar um compilador completo para uma linguagem algorítmica.

Conteúdo Programático

Sumário

  1. Visão Geral de um Compilador
  2. Análise Léxica
  3. Autômatos Finitos
  4. Flex/Lex
  5. Scanners
  6. Análise Sintática
  7. Yacc/Bison
  8. Código Intermedíario
  9. Analisador Sintático Descendente
  10. Analisador Sintático Ascendente
  11. Construção de um Compilador

Tópicos de Aula

01. Visão Geral de Um Compilador

Conteúdo
  • Estrutura de um compilador
  • Processadores de linguagens
  • Evolução das LPs
  • Fundamentos da LP
Materiais

02. Análise Léxica

Conteúdo
  • Arquitetura da análise léxica
  • Especificações de tokens
  • Erros léxicos
  • Operações sobre linguagens
  • Expressões Regulares
  • Definições Regulares
  • Extensões de ERs
Materiais

03. Autômatos Finitos

Conteúdo
  • Definição de Autômatos
  • Representação Gráfica
  • Representação Matricial
  • AFD e AFND
  • Aceitação de uma cadeia
  • Simulando um AFD e um AFND
  • Algoritmo de Thompson
  • ER para Autômato
  • Construção de Subconjunto
  • Minimização de Estados
Materiais

04. Flex/Lex

Conteúdo
  • Gerador de Scanner
  • Usando o flex
  • Especificações da entrada
  • Definições, Regras e Padrões
  • Regras de Matching
Materiais

05. Scanners

Conteúdo
  • Arquitetura de um Scanner
  • Scanner feito à mão
  • Scanner utilizando AFD e AFND
  • Eficiência
  • Projeto de um analisador de cadeia
  • Pares de Buffers
  • Casamento de Padrão

06. Análise Sintática

Conteúdo
  • Arquitetura
  • Hierarquia de Chomsky
  • Gramática Livre de Contexto
  • Derivações
  • Formas de Derivações
  • Árvore de Derivação
  • Ambiguidade
  • Análise Léxica vs Sintática
Materiais

07. YACC/Bison

Conteúdo
  • Arquitetura
  • Fluxo de Controle
  • Especificações
  • Declarações
  • Regras de Produção
Materiais

08. Código Intermedíario

Conteúdo
  • Processo de compilação
  • Linguagem de três endereços
  • Especificações
  • Comandos
Materiais

09. Analisador Sintático Descendente

Conteúdo
  • Ambiguidade
  • Análise Top-Down
  • Recursão à Esquerda
  • Lookhead
  • Parses Preditivos
  • First e Follow
  • Gramáticas LL(k) e LR(k)
  • Analisador de Descida Recursiva
  • Analisador Preditivo sem Recursão

10. Analisador Sintático Ascendente

Conteúdo
  • Handle
  • Parsers Shift-Reduce
  • Parsers LR(1)
  • Itens Canônicos
  • Autômato LR(0)
  • Tabela de Análise SLR

11. Construção de um Compilador

Conteúdo
  • Declaração
  • Tipo de dados primitivos
  • String
  • Matrizes
  • Expressões
  • Operadores
  • Comandos
  • Escopo
  • Blocos
  • Mecanismos de Controle de Laços
  • Detecção de Erros
  • Subprograma
Materiais

Referência Bibliográfica

Principal

  • SETHI, Ravi; ULLMAN, Jeffrey D.; MONICA S. LAM. Compiladores: princípios, técnicas e ferramentas. Pearson Addison Wesley, 2008.

Complementar

  • RICARTE, Ivan. Introdução à compilação. Elsevier Brasil, 2012.