next up previous contents
Next: Geradores de analisadores léxicos Up: Compiladores Previous: Minimização de estados   Sumário


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$.


\begin{Program}
% latex2html id marker 1736\begin{algorithm}{Scanner}{M,\sigm...
...\end{WHILE}\end{algorithm}\caption{Algoritmo do analisador léxico.}\end{Program}



Subsections
next up previous contents
Next: Geradores de analisadores léxicos Up: Compiladores Previous: Minimização de estados   Sumário
Ivan L. M. Ricarte 2003-02-14