Compiladores

Aviso: Este é um trabalho-Frankenstein, ou seja, são vários parágrafos encontrados na web juntos em um único texto, eventualmente você pode encontrar aqui conteúdo que tenha lido em outros lugares da web.

Conceito

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. Um compilador tem algumas fases de processamento e análise como, por exemplo, a Análise Léxica e Análise Sintática, fases importantes responsáveis pelo reconhecimento de caracteres. Um compilador também esta configurado para não aceitar determinados erros e seguir determinadas regras predeterminadas pela linguagem da qual ele é programado para interpretar, como a linguagem “C” por exemplo. Depois de identificado o erro o compilador parar o processo e emitir uma mensagem de erro para que o programador possa concertá-lo. O erro tem que afetar o mínimo possível no desenvolvimento do programa. Já os analisadores léxicos, devem detectar erros como o uso de caracteres não suportados pela linguagem, ou números inteiros com grandeza maior que a máxima representada no computador. 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-alvo, que a máquina precisa.

Histórico

Nos primeiros dias da computação, computadores eram programados diretamente em linguagem de máquina. Os programadores, para implementar um programa, necessitavam combinar certas chaves e fios para que as tarefas fossem executadas. As dificuldades eram tremendas, sendo que um mísero programa (Tipo “Olá Mundo”) levava meses e mais meses para ser feito e depurado. A necessidade por um modo mais fácil e prático de trabalho, além de uma maior segurança na confecção e uma maior produtividade, levou, na década de 50, ao surgimento dos primeiros computadores a cartão perfurado e as linguagens de montagem (Assembly). Os montadores facilitavam muito a vida dos programadores, mas a linguagem usada ainda era demasiadamente complexa e exigia que o programador, além de ter profundos conhecimentos do hardware para o qual ele estava fazendo o programa, fizesse todo o tratamento e consistência deste em relação ao processador (Alocação de memória e acessos aos registradores). Não existiam bibliotecas já preparadas ou recursos similares. Uma linguagem mais próxima daquela utilizado pelo homem seria mais ideal. Deste modo, surgiram por volta do final da década de 50, as primeiras linguagens de alto nível, como o Fortran e o Algol. Com elas surgiram os primeiros compiladores para estas linguagens e com isto, muitas das tarefas do programador passaram a ser feitas pelo próprio compilador, tais como a definição de áreas de alocação de memória, acesso aos registradores, ao processador e ao barramento do hardware.

Atualmente existe um grande número de linguagens disponíveis, sendo distribuídas dentro de quatro grandes paradigmas: Procedimental ou Imperativas, Funcional, Lógico e Orientado à Objeto. A escolha de uma linguagem e de um paradigma depende dos objetivos a serem atingidos. Entretanto, para fins comerciais e científicos, normalmente se utiliza linguagens dos paradigmas lógico ou orientado a objetos. Dentre estas linguagens podemos citar: C/C++, Pascal, Object Pascal, Delphi, Visual Basic, entre outras. Para implementação de inteligência artificial, normalmente são utilizadas linguagens dos paradigmas lógico e funcional. Nestes paradigmas, as linguagens mais conhecidas são: Prolog, Gödel, Isabelle, Lisp e Scheme.

Tradutores de linguagens

Um tradutor de linguagem é um programa que traduz programas de linguagem de fonte, em um programa equivalente em uma determinada linguagem de objeto. A linguagem de fonte é geralmente de alto-nível, enquanto a linguagem de objeto é, geralmente, a linguagem de máquina de um computador real. De um ponto de vista mais realista, o tradutor define a semântica de uma linguagem de programação, ele transforma as operações especificadas pela sintaxe, em operações de modelo computacional – neste caso, a alguma máquina virtual. As gramáticas context-free (livre de contexto) são usadas na construção de tradutores de linguagem. Desde que a tradução seja baseada na sintaxe da linguagem de fonte, a tradução é dita ser syntax-directed. Um compilador nada mais é do que um tradutor, um programa que tem a finalidade de traduzir ou converter um programa escrito em uma linguagem fonte, geralmente de alto-nível, para uma linguagem objeto, que seja perto de uma linguagem de máquina de um computador real.

O compilador típico consiste em uma fase de análise e em uma fase da síntese. No contraste com compiladores, um intérprete é um programa que simula a execução dos programas escritos em uma linguagem fonte. Os intérpretes podem ser usados ou no nível do programa fonte, ou também pode ser usado para interpretar um código objeto para uma máquina idealizada. Este é o caso quando um compilador gera o código para uma máquina idealizada, cuja arquitetura se assemelhe a mais próxima ao código fonte. Há diversos outros tipos de tradutores que são usados freqüentemente, conjuntamente com um compilador, para facilitar a execução dos programas. Um assembler é um tradutor cuja linguagem fonte (uma linguagem de conjunto) represente um transliteration one-to-one do código de máquina do objeto (Cada comando da linguagem corresponde a um símbolo de máquina).

Alguns compiladores geram o código de conjunto, que é montado então no código de máquina por um assembler. Um carregador é um tradutor cujas linguagens de fonte e de objeto, são linguagens de máquina. Os programas de linguagem fonte contêm tabelas dos dados que especificam pontos no programa, que devem ser modificados se o programa for executado. Um editor de ligação faz um exame de coleções de programas executáveis, e liga-os junto para a execução real. Um pré-processador é um tradutor cuja linguagem fonte, seja um formulário prolongado de alguma linguagem de alto-nível, e cuja linguagem objeto seja o formulário padrão da linguagem de alto-nível.

Funcionamento dos Compiladores

Basicamente, um compilador é um programa de computador escrito em uma linguagem L, para uma máquina M, cuja finalidade é converter um programa PM, denominado programa-fonte, escrito em uma linguagem LF, denominada linguagem-fonte, para uma máquina MF, para um programa PO, denominado programa-objeto, em uma linguagem LO, denominada linguagem-objeto, o qual será executado em uma máquina MO. Graficamente teríamos:

Figura 1: Esquema de tradução

O compilador pode ser composto de várias fases, denominadas neste caso de passos do compilador. Em cada passo, é usada uma linguagem-fonte e uma linguagem-objeto, próprias desse passo, original. No primeiro passo temos a linguagem-fonte a ser compilada, Lf, e no último passo a linguagem-objeto final desejada, Lo. As outras linguagens envolvidas são denominadas linguagens-intermediárias. Graficamente teríamos o mesmo que representado pela Figura 2.

Figura 2: Esquema de tradução em vários passos

Em alguns casos a linguagem-objeto gerada pelo compilador é uma linguagem de montagem (Assembly), necessitando assim de um passo adicional, que é montagem. Neste caso, o programa responsável por esta tarefa é denominado montador (Assembler). A função básica deste programa é a tradução do código fonte Assembly para linguagem de máquina na qual o programa será executado. A principal característica deste tipo de tradutor é que para cada instrução Assembly será gerada uma única instrução de máquina.

As etapas realizadas pelo montador são:

• Substituição dos mnemônicos encontrados por instruções de máquina;
• Substituição dos nomes simbólicos (nomes de variáveis e rótulos de desvio) para endereços de memória;
• Reservar espaço de memória para o armazenamento das instruções e dados;
• Converter valores de constantes para código binário;
• Examinar a correção de cada instrução

Em outros casos, a linguagem-objeto encontra-se em uma forma intermediária, não podendo ser executado diretamente pela máquina. E, em outros casos, não se deseja compilar o programa-fonte, mas executá-lo diretamente. Nestes casos é necessária a presença de um Interpretador, o qual simula uma máquina virtual, possibilitando assim a execução do programa sobre uma máquina real.

Basicamente, a interpretação se caracteriza por realizar as fases de compilação e execução, de cada um dos comandos encontrados no programa. Na realidade o interpretador lê cada linha do programa fonte, extrai os comandos nela presentes, verifica a sua sintaxe, e os executa diretamente. Não existem etapas intermediárias. Caso uma linha de programa seja executada mais de uma vez, ela deverá ser novamente interpretada. São exemplos de linguagens interpretadas: Basic, SmallTalk, Apl, Matlab, etc.

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, sintática e 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.

Análise léxica:

Esta é a fase em que são divididos, a partir do código-fonte, os tipos de palavras, como identificadores, palavras reservadas, números reais, etc. Cabe a análise léxica definir se um identificador é ou não uma palavra reservada. Por exemplo, suponha a expressão abaixo, descrita em Pascal:

Exp := (A + B) * 1.5;

Os itens léxicos contidos nesta expressão são:

Exp, :=, (, A, +, B, ), *, 1.5 e ;.

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. Por exemplo, suponhamos que uma linguagem só suporte valores inteiros. Então o valor 1.5 iria ocasionar um erro, o qual deverá ser tratado.

Análise sintática

É a parte mais importante de um compilador, verifica-se se as frases estão escritas corretamente, ou seja, verificar a ordem das palavras (tokens) escritas essas frases. O analisador sintático que recebe a seqüência de tokens extraídas do código-fonte, que foi enviada pelo analisador léxico, e analisa a seqüência dessas palavras de acordo com a gramática na qual se baseia o analisador.

O responsável pelo agrupamento de símbolos em unidades sintáticas é o chamado Parser. A sua saída é uma representação da árvore do analisador gramatical do programa.

Análise semântica

É toda análise feita pelo compilador além da sintática e da léxica. É responsável pela execução das ações semânticas sempre que forem atingidos certos estados de reconhecimento. Abaixo, estarão demonstradas algumas ações que englobam a análise semântica segundo:

1. Analisar restrições quanto à utilização dos identificadores: em função do contexto em que são empregados, os identificadores devem ou não exibir determinados atributos. Cabe ao compilador, através das ações semânticas, efetuar a verificação da coerência de utilização de cada identificador em cada uma das situações em que é encontrado, no texto-fonte.
2. Verificar o escopo dos identificadores: mediante consulta à informação do escopo em que um identificador está sendo referenciado, o compilador deve executar procedimentos capazes de garantir que todos os identificadores utilizados no texto-fonte correspondam a objetos definidos nos pontos dos programas em que seus identificadores ocorreram.
3. Identificar declarações contextuais: algumas linguagens permitem, para alguns tipos de objetos, que a sua declaração seja feita de modo implícito, e não através de construções sintáticas específicas. É outra função das ações semânticas do compilador localizar tais identificadores em seu contexto sintático, e associar-lhes atributos compatíveis com tal contexto.
4. Verificar a compatibilidade de tipos: cabe às ações semânticas efetuar a verificação do uso coerente dos objetos, que representam os dados do programa, nos diversos comandos de que o programa é composto. O mecanismo de passagem por parâmetro também é verificado através dessas ações semânticas.
5. Efetuar a tradução do programa: a principal função das ações semânticas é exatamente a de criar, a partir do texto-fonte, com base nas informações tabeladas e nas saídas dos outros analisadores, uma interpretação deste texto-fonte, expresso em alguma notação adequada. Esta notação não se refere obrigatoriamente a alguma linguagem de máquina, sendo em geral representada por uma linguagem intermediária do compilador.

A análise semântica engloba duas tarefas principais:

• A Análise de contexto e a Geração de código.
• Verificação de erros em frases que estão sintaticamente corretos.

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 à 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.

Carregadores e Editores de Ligação

A tradução completa de um programa fonte requer dois passos: compilação ou montagem. Neste passo é gerado um código objeto no formato relocável, o qual não é executado diretamente, visto que em um programa podem ocorrer referências a outros programas ou dados (referência externa) os quais se encontram em outros programas, compilados separadamente, ou em bibliotecas (librarys) da linguagem sendo compilada. Deste modo, a função do editor de ligação (Linkeditor) é coletar programas traduzidos separadamente e ligá-los em um único módulo, normalmente denominado módulo absoluto de carga ou simplesmente programa executável (o EXE). Já a função do carregador é carregar o módulo absoluto de carga na memória principal, substituindo os endereços relativos ao módulo de carga por endereços reais de memória.

Para resolver todas as referências a símbolos, o Linkeditor também pode pesquisar em bibliotecas do sistema ou do próprio usuário. Bibliotecas são arquivos que contêm diversos módulos-objeto já preparados e/ou definições de símbolos.

Outra função importante do linker é determinar uma região de memória, na qual o programa será carregado para ser executado, e também a área de Stack (Pilha). Esta operação é denominada relocação. Em sistemas operacionais antigos, a relocação era realizada somente uma vez, na etapa de linkedição. Todos os endereços simbólicos do programa são traduzidos para endereços físicos (binding), e o programa executável é gerado, podendo ser carregado a partir de uma posição prefixada na memória (código absoluto). Nesse tipo de relocação, o programa poderá ser carregado, apenas, a partir de uma única posição na memória.

Token

Token é uma unidade do código que estamos compilando. É uma literal, uma função, um sinal qualquer, um abre-parênteses ou um fecha-parênteses, ponto, um ponto e vírgula, uma palavra reservada, enfim, qualquer parte do código original que faça algum sentido. Exemplo: BEGIN é um token, é uma unidade de um programa pascal. A letra E, pode ser considerado um token? A resposta é: depende. Se você estiver se referindo a E := E + 1, então E é um token do código. Se você estiver se referindo a segunda letra da palavra reservada BEGIN, então E não é um token, E é uma simples letra.

Um exemplo um pouco mais complicado: * (asterisco) é um token, ele simboliza a operação de multiplicação. ** (dois asteriscos) é um único token ou são dois tokens juntos? Depende! Se você tem os dois asteriscos listados como um operador, então ele deverá ser considerado um único token. À medida que os tokens são reconhecidos, devem ser comparados com uma lista em memória e deve-se tentar agrupá-los. Caso não se consiga agrupar, então se deve tratar cada caractere como sendo um token.

Literais

Literal nada mais é do que uma constante. Os números são literais numéricas, e tudo que começa com um ‘(apóstrofe) são literais string ou alfanuméricas.

Palavras Reservadas

São aquelas que não podem ser usadas como nome de Identificador, por fazer parte da lista de tokens do nosso compilador e fatalmente vai gerar erro de compilação.

Espero que tenham gostado do trabalho-Frankenstein, se você é o autor de algum parágrafo me avise e eu coloco os créditos.