Compiladores: Processo, Fases e Estruturas de Dados

Um compilador é um programa de computador que traduz um programa escrito em uma linguagem de programação para outra linguagem de programação, gerando um programa equivalente que a máquina será capaz de interpretar. Normalmente a segunda linguagem é a linguagem de máquina, mas pode ser apenas texto. Este processo de tradução é chamado compilação.¹

Um compilador é um programa que pode traduzir o código-fonte de um programa em linguagem de alto nível para outro idioma de nível inferior (geralmente em linguagem de máquina). Desta forma, um desenvolvedor pode criar um programa em uma linguagem muito mais próxima de como um ser humano pensa, e então compilá-lo para um nível mais administrável por um computador.

Processo de Construção

É o processo pelo qual se traduz instruções escritas em uma linguagem de programação específica em linguagem de máquina. Além de um tradutor, você pode precisar de outros programas para criar um programa objeto executável. Um programa-fonte pode ser dividido em módulos armazenados em arquivos separados. A tarefa de montar o programa de origem é muitas vezes confiada a um programa separado chamado pré-processamento. O pré-processador também pode expandir abreviações, as chamadas macros, e declarações do idioma de origem.

Normalmente, a criação de um programa executável (um típico .exe para Microsoft Windows ou DOS), envolve duas etapas. O primeiro passo é chamado de compilação (em si) e traduz o código fonte escrito em uma linguagem de programação para um arquivo armazenado em código de baixo nível (geralmente código-objeto, e não diretamente em linguagem de máquina). A segunda etapa é chamada ligação (ou vinculação), na qual o código de baixo nível gerado é combinado com o código de todos os arquivos e sub-rotinas que foram compilados, e o código das funções das bibliotecas do compilador é adicionado ao arquivo executável. Isso permite que o arquivo executável se comunique diretamente com o sistema operacional e, finalmente, traduz o código objeto para código de máquina, gerando o módulo executável.

Estes dois passos podem ser feitos separadamente, armazenando o resultado da fase de compilação em arquivos de objeto (um típico .obj para Microsoft Windows, DOS ou Unix) para ligá-los depois, ou criar diretamente o executável, caso em que a fase de compilação é armazenada apenas temporariamente. Um programa pode ter partes escritas em diferentes linguagens (ex: C, C++ e ASM), que podem ser compiladas separadamente e depois ligadas para formar um único módulo executável.

Fases do Processo

O processo de tradução é composto internamente por vários estágios ou fases, que realizam diferentes operações lógicas. É útil pensar nessas fases como partes separadas dentro do tradutor, e podem realmente ser escritas como operações codificadas separadamente, mas na prática muitas vezes são integradas.

Fase de Análise

Análise Léxica

Ver artigo principal: Lexer

A análise léxica é o primeiro passo. Aqui, o programa fonte é lido da esquerda para a direita e agrupado em componentes léxicos (tokens), que são sequências de caracteres que têm significado. Além disso, todos os espaços em branco, linhas em branco, comentários e outras informações desnecessárias são removidos do programa de origem. Ele também verifica se os símbolos da linguagem (palavras-chave, operadores, ...) estão escritos corretamente.

Como as tarefas realizadas por um analisador léxico são um caso especial de correspondência de padrões, são necessários métodos de especificação e reconhecimento de padrões, e estes métodos são principalmente as expressões regulares e autômatos finitos. No entanto, um analisador léxico é também a parte do tradutor que gerencia a entrada de código-fonte e, como esta etapa muitas vezes envolve um gasto significativo de tempo, o analisador léxico deve funcionar o mais eficientemente possível.

Análise Sintática

Ver artigo principal: Parser

Nesta fase, os caracteres ou componentes lexicais são agrupados hierarquicamente em frases gramaticais que o compilador usa para sintetizar a saída. Verifica-se se o produto da fase anterior é sintaticamente correto (de acordo com a gramática da linguagem). Em geral, as frases gramaticais do programa fonte são representadas por uma árvore de análise.

A estrutura hierárquica de uma linguagem é geralmente expressa de forma recursiva. Por exemplo, podem-se dar as seguintes regras no âmbito da definição das expressões:

• Qualquer identificador é uma expressão.
• Qualquer número é uma expressão.
• Se expressão₁ e expressão₂ são expressões, então também:
  • expressão₁ + expressão₂
  • expressão₁ * expressão₂
  • (expressão₁)

Regras 1 e 2 são as regras básicas (não recursivas), enquanto a regra 3 define expressões em termos de operadores aplicados a outras expressões.

A divisão entre a análise léxica e a análise sintática é um pouco arbitrária. Um fator para determinar a divisão é se uma construção da linguagem de origem é inerentemente recursiva ou não. Construções léxicas não requerem recursão, embora muitas vezes necessitem de estruturas sintáticas. Recursão não é necessária para reconhecer identificadores, que geralmente são sequências de letras e dígitos, começando com uma letra. Normalmente, os identificadores são reconhecidos pela simples consideração do fluxo de entrada, esperando encontrar um caractere que não é letra ou dígito, e depois de reunir todas as letras e os números encontrados até aquele ponto em um componente lexical chamado ID. Além disso, esse tipo de análise não é poderoso o suficiente para analisar expressões ou proposições. Por exemplo, não podemos corresponder adequadamente os parênteses de expressões ou palavras em frases começam e terminam sem impor algum tipo de hierarquia ou estrutura na entrada.

Análise Semântica

A fase de análise semântica verifica o programa-fonte para tentar encontrar erros semânticos e reúne informações sobre os tipos para a fase posterior de geração de código. Ela usa a estrutura hierárquica determinada pela fase de análise sintática para identificar os operadores e operandos das expressões e proposições.

Um importante componente da análise semântica é a verificação de tipos. Aqui, o compilador verifica se cada operador tem operandos permitidos pela especificação da linguagem fonte. Por exemplo, as definições de várias linguagens de programação requerem que o compilador indique um erro cada vez que se usa um número real como índice de uma matriz. No entanto, a especificação da linguagem pode impor restrições sobre os operandos, por exemplo, quando um operador aritmético binário é aplicado a um inteiro e um número real. Verifica-se se o sistema de tipos definiu o tamanho correto.

Fase de Síntese

A fase de síntese gera código objeto equivalente ao programa fonte. O código objeto é gerado apenas quando o programa fonte está livre de erros de análise, o que não significa que o programa será executado corretamente, uma vez que um programa pode ter equívocos lógicos ou expressões mal calculadas. Normalmente, o código objeto é o código de máquina relocável ou um código de montagem. As localizações de memória são selecionadas para cada uma das variáveis usadas pelo programa. Então, cada uma das instruções intermediárias é traduzida em uma sequência de instruções de máquina que executam a mesma tarefa. Um aspecto fundamental é a atribuição de variáveis a registradores.

Geração de Código Intermediário

Após a análise sintática e semântica, alguns compiladores geram uma representação intermediária explícita do programa fonte. Pode-se considerar isto como uma representação intermediária do programa para uma máquina abstrata. Esta representação intermediária deve ter duas propriedades importantes: deve ser fácil de produzir e fácil de traduzir para o código objeto do programa.

A representação intermediária pode assumir muitas formas. Existe uma forma intermediária denominada"código de três endereço", que é como a linguagem de montagem de uma máquina em que cada posição de memória pode funcionar como um registrador. O código de três endereços consiste de uma sequência de instruções, cada qual tem no máximo três operandos. Esta representação intermediária tem várias propriedades:

• Primeiro: Cada instrução de três endereços tem no máximo um operador, além da atribuição. Portanto, quando essas instruções são geradas, o tradutor tem de decidir a ordem em que as operações são realizadas.
• Segundo: O tradutor deve gerar um nome temporário para armazenar os valores calculados para cada instrução.
• Terceiro: Algumas instruções em"três endereço" têm menos de três operandos, por exemplo, a atribuição.

Otimização de Código

A fase de otimização de código visa melhorar o código intermediário, de modo que o código de máquina resultante seja executado mais rápido. Esta fase da etapa de síntese é possível, especialmente se o tradutor é um compilador (dificilmente um interpretador pode otimizar o código). Existe uma grande variação na quantidade de otimização de código que diferentes compiladores realizam. Naqueles que fazem muita otimização, chamados compiladores otimizadores, uma porção significativa do tempo do compilador é gasta nesta fase. No entanto, existem otimizações simples que melhoram significativamente o tempo de execução sem que a compilação se torne muito lenta.

Estruturas de Dados Chave

A interação entre os algoritmos utilizados pelas fases do compilador e as estruturas de dados que suportam essas fases é naturalmente muito forte. O desenvolvedor do compilador se esforça para aplicar estes algoritmos de uma forma tão eficaz quanto possível, sem acrescentar complexidade excessiva. Idealmente, um compilador deve ser capaz de compilar um programa em tempo proporcional ao seu tamanho.

Tokens ou Componentes Léxicos

Quando um analisador léxico reúne os caracteres de um token, normalmente representa um símbolo, ou seja, um valor de um tipo de dados enumerado que representa o conjunto de símbolos da linguagem de origem. Também é por vezes necessário manter a string ou outras informações derivadas dela, como o nome associado a um token de identificador ou o valor de um token numérico.

Na maioria das linguagens, o analisador léxico só precisa gerar um token de cada vez. Neste caso, pode-se usar uma variável global simples para manter a informação do token. Em outros casos (o exemplo mais notável é FORTRAN), pode-se precisar de um array (ou vetor) de tokens.

Árvore de Sintaxe

Se o analisador sintático gera uma árvore de sintaxe, ela é geralmente construída como uma estrutura padrão com base em ponteiros que é alocada dinamicamente à medida que a análise é feita. A árvore inteira pode ser armazenada como uma única variável que aponta para o nó raiz. Cada nó da estrutura é um registro cujos campos representam os dados coletados tanto pelo analisador sintático quanto, em seguida, pelo analisador semântico. Por exemplo, o tipo de dados de uma expressão pode ser armazenado como um campo no nó da árvore de sintaxe correspondente à expressão.

Às vezes, para economizar espaço, esses campos são atribuídos dinamicamente, ou armazenados em estruturas de dados, tais como a tabela de símbolos, que permitem a atribuição seletiva e desalocação. Na verdade, cada nó na árvore de sintaxe em si pode exigir diferentes atributos a serem armazenados, de acordo com o tipo de construção da linguagem a representar. Neste caso, cada nó na árvore de sintaxe pode ser representado por uma variável de registro, com cada tipo de nó contendo apenas as informações necessárias para o caso específico.

Tabela de Símbolos

Esta estrutura de dados mantém informações associadas a identificadores, funções, variáveis, constantes e tipos de dados. A tabela de símbolos interage com quase todas as fases do compilador: o analisador léxico, o analisador sintático e o analisador semântico. Identificadores podem ser inseridos na tabela pelo analisador léxico, o analisador semântico adicionará outros tipos de dados e informações, e as fases de geração e otimização utilizarão as informações fornecidas pela tabela de símbolos para fazer seleções de código objeto apropriadas.

Como a tabela de símbolos é acessada tão frequentemente pelas aplicações, as operações de inserção, busca e supressão precisam ser eficientes, de preferência com tempo de operação constante. Uma estrutura de dados padrão para essa finalidade é a tabela hash, embora possam ser usadas estruturas diferentes, como árvores. Às vezes, várias tabelas são usadas e mantidas em lista ou pilha.

Tabela de Literais

Busca e inserção rápida são também essenciais para a tabela de literais, que armazena constantes e strings utilizadas no programa. No entanto, uma tabela de literais não necessita de exclusões, porque os dados são aplicados globalmente ao programa e uma constante ou sequência aparece apenas uma vez nesta tabela. A tabela de literais é importante na redução do tamanho de um programa na memória, permitindo a reutilização de constantes e strings. É também necessária para a construção do gerador de código, para endereçar simbolicamente os literais e inserir definições de dados no arquivo de código objeto.

Código Intermediário

De acordo com o tipo de código intermediário (por exemplo, código de três endereços ou código P) e os tipos de otimizações realizadas, este código pode ser armazenado como um conjunto de strings, um arquivo de texto temporário ou uma lista de estruturas relacionadas. Em compiladores que realizam otimizações complexas, deve-se dar atenção especial à seleção das representações que permitem a reorganização fácil.

Geração de Código Intermediário

Após a análise sintática e semântica, alguns compiladores geram uma representação intermediária explícita do programa fonte. Pode-se considerar isto como uma representação intermediária para um programa de máquina abstrata. Esta representação intermediária deve ter duas propriedades importantes: deve ser fácil de produzir e fácil de traduzir para o código objeto do programa.

A representação intermediária pode assumir muitas formas. Existe uma forma intermediária denominada "código de três endereços", que é como a linguagem de montagem para uma máquina em que cada posição de memória pode agir como um registrador. O código de três endereços consiste de uma sequência de instruções, cada qual tem no máximo três operandos. O código para o programa de origem (1) pode aparecer em três endereços como:

temp1 := entarea1(60)

temp2 := id3 * temp1

temp3 := id2 + temp2

id1 := temp3

Esta representação intermediária tem várias propriedades. Primeiro, cada instrução em três endereços tem no máximo um operador, além da atribuição. Portanto, quando essas instruções são geradas, o compilador tem de decidir a ordem em que as operações são realizadas; por exemplo, a multiplicação precede a adição na fonte do programa. Em segundo lugar, o compilador deve gerar um nome temporário para armazenar os valores calculados para cada instrução. Terceiro, algumas instruções em "três endereços" têm menos de três operandos, como a atribuição e as primeiras instruções.

Otimização de Código

A fase de otimização de código tenta melhorar o código intermediário para que o código de máquina resultante seja executado mais rápido. Algumas otimizações são triviais. Por exemplo, um algoritmo natural gera o código intermediário (2) usando uma instrução para cada operador da representação da árvore após a análise semântica, embora haja uma maneira melhor de executar os mesmos cálculos usando as duas instruções:

temp1 := id3 * 60.0

id1 := id2 + temp1

Este algoritmo simples não está errado, pois o problema pode ser resolvido na fase de otimização de código. Ou seja, o compilador pode inferir que a conversão do literal 60 para real (60.0) pode ser feita uma vez durante o tempo de compilação, eliminando a operação de conversão em tempo de execução. Além disso, temp3 é usado apenas uma vez, para transmitir seu valor para id1. Por isso, é seguro substituir temp3 por id1, eliminando a última instrução do código (2) e obtendo o código (3).

Há muitas variações na quantidade de otimização de código que diferentes compiladores realizam. Compiladores que fazem muita otimização são chamados de "compiladores otimizadores", e uma porção significativa do tempo do compilador é gasta nesta fase. No entanto, existem otimizações simples que melhoram significativamente o tempo de execução sem que a compilação se torne muito lenta.

Arquivos Temporários

No início, os computadores não tinham memória suficiente para armazenar um programa completo durante a compilação. Este problema foi resolvido usando arquivos temporários para manter os produtos das etapas intermediárias durante a tradução ou para compilar "em tempo real", ou seja, mantendo apenas a informação suficiente das partes anteriores do programa fonte que permite prosseguir com a tradução.

Atualmente, as limitações de memória são um problema muito menor, e uma unidade de compilação inteira pode ser mantida na memória, especialmente se a coleta de lixo estiver disponível separadamente na linguagem. Contudo, ocasionalmente, compiladores acham útil gerar arquivos intermediários durante determinadas fases do processamento. Um exemplo típico disso é a necessidade de correção de endereços durante a geração de código.