Aula 01 - COMPILADORES - Estácio

Prévia do material em texto

COMPILADORES
AULA 01
COMPILADORES
Aula 01
COMPILADORES
AULA 01
Apresentação da Disciplina
Professor: Marcus Pantoja da Silva
E-mail: marcus.pantoja@estacio.br
mailto:marcus.pantoja@estacio.br
COMPILADORES
AULA 01
Plano de Ensino
Unidade 1 – Introdução aos conceitos básicos
O processo de compilação
Passos da compilação
Função do compilador
A arquitetura geral de um compilador
Estrutura funcional de um compilador
Unidade 2 – Análise Léxica
Papel do analisador léxico
Especificação e reconhecimento de tokens
Analisador léxico como autômato finito
Ações semânticas do analisador léxico
Linguagem para especificação de analisadores léxicos
Projeto de um analisador léxico
COMPILADORES
AULA 01
Sumário
• Conceito de compilador
• O Modelo de compilação de Análise Síntese
• Contexto de um Compilador
• Análise Léxica
• Análise Sintática
• Análise Semântica
• Fases de um Compilador
COMPILADORES
AULA 01
Conceito de Compilador
• Um compilador pode ser entendido com um programa que
lê um programa escrito em uma linguagem (linguagem
fonte) e o traduz em um programa equivalente numa outra
linguagem (linguagem alvo).
CompiladorPrograma fonte Programa alvo
Mensagens de erro
Figura 1: Conceito de compilador
COMPILADORES
AULA 01
Funcionalidades
• Facilitar a programação (abstração)
• Checar certos tipos de erros e
vulnerabilidades
• Gerar código portável
• Otimizar código
• Velocidade, tamanho, etc
COMPILADORES
AULA 01
Exemplo de Erros
• Erro de sintaxe
• Variável não declarada
• Variável não inicializada
• Código inalcançável
• Erro léxico
• Número ou tipo de argumentos inválidos
em chamada de função
COMPILADORES
AULA 01
História dos compiladores
• Os compiladores começaram a desenvolver em
1955
• Anteriormente os códigos eram desenvolvidos
diretamente em linguagem de máquina.
• Rapidez de execução versus desenvolvimento complicado
• Necessidade de um montador
• Linguagens de mais alto nível
COMPILADORES
AULA 01
História dos compiladores
• Primeiros compiladores começaram a surgir na
década de 70
• Trabalhos iniciais: Realizam de tradução de
fórmulas aritméticas em código de máquina
• Compiladores eram considerados programas de
alta complexidade
• Primeiro compilador: Fortran (permitia a
declaração de identificadores com até seis
caracteres)
▪ FORmula TRANslation System
COMPILADORES
AULA 01
História dos compiladores
FORmula TRANslation System
COMPILADORES
AULA 01
História dos compiladores
• A partir de então foram desenvolvidas várias
técnicas sistemáticas para compiladores
• Reconhecimento de cadeias, gramáticas, geração de
linguagem.
• Desenvolveram-se várias linguagens de alto nível
• C, C++, Java, Linguagens visuais
COMPILADORES
AULA 01
História dos compiladores
• Desenvolvimento de programas para produção automática de
compiladores
➢ lex, flex
✓ Lex: Gerador de analisadores léxicos (UNIX)
✓ Flex: Gerador de analisadores léxicos (LINUX / Windows)
✓ Entrada: Arquivo de descrição do analisador léxico
✓ Saída: Programa em linguagem C que realiza a análise léxica
➢ Outros geradores de analisadores
✓ TPly – TP Lex /Yacc: Gera um programa em Pascal
✓ JavaCC: Para linguagem Java
✓ JFlex
✓ Flex++: Para linguagem C++
COMPILADORES
AULA 01
Compilador, interpretador e máquina virtual
Compilador
Prog. Fonte
Entrada de Dados
Prog. Objeto Saída
Ex: Pascal, 
C, C++
Interpretador
Prog. Fonte
Saída
Ex: PHP, 
javascript
Entrada
Compilador
Prog. Fonte
Entrada de Dados
Saída Ex: JavaMáquina 
Virtual
Cód. Intermediário
bytecode
COMPILADORES
AULA 01
O modelo de compilação de Análise e Síntese
• Podemos dividir a compilação em duas partes: análise e
síntese:
• Análise: Divide o programa fonte nas partes constituintes
criando uma representação intermediária.
• Síntese: Constrói o programa alvo a partir da representação
intermediária.
Figura 2: O Modelo de análise e síntese
COMPILADORES
AULA 01
O modelo de compilação de Análise e Síntese
Na fase de análise, as operações que são realizadas pelo
programa, são organizadas em uma forma hierárquica em
formato de árvore.
Muitas vezes é utilizada um tipo de árvore especial chamada de
árvore sintática, na qual cada nó representa uma operação e o
filho de um nó representa o argumento da operação.
COMPILADORES
AULA 01
O modelo de compilação de Análise e Síntese
Figura 3: Exemplos de árvores sintáticas
COMPILADORES
AULA 01
Análise
Análise Léxica:
✓ Organiza caracteres de entrada em grupos, chamados tokens
✓ Erros: Tamanho máximo da variável excedido, caracteres
inválidos...
Análise sintática:
✓ Organiza tokens em uma estrutura hierarquíca
✓ Erros: falta de (,), =, identificador inválido...
COMPILADORES
AULA 01
Análise
Análise Semântica:
✓ Checa se o programa respeita as regras básicas de consistência
✓ Erro: tipos inconsistentes -> atribuir uma String a uma variável
inteira.
COMPILADORES
AULA 01
Outros contextos onde compiladores são aplicados
• Os compiladores são associados na maioria das vezes as
linguagens de programação, no entanto, há outras áreas nas
quais eles são aplicados como por exemplo em formatadores
de texto que recebe como entrada um fluxo de caracteres que
deve ser organizado em parágrafos, seções etc. A parte que
“formata” o texto inclui comandos que devem ser traduzidos
de forma que o texto seja exibido de forma organizada.
COMPILADORES
AULA 01
Outros contextos onde compiladores são aplicados
• Compiladores de Silício: Utilizam uma linguagem fonte que é
similar ou idêntica a uma linguagem de programação
convencional (VHDL por exemplo), no entanto, as suas
variáveis não representam localizações de memória, mas sinais
lógicos (0 ou 1). Normalmente sua saída é um projeto de um
circuito.
COMPILADORES
AULA 01
• Adicionalmente a um
compilador, para ser criado
um programa fonte alvo
executável, vários outros
programas são necessários
COMPILADORES
AULA 01
Análise Léxica (scanner)
• Lê os caracteres de entrada (scanner) e os agrupa em
sequências chamadas lexemas (tokens )
• Os tokens são consumidos na fase seguinte (análise sintática)
Analisador 
Léxico
(scanner)
Analisador 
sintático 
(parser)
Programa 
fonte
token
GetToken()
Para análise 
sintática
Tabela de Símbolos
(identificadores e 
constantes)
COMPILADORES
AULA 01
Análise Léxica (scanner)
• Pode ser realizada com o uso de expressões regulares e
autômatos finitos
Exemplo de Expressões Regulares:
➢ letra → [A-Z] | [a-z]
➢ dígito → [0-9]
➢ dígitos → dígito dígito*
➢ identificador → letra[letra | dígito]*
COMPILADORES
AULA 01
Análise Léxica (scanner)
Exemplo de Autômatos finitos
Exemplo para > e >=
COMPILADORES
AULA 01
Análise Sintática
• Utiliza os tokens produzidos pela análise léxica e verifica a
formação de programa com uso de GLC (gramáticas livres do
contexto)
• A partir dos tokens cria uma representação intermediária tipo
árvore (árvore sintática) mostra a estrutura gramatical da
sequência de tokens.
COMPILADORES
AULA 01
Análise Sintática
exp = a + b * 30
<identificador, 1>, <=>,
<identificador, 2>, <+>,
<identificador, 3>, <*>,
<numero, 60>
Analisador
Sintático
COMPILADORES
AULA 01
Análise Semântica
❖ Utiliza a árvore sintática e a tabela de símbolos para:
▪ Criar a consistência semântica (significado) do programa
fonte em relação à linguagem.
▪ Exemplo: verificação de tipos
o A expressão:
x = x + 4.0;
Pode estar sintaticamente correta, mas semanticamente
errada dependendo do tipo de x (inteiro, real, etc.)
COMPILADORES
AULA 01
Exercícios
1) Os itens abaixo estão relacionados a compiladores com
EXCEÇÃO de:
a) Analisador sintático
b) Tabela de alocação de arquivos
c) Analisador Semântico
d) Otimizador de código fonte
e) Gerador de código
•
COMPILADORES
AULA 01
Exercícios
2) De uma forma geral, um compilador é um programa que
recebe como entrada o texto de um programa (fonte) em uma
certa linguagem e produz como saída outro texto de programa
em uma linguagem diferente da utilizada no fonte. Para isso,
compiladoressão estruturados internamente em uma série de
módulos que produzem, em sequência, representações
intermediárias do programa fonte ou de suas partes.
A quebra do texto do programa fonte em unidades básicas da
linguagem denominadas de tokens é realizada pelo módulo
denominado
•
COMPILADORES
AULA 01
Exercícios
a) Interpretador
b) Analisador Léxico
c) Analisador Sintático
d) Tradutor de Contexto
e) Gerador de Código
•
COMPILADORES
AULA 01
Exercícios
3) Desenvolva autômatos finitos:
a) Frases terminadas com um ponto de interrogação
Ex: Qual seu nome?
b) Expressões aritméticas
Ex: 2 + 3, 4*3-3+3
c) CNPJ ou CPF: xxx.xxx.xxx/xxxx-xx |yyy.yyy.yyy-yy
Ex:123.456.789/0001-50, 123.456.789-00
d) Comentários em C
Ex: /* texto */
•
COMPILADORES
AULA 01
Bibliografia Básica 
AHO, Alfred V.; SETHI, Ravi; ULLMAN, Jeffrey D. Compiladores: princípios, 
técnicas e ferramentas. Rio de Janeiro: LTC, 2008. MENEZES, Paulo Fernando 
Blauth. 
Linguagens Formais e Autômatos. 4. ed. Porto Alegre: Bookman, 2002. PRICE, Ana 
Maria; TOSCANI, Simão Sirineo. Implementação de Linguagens de Programação: 
Compiladores. 2. ed. Porto Alegre: Sagra-Luzzato - Instituto de Informática da 
UFRGS, 2001.
COMPILADORES
AULA 01
Bibliografia Complementar 
LEWIS, Harry; PAPADIMITRIOU, Christos. Elementos de Teoria da Computação. 2 
ed. Porto Alegre: Bookman, 2004;
DIVERIO,Tiaraju Asmuz; MENEZES,Paulo Blauth. Teoria da Computação: Máquinas 
Universais e Computabilidade . 3ª Ed. Vol. 5. Rio de Janeiro: Bookman, 2011. 
GRUNE, Dick. Projeto moderno de compiladores: implementação e aplicações. Rio 
de Janeiro: Campus, 2001. 
JOSÉ NETO, João. Introdução à compilação. Rio de Janeiro: LTC, 1987. DELAMARO, 
Márcio E. Como construir um compilador utilizando ferramentas Java. São Paulo: 
Novatec, 2004 
COMPILADORES
AULA 01
AVANCE PARA FINALIZAR 
A APRESENTAÇÃO.