Introdução aos Compiladores

Prévia do material em texto

COMPILADORES – COM590 
Prof. Dr. Júlio Cezar Estrella 
Acompanhamento da Oferta 
Professor Associado no Instituto de Ciências Matemáticas e de Computação da Universidade de São 
Paulo (ICMC/USP) e Livre-Docente pela mesma instituição. Possui Doutorado e Mestrado em Ciências 
de Computação e Matemática Computacional pela Universidade de São Paulo (USP) e Graduação em 
Ciência de Computação pela Universidade Estadual Paulista “Júlio de Mesquita Filho” (Unesp). Suas 
linhas de pesquisa incluem: Provisionamento Dinâmico de Recursos Computacionais em Sistemas 
Distribuídos, com destaque para aplicações no contexto de: Internet das Coisas, Smart Cities e Smart 
Building, Cloud Computing, Virtualização, Microsserviços e SOA. Desenvolve também pesquisa com 
foco na otimização de aplicações distribuídas e em processamento de alto desempenho. 
 
1 
Introdução aos Compiladores 
 
Nesta semana, vamos mergulhar no fascinante mundo dos compiladores, destacando a sua relevância e 
importância para a computação e as aplicações que utilizamos no cotidiano. É importante entender como 
esses conceitos estão interconectados, pois são fundamentais para a compreensão da construção de 
linguagens de programação e processos de compilação. Durante esta jornada, você desenvolverá as 
seguintes habilidades e competências: compreensão dos princípios dos compiladores e aplicação prática 
desses conhecimentos em cenários reais. 
Objetivos de aprendizagem 
Ao final dessa semana, você deverá ser capaz de: 
• Definir o que são compiladores e sua função essencial; 
• Reconhecer a relevância dos compiladores no processo de desenvolvimento de software; 
• Aplicar os conceitos aprendidos para interpretar problemas práticos. 
 
Desafio 
Imagine que você está desenvolvendo uma nova linguagem de programação e precisa criar um 
compilador para traduzir o código escrito nessa linguagem em código de máquina. Como ponto de partida, 
gostaríamos que você refletisse sobre as seguintes questões: 
• Qual é o papel de um compilador no processo de desenvolvimento de software? 
• Quais são os principais componentes de um compilador e como eles se relacionam? 
• Quais são os desafios comuns que os desenvolvedores enfrentam ao criar um compilador? 
• Como a compreensão dos compiladores pode impactar positivamente a sua carreira como 
programador(a)? 
 
 
Revisitando Conhecimentos 
Para um melhor entendimento desta semana, é importante possuir conhecimentos prévios em: 
• Vídeo de apoio: Introdução à programação do zero | O Universo da Programação 
• Vídeo de apoio: Estrutura de Dados - Aula 1 - Apresentação da disciplina | Univesp 
Vídeo sobre linguagens de programação. 
 
Orientação de estudos 
Aprofunde-se nos conceitos da seguinte forma: 
https://ava.univesp.br/bbcswebdav/pid-1552359-dt-content-rid-17802289_1/courses/COM590-2024S1B2-T001/COM590/S1.html#tab-1
https://ava.univesp.br/bbcswebdav/pid-1552359-dt-content-rid-17802289_1/courses/COM590-2024S1B2-T001/COM590/S1.html#tab-2
1. Primeiro, assista à videoaula “Introdução aos Compiladores - Parte 1”, que traz uma introdução aos 
compiladores e sua importância no processo de desenvolvimento de aplicações. 
2. Prossiga e assista à videoaula “Introdução aos Compiladores - Parte 2”, para entender os princípios 
que permitem construir compiladores. 
3. Em seguida, assista à videoaula “Introdução aos Compiladores - Parte 3”, para conhecer a estrutura de 
um compilador, identificadores e operadores. 
4. Ao terminar de assistir às videoaulas, faça a leitura dos textos-base indicados. 
5. Para aprofundar o assunto, prossiga escolhendo um dos materiais de apoio. 
6. Leia o Desafio e o escopo do Fórum Temático, depois procure discutir com seus colegas o assunto. 
7. Teste seus conhecimentos sobre o assunto fazendo os Exercícios de Apoio propostos. 
8. Em seguida, faça a Atividade Avaliativa da semana. 
Bons estudos! 
 
COMPILADORES 
Introdução aos Compiladores 
 
Parte 1 
 
ROTEIRO 
• Organização de um computador 
• Linguagens de Programação 
• Execução de um programa 
• Tradução 
• Comparação entre as traduções 
 
ORGANIZAÇÃO DE UM COMPUTADOR 
 
Um computador tradicional é composto por: 
● Unidades de entrada 
● Memórias secundárias 
● Memória cache 
● Registradores 
● Unidade Lógica e Aritmética 
● Unidade de controle 
● Memória RAM e Memória ROM 
● Unidades de Saída 
 
LINGUAGENS DE PROGRAMAÇÃO 
 
Uma linguagem de programação é definida como: 
● Conjunto de símbolos e comandos que são usados para criar programas 
● É uma forma padronizada para expressar instruções para um computador 
● É por meio da linguagem de programação que conseguimos nos comunicar com o computador, de modo que este 
compreenda e execute o que o programador determina 
Uma linguagem de programação é formada por: 
● Sintaxe 
● Forma ou estrutura das expressões 
● Semântica 
● Fornece significado às expressões 
 ● Sintaxe 
● Determina regras de como se escreve corretamente em uma linguagem 
● Exemplo 1: 
● As pessoas gostam de carinho. (Sintaticamente correta) 
● As pessoa gosta de carinho (Sintaticamente incorreta) 
● Exemplo 2 
● Considere comandos na linguagem C 
● Int Idade; // erro: Int 
● int idade // erro: falta ; 
● São comandos sintaticamente incorretos, no contexto da linguagem C. 
● Semântica 
● Está relacionada ao significado das palavras ou frases 
● Veja os comandos na linguagem C 
● int numero; 
● numero = 10; 
● São comandos sintática e semanticamente corretos 
● Agora, considere os comandos também em linguagem C 
● int idade; 
● idade = 12.5 // este comando de atribuição está semanticamente incorreto 
 
EXECUÇÃO DE UM PROGRAMA 
 
Todo programa de computador é organizado na memória em três blocos: 
● Segmento de código 
● Envolve instruções do programa (tamanho e conteúdo fixo) 
● Segmento de dados 
● Envolve variáveis globais (tamanho fixo e conteúdo variável) 
● Segmento de pilha 
● Envolve variáveis locais e parâmetros (tamanho e conteúdo variáveis) 
 
TRADUÇÃO 
● Processo que consiste em converter linguagem de programação para a linguagem de máquina 
● Os tipos de traduções conhecidas envolvem: 
● Compilador 
● Interpretador 
● Linguagem de alto nível (Compilação/Interpretação)→ Linguagem de máquina 
 
● Compilador 
● Transforma todo o código-fonte para código executável de uma só vez 
● Isso ocorre uma única vez 
● Fluxo 
● Editor de texto → Código-Fonte → Compilador (anexa bibliotecas) → código executável → CPU (fase de execução) 
 
● Interpretador 
● Transforma os comandos do código-fonte para uma ou mais instruções do código executável 
● Isso ocorre toda vez que o código-fonte é executado 
 
COMPARAÇÃO ENTRE AS TRADUÇÕES 
● Compilação 
● Execução mais rápida 
● Menos portável 
 
● Interpretação 
● Execução mais lenta 
● Mais portável 
 
 
Introdução aos Compiladores 
Parte 2 
ROTEIRO 
• O que é um compilador? 
• Por que estudar compilador? 
• História 
• O processo de compilação 
• A importância dos compiladores na programação 
 
O QUE É UM COMPILADOR ? 
● Um compilador é um tradutor de programas de uma linguagem de programação para outra 
● Traduz de uma linguagem de alto nível para uma linguagem de baixo nível 
● É a principal técnica para implementação de linguagens 
 
POR QUE ESTUDAR? 
● Compiladores são ferramentas de cientistas e engenheiros 
● As técnicas de compilação se aplicam a projetos de programas 
● Editores de texto 
● Teste de programas 
● Desenho de figuras 
● Parte integrante de diversas outras disciplinas 
● Linguagens de programação 
● Engenharia de software 
● Arquitetura de computadores 
 
HISTÓRIA 
● Fase 1: Nos primórdios da computação, a programação era feita em código de máquina 
● Fase 2: Programação em linguagem de montagem 
● Mais fácil de programar, mas precisa de um montador 
● Fase 3: Linguagens de mais alto nível 
● Primeiros compiladores surgiram no início dosanos 50 
● Trabalhos iniciais consistiam em traduzir fórmulas aritméticas em códigos de máquina 
● Eram considerados muito complexos para se construir 
● Na sequência foram: 
● Criadas técnicas sistemáticas para construir compiladores 
● Desenvolvidas boas linguagens de programação e ambiente de programação 
● 1957 – Fortran 
● Usado para processamento de expressões aritméticas e fórmulas 
● 1960 – Algol 
● Primeira definição formal de linguagem, com gramática, estrutura de blocos, recursão 
● 1970 – Pascal 
● Definição de tipos pelos usuários 
● 1985 – C++ 
● Orientado a objetos e tratamento de exceções 
● 1995 – Java 
● Traduz bytecodes para código de máquina e executa 
 
EXEMPLOS DE COMPILADORES 
● Javac 
● GCC 
● Fortran 
● GNU Pascal 
● Turbo Pascal 
● PHPlanger 
● Rustc 
 
O PROCESSO DE COMPILAÇÃO 
● A tarefas de um compilador envolvem: 
● Transformar a linguagem fonte em uma linguagem alvo (objeto) equivalente 
● Deve informar os erros do programa fonte, caso haja tais erros 
● Permitir que os programas sejam independentes de máquina (portabilidade) 
● As propriedades de um compilador envolvem: 
● Gerar corretamente o código 
● Capacidade de tratar programas de qualquer tamanho permitido pela memória 
● Que seja razoavelmente simples de utilizar 
● Que o código gerado seja rápido, veloz 
● Estrutura geral de um compilador 
 
 
● Podemos considerar o processo de compilação em 3 fases: 
● Frontend: Envolve análise léxica, análise sintática e análise semântica. É uma fase que lida com a linguagem fonte 
● Backend: Lida com a geração de código de máquina e envolve: seleção de instruções e alocação de registros, 
otimização de código 
● Intermediária: Independe da linguagem fonte e do código de máquina 
 
Introdução aos Compiladores 
Parte 3 
ROTEIRO 
● Fases do Compilador 
● Analisador Léxico 
● Analisador Sintático 
● Analisador Semântico 
● Tabela de Símbolos 
● Gerador de Código Intermediário 
● Otimizações 
● Gerador de Código 
 
FASES DO COMPILADOR 
● Analisador Léxico 
● É uma interface entre o programa fonte e o compilador 
● Funções básicas envolvem 
● Ler o programa fonte 
● Agrupar caracteres em itens léxicos (chamados de tokens): 
● identificadores 
● palavras reservadas 
● constantes (números e letras) 
● símbolos especiais 
● Analisador Léxico 
● Funções básicas envolvem (cont.) 
● Ignorar elementos sem valor sintático 
● Espaços em branco, comentários, caracteres de controle 
● Detectar erros léxicos 
● Símbolos inválidos e elementos malformados 
● Exemplo x:=x+y*10 
<x, id1> < :=,:=> < x, id1> < +,op> <y, id2> <*,op> <10, num> 
 
● Analisador Sintático 
● Verifica a formação do programa 
● Funções básicas envolvem: 
● Agrupamento de tokens em estruturas sintáticas (expressões, comandos, declarações) 
● Verifica se a sintaxe da linguagem na qual o programa foi escrito está sendo respeitada 
● Detectar erros sintáticos 
● Exemplo 
● <x, id1> < :=,:=> < x, id1> < +,op> <y, id2> <*,op> <10, num> 
● Comando-atribuição →id1 := id1 op id2 op num 
● Analisador Semântico 
● Semântica = Significado = Sentido lógico 
● Funções básicas envolvem 
● Verificar se as construções no programa fonte estão semanticamente corretas 
● Detectar erros semânticos 
● Obter informações do programa fonte que permitam a geração do código 
● Verificações mais comuns 
● Análise de escopo: declaração de variáveis 
● Compatibilidade de tipos 
● Coerência entre declaração e uso de identificadores 
● Exemplo 
● id1 := id1 op id2 op num 
● (id1)int := (id1 op id2 op num)int 
● busca_tabela_símbolos (id1) = VERDADEIRO 
● busca_tabela_símbolos (id2) = VERDADEIRO 
● Tabela de Símbolos 
● É uma estrutura em que são armazenadas as informações relevantes sobre cada identificador utilizado no 
programa fonte 
● Atributos mais usuais: 
● nome 
● endereço relativo 
● categoria 
o variável (simple – tipo), (array – dimensão) 
o constante (tipo e valor) 
o procedimentos 
● função 
● número de parâmetros 
● Gerador de código intermediário 
● Envolve a geração de um conjunto de instruções (equivale ao programa fonte de entrada) para uma máquina 
virtual (hipotética) 
● id1 := id1 op id2 op num 
 
 ● temp1 := id2 * 10 
● temp2 := id1 + temp1 
 ● id1 := temp2 
x:=x+y*10 
 
● Otimizações 
● Funções básicas envolvem 
● Melhorar o código de modo que a execução seja mais eficiente quanto ao tempo ou espaço ocupado 
● Otimizações mais usuais 
● Agrupar subexpressões 
● Alocação ótima de registradores 
● Eliminação de desvios para a próxima instrução 
● Exemplo 
● temp1 := id2 * 10 
 ● temp2 := id1 + temp1 
 ● id1 := temp2 
● temp1 := id2 * 10 
 ● id1 := id1 + temp1 x:=x+y*10 
● Geração de Código 
● Funções 
● Converter o programa fonte para uma sequência de instruções de uma máquina real 
● A conversão pode ser feita diretamente ou a partir da representação do código intermediário 
● A sequência de instruções pode ser em assembler ou código de máquina) 
● temp1 := id2 * 10 
● id1 := id1 + temp1 
 
 ● MOV id2 R1 
 ● MULT 10 R1 
 ● MOV id1 R2 
 ● ADD R1 R2 
 ● MOV R2 id1 
 
FERRAMENTA 
● Acessem a ferramenta online a seguir para verificar como o programa fonte é convertido para uma sequência de 
instruções de uma máquina real 
● https://godbolt.org/ 
 
Semana 1 - Fórum Temático 
 
A importância e relevância dos compiladores para a computação 
Considerando sua experiência como estudante de computação, como você vê a importância dos compiladores no 
contexto da programação moderna? Eles são apenas "máquinas de tradução" ou existem aspectos mais profundos a 
serem explorados? Compartilhe suas ideias, experiências e perspectivas sobre o tema, e debata sobre o papel crítico 
que os compiladores desempenham no desenvolvimento de software. 
 
Exercícios de apoio 
1. Assinale a alternativa correta que indica qual é a principal função de um compilador em 
relação a uma linguagem de programação. 
a. Interpretar o código-fonte diretamente para a execução. 
b. Traduzir o código-fonte em linguagem de máquina. 
c. Verificar a correção lógica do código-fonte. 
d. Melhorar o desempenho do código-fonte. 
e. Fornecer uma interface de desenvolvimento integrada (IDE). 
 
 
2. Qual é a principal vantagem de usar um compilador em vez de um interpretador em 
linguagens de programação? Escolha a alternativa correta. 
a. Compiladores são mais fáceis de desenvolver. 
b. Compiladores executam o código mais rapidamente. 
c. Interpretadores geram código de máquina diretamente. 
d. Compiladores facilitam a depuração de código. 
e. Interpretadores geram executáveis independentes. 
 
ATIVIDADE AVALIATIVA 
PERGUNTA 1 
Considere as alternativas a seguir e escolha apenas aquela que define o que é um "analisador léxico" em um 
compilador. 
 
a. Um componente que gera o código executável a partir do código-fonte. 
 
b. Um componente que verifica a sintaxe do código-fonte. 
 
c. Um componente que remove comentários e espaços em branco do código-fonte. 
 
d. Um componente que otimiza o código-fonte para melhor desempenho. 
 
e. Um componente que verifica se as variáveis no código-fonte estão declaradas. 
 
PERGUNTA 2 
Considere o processo de compilação de um programa e analise as afirmações para, em seguida, assinalar a 
alternativa correta. 
I. A execução do programa faz parte do processo de compilação. 
II. A execução do programa é uma etapa separada após a compilação 
III. Na análise léxica, os caracteres são lidos e, depois, agrupados em conjuntos que são relevantes para 
outros componentes do compilador. 
IV. Na análise semântica, são analisados erros sintáticos de um programa. 
 
a. Apenas II e IV estão corretas. 
 
b. Apenas I e III estão corretas. 
 
c. Apenas I e IIestão corretas. 
 
d. Apenas I, II e III estão corretas. 
 
e. Apenas II e III estão corretas.