Construindo um Compilador - Parte 1

Esta série de posts foi instigada por uma mensagem no grupo C++ Brasil.

Minha primeira experiência em construir um compilador foi na faculdade. Lembro vagamente que era um compilador que gerava um programa para uma calculadora Texas a partir de uma linguagem parecida com Basic.

Recem formado, tive a oportunidade de participar de uma série de cursos na Scopus, não relacionados diretamente a projetos. Um deles foi A Construção de Um Compilador, lecionado pelo professor Valdemar Setzer. O material para este curso foi uma versão preliminar de um livro do próprio Setzer (em conjunto com Inês S Homem de Melo), que posteriormente viria a ser publicado pela Editora Campus.

Vários anos depois, tive a oportunidade de utilizar na prática estes conhecimentos, ao participar da definição e desenvolvimento de uma linguagem de script para o programa de comunicação Zapt da Humana Informática.

A forma de implementar um compilador que vou apresentar nestes posts se baseia diretamente no livro do Setzer. Obviamente vou ser bastante superficial nestes posts (o livro tem mais de 300 páginas).



O Que é Um Compilador?

Podemos dizer que um compilador é um programa que traduz um programa escrito em uma linguagem (linguagem fonte) para uma outra linguagem (linguagem objeto). Tipicamente a linguagem fonte é uma linguagem de alto nível e a linguagem objeto é o código de máquina.

Um parente próximo do compilador é o interpretador, que ao invés de gerar o programa em linguagem objeto ele o executa.

Um compilador pode não converter diretamente a linguagem fonte na linguagem objeto, ele pode ser composto de vários passos utilizando linguagens intermediárias. Um exemplo típico são compiladores que usam linguagem Assembly como uma linguagem intermediária.

Definindo Uma Linguagem

Tipicamente a definição de uma linguagem começa com os itens básicos para a escrita de programas: palavras reservadas, símbolos especiais, constantes e identificadores. Estes itens são denominados itens léxicos.

A forma como estes itens léxicos são combinados para gerar declarações, expressões e comandos em geral de uma linguagem é definida pela gramática da linguagem. Existem várias formas de se definir uma linguagem, algumas mais formais (como a notação BNF) e outras menso. Nestes posts vou usar os grafos sintáticos para descrever a gramática.

A definição da linguagem pode facilitar ou complicar a sua compilação. O método que será abordado é mais adequado para lingugens "bem comportadas".

Estrutura de Um Compilador

Tradicionalmente se divide o compilador em três grandes partes:

• Analisador Léxico: reconhece no fonte os itens léxicos
• Analisador Sintático: verifica se a sequência de itens léxicos contida no fonte está de acordo com a gramática da linguagem e reconhece as várias construções.
• Analisador Semântico: Gera o código objeto para as construções reconhecidas pala analisador sintático.

No próximo post veremos como fazer um analisador léxico.

De volta com o post #100 e um balanço

Após um mês de muito trabalho, estou retomando os posts no blog com um balanço deste um ano e meio de existência e uma idéia do que pretendo publicar no futuro.

Pois é, este é o centésimo post. Num levantamento rápido, os 99 posts passados envolveram principalmente Programação (27), Livros (22) e Microsoft (21). Como o gráfico abaixo (total de visitas por semana) mostra, tem algumas pessoas passando por aqui, mesmo quando não tem um post novo. As séries sobre gerenciamento de memória e construção de compiladores são as mais populares . Os posts sobre livros também tem os seus hits, principalmente por gente procurando eBooks para baixar.

O número de posts me parece satisfatório, considerando o tipo de posts que eu procuro fazer. De um modo geral, eu evito os posts curtos que tem apenas um link (principalmente para notícias efêmeras). A maioria dos meus posts exige um tempo razoável de pesquisa e escrita e certamente não dá para fazer um por dia.

Segue uma lista parcial de idéias para posts (ou série de posts) futuros; aceito sugestões nos comentários:

• Concluir a série "Construindo um Compilador" (urgente!)
• Projeto de Hw com PIC (controlando um LED, construindo um velocímetro para bicicleta)
• Gravação de CD usando a interface IMAPI do Windows
• A Reserva de Mercado de Informática
• Memórias (programando em Assembler 8bits e participando do projeto de um clone do IBM-PC na Scopus, desenvolvendo um software de comunicação de dados, etc)
• Meus primeiros computadores (TK-82C e o Apple II)

Construindo um Compilador - Parte 2

Nesta parte vamos ver como se constrói um analisador léxico. Como vimos na parte 1, ele é responsável por reconhecer os itens léxicos no fonte.

Itens léxicos típicos são identificadores de variáveis e rotinas, palavras reservadas, constantes e símbolos. Cada um destes itens se caracteriza por uma seqüência de caracteres que segue uma regra simples (por exemplo, "um identificador deve começar por uma letra e possuir somente letras e números"). Isto recomenda o uso de máquinas de estado para o reconhecer os itens léxicos. Toda vez que o analisador léxico é chamado para reconhecer o próximo item léxico, ele parte de um estado inicial e vai mudando de estado a cada caractere examinado, até reconhecer o item ou detectar uma seqüência inválida de caracteres (um "erro léxico").

Por exemplo, vamos considerar um caso simples, em que os itens léxicos são números inteiros decimais e as operações + e -. De uma forma livre, teríamos o seguinte analisador léxico na linguagem C:

estado = INICIAL;
while (estado != FINAL)
{
c = ProximoCaracter();
switch (estado)
{
case INICIAL:
  if (c == EOF)
  {
     item = EOF;
     estado = FINAL;
  }
  else if (isdigit(c))
     estado = NUMERO;
  else if (c == '+')
  {
     item = MAIS;
     estado = FINAL;
  }
  else if (c == '-')
  {
     item = MENOS;
     estado = FINAL;
  }
  else if (!isspace(c))
  {
     item = ERRO;
     estado = FINAL;
  }
  break;
case NUMERO:
  if (c == EOF)
  {
     item = NUMERO;
     estado = FINAL;
  }
  if (!isdigit(c))
  {
     DevolveCaracter(c);
     item = NUMERO;
     estado = FINAL;
  }
}
}

Para não estender mais o código, não estamos guardando o valor do número (o que fica como exercício para o leitor). Reparar que eventualmente o código acima examina um caractere além do final do item e precisa "devolvê-lo". Tipicamente um analisador léxico não precisa guardar estados entre uma chamada e outra nem voltar atrás nos seus passos.

Algumas linguagens possuem idiossincrasias que dificultam o analisador léxico. Por exemplo, algumas versões do FORTRAN permitem colocar espaços no meio de identificadores, criando seqüências de difícil análise como:

DO 10 I = 1, 10

Somente ao encontrar a vírgula o analisador léxico descobre que os itens léxicos são <DO> <10> <I> <=> (comando DO) ao invés de <DO10I> <=> (o que seria um comando de atribuição).

O analisador léxico é também responsável por desprezar os comentários nos fontes.

No caso de identificadores e palavras reservadas, a máquina de estado apenas isola a seqüência de caracteres. O analisador léxico precisa também identificar o item.

No caso das palavras reservadas, normalmente existe uma tabela ou lista onde a seqüência isolada deve ser procurada. Uma forma simples, mas ineficiente, é fazer uma busca seqüencial. Uma forma mais inteligente é ordenar previamente a lista e fazer uma busca binária.

Uma forma ainda melhor é usar hashing. No hashing, calcula-se um número (hash) a partir da seqüência de caracteres e usa-se este número como índice para a tabela.

O principal problema com o hashing é que várias seqüências podem gerar o mesmo hash (gerando uma colisão). Ao inserir um item numa tabela de hash, se a posição já estiver ocupada é preciso fazer uma lista ligada na posição para colocar o novo item. Ao fazer uma busca, é preciso fazer uma busca seqüencial nesta lista ligada.

Uma opção para diminuir as colisões é aumentar a faixa de valores para o hash, porém isto leva ao desperdício de memória. No caso das palavras reservadas, a lista é constante, o que permite escolher previamente uma função de hash que evite colisões. Por exemplo, pode-se criar uma função parametrizada e deixar um computador procurando exaustivamente os parâmetros que otimizem a função de hash.

Uma vez determinado que uma seqüência não é uma palavra reservada, o analisador léxico deve tentar descobrir o tipo de identificador. Isto é feito procurando a seqüência em tabelas de nomes de variáveis, funções, etc construída pelo analisador semântico. Estas tabelas podem usar o hashing para otimizar a busca. Um truque simples mas eficaz consiste ao encontrar um item na lista ligada da tabela de hash mover este item para o início da lista. Isto faz com que a lista automaticamente se ordene em função do uso dos itens.

Em algumas linguagens é permitido usar um identificador que ainda não foi declarado e portanto tem tipo ignorado. Isto não afeta o analisador léxico porém complica o analisador sintático e pode obrigar o analisador semântico a segurar a geração do código objeto até que o identificador seja declarado.

Na próxima parte vamos ver o coração do compilador, o analisador sintático.

Construindo um Compilador - Parte 4

Recordando o que vimos na parte anterior, o algorítmo que estamos apresentando realiza uma análise descendente, na qual se procura identificar itens sintáticos cada ver mais simples. Em cada instante temos como objetivo reconhecer um determinado item sintático. A gramática indica quais os itens sintáticos que compõem o nosso objetivo, Alguns destes itens correspondem diretamente a item léxicos (são os chamados símbolos terminais), outros correspondem a itens sintáticos mais complexos (os não-terminais). No caso dos não-terminais, vamos salvar temporariamente o nosso objetivo atual numa pilha enquanto reconhecemos este novo objetivo.

A estrutura principal para realizar a análise sintática representa o grafo sintático e é um vetor de estruturas que armazenam os nós. Exemplificando em C:

typedef struct
{
int simb; // código do símbolo
int fTerm; // TRUE se simbolo terminal, FALSe se não-terminal
int alt; // índice do nó alternativo (-1 se não tiver)
int seg; // índice do nó seguinte (-1 se não tiver)
} NO;

Um segundo vetor armazena o índice do primeiro nó de cada não-terminal:

typedef struct
{
char *nome; // nome do não terminal (para debug)
int prim; // índice do primeiro nó
} NT;

Desta forma, quando queremos reconhecer um não-terminal, partimos do primeiro nó e vemos se ele corresponde ao item léxico atual. Se sim, obtemos o próximo item léxico e passamos ao nó seguinte. Se for diferente, vamos examinar o nó alternativo.

Estas tabelas podem ser constantes dentro do programa ou carregadas dinamicamente a partir de um arquivo. O trecho abaixo corresponde ao nosso exemplo da parte anterior:

// códigos dos terminais
#define T_VAZIO 0
#define T_NUM 1
#define T_MUL 2
#define T_DIV 3
#define T_SOMA 4
#define T_SUB 5
#define T_ABRE 6
#define T_FECHA 7

// códigos dos não-terminais
#define NT_FATOR 0
#define NT_TERMO 1
#define NT_EXPR 2

NT TabNaoTerm[] =
{
{ "Fator", 0 },
{ "Termo", 4 },
{ "Expr", 8 }
}

NO GrafoSint[] =
{
/* simb fTerm alt seg */
/* 0 */ { T_NUM, FALSE, 1, -1 },
/* 1 */ { T_ABRE, TRUE, -1, 2 },
/* 2 */ { NT_EXPR, FALSE, -1, 3 },
/* 3 */ { T_ABRE, TRUE, -1, -1 },

/* 4 */ { NT_FATOR, FALSE, -1, 5 },
/* 5 */ { T_MUL, TRUE, 5, 4 },
/* 6 */ { T_DIV, TRUE, 6, 4 },
/* 7 */ { T_VAZIO, TRUE, -1, -1 },

/* 8 */ { NT_TERMO, FALSE, -1, 9 },
/* 9 */ { T_SOMA, TRUE, 10, 8 },
/* 10 */ { T_SUB, TRUE, 11, 8 },
/* 11 */ { T_VAZIO, TRUE, -1, -1 },

}

O terminal T_VAZIO indica a situação em que o item léxico atual não precisa ser consumido para o reconhecimento.

O algorítmo do analisador sintático fica assim:

#define TAM_PILHA
int pilha[TAM_PILHA];
int topo = 0;

// retorna TRUE se sucesso, FALSE se encontrou erro
int AnalisadorSintatico ()
{
int item; // item léxico atual
int no; // no atual

// Nosso objetivo é uma expressão
no = TabNaoTerm [NT_EXPR].prim;

// le o primeiro item léxico
item = AnalisadorLexico ();

while (TRUE)
{
if (no != -1)
{
if (GrafoSint[no].fTerm)
{
if (GrafoSint[no].simb == T_VAZIO)
no = GrafoSint[no].seg; // reconheceu vazio
else if (GrafoSint[no].simb == item)
{
no = GrafoSint[no].seg; // reconheceu item léxico
item = AnalisadorLexico ();
}
else if (GrafoSint[no].alt != -1)
no = GrafoSint[no].alt; // não reconheceu mas tem alternativa
else
return FALSE; // sem alternativas: erro sintático
}
else
{
// temos um novo objetivo
if (topo >= TAM_PILHA)
return FALSE; // pilha cheia
pilha[topo++] = no;
no = TabNaoTerm [GrafoSint[no].simb].prim;
}
}
else
{
// reconheceu um não terminal
if (topo > 0)
{
// continua no seguinte
no = pilha[--topo];
no = GrafoSint[no].seg;
}
else
return TRUE; // chegamos ao final
}
}
}

Obviamente estamos fazendo grandes simplicações neste código.

Em primeiro lugar, estamos ignorando o tratamento de erros sintáticos. No mínimo o analisador deveria indicar em que ponto ocorreu o erro. Uma outra informação é a indicação do que era esperado. Por último existe a questão de recuperação do erro, permitindo prosseguir a análise. Embora tudo isto possa ser feito automaticamente a partir do grafo sintático, na prática é preferível programar um heurística específica para a linguagem, considerando quais os erros mais comuns e quais as recuperações que introduzem menos erros espúrios.

Neste algorítmo estamos apenas percorrendo o gráfico e verificando se a entrada obedece à gramática. Um compilador ou interpretador precisa executar ações à medida em que os itens são reconhecidos. Isto pode ser feito acrescentando ao nó uma indicação de qual rotina semântica deve ser executada (esta indicação pode ser um índice ou um ponteiro).

Na próxima parte vamos examinar um pouco mais o tratamento semântico.

Construindo um Compilador - Parte 3

Vamos começar a estudar nesta parte como fazer um analisador sintático. Na parte anterior, usamos uma máquina de estados (também chamada de autômato finito) para fazer a análise léxica. Na máquina de estados do analisador léxico os itens léxicos são reconhecidos analisando a entrada sequêncialmente da esquerda para a direita.

Na análise sintática esta forma de operação não é suficiente. O reconhecimento de uma construção sintática requer o reconhecimento de vários trechos, não necessáriamente da esquerda para a direita. Além disso, é comum um item ser definido de forma recursiva. Consideremos este exemplo de linguagem, onde os itens léxicos são num, '*', '/', '+', '-', '(' e ')':

e vamos analisar o seguinte "programa fonte":

10 + ( 70 - 4 * 5 )

o reconhecimento dos vários itens léxicos e sintáticos gera um árvore:
A figura acima sugere duas estatégias básicas para a análise sintática:

• análise ascendente, onde itens sintáticos mais complexos vão sendo reconhecidos a partir de itens sintáticos mais simples.
• análise descentente, onde se procura identificar itens sintáticos cada ver mais simples.

O algorítimo que apresentarei utiliza a análise descendente. Em cada passo teremos como objetivo reconhecer um item sintático. Para isto utilizamos uma tabela que representa os grafos que indicam as várias alternativas disponíveis naquele instante, junto com uma pilha que guarda os sucessivos objetivos à medida em que descemos na análise.

Considerando a expressão de exemplo, teríamos os seguintes passos iniciais:

• O nosso objetivo inicial é reconhecer uma expressão.
• O primeiro item de uma expressão tem que ser um termo, salvamos na pilha o ponto em que estamos no reconhecimento da expressão e passamos a tentar reconhecer um termo.
• O primeiro item de um termo tem que ser um fator, salvamos na pilha o ponto em que estamos no reconhecimento do termo e passamos a tentar reconhecer um fator.
• Um fator pode começar com um '(' ou com um número. No nosso caso encontramos o número '10' e com isto concluímos o reconhecimento de um fator.
• Retiramos da pilha o nosso objetivo. Estamos reconhecendo um termo, já reconhecemos um fator. As alteranativas seguintes são '*', '/' ou final do reconhecimento. Como o item seguinte é um '+', damos por encerrado o reconhecimento do termo.
• Voltamos assim ao reconhecimento da expressão. Já reconhecemos um termo, as alternativas seguintes são '+', '-' ou fim do reconhecimento.
• Como temos um '+', passamos a reconhecer um novo termo

Este algorítimo, que usa um autômato finito com pilha, permite analisar uma grande variedade de linguagens, mas não todas. A principal restrição é que cada item léxico reconhecido determina imediatamente o próximo "ramo" da sintaxe a ser examinado.

No próximo post vamos ver em detalhes como se implementa este algorítimo.