Em outros casos, o 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ário 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 comando 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, 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 3 ilustra todas estas fases. 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. A saída é um fluxo do símbolo. As expressões regulares são usadas para definir o símbolo reconhecido por um varredor (ou pelo analisador lexical). 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.
Estes itens léxicos são fornecidos ao analisador sintático, assim que solicitados, o qual os agrupa em uma estrutura denominada de árvore sintática. Para isto, ele usa uma série de regras de sintaxe definidas pela gramática da linguagem-fonte. Caso algum item léxico não seja reconhecido pela regra sintática sendo analisada, ocorre então um erro sintático, o qual deverá ser tratado. Para o nosso exemplo, a árvore sintática da expressão acima é dada pela Figura 4. 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.

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.

Dentre os métodos criados para análise sintática, dois têm maior destaque: top-down e bottom-up.

Os top-down caracterizam-se por construir a árvore de derivação da raiz para as folhas, enquanto que os bottom-up realizam o movimento contrário, constróem a árvore das folhas para a raiz. Os algoritmos top-down costumam ser bem mais simples que os bottom-up, mas também bem mais limitados. A grande maioria das técnicas para análise sintática, independente de seu tipo, possui alguma forma de limitação. A restrição mais geral, presente em quase todos algoritmos, é com relação à ambigüidade da gramática. Uma gramática é dita ambígua se ela apresentar mais de uma árvore de derivação para gerar uma mesma sentença. Além disso, características como recursão à esquerda também não são permitidos em algumas técnicas, especialmente as top-down, exigindo que a gramática tenha que ser reescrita em alguns trechos.

Já as bottom-up costumam ser bem mais gerais, embora mais complexas, tendo, na maioria dos casos, restrições somente com relação à ambigüidade da gramática, mas que mesmo assim, em alguns casos, podem ser resolvidas pela intervenção do desenvolvedor. Dentre os reconhecedores bottom-up, os mais conhecidos pertencem à família dos reconhecedores LR (Left-Right), com destaque para o conhecido SLR (Simple Left-Right). O funcionamento do algoritmo SLR lembra de maneira clara o funcionamento de um autômato de pilha. Ele possui uma tabela de estados por terminais ou não-terminais, que define os movimentos possíveis do autômato, divididos em ações, determinadas pelo estado corrente e pelo terminal na entrada, e desvios, determinados pela posição não-terminal X estado. Além disso, o SLR utiliza uma pilha que implicitamente monta a árvore de derivação. Aliás, esta não é uma particularidade do SLR. A maioria dos algoritmos utiliza uma pilha em vez de uma árvore de derivação, devido ao enorme espaço de memória que a árvore completa ocuparia no reconhecimento total de um programa fonte de uma linguagem de programação qualquer. Todavia a utilização de uma pilha ao invés da árvore explícita tem severas conseqüências no funcionamento de um compilador, graças à volatilidade presente neste tipo de estrutura. Com a utilização da pilha, durante todo o reconhecimento, só são mantidos nesta os ramos da árvore de derivação que ainda não foram reconhecidos. Assim que a análise sintática termina o reconhecimento de um trecho da pilha, este é removido, o que obriga a execução das fases de análise semântica e de geração de código sobre este mesmo trecho, antes que ele seja perdido. Esta técnica é conhecida como Tradução Dirigida pela Sintaxe e utilizada em quase todos os compiladores modernos. Nesta técnica, as fases de análise léxica e semântica passam a ser funções disparadas pela análise sintática, sob a demanda desta, e as fases de geração de código são inseridas dentro das próprias regras semânticas.

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 pode ocorrer referências a outros programa 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, matriz de decisão, símbolo terminal, fila de processamento? Ques bichos são estes????

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 considerada 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. A 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 deve-se tratar cada caracter 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.

Símbolos Terminais: Todo token está associado a um símbolo terminal. Ou ainda melhor - um token é um símbolo terminal! A diferença é que o termo "Token" designa uma parte do código, e o termo "Símbolo" faz parte de uma lista complicada que nós já iremos discutir melhor.

Símbolos não Terminais: Símbolo não terminal é transformado em uma lista de outros símbolos terminais e/ou não terminais, para dar sequência ao algoritmo. Quando o algoritmo abre o arquivo fonte e começa a interpretar os tokens, uma pilha (LIFO - Último que entra é o primeiro que sai) de símbolos terminais e não terminais é comparada em paralelo. Quando o símbolo atual da pilha é terminal, ele deve coincidir com o token atual ou ser um token "vazio" (veremos adiante), senão teremos um erro de sintaxe. Se o símbolo é um não terminal, tanto o token quanto o símbolo vão para a matriz de decisão, e verificam qual regra será utilizada para abrir o tal símbolo não terminal. Se não houver uma regra para a nossa dupla, erro de sintaxe também.

Firsts: A lista de firsts é apenas e tão somente o principal termo de um símbolo não terminal. Exemplo, você já se deparou com um erro de compilação assim: 'Identificador esperado!', ou 'BEGIN esperado', pois então, neste ponto o compilador não conseguiu associar o seu token (no código fonte) com o símbolo não terminal que estava na sua lista de processamento. O 'First' daquele símbolo não terminal era, no primeiro caso, o 'Identificador', e no segundo, a palavra reservada 'BEGIN'. Os Firsts existem apenas para que seja apresentada uma mensagem de erro mais simpática a nós, pobres seres humanos.

O Token 'Vazio': Esta terei que utilizar um exemplo. Por sinal, este exemplo poderá ajudá-lo(a) a compreender melhor os itens colocados acima (vou me basear na sintaxe do Pascal):

BLOCO - tudo o que pode vir dentro de uma 'procedure' ou de um 'program'

Regra 1 BLOCO -> <DCLCONST> <DCLTYPE> <DCLVAR> <CODIGO>

Se Token = 'CONST', use Regra 1
Se Token = 'TYPE', use Regra 1
Se Token = 'VAR', use Regra 1
Se Token = 'BEGIN', use Regra 1

Você conhece bem a sintaxe do Pascal - após a declaração do programa ou de uma procedure, poderemos opcionalmente declarar uma área para constantes, e/ou para tipos e/ou para variáveis. O Begin é obrigatório. Continue acompanhando:

Regra 2 <DCLCONST> - Vazio
Regra 3 <DCLCONST> - CONST Identificador = <LITERAL> ; <DCLCONST2>

Se Token = 'CONST', use Regra 3
Se Token = 'TYPE', use Regra 2
Se Token = 'VAR', use Regra 2
Se Token = 'PROCEDURE', use Regra 2

Assim suscessivamente. Verifique que o Token 'Vazio', conforme já verificamos, permite que o algoritmo continue sem causar erro, e mantém o Token para ser comparado com a próxima regra.

Matriz Decisão : Esta matriz é a responsável por receber a dupla 'Token atual' e 'Símbolo não terminal' e indicar qual regra será utilizada para abrir o Símbolo. É importante lembrar que esta abertura não irá 'aprovar' o nosso token. Esta aprovação irá ocorrer apenas quando o Token atual coincidir com o seu símbolo terminal. Quando o token atual bate com o símbolo terminal atual, de um lado passamos para o próximo token, e de outro, tiramos o símbolo da pilha. Neste momento, o símbolo terminal estará associado a um evento que grava uma informação em um arquivo de saída ou na memória. Em caso de programas, geralmente é criado um código-objeto que deverá ser linkado com bibliotecas de rotinas, e será formado o código executável. Para uma expressão matemática, deverá ser criada uma lista encadeada por ponteiros, cujos itens estarão ligados dinamicamente à variáveis e funções.