Compiladores

1. Componente Curricular:

Compiladores.

2. Carga Horária:

60 horas

3. Objetivo:

Tendo como base a execução de atividades práticas e o desenvolvimento de produtos, apresentar ao estudante os principais conceitos relacionados a construção dos compiladores.

4. Ementa Oficial:

• • Estrutura do Compilador. Análise Léxica. Análise Sintática. Análise Semântica. Geração de Código Intermediário. Otimização. Geração de Código. Geradores de Analisadores Léxicos e Semânticos.

5. Conteúdo Programático:

1. Introdução

• • Conceitos Básicos e Estrutura dos Compiladores.

  • Visão Geral do Desenvolvimento dos Compiladores.

2. Análise Léxica

• • Conceitos Básicos e Expressões Regulares.

  • Autômatos Finitos e Reconhecedores.

3. Análise sintática

• • Gramática livre de contexto.

  • Análise sintática descendente.

  • Análise sintática ascendente.

4. Análise semântica

• • Verificação de Tipos e Análise Dirigida.

  • Gestão de Nomes e Tipos de Dados.

5. Geração de código

• • Modelos e Ambientes de Execução de Códigos.

  • Código Intermediário.

  • Geração de Código Intermediário.

6. Abordagem Metodológica:

Aprender fazendo e fazer aprendendo. As ações implementadas têm como foco o aprendizado do desenvolvimento de Compiladores pelo uso de recursos computacionais - privilegiando o projeto por simuladores e o desenvolvimento prático; seguido de exposições teóricas, apoiadas por: simulações, slides e vídeos. Em resumo, a metodologia tem como base a tríade Conteúdo, Atividade e Produto.

A nota final será dada pelas avaliações dos artefatos (relatório, lista de exercício - manuscritas, apresentação oral, pôster, postagem, vídeo, ...) produzidos durante as aulas e entregues em cada uma das datas especificadas. O aluno também será avaliado através de outros recursos, como p.ex. a frequência e a apresentação de artefatos não obrigatórios - os quais poderão até ter pontuação extra.

7. Plano de Aprendizado:

Aula 1

Conteúdo: 

• • • Conceitos Básicos e Estrutura dos Compiladores.

      • Compiladores - Da Teoria à Prática. (1.1 a 1.3)

      • Que es un compilador y como funciona?

Atividades: 

• • • Entendendo um compilador pela observação de suas Fases de Execução.

    • Discutindo a viabilidade da criação de um "compilador" do K&S Simulator  (ISA) para o 8 Bits Assembler.

      • Máquinas diferentes, mas de mesmo nível, podem ter compatibilidade na execução de atividades?

      • Diferenças nos modos de endereçamento de dados inviabilizam a tradução entre códigos de máquinas?

    • Avaliativas:

      • Especificar uma linguagem simples para cada máquina virtual. Observar as características de cada máquina (1.5 e 1.6).

        • Para uma máquina PC, desenvolver um "interpretador" para a linguagem especificada.

          • Iteração para leitura e processamento das instruções (funções), criando tabela de dados e etiquetas; ou

          • Usar uma linguagem como PHP (via "macro substituição" de código) para "compilar" para esta plataforma.

      • Criar uma máquina virtual "intermediária" a partir das máquinas citadas. Observar o melhor de cada máquina (1.4).

        • Especificar uma linguagem simples para esta máquina.

      • Criar um tradutor do  K&S Simulator  para o 8 Bits Assembler; e vice-versa.

Produtos:

• • • O Compilador JIT.

    • Debugging DLL Files with IDA Disassembler.

    • Compilador (O Programa Essencial de Todos os Programadores).

    • Compiladores (Play List).

Aula 2

Conteúdo: 

• • • Visão Geral do Desenvolvimento dos Compiladores.

      • Compiladores - Da Teoria à Prática. (1.4 a 1.6)

      • Basic LEX Programming tutorial.

      • LEX and YACC Program to recognize a valid arithmetic expression that uses operators +, -, * and /.

Atividades: 

• • • Observando a visão geral do compilador e do seu trabalho.

      • Uma nova visão para as suas Fases de Execução.

    • Ressaltando a complexidade do trabalho do compilador.

      • Em uma linguagem de alto nível podemos ter c = a * 2 + b;

      • Qual código de linguagem de máquina para o K&S, poderia ser equivalente a expressão anterior?

    • Avaliando o trabalho dos analizadores léxicos e sintáticos. Onde está o erro na imagem?

      • Adaptando a expressão anterior para uma inversão de prioridade como no exemplo: x = 2 * 7 + 3.

      • Como o compilador define as prioridades em uma expressão matemática? Explicando:

        • Entendendo a Notação infixa para pós-fixa.

        • Em exemplo com uma abordagem um pouco diferenciada.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Produzir tutoriais sobre: Lex, Yacc, Padrões e Gramáticas.

      • Lista de exercícios do capítulo 1.

Produtos: 

• • • lex - Online in the Cloud.

    • Lex & Yacc.

    • Programa de exemplo para os programas lex e yacc.

    • Ferramenta para o ensino de compiladores.

    • Um Back End Para O Desenvolvimento De Compiladores.

    • Compiler Explorer.

Aula 3

Conteúdo: 

• • • Análise Léxica: Conceitos Básicos e Expressões Regulares.

      • Compiladores - Da Teoria à Prática. (2.1)

      • Análise Léxica.

      • Conceitos de Linguagens de Programação e Análise Léxica.

      • Aprenda tudo sobre RegEx em menos de 10 minutos!

Atividades: 

• • • Observando a Visão Geral da Análise Léxica.

      • Listar os Tokens para a linguagem simples.

    • Identificando Tokens e reconstruindo a linha de comando a partir e uma "árvore léxica".

    • Construindo Expressões Regulares com o Regular Expression 101.

      • Referência Rápida para Expressões Regulares.

      • Expressões Regulares na Composição de Textos.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Objetivando minimizar o trabalho do analisador léxico, quais mudanças poderiam ser feitas na linguagem simples?

      • Criar um analisador léxico para a linguagem simples, ou para outra linguagem qualquer.

      • Desenvolver um aplicativo simplificado, e em português, semelhante ao Regular Expression 101.

Produtos: 

• • • Analisador Léxico - FLEX.

    • Análise Léxica - Aula Prática.

    • Usando Expressões Regulares na Linguagem C.

    • Expressões regulares (C++).

Aula 4

Conteúdo: 

• • Análise Léxica: Autômatos Finitos e Reconhecedores.

    • Compiladores - Da Teoria à Prática. (2.2 e 2.3)

    • Gerando Expressão Regular A Partir De Autômatos Finitos.

    • Flex (e Lex).

Atividades: 

• • • Gerando um Diagrama e uma Tabela de Transição, a partir de uma Expressão Regular.

      • Compiladores - Da Teoria à Prática. (2.2.1)

      • Uma alternativa ao autômato do livro.

    • Desenvolvendo um Analisador Léxico simples (para a STM 0.1), com implementações usando:

      • Programação orientada ao problema.

      • Programação orientada a "solução" com autômato finito.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Com relação a atividade anterior, desenvolver um Analisador Léxico para Programação orientada a "solução" com expressões regulares.

      • Lista de exercícios do capítulo 2.

Produtos: 

• • • Automaton Simulator.

    • Convert simple regular expressions to deterministic finite automaton.

    • Regular Expressions and Converting to a NFA.

    • Assembler para o Altair 8800 Simulator.

Aula 5

Conteúdo: 

• • • Revisão de conteúdos e 1ª Avaliação.

Atividades: 

• • • Apresentação e Avaliação de trabalhos.

Produtos: 

• • • Relatório de Produto 1 e/ou Prova Prática 1.

Aula 6

Conteúdo: 

• • • Análise sintática: Gramática livre de contexto.

      • Compiladores - Da Teoria à Prática.  (3)

      • Linguagem Livre De Contexto.

      • Gramáticas livres de contexto.

Atividades: 

• • • A Gramática Livre de Contexto (exemplo) no contexto das Linguagens na Hierarquia de Chomsky.

    • Reconhecendo declarações a partir de definições gramaticais e elementos léxicos: Trecho simplificado da gramática formal para a linguagem de programação C e uma derivação de um trecho de código C do símbolo não terminal. 

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Produzir uma Gramáticas para que um programa na linguagem simples (ou outra a sua escolha) seja avaliado pelo Yacc.

      • Lista de exercícios do capítulo 3.

Produtos: 

• • • Exercícios de Linguagens Livre de Contexto.

    • Exercícios de Gramática Livre de Contexto.

    • The Context Free Grammar Checker.

    • OneCompiler.

    • Listas, pilhas e filas em C++.

Aula 7

Conteúdo: 

• • • Análise sintática: Análise sintática descendente.

      • Compiladores - Da Teoria à Prática.  (4)

      • Análise Sintática Descendente Preditiva (Tabular).

      • Análise Sintática Top-Down preditiva Tabular.

Atividades: 

• • • Implementando o Algoritmo da Análise Sintática Descendente.

      • Quando existir, eliminar recursividade esquerda.

      • Montar a Tabela de Análise Sintática.

      • Criar a árvore sintática a partir da tabela.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Produzir uma Gramáticas para que um programa na linguagem simples (ou outra a sua escolha), de modo que esta seja usada em uma implementação de analisador sintático.

      • Lista de exercícios do capítulo 4.

Produtos: 

• • • Linguagens e Compiladores - Conceitos de Análise Sintática e Análise Sintática Descendente.

    • Análise Sintática Top-Down com Retrocesso (Backtraking).

    • CFG Developer.

    • Earley parser.

Aula 8

Conteúdo: 

• • • Análise sintática: Análise sintática ascendente.

      • Compiladores - Da Teoria à Prática.  (5)

      • Analisadores Ascendentes.

      • Análise Sintática Ascendente.

Atividades: 

• • • Detalhando o Algoritmo da Análise Sintática Ascendente.

      • Análise Sintática Bottom-up para Gramáticas LR.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Lista de exercícios do capítulo 5.

Produtos: 

• • • LR Parsing.

    • Análise Sintática.

    • Grammophone, a context-free grammar checker.

    • PLY (Python Lex-Yacc).

Aula 9

Conteúdo: 

• • • Análise semântica: Verificação de Tipos e Análise Dirigida.

      • Compiladores - Da Teoria à Prática.  (7.1 e 7.2)

      • Análise semântica.

      • Compiladores - Análise Semântica.

Atividades: 

• • • Definindo os papeis da Análise Semântica.

      • Verificar ou tratar o escopo (ou acesso) aos nomes (identificadores).

      • Verificar ou tratar os tipos de dados.

    • Detalhando algumas atividades das Verificações Estáticas.

      • Estática versus Dinâmica.

      • Validação de tipos de dados em expressões e em declarações de sub programas.

      • A verificação do fluxo de controle tem como foco os alvos das instruções de desvio incondicional.

      • Tags e outros modos para delimitar blocos também devem ser verificados.

      • Determinar o escopo de variáveis declaradas em estruturas de controle e blocos.

    • Resumindo o trabalho do Analisador Semântico.

      • Usa da árvore de sintaxe e da tabela de símbolos para verificar consistência.

      • Suporte para geração de código.

        • Exemplo de Código para Avaliar Expressões.

        • Uso de ferramentas para a automação do processo.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Lista de exercícios do capítulo 7 (7.1 a 7.3).

Produtos: 

• • • Compilador Bahtche - Análise Semântica.

    • Compiladores: Análise Semântica.

    • Um Tradutor Dirigido por Sintaxe.

Aula 10

Conteúdo: 

• • • Revisão de conteúdos e 2ª Avaliação.

Atividades: 

• • • Apresentação e Avaliação de trabalhos.

Produtos: 

• • • Relatório de Produto 2 e/ou Prova Prática 2.

Aula 11

Conteúdo: 

• • • Análise semântica: Gestão de Nomes e Tipos de Dados.

      • Compiladores - Da Teoria à Prática.  (7.3 e 7.4)

      • Tradução Direcionada Por Sintaxe No Design Do Compilador.

      • Análise Semântica - TDS - Tradução Dirigida por Sintaxe.

Atividades: 

• • • Revisando o Trabalho do Compilador.

    • Visão geral da Tradução Dirigida por Sintaxe.

      • A relação da Gramática com as Ações Semânticas e possibilita a geração da Árvore de Sintaxe Anotada.

        • Usar esta Gramática para fazer um programa que implemente a árvores para solução de problemas como: 2+4*6, 2*4+6 e 1*2+3*4.

        • Um exemplo para declarações de variáveis em C: Gramática e Árvore.

      • Exemplos de Árvores Sintática para suporte à Análise Semântica.

      • Exemplo de Árvore  Sintática para suporte à Tradução (código intermediário).

    • Observando alguns problemas para compilação.

      • Gestão de nomes (identificadores) no escopo dos programas.

      • Verificando compatibilidade de tipos: exemplo de Tabela de Compatibilidade.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Usar esta Gramática para fazer um programa que implemente a árvores para solução de problemas como: 2+4*6+8 e 2+4+6*8.

      • Lista de exercícios do capítulo 7 (7.4 a 7.6).

Produtos: 

• Parsing Preditivo.

• Desenvolvimento do Compilador da Linguagem Basico.

Aula 12

Conteúdo: 

• • • Geração de código: Modelos e Ambientes de Execução de Códigos.

      • Compiladores - Da Teoria à Prática.  (9)

      • Representação de dados.

      • Arquitetura de Computadores: IEEE 754.

      • Registros de Ativação.

Atividades: 

• • • Observando algumas dificuldades na gestão de memória da aplicação.

      • Diferença na alocação de dados das estruturas.

      • Variáveis Locais e herança múltipla gerando o problema da ambiguidade de nomes.

    • Verificando como valores são realmente armazenados por um computador.

      • Como são armazenados os ponteiros, vetores e estruturas?

        • Não é tão simples assim...

        • Passagem de parâmetros por valor e por referência. Um exemplo "funcional".

      • Como são realmente acessados os elementos de um vetor?

    • Descobrindo sobre os registros de ativação.

      • Quais os dados manipulados por uma função? Verificar pilha de dados da função.

      • O "referenciamento indireto" dificultando o controle dos dados passados por "valor". 

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Diferentemente de C, em Python é possível criar uma função dentro de outra. Crie um programa simples que faça isso.

      • Lista de exercícios do capítulo 9.

Produtos: 

• • • Sistemas Numéricos e a Representação Interna dos Dados no Computador.

    • IEEE 754 Floating Point Representation to its Decimal Equivalent.

    • Registros de ativação.

    • Ambientes De Tempo De Execução Em Design De Compilador.

Aula 13

Conteúdo: 

• • • Geração de código: Código Intermediário.

      • Compiladores - Da Teoria à Prática.  (10)

      • Geração de código e otimização. (9.1 e 9.2)

      • Geração de Código Intermediário.

Atividades: 

• • • Explorando a Geração de Código.

      • Tipos de código intermediário: HIR, MIR, LIR e EIR.

      • Representação de cada Tipo.

        • HIR e MIR: Árvore e grafo de sintaxe; Notações Pré e Pós Fixadas e Representações linearizadas.

        • LIR e EIR: Instruções Assembly.

      • Visão geral da Geração de Código.

        • Representação Intermediária.

        • Código de Três Endereços.

        • Representação linear de um Grafo Acíclico Dirigido.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Lista de exercícios do capítulo 10.

Produtos: 

• • • Three Address Code in Compiler Design.

    • Falando sobre JIT Compiler.

    • Building Abstract Syntax Trees.

Aula 14

Conteúdo: 

• • • Geração de código: Geração de Código Intermediário.

    • Compiladores - Da Teoria à Prática.  (11)

    • Geração de código e otimização. (9.3)

    • Construção de compiladores: Geração de código intermediário.

    • Linguagens e Compiladores - Código intermediário.

    • Otimização de Código.

    • Compiladores - Otimização de Código.

Atividades: 

• • • Gerando Código Intermediário.

      • Exemplo usando Código de Três Endereços.

      • Exemplo de código intermediário.

      • Comentários sobre chamadas de sistema em um código final real.

      • Exemplos e execução de códigos fontes, "intermediários", "otimizados" e "finais".

        • Expressão em modo pós-fixado.

        • Estruturas de Seleção e de Repetição.

        • Operação com vetores.

        • Execução de subprogramas.

    • Avaliativas:

      • Usar o apresentado hoje nas atividades já propostas.

      • Lista de exercícios do capítulo 11.

Produtos: 

• • • How to Build a C Compiler Using Lex and Yacc.

Aula 15

Conteúdo: 

• • • Revisão de conteúdos e 3ª Avaliação.

Atividades: 

• • • Apresentação e Avaliação de trabalhos.

Produtos: 

• • • Relatório de Produto 3 e/ou Prova  3.

8. Bibliografia Básica:

• • Alfred, V.A.; Lam, M.S.; Sethi, R.; Ullman, J.D. Compiladores: Princípios, Técnicas e Ferramentas. Pearson, 2a Edição, 2007.

  • Louden, K.C. Compiladores: Princípios e Práticas. Cengage, 2006.

  • Toscani, S.S.; Price, A.M.A. Implementação de Linguagens de Programação: Compiladores. Bookman, 3a Edição, 2008.