Compiladores.
60 horas
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.
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.
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.
Desenvolvimento do Analisador.
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.
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 relação prática entre Conteúdos, Atividades e Produtos. Neste contexto, o conteúdo é toda base de conhecimento necessária a aula; a atividade é tida ação de aprendizado e; o produto é qualquer produção prática e/ou teórica sobre o conteúdo, podendo até ser uma aplicação deste ou até mesmo uma ação de aprendizado com escopo expandido.
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.
Conteúdo:
Conceitos Básicos e Estrutura dos Compiladores.
Atividades:
Conversando sobre as Linguagens Formais.
BNF (Simbologia) e EBNF (Exemplo) usados descrição sintática.
Entendendo o Compilador e a Compilação.
Análise Léxica identifica Tokens pela implementação de Autômatos Finitos.
Uso de Gramáticas para Validação de Estruturas Sintáticas.
GLCs para implementando Derivação Sintática.
Análise Semântica identificando Estruturas Sintáticas para Geração de Código.
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: Em equipes de 3 a 5 alunos, selecionar uma instrução de controle de fluxo (de uma linguagem de programação qualquer) e desenvolver especificações BNF e EBNF para a instrução selecionada. Ao término da atividade prática, desenvolva um Relatório (Roteiro) da atividade, com foco na comparação entre as especificação. PS: o relatório fará parte do trabalho prático da primeira avaliação.
Produtos:
Conteúdo:
Visão Geral do Desenvolvimento dos Compiladores.
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.
Adaptando a expressão anterior para uma inversão de prioridade como no exemplo: a = b * c + d.
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.
Avaliativa: Produzir tutoriais sobre: Lex, Yacc, Padrões e Gramáticas.
Produtos:
Conteúdo:
Análise Léxica: Conceitos Básicos e Expressões Regulares.
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.
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:
Conteúdo:
Análise Léxica: Desenvolvimento do Analisador.
Atividades:
... Autômatos Finitos e Reconhecedores.
...
Gerando um Diagrama e uma Tabela de Transição, a partir de uma Expressão Regular.
Desenvolvendo um Analisador Léxico simples (para a STM 0.1), com implementações usando:
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:
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.
Conteúdo:
Análise sintática: Gramática livre 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:
Conteúdo:
Análise sintática: Análise sintática descendente.
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:
Conteúdo:
Análise sintática: Análise sintática ascendente.
Atividades:
Detalhando o Algoritmo da Análise Sintática Ascendente.
Avaliativas:
Usar o apresentado hoje nas atividades já propostas.
Lista de exercícios do capítulo 5.
Produtos:
Conteúdo:
Análise semântica: Verificação de Tipos e Análise Dirigida.
Atividades:
Definindo os papeis da Análise Semântica.
Detalhando algumas atividades das Verificações Estáticas.
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:
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.
Conteúdo:
Análise semântica: Gestão de Nomes e Tipos de Dados.
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.
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.
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:
Conteúdo:
Geração de código: Modelos e Ambientes de Execução de Códigos.
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?
Passagem de parâmetros por valor e por referência. Um exemplo "funcional".
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:
Conteúdo:
Geração de código: Código Intermediário.
Compiladores. (4.1)
Geração de código e otimização. (9.1 e 9.2)
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.
Avaliativas:
Usar o apresentado hoje nas atividades já propostas.
Lista de exercícios do capítulo 10.
Produtos:
Conteúdo:
Geração de código: Geração de Código Intermediário.
Atividades:
Exemplo usando Código de Três Endereços.
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".
Avaliativas:
Usar o apresentado hoje nas atividades já propostas.
Lista de exercícios do capítulo 11.
Produtos:
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.
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.