COMPILADORES (36)

Prévia do material em texto

Universidade Católica de Pelotas 
Bacharelado em Ciência da Computação 
364018 Linguagens Formais e Autômatos 
TEXTO 6 
Introdução à Compilação 
Prof. Luiz A M Palazzo 
Maio de 2011 
_______________________________________________ 
 
Um COMPILADOR é um programa que lê um programa escrito numa linguagem - a linguagem 
fonte - e o traduz num programa eqüivalente numa outra linguagem - a linguagem objeto, 
relatando ao usuário a presença de erros no programa fonte. 
· Esquematicamente: 
 
· Existem duas partes na compilação: A ANÁLISE E A SÍNTESE. 
 ANÁLISE: Divide o programa fonte nas partes constituintes e cria uma representação 
intermediária. 
 SÍNTESE: Constrói o programa objeto desejado, a partir da representação 
intermediária. 
· Durante a análise, as operações implicadas pelo programa fonte são determinadas e 
registradas numa estrutura hierárquica, chamada de árvore. (Ex. Árvore Sintática). 
 
· Ferramentas que manipulam programas fontes: 
· EDITORES DE ESTRUTURAS - Recebe como entrada um conjunto de comandos para construir 
um programa fonte. 
· PRETTY PRINTERS - Analisa um programa e o imprime numa forma em que a sua estrutura 
se torne claramente visível. 
· VERIFICADORES ESTÁTICOS - Lê um programa, analisa-o e tenta descobrir erros potenciais, 
sem executá-lo. 
· INTERPRETADORES - Em lugar de produzir um programa objeto como resultado da tradução, 
um interpretador realiza as operações especificadas pelo programa fonte. 
· O contexto de um compilador: 
 
 
 
FASES DE UM COMPILADOR (MODELO ANÁLISE-SÍNTESE) 
 
 
Análise Léxica 
 
· Nesta fase o arquivo de entrada é varrido caractere a caractere. 
· Símbolos especiais (espaço em branco, símbolos de pontuação e new line) são utilizados para 
estabelecer os limites das palavras. 
· Eliminação de espaços em branco e comentários. 
· Durante a análise léxica, as palavras ou lexemas são guardados na tabela de símbolos e 
classificados de acordo com a linguagem, em palavras reservadas, comandos, variáveis e tipos 
básicos. 
· Identificação de erros léxicos ("overflow" de campo numérico, uso de símbolos não 
pertencentes ao alfabeto da linguagem). 
 
Análise Sintática 
 
 
· É responsável pela verificação da bem formação dos comandos da linguagem, de acordo com 
as regras especificadas pela gramática da linguagem. 
· Sentenças mal formadas, geralmente, interrompem o processo de compilação e são 
apresentadas como mensagens de erro. 
· No fim da análise sintática, temos a representação do programa original de forma hierárquica, 
onde o programa é representado por uma árvore sintática. 
· Uma árvore sintática é uma representação compactada de uma árvore PARSE na qual os 
operadores aparecem como nós interiores e os operandos de um operador são os filhos do nó 
daquele operador. 
· Os erros de sintaxe são mais freqüentes que os erros léxicos. 
· Identificação e recuperação de erros de sintaxe. 
· Construções léxicas não requerem recursão, enquanto as sintáticas sim. As gramáticas livres 
de contexto são uma formalização de regras recursivas que podem ser usadas para guiar a 
análise sintática. 
 
 
 
Análise Semântica 
 
 
· A análise semântica mais comum consiste na verificação da consistência de tipos dos 
operandos envolvidos em operações aritméticas ou dos parâmetros passados a procedimentos. 
· O código intermediário deve ser fácil de produzir e fácil de traduzir no programa objeto. 
 
 
 
Geração do Código Intermadiário 
 
 
· O gerador de código intermediário será acionado quando o programa for analisado léxica, 
sintática e semanticamente, e estiver correto do ponto de vista das três análises citadas. Neste 
ponto do projeto, finda-se a parte de análise e entramos no processo de síntese. Para essa 
geração, deve-se percorrer a árvore em profundidade (depth first), para que o código seja 
gerado das folhas para os nós. A geração de código se dá através do uso de quádruplas, ou 
seja, quatro campos que já deixam o código numa linguagem bem acessível para a posterior 
tradução para código de máquina. Os quatro campos são: Operador, Operando 1, Operando 2 e 
Resultado. Além disso, temos um quinto campo, que guarda a linha da quádrupla, a qual será 
útil para endereços que necessitem de resolução mais adiante no processo (endereços não 
resolvidos). Por exemplo, 
x:=(a+c)*(d-10); 
nos daria a seguinte tabela de código intermediário: 
 
 
 
. Quando temos que trabalhar com expressões aritméticas ou booleanas, devem ser usadas 
variáveis temporárias, para guardarem resultados de cálculos intermediários. Também vale 
ressaltar que para as construções if e while devemos manter saltos (ou jumps GOTO), para que 
determinados trechos de código possam ser evitados na hora da execução. Ainda no caso do 
while, deve-se ter um salto para o teste da condição de repetição, que está numa linha mais 
anterior, caracterizando assim o loop dessa estrutura. Na próxima tabela, pode-se ver o 
resultado da geração de código intermediário para o exemplo de programa dado, com todos os 
aspectos acima citados: 
 
 
 
 
 
 
 
 
Tratamento de Erros 
 
 
· Tipos de erros: léxicos, sintáticos, semânticos e lógicos. 
· Os erros sintáticos são os mais freqüentes. 
· Estratégias de recuperação de erros: 
1) PANIC MODE - O compilador descarta símbolos de entrada até encontrar um token de 
sincronização( ";" ou "end"). 
2) PHASE LEVEL - O compilador tenta corrigir o erro encontrado, sem alterar o código fonte. 
(colocar um ";" onde não tem ou trocar ":" por ";"). 
3) PRODUÇÃO DE ERRO - Pode ser usado quando sabe-se, de antemão, quais são os erros 
mais prováveis de acontecer; acrescenta-se à gramática, algumas produções que usam as 
construções erradas. 
4) CORREÇÃO GLOBAL - Tenta calcular a seqüência mínima de mudanças para a correção de 
um erro. Essa estratégia tem apenas interesse teórico. 
 
Gerenciamento da Tabela de Símbolos 
 
· Uma função essencial do compilador é registrar os identificadores usados no programa fonte e 
coletar as informações sobre os seus diversos atributos de um identificador, tais como: 
memória alocada, tipo, escopo). 
· Uma tabela de símbolos é uma estrutura de dados contendo um registro para cada 
identificador, com os campos contendo os atributos do identificador. 
 
 
Geração do Código Objeto 
 
 
. O gerador de código objeto é a última parte de um compilador, como vemos na figura abaixo. 
No entanto, muitas vezes ainda existe mais uma etapa, que é a otimização de código, tanto 
intermediário, quanto objeto. Para não adicionarmos complexidade ao nosso trabalho, não 
implementamos um otimizador. 
 
 
 
 
 
. A tarefa central desse gerador de código é transformar uma especificação de código 
intermediário vinda da etapa anterior para uma especificação de código assembly, para poder 
ser executado num PC. 
. Como vimos, um gerador de código intermediário disponibiliza um conjunto de quádruplas, 
com as informações de label, operador, operandos e resultado. 
. As quádruplas são geradas sempre no mesmo formato, ou seja, uma quádrupla: 
+ x y _temp1 
 
sempre fará a soma de x com y e guardará esse resultado em _temp1. Sendo assim, podemos 
estabelecer um conjunto de mnemônicos aceitos pela linguagem assembly, que representam 
cada tipo de quádrupla do código intermediário. Os conjuntos de mnemônicos, bem como a 
quem se referem, são mostrados abaixo: 
 
 
 
 
(*) - Na operação de divisão, o operador IDIV realiza a divisão de um valor em 32 bits por 
outro em 16 bits. Por isso, temos que efetuar uma multiplicação antes da divisão, para que o 
resultado armazenado no registrador AX seja de 32 bits.. Alguns mnemônicos não fazem parte do assembler, mas são macros e rotinas construídas a 
parte. As mesmas foram retiradas de dois arquivos: macros.bib, impress.bib e macrdk.bib (esta 
criada por Adriane Cardozo e Kelvin Reinhardt). 
. Além deste passo, temos que colocar um cabeçalho constante antes do código, para 
incluírmos as bibliotecas, instanciarmos segmentos, etc. No final do código, temos também que 
declarar as variáveis utilizadas, sendo que podem ser de três tipos: BYTE (DB), que ocupa 8 
bits, WORD (DW), que ocupa 16 bits e DWORD (DD), que ocupa 32 bits. Em nossos programas, 
somente utilizamos os dois primeiros. 
. Depois de formarmos esse arquivo contendo o código objeto (.ASM), devemos submetê-lo à 
ação de um assembler (montador), que transformará o mesmo em um arquivo legível para a 
ligação (link), cuja extensão é .OBJ. Para a tarefa de montagem, utilizamos o TASM (Turbo 
Assembler) e para a ligação, o TLINK (Turbo Linker), ambos da Borland International. O TLINK 
já converte automaticamente o arquivo .OBJ em um arquivo .COM. Obedecidas essas fases, o 
arquivo executável está pronto para ser rodado. Para maiores informações sobre montadores e 
ligadores, consulte [SANT90]. 
 
Geração do Módulo Executável 
 
 
. Compilação é o processo de tradução de um programa escrito em linguagem de alto nível para 
código em linguagem de máquina. Compilação é um processo análogo ao da montagem 
(verificação / análise do código fonte, resolução das referências de memória, reserva de espaço 
em memória e conversão para código de máquina binário). O que diferencia a compilação do 
processo de montagem é sua maior complexidade. No processo de montagem, há uma relação 
de 1:1, ou seja, cada instrução do código fonte resulta em uma instrução de máquina, 
enquanto na compilação a relação é múltipla, cada instrução do código fonte gerando várias 
instruções de máquina. 
. Durante a compilação, o código fonte é analisado (análise léxica, sintática e semântica), é 
gerado um código intermediário e são construídas tabelas de símbolos, alocam-se as áreas de 
memória para variáveis e atribui-se os registradores a serem utilizados, e é finalmente gerado o 
código objeto em linguagem binária de máquina. Em alguns compiladores, é gerado um código 
intermediário em Assembly (que pode ser visualizado pelo programador) e que em seguida 
passa pelo montador para gerar finalmente o código objeto em linguagem de máquina. 
. O código objeto pode ser absoluto (os endereços constantes são endereços reais de memória) 
ou relocável (os endereços são relativos, tendo como referência o início do programa, e os 
endereços reais de memória são definidos apenas em tempo de execução). 
 
 
 
Edição de Ligações 
 
. Assim, o código objeto preparado pelo compilador em geral não é imediatamente executável, 
pois ainda existe código (as rotinas de biblioteca) a ser incorporado ao programa. A cada 
chamada de biblioteca encontrada no código fonte, o compilador precisará incluir uma chamada 
para a rotina e o endereço dos dados que devam ser passados para a rotina. 
. A tarefa de examinar o código objeto, procurar as referências a rotinas de biblioteca (que 
constituem referências externas não resolvidas), buscar a rotina da biblioteca, substituir a 
chamada pelo código ("resolver as referências externas") e obter os parâmetros para incluí-los 
no código objeto é executada por um programa chamado Ligador (LinkEditor). O resultado da 
execução do Ligador é o código final pronto para ser executado pelo computador, chamado 
módulo de carga ou código executável. 
. O módulo de carga, após testado e depurado (isto é, depois de resolvidos todos os erros, 
também chamados "bugs") é armazenado em memória de massa para ser executado quando 
necessário. O processo de compilação e ligação é executado apenas pelo programador na fase 
de desenvolvimento e não mais precisará ser executado pelo usuário, quando da execução do 
programa.