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.