Visão geral da função do compilador

Como funcionam os compiladores: uma introdução

A finalidade desta seção é oferecer uma rápida visão geral da função do compilador, que ajudará o

leitor a entender como ele traduz um programa em linguagem de alto nível para instruções de máquina.

Lembre-se de que o assunto de construção de compiladores normalmente é lecionado em um curso

de um ou dois semestres; nossa introdução abordará apenas os aspectos básicos.

Nossa descrição das funções de um compilador segue a estrutura da Figura 2.31. Para ilustrar os

conceitos nesta seção, usaremos a versão C de um loop while de uma seção anterior:

while (save[i] == k)

i += 1;

O front-end

A função do front-end é ler um programa fonte, verificar a sintaxe e a semântica e traduzir o programa

fonte para uma forma intermediária, que interprete a maioria das operações do programa específicas

à linguagem. Conforme veremos, as formas intermediárias normalmente são simples, e algumas

de fato são semelhantes aos bytecodes Java, que podem ser encontrados na Seção 2.14.

O front-end normalmente é dividido em quatro funções separadas:

1. A varredura lê caracteres individuais e cria uma seqüência de tokens. Alguns exemplos de tokens

são palavras reservadas, nomes, operadores e símbolos de pontuação. No exemplo anterior,

a seqüência de tokens é “while”, “(“, “save”, “[”, “i”, “]”, “==”, “k”, “)”, “i”, “+=”, “1”.

Uma palavra como “while” é reconhecida como uma palavra reservada em C, mas “save”, “i”

e “j” são reconhecidos como nomes, e “1” é reconhecido como um número.

2. O parsing apanha o fluxo de tokens, garante que a sintaxe esteja correta e produz uma árvore

de sintaxe abstrata, que é uma representação da estrutura sintática do programa. A Figura

2.12.1 mostra como seria a árvore de sintaxe para esse fragmento de programa.

3. Análise semântica apanha a árvore de sintaxe abstrata e verifica a exatidão semântica do programa.

As verificações semânticas em geral garantem que as variáveis e os tipos são declarados

corretamente e que os tipos de operadores e objetos combinam, uma etapa chamada

verificação de tipos. Durante esse processo, uma tabela de símbolos representando todos os

objetos nomeados – classes, variáveis e funções – normalmente é criada e usada para verificação

de tipos no programa.

4. Geração da representação intermediária (RI) apanha a tabela de símbolos e a árvore de sintaxe

abstrata e gera a representação intermediária que é a saída do front-end. As representações

intermediárias utilizam operações simples sobre um conjunto de tipos primitivos, como inteiros,

caracteres e reais. Bytecodes Java representam um tipo de forma intermediária. Nos compiladores

modernos, a forma intermediária mais comum se parece com o conjunto de

instruções MIPS, mas com um número infinito de registradores virtuais; mais adiante, descreveremos

como mapear esses registradores virtuais em um conjunto finito de registradores reais.

A Figura 2.12.2 mostra como nosso exemplo poderia ser representado em tal forma

intermediária. Escrevemos as instruções MIPS nesta seção em maiúsculas quando elas representarem

formas de RI.

A forma intermediária especifica a funcionalidade do programa de uma maneira independente do

fonte original. Depois que esse front-end tiver criado a forma intermediária, as passadas restantes

são em grande parte independentes da linguagem.

# comentários são escritos desta forma – código fonte normalmente incluído

# while (save[i] == k)

loop: LI R1,save # lê o endereço inicial de save para R1

LW R2,i

MULT R3,R2,4 # Multiplica R2 por 4

ADD R4,R3,R1

LW R5,0(R4) # lê save[i]

LW R6,k

BNE R5,R6,fimloopwhile

# i += 1

LW R6, i

ADD R7,R6,1 # incrementa

SW R7,i

branch loop # próxima iteração

fimloopwhile:

FIGURA 2.12.2 O exemplo de loop while é mostrado usando uma representação intermediária típica.

Na prática, os nomes save, i, k seriam substituídos por algum tipo de endereço, como uma referência ao stack pointer local

ou a um ponteiro global e um offset, semelhante ao modo como save[i] é acessado. Observe que o formato das instruções

MIPS é diferente porque são usadas para ilustrar representações intermediárias: as operações estão em maiúsculas, e os registradores

utilizam a notação RXX.

2.12-2 2.12 Como funcionam os compiladores: uma introdução ELSEVIER

instrução while

condição do while corpo da instrução

expressão atribuição