Disciplina: Compiladores

1Introdução à Compilação

Objetivo da aula

•Apresentar a estrutura geral de um compilador "típico", descrevendo suas partes componentes principais e o seu funcionamento simplificado.

Motivação

•Conhecimento das estruturas e algoritmos usados na implementação de linguagens: noções importantes sobre uso de memória, eficiência, etc.

•Aplicabilidade freqüente na solução de problemas que exigem alguma forma de tradução entre linguagens ou notações.

•Implementação de linguagens para um domínio específico.

•Geradores e analisadores de código.

Motivação

•A disciplina de compiladores faz uso de um grande número de conceitos estudados em outras disciplinas do curso: linguagens de programação, algoritmos, linguagens formais, arquitetura, engenharia de software.

Introdução

1.Linguagens de programação: alto nível ×baixo nível

2.Processadores de linguagens

3.Especificação da sintaxe e semântica de linguagens de programação

Níveis de Linguagens de Programação

•Linguagens de programação são uma notação formal para expressar algoritmos

•Além de poder expressar e analisar algoritmos, programadores precisam de meios para editar, traduzir e interpretar os programas em um computador: precisam de Processadores de Linguagens de Programação

C Linguagem de Máquina

•Computadores entendem código demáquina ou linguagem de máquina: seqüência de instruções primitivas expressas por uma seqüência de bits, que éinterpretada para executar uma determinada operação (primitiva): carregar dados, somar registradores, desvios condicionais e incondicionais, etc.

Linguagem de Máquina

•Originalmente se escrevia diretamente em linguagem de máquina: 0 0001 01 0010

•Problemas: dificuldade em ler, escrever, editar; controle explícito dos endereços de memória para dados e para o próprio programa;

•Limite para entendimento/gerenciamento dos programas: alguns milhares de instruções

Linguagem de Montagem

•Notação simbólica para facilitar a escrita, leitura e edição: LOAD x ADD R1 R2 JUMPZ h

•Tradução para linguagem de máquina = montagem do programa

•Assembly language

•Uso de um programa montador (assembler)

•Instruções ainda muito próximas da linguagem de máquina (relação de 1 para 1)

Linguagem de Montagem

•LOAD R1 a;

ADD R1 b; ADD R1 c; DIV R1 #2; LOAD R2 R1; LOAD R3 R1; SUB R3 a; MULT R2 R3; LOAD R3 R1; SUB R3 b; MULT R2 R3; LOAD R3 R1; SUB R3 c; MULT R2 R3; LOAD R0 R2; CALL sqrt;

Linguagens de Programação de alto nível

•Maior nível de abstração: let s = (a+b+c)/2

Linguagens de alto nível devem suportar os seguintes conceitos:

•uso de expressões, usando notação semelhante à matemática;

•tipos de dadosprimitivos e compostos;

•estruturas de controlecomo if-then-else, while, for etc.;

•declaraçõesde variáveis, tipos, funções, procedimentos etc.;

•abstração: o que éfeito xcomo éfeito;

•encapsulamento(ou abstração de dados): classes, pacotes, módulos (orientação a objetos).

Processadores de Linguagens de Programação

•Sistemas que manipulam programas expressos em alguma linguagem de programação: editores, tradutores, compiladores, interpretadores.

Especificação de Linguagens de Programação

•Projetista (designer): projeta linguagens de programação;

•Implementador: implementa uma linguagem;

•Programador: éusuário da linguagem.

•Todos devem ter o mesmo entendimento da linguagem: ter como referência a especificaçãoda linguagem

Especificação de Linguagens de Programação

•Sintaxe: define a forma do programa: palavras reservadas, organização das frases;

•Restrições contextuais (semântica estática): regras de escopoe regras de tipo;

•Semântica: significado do programa.

Podemos ver o significado do programa como uma função mapeando a entrada no resultado (denotacional); ou baseado no seu comportamento (operacional);

Especificação de Linguagens de Programação

•Especificação informal: texto em linguagem natural (inglês ou outra). Riscos: especificação imprecisa, incompleta ou ambígua.

•Especificação formal: consistente, completa, não ambígua. Porém mais difícil de escrever e difícil de ser entendida por pessoas que não conhecem a notação utilizada.

Especificação de Linguagens de Programação

•Na prática:

–especificação formal da sintaxe

–Especificação informal das restrições contextuais e da semântica

Sintaxe

•Éespecificada usando gramáticas livres de contexto(BNF –Backus-Naur Form):

–Conjunto finito de símbolos terminais: ‘>=’, ‘while’, ‘;’.

–Conjunto finito de símbolos não-terminais: Programa, Comando, Expressão, Declaração.

–Um Símbolo inicial(um dos não-terminais): Programa

–Conjunto finito de regras de produção.

Exemplo: BNF Árvore Sintática

•Cada gramática livre de contexto Ggera uma linguagem (seqüência de símbolos terminais).

•Uma árvore sintática de Géuma árvore com labelsordenada em que:

–as folhas são símbolos terminais; –os nós são símbolos não-terminais.

Sintaxe

•Sintaxe concreta:

–Define a estrutura das frases, a ordem em que subfrases devem ser escritas, e os símbolos terminais que as delimitam;

–Define como escrever programas sintaticamente bem formados;

–Não éutilizada para a descrição semântica do programa;

Árvores Sintáticas: Exemplo

Onde o compilador entra nesta história?

•No processamento de um código-fonte de acordo com as especificações formais da linguagem...

Compilador

•Programa que lê um programa escrito em uma linguagem (fonte) e o traduz para uma outra linguagem (destino), reportando erros quando eles ocorrem.

•O nome compilador, criado nos anos 50, faz referência ao processo de composição de um programa pela reunião de várias rotinas de biblioteca; o processo de tradução (de uma linguagem fonte para uma linguagem objeto), era então conhecido como programação automática.

C Linguagens

•Linguagem fonte: C, Pascal, Java, Fortran, etc.

•Linguagem destino: linguagem de máquina (assembler) de um processador, de uma máquina virtual (e.g. Java ou .NET), ou qualquer outra linguagem (e.g. C). Compilador

Programa fonte

Programa destino

Processadores de Linguagens: Compilador

Programa destino entrada saída

Execução de um programa

Interpretador

Programa fonte saída

Processadores de Linguagens: Interpretador entrada

Máquina Virtual

Programa intermediário saída

Compilador Híbrido entrada

Tradutor Programa fonte compilador preprocessador assembler

Linker / Loader

Programa fonte

Programa fonte modificado

Programa em assembler

Código objeto (relocável*)

Código objeto (executável)

Bibliotecas / código objeto

Sistema de processamento de uma linguagem

Programas auxiliares do processo de compilação (tradutores de linguagens de programação

• Preprocessadores(precompiladores): mapeiam instruções de uma ling. de alto nível estendida para instruções da ling. de programação original, ou seja, fazem conversão entre duas linguagens de alto nível.

•Assemblers (montadores): mapeiam instruções em linguagem simbólica (assembly) para instruções de linguagem de máquina.

Programas auxiliares do processo de compilação (tradutores de linguagens de programação

•Interpretadores –aceitam como entrada o código intermediário e produzem o “efeito de execução”do algoritmo original sem, porém, mapeá-lo para linguagem de máquina. Não é gerado um programa objeto.

–Apresentam como desvantagem o tempo de execução maior que de um compilador

Programas auxiliares do processo de compilação (cont.)

•Carregadores (loaders) e linkeditores (linkers)

–Ajustam o código relocável, resolvem referências externas.

•Linker: Ele éo responsável por fazer a ligação entre os módulos do programa, para gerar um único executável. Também adiciona ao código-objeto bibliotecas e funções de outros programas alem de inserir código para lidar com o Sistema Operacional.

•Loader: Carrega o programa executável na memória principal para ser executado

Compilação: Análise e Síntese

•Nesse processo de tradução, háduas tarefas básicas a serem executadas por um compilador:

–análise, em que o texto de entrada (na linguagem fonte) éexaminado, verificado e compreendido

–síntese, ou geração de código, em que o texto de saída (na linguagem objeto) égerado, de forma a corresponder ao texto de entrada.

Compilação: Análise e Síntese

•Normalmente, pensamos nessas tarefas como fases do processo de compilação, mas não é absolutamente necessário que a análise de todo o programa seja completada antes que o primeiro trecho de código objeto seja gerado:

–essas duas fases podem ser intercaladas.

–Como exemplos, um compilador pode analisar cada comando do programa de entrada, e gerar imediatamente o código de saída correspondente a esse comando;

Compilação: Análise e Síntese

•A tarefa de análise deve ter como resultado uma representação (conhecida como representação intermediária) do programa fonte que contenha informação suficiente para a geração do programa objeto correspondente.

–Normalmente, essa representação écomplementada por tabelas que contêm informação adicional sobre o programa fonte.

•Em alguns casos, a representação intermediária pode tomar a forma de um programa em uma linguagem intermediária, a partir da qual seja fácil a tradução para a linguagem objeto desejada.

–Ela deve conter toda a informação necessária para a geração do código objeto.

C Compilação: Análise e Síntese

natureza (variável, constante, procedimento,), tipo, endereço, espaço ocupado,

Uma das formas mais comuns de tabela utilizada nessa representação intermediária éa tabela de símbolos, em que se guarda para cada identificador (símbolo) usado no programa as informações correspondentes, tais como etc.

Organizando fases em passos

•Fases: visão lógica de um compilador

•Em uma implementação as fases podem ser agrupadas em um ou mais passos

•Passos: número de vezes em que se passa pelo mesmo código.

•Um dos modelos possíveis para a construção de compiladores faz a separação total entre o front-end, encarregado da fase de análise, e o back-end, encarregado da geração de código objeto, de forma que ·front-end e back-end se comunicam apenas através da representação intermediária;

Análise: front-end do compilador (atégeração de código intermediário)

Síntese: back-enddo compilador

•Essa idéia visa simplificar a implementação de várias linguagens de programação para várias máquinas:

–em princípio, basta escrever um front-end para cada linguagem, e um back-end para cada máquina.

Front-end

Separação entre front-end e back-end para criação de múltiplos compiladores código intermediário código intermediário

Back-end

Front-end

Front-end Front-end

C# Pascal Fortran

Pascal

Front-end ARM

Separação entre front-end e back-end para criação de múltiplos compiladores código intermediário código intermediário

Back-end Back-end Back-end Back-end

Front-end ARM

Separação entre front-end e back-end para criação de múltiplos compiladores código intermediário código intermediário

Back-end Back-end Back-end Back-end

Front-end

Front-end Front-end

C# Pascal Fortran

Ferramentas auxiliares para a construção de compiladores

•Scanner generators, baseados em expressões regulares. Exemplo: lex

•Parser generators, baseados em gramáticas livres de contexto. Exemplo: yacc

•Engenhos de tradução dirigida por sintaxe, geram rotinas para navegar na parse tree e gerar código intermediário

•Geradores de geradores de código(template matching)

•Toolkits de construção de compiladores

Fases de um compilador

Analisador léxico stream de caracteres

Código de máquina

Analisador sintático Analisador semântico

Ger. de código intermediário Otimizador de código

Gerador de código stream de tokens árvore sintática árvore sintática representação intermediária representação intermediária

Análise do programa fonte

•Análise léxica –lê a seqüencia de caracteres e a organiza como tokens–sequencias de caracteres com algum significado

•Análise sintática –agrupa caracteres ou tokensem uma estrutura hierárquica com algum significado

•Análise semântica –verifica se os componentes de um programa se encaixam de forma a ter um significado adequado.

Análise léxica ou Scanning

•Lê os caracteres de entrada e agrupa-os em sequencias chamadas lexemas.

•Para cada lexema o analisador léxico produz como saída um tokenda forma

<nome do token, valor do atributo> que épassado para a fase seguinte.

Exemplo

•position = initial + rate * 60

<identificador, 2>

<identificador, 3>

Tabela de Símbolos identificador tipo … 1 position … 2 initial … 3 rate … … … … …

C Análise sintática ou parsing

•A partir dos tokens cria uma estrutura em árvore (árvore sintática) que representa a estrutura gramatical do programa.

•A análise sintática deve reconhecer a estrutura global do programa, por exemplo, verificando que programas, comandos, declarações, expressões, etc têm as regras de composição respeitadas.

Análise Sintática -Exemplo

•Caberia àanálise sintática reconhecer a estrutura do trecho if x>0 then modx := x else modx := (-x)

•identificando que se trata de um <comando>,no caso um <comando-if>, composto pela palavra reservada if, seguida de uma <expressão>, seguida da palavra reservada then, etc. Os itens <expressão>e <atribuição>ainda podem ser decompostos em fragmentos menores.

Árvore Sintática –Exemplo 2 •position = initial + rate * 60

Análise semântica

•Verifica o programa em relação a possíveis erros semânticos e guarda informações adicionais

•Por exemplo, não épossível representar em uma gramática livre de contexto uma regra como "Todo identificador deve ser declarado antes de ser usado.", e a verificação de que essa regra foi aplicada cabe àanálise semântica.

Exemplo: verificação de tipos

A expressão x = x + 3.0 estásintaticamente correta, mas pode estar semanticamente certa ou errada, dependendo do tipo de x.

C Código intermediário

•Idealmente deve ser fácil de produzir e também de traduzir para a linguagem-destino.

•Na prática, se estágerando código para uma máquina abstrata.

Código intermediário -exemplo

Geração de código

•Realiza a alocação de registradores (se necessária) e a tradução do código intermediário para a linguagemdestino.

soma, uma para produto,), existe pouca ou

•Por exemplo, se uma máquina tem apenas um registrador (acumulador) em que as operações aritméticas são realizadas, e apenas uma instrução para realizar cada operação (uma instrução para nenhuma possibilidade de variação no código que pode ser gerado.

•Considere o comando de atribuição: x := a + b * c

Geração de Código

Geração de código

•Podemos fazer um gerador de código relativamente simples usando regras como:

Geração de código

•O comando de atribuição x := a + b * c, gera o código

C Otimização de código

•Realiza transformações no código visando melhorar sua performance em aspectos de tempo de execução, uso de memória, tamanho do código executável etc.

Otimização de código -exemplo

Otimização de código -exemplo Tabela de Símbolos

•Estrutura de dados usada para guardar identificadores e informações sobre eles:

–alocação de memória,

–tipo do identificador,

–escopo (onde éválido no programa)

–se for um procedimento ou função: número e tipo dos argumentos, forma de passagem dos parâmetros e tipo do resultado.

Tabela de Símbolos identificador tipo … 1 position … 2 initial … 3 rate … … … … …

Comentários