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:
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 . 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 pertence à linguagem reconhecida pelo autômato .