Construção de compiladores/Análise léxica

Análise léxica é o processo de analisar a entrada de linhas de caracteres (tal como o código-fonte de um programa de computador) e produzir uma sequência de símbolos chamado "símbolos léxicos" (lexical tokens), ou somente "símbolos" (tokens), que podem ser manipulados mais facilmente por um parser (leitor de saída). O componente do compilador responsável pela execução desse processo é conhecido como Analisador léxico.

O analisador léxico, ou scanner como também é chamado, faz a varredura do programa fonte caractere por caractere e, traduz em uma sequência de símbolos léxicos ou tokens. É nessa fase que são reconhecidas as palavras reservadas, constantes, identificadores e outras palavras que pertencem a linguagem de programação. O analisador léxico executa outras tarefas como por exemplo o tratamento de espaços, eliminação de comentários, contagem do número de linhas que o programa possui e etc.

A análise léxica é a forma de verificar determinado alfabeto. Quando analisamos uma palavra, podemos definir através da análise léxica se existe ou não algum caractere que não faz parte do nosso alfabeto, ou um alfabeto inventado por nós.

É a primeira etapa do processo de compilação e seu objetivo é dividir o código fonte em símbolos, preparado-o para a Análise Sintática. Neste processo pode-se destacar três atividades como fundamentais:

Extração e classificação dos tokens;
Eliminação de delimitadores e comentários;
Recuperação de Erros.

O analisador léxico funciona de duas maneiras:

Primeiro estado da análise: A primeira etapa lê a entrada de caracteres, um de cada vez, mudando o estado em que os caracteres se encontram. Quando o analisador encontra um caracter que ele não identifica como correto, ele o chama de "estado morto" então, ele volta à última análise que foi aceita e assim tem o tipo e comprimento do léxico válido.

Um léxico, entretanto, é uma única lista de caracteres conhecidas de ser um tipo correto. Para construir um símbolo, o analisador léxico necessita de um segundo estado.

Segundo estado da análise: Nesta etapa são repassados os caracteres do léxico para produzir um valor. O tipo do léxico combinado com seu valor é o que adequadamente constitui um símbolo, que pode ser dado a um parser. (Alguns símbolos tais como parênteses não têm valores, e então a função da análise pode retornar nada).

A análise léxica escreve um parser muito mais fácil. Em vez de ter que acumular, renomeia seus caracteres individualmente. O parser não mais se preocupa com símbolos e passa a preocupar-se só com questões de sintática. Isto leva a eficiência de programação, e não eficiência de execução. Entretanto, desde que o analisador léxico é o subsistema que deve examinar cada caracter único de entrada, podem ser passos intensivos e o desempenhos se torna crítico, pode estar usando um compilador.

As desvantagens da Análise Léxica são o tratamento de dados em branco, formato fixo de entrada e a inexistência de palavras reservadas, em determinadas linguagens.

Analisador Léxico

A implementação de um analisador léxico requer uma descrição do autômato que reconhece as sentenças da gramática ou expressão regular de interesse com os seguintes procedimentos auxiliares:

Estado-Inicial: Recebe como argumento a referência para o autômato e retorna o seu estado inicial;

Estado-final: Recebe como argumentos a referência para o autômato e a referência para o estado corrente. O procedimento retorna true (verdadeiro) se o estado especificado é elemento do conjunto de estados finais do autômato, ou false (falso) caso contrário; e

Próximo-Estado: Recebe como argumento a referência para o autômato, para o estado corrente e para o símbolo sendo analisado. O procedimento consulta a tabela de transições e retorna o próximo estado do autômato, ou o valor nulo se não houver transição possível.

Nesta fase do processo de compilação, uma sequência de caracteres do código do programa é lida e agrupada em uma sequência de tokens.

Erros léxicos

Poucos erros podem ser detectados durante a análise léxica dada a visão restrita desta fase,

como mostra o exemplo: fi(a== f(x)) outro_and;

fi é a palavra chave if grafada incorretamente?
fi é um identificador de função que não foi declarada faltando assim um separador (‘;’)

entre a chamada da função fi e o comando seguinte (outro_and)?

Ainda assim o analisador léxico pode não conseguir prosseguir dado que a cadeia encontrada não se enquadra em nenhum dos padrões conhecidos.
Para permitir que o trabalho desta fase prossiga mesmo com a ocorrência de erros deve ser implementada uma estratégia de recuperação de erros

Recuperação de erros

Ações possíveis:

remoção de sucessivos caracteres até o reconhecimento de um token válido (modalidade Pânico).
inserção de um caractere ausente.
substituição de um caractere incorreto por outro correto.
transposição de caracteres adjacentes.

Tais estratégias poderiam ser aplicadas dentro de um escopo limitado(denominado erros de distância mínima).

While (a<100) {fi(a==b) break else a++;} ...

Estas transformações seriam computadas na tentativa de obtenção de um programa sintaticamente correto (o que não significa um programa correto, daí o limitado número de compiladores experimentais que usam tais técnicas).

Tokens

O objetivo principal da análise léxica é identificar sequências de caracteres que constituem unidades léxicas ("tokens"). O analisador léxico lê, caractere a caractere, o texto fonte, verificando se os caracteres lidos pertencem ao alfabeto da linguagem, identificando tokens, e desprezando comentários e brancos desnecessários.

Os tokens constituem classes de símbolos tais como palavras reservadas, delimitadores, identificadores, etc., e podem ser representados, internamente, através do próprio símbolo (como no caso dos delimitadores e das palavras reservadas) ou por um par ordenado, no qual o primeiro elemento indica a classe do símbolo, e o segundo, um índice para uma área onde o próprio símbolo foi armazenado (por exemplo, um identificador e sua entrada numa tabela de identificadores).

Além da identificação de tokens, o Analisador Léxico, em geral, inicia a construção da Tabela de Símbolos e envia mensagens de erro caso identifique unidades léxicas não aceitas pela linguagem em questão. A saída do Analisador Léxico é uma cadeia de tokens que é passada para a próxima fase, a Análise Sintática. Em geral, o Analisador Léxico é implementado como uma sub-rotina que funciona sob o comando do Analisador Sintático.

O analisador léxico tem a função de ler uma sequência de caracteres que constitui um programa fonte e coleta, dessa sequência, os tokens que constituem esse programa.

Os tokens (símbolos léxicos) são unidades básicas de texto do programa. Eles são representados internamente por três informações: classe do token, valor do token e posição do token.

Classe do token – representa o tipo do token conhecido.

Valor do token – dependente da classe; podem ser divididos em dois grupos: tokens simples e tokens com argumento.

Posição do token – indica o local do texto fonte (linha e coluna) onde ocorreu o token.

Tokens simples – não tem um valor associado, por exemplo como as palavras reservadas.

Tokens com argumento – possuem um valor associado, por exemplo como os identificadores e as constantes.

As classes para palavras reservadas constituem-se em abreviações dessas, não sendo necessário passar seus valores para o analisador sintático.

É usual que os compiladores representem a classe de um token por um número inteiro para tornar a representação mais compacta.

Especificação

Os analisadores léxicos são, usualmente, especificados através de notações para a descrição de linguagens regulares tais como autômatos finitos, expressões regulares ou gramáticas regulares.

A especificação descreve o conjunto de tokens que formam a linguagem. Fazem parte dessa especificação sequências de caracteres que podem aparecer entre tokens e devem ser ignoradas tais como espaços em branco e comentários.

Na grande maioria das linguagens de programação, as palavras reservadas da linguagem são casos particulares dos identificadores e seguem a mesma notação desses.

As especificações de analisadores léxicos, usualmente, não expressam, explicitamente, o reconhecimento de palavras reservadas. Todas essas palavras então são armazenadas em uma tabela interna, que é examinada cada vez que um identificador é reconhecido. Se esse identificador ocorre na tabela, então trata-se de uma palavra reservada, caso contrário, trata-se de um identificador.

Em geral, o analisador léxico e o analisador sintático formam um único passo, porém, o analisador léxico pode constituir um passo individual do compilador. Quando atuam em um único passo, o analisador léxico atua como uma sub-rotina que é chamada pelo analisador sintático sempre que este necessita de mais um token.

Existem motivos que levam a dividir (conceitualmente) a análise do programa em análise léxica e sintática:

1) Simplificação e modularização do projeto do compilador;

2) Os tokens podem ser descritos utilizando-se notações simples (como expressões regulares), enquanto a estrutura sintática de comandos e expressões das linguagens de programação requer uma notação mais expressiva, como as gramáticas livres do contexto;

3) Os reconhecedores construídos a partir da descrição dos tokens (através de gramáticas regulares, expressões regulares ou autômatos finitos) são mais eficientes e compactos do que os reconhecedores construídos a partir das gramáticas livres de contexto.

Implementação

A implementação de analisadores léxicos é feita, em geral, através de uma tabela de transição, a qual indica a passagem de um estado a outro pela leitura de um determinado caractere. Através do uso de um gerador de analisadores léxicos, podem ser gerados a tabela e o correspondente programa de controle. No caso do gerador, o próprio projetista especifica os tokens a serem reconhecidos através de expressões regulares e a partir dessas expressões, o gerador gera um programa que implementa o analisador léxico correspondente.

Existe outra forma (alternativa) para se implementar um analisador léxico que é através da construção de um programa que simule o funcionamento do autômato correspondente.

Tabela de Símbolos

É uma estrutura de dados gerada pelo compilador com o objetivo de armazenar informações sobre os nomes (identificadores de variáveis, de parâmetros, de funções, de procedimentos, etc) definidos no programa fonte. Essa tabela associa atributos (tipo, escopo, limites no caso de vetores e número de parâmetros no caso de funções) aos nomes que foram definidos pelo programador. A construção dessa tabela, em geral, se dá durante a análise léxica, quando os identificadores são reconhecidos.

Quando um identificador é encontrado pela primeira vez, o analisador léxico armazena-o na tabela sem condições ainda de associar atributos a esse identificador. Geralmente essa tarefa é executada durante as fases de análise sintática e semântica.

Existem vários modos de se organizar e acessar as tabelas de símbolos sendo, os mais comuns:

1) Listas lineares - é o mecanismo mais simples, mas seu desempenho é pobre quando o número de consultas é elevado.

2) Árvores binárias

3) Tabelas hash - têm melhor desempenho, mas exigem mais memória e esforço de programação.