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.