Implementação de Compiladores

Enviado em: 04/04/2008
Autor(es): Glaucia Bittencourt Tristão e Cleber Stefanello Pippi

Este artigo descreve a implementação de compiladores, apresentando um resumo de seus conceitos e algumas aplicações.

1. Compiladores

Um compilador é um programa que converte uma linguagem de fácil escrita e leitura, para programadores em uma linguagem que possa ser interpretada e executada pelas máquinas.
O compilador está configurado para não aceitar determinados erros e seguir determinadas regras predeterminadas pela linguagem da qual ele é programado para interpretar. Sendo assim, um compilador deve detectar erros feitos pelo programador, corrigir ou indicar o melhor caminho para a correção do programa, e só então traduzir para linguagem de máquina (Assembly).
Em linguagens de programação híbridas, o compilador tem o papel de converter o código fonte em um código chamado de byte code, que é uma linguagem de baixo nível. Um exemplo deste comportamento é o do compilador da linguagem Java que, em vez de gerar código onde está sendo executado o compilador, gera código chamado Java Bytecode.
Muitos compiladores incluem pré-processadores. Um pré-processador normalmente é responsável por mudanças no código fonte destinadas de acordo com decisões tomadas em tempo de compilação.

2. Organização de um compilador

As fases de um compilador podem ser classificadas em dois grupos: análise e síntese. Na fase de análise, encontram-se as fases de análise léxica, análise sintática e análise semântica. Já na fase de síntese encontram-se as fases de geração de código intermediário, otimização e geração de código. Adicionalmente as estas fases, existem ainda duas fases adicionais que interagem com todas as fases do compilador: o gerenciamento de tabelas e o tratamento de erros. A Figura  abaixo ilustra todas as fases de um compilador.

A fase de análise léxica (varredora) tem por objetivo ler o programa fonte e transformar seqüências de caracteres em uma representação interna, denominada itens léxicos.
 Os itens léxicos a serem reconhecidos pelo analisador léxico são determinados pela gramática da linguagem-fonte. Deste modo, caso um item léxico não seja definido por esta gramática, um erro léxico é gerado.           
          
         
 A análise Sintática responsabiliza-se por traduzir os Tokens, e descobrir a relação de uns com os outros. Se você escreve writeln, um espaço, e um identificador, seu programa passará pela análise léxica (writeln e identificador existem), mas não passará pela análise sintática, que informa a necessidade de um abre-parênteses logo após esta procedure.
A fase de análise semântica analisa a árvore sintática para a informação context-sensitive, gerada pelo analisador sintático em busca de inconsistências semânticas. Uma das tarefas mais importantes é a verificação de tipos, ou análise de contexto. É nesta fase que são detectadas, por exemplo, os conflitos entre tipos, a ausência de declarações de variáveis, funções e procedimentos.
A saída da fase de análise semântica, é anotada na árvore do analisador gramatical. As gramáticas de atributo são usadas para descrever a semântica de estática de um programa.
A fase de geração de código intermediário permite a geração de instruções para uma máquina abstrata, normalmente em código de três endereços, mais adequadas a fase de otimização. Esta forma intermediária não é executada diretamente pela máquina alvo.
A fase de otimização analisa o código no formato intermediário e tenta melhorá-lo de tal forma que venha a resultar um código de máquina mais rápido em tempo de execução, usando as réguas que denotam a semântica da linguagem-fonte. Uma das tarefas executadas pelo otimizador é a detecção e a eliminação de movimento de dados redundantes e a repetição de operações dentro de um mesmo bloco de programa.
E por fim, a fase de geração de código tem como objetivo analisar o código já otimizado é a gerar o um código objeto definitivo para uma máquina alvo. Normalmente este código objeto é um código de máquina relocável ou um código de montagem. Nesta etapa as localizações de memória são selecionadas para cada uma das variáveis usadas pelo programa. Então, as instruções intermediárias são, cada uma, traduzidas numa seqüência de instruções de máquina que realizam a mesma tarefa.
Atualmente, as pesquisas e os estudos desenvolvidos sobre autômatos finitos, expressões regulares e gramáticas livres de contexto, além dos próprios estudos sobre compiladores, permitiram que as fases de análise léxica e sintática tivessem um desenvolvimento bem maior que as anteriores, chegando-se ao ponto de se ter geradores automáticos para estas fases. Isto já não ocorre com a análise semântica e com a geração de código, sobre as quais ainda não se tem tão bem definido um formalismo como nas duas primeiras fases.
Ao se criar um compilador, estas últimas fases, ainda hoje são de total responsabilidade do desenvolvedor, não havendo ferramentas que as automatize, como no caso da análise sintática. Existe, no entanto, um senso comum sobre o que deve ser realizado em uma análise semântica e como aproximadamente deve ser gerado o código para as construções mais comuns em linguagens de programação, mas ainda se mantém como um trabalho manual, onde a criatividade do desenvolvedor tem mais influência dentro da implementação de um compilador.

3. Propriedades de um bom compilador

• Gerar código correto;
• Estar de acordo com a especificação da linguagem;
• Ser escalável, ou seja, ser capaz de tratar códigos fonte de tamanhos arbitrários;
• Velocidade de compilação não é mais importante;
• Algoritmos desejavelmente lineares – O(n);
• Não é interessante a existência de algoritmos não lineares no processo de compilação;
• Problema: a otimização de código não é linear;
• Outras características importantes:
• Portabilidade do compilador;
• Portabilidade do código alvo;

4. Implementação de um analisador léxico:

• Como ler o arquivo texto de entrada?
  • Memória não é mais um problema;
  • A entrada por dois buffers (atual e anterior);
  • Leitura do arquivo de entrada colocando-o em memória em uma única chamada ao sistema operacional;
• O problema da nova linha
  • No Windows/DOS, uma nova linha é marcada pela seqüência de caracteres ASCII 13 e 10;
  • No Linux, uma nova linha é marcada pelo caractere ASCII 10;
  • No OS/2, cada linha é um vetor de caracteres;
• O que é um token exatamente?
  • Simplificação: se você pode colocar espaços na esquerda e direita sem alterar o significado, trata-se de um token;
• Comentários não são tokens. A análise léxica os remove da seqüência de tokens gerada como saída.

 4.1 Interface de Programação (API) Léxica

• Funções públicas
  • void startLex(string fileName);
• Abre o arquivo fonte de entrada fileName e o copia por inteiro para a memória
• Caso o compilador manipule múltiplos arquivos, utiliza uma pilha para armazenar a posição em que estava manipulando o arquivo atual e abre o novo arquivo
  • Token nextToken();
• Avalia o arquivo fonte atual, caractere por caractere, e retorna o próximo token
• Implementação de autômatos
• Algumas funções privadas úteis
  • char nextChar();
• Retorna o próximo caractere do arquivo atual, contando as linhas e colunas;
  • void skipLayoutAndComment();
• Percorre o fonte ignorando comentários até encontrar um caractere que não seja espaço, tabulação ou pulo de linha.

5. Conclusão

Graças aos compiladores podemos utilizar uma linguagem de fácil escrita para a linguagem que a máquina entenda, tornando assim muito mais fácil a elaboração de programas em diversas linguagens, uma vez que a maioria dos compiladores checa a consistência do código informado pelo programador, sem ter a preocupação de estar tendo que passar diretamente para a máquina a sua linguagem (assembly).

Referências

Disponível em: http://pt.wikipedia.org/wiki/Compilador. Último acesso: 11/2007.
Disponível em: http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node37.html.  Último acesso: 11/2007.
Disponível em: http://www.geocities.com/SiliconValley/Bay/1058/compiler.html. Último acesso: 11/2007.
Disponível em: http://br.geocities.com/feliposz/compiladores/crenshaw/tutor03.html.      Último acesso: 11/2007.
Disponível em: www.inf.ufsc.br/~olinto/ine5622-cap1.doc. Último acesso: 11/2007.