Analisadores léxicos

Um analisador léxico, ou scanner, é um programa que implementa um autômato finito, reconhecendo (ou não) strings como símbolos válidos de uma linguagem.

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 essa descrição, é possível oferecer os seguintes procedimentos auxiliares para o analisador léxico:

ESTADO-INICIAL, que recebe como argumento a referência para o autômato e retorna o seu estado inicial;

ESTADO-FINAL, que recebe como argumentos a referência para o autômato e a referência para o estado corrente. O procedimento retorna true se o estado especificado é elemento do conjunto de estados finais do autômato, ou false caso contrário; e

PRÓXIMO-ESTADO, que 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.

A sentença a ser reconhecida é estruturada como uma lista de símbolos, que é passada como argumento para o analisador léxico juntamente com a referência para o autômato.

O analisador léxico inicia sua operação definindo o estado inicial como o estado corrente. Obtém então o próximo símbolo (que inicialmente é o primeiro símbolo) da sentença $\sigma$. Se não houver próximo símbolo, é preciso verificar se o estado corrente é um estado final. Se for, o procedimento retorna true, indicando que a sentença foi reconhecida pelo autômato. Se o estado corrente não for um estado final e não houver mais símbolos na sentença, então não houve reconhecimento e o procedimento retorna false.

Se houver símbolo a ser analisado, então o procedimento deve continuar o processo de reconhecimento. Para tanto, obtém o próximo estado correspondente à transição do estado atual pelo símbolo sob análise. Se não houver transição possível, então a sentença não foi reconhecida e o procedimento deve encerrar, retornando false.

Esse algoritmo é apresentado no Algoritmo 3.1, que determina se a string $\sigma$ pertence à linguagem reconhecida pelo autômato $M$.