Análise Léxica

Como já sabemos, a análise léxica é responsável de devolver para o parser o conjunto das tuplas <token, conteúdo> associado a cada padrão reconhecido no programa, para que o este realize a construção da árvore sintática. Na realidade, o parser não recebe o resultado do processamento de todo programa pelo analisador léxico, os dois trabalham juntos processando o programa de entrada sob o comando do parser. Na leitura do primeiro caracter do programa, o parser chama o analisador léxico para avaliar o fluxo de entrada até que este retorne o padrão reconhecido, quando o parser efetua a comparação com a gramática da linguagem. Quando ele consegue associar o token a uma possibilidade de casamento com a gramática, chama o analisador léxico novamente para que retorne o novo token encontrado, com o qual um parser tentará realizar um novo casamento, como mostrado na Figura 6. Na prática então, o analisador léxico nada mais é do que uma sub-rotina do parser.

 O fluxo entre programa fonte e analisador léxico ocorre caracter por caracter, enquanto o corrente conjunto de caracteres não é identificado com um símbolo válido para linguagem. Um símbolo válido pode ser uma sequência que defina um número, um identificador de variável, um operador qualquer ou uma palavra reservada da linguagem. O token é o identificador do padrão reconhecido. Abaixo podemos ver uma sequência de palavras lidas, ou lexemas, e os correspondentes tokens reconhecidos para uma linguagem Pascal-like. 

O applet Java a seguir implementa um analisador léxico para uma pequena classe de tokens: identificador, números inteiros e operadores relacionais. Você poderá escrever o código a ser analisado na área de texto e depois acionar o analisador pressionando a tecla "Iniciar". Cada vez que o você pressionar a tecla "Passo" o analisador avaliará o próximo caracter. Na caixa branca será mostrada uma lista das palavras identificadas e correspondentes tokens. Experimente primeiro o código circunf >= 12 e verifique o que ocorre.

Experimente o código >=circunf 12. O analisador léxico detectou algum erro? Por quê?

Especificar para uma linguagem todas as sequências de lexemas possíveis para um token, pode funcionar para palavras reservadas ou operadores, mas não funciona para identificadores e números porque há infinitas possibilidades de sequências de caracteres que constituem lexemas válidos. A melhor maneira de faze-lo é usando padrões.

Muito embora não possamos listar todos os identificadores possíveis para nossa linguagem, sabemos para serem válidos devem necessariamente começar por uma letra, seguida de uma sequência de letras, dígitos e mais alguns caracteres. Um número pode ser descrito como uma sequência de dígitos, podendo conter um único ponto em qualquer posição (desconsiderando aqui o caso de número com expoente). A melhor forma de especificarmos os padrões de tokens é por meio de expressões regulares.

Uma expressão regular define formalmente um padrão, mostrando quais os sub-padrões ou expressões regulares que a formam, com que regularidade cada uma delas aparece e quais são os diferentes sub-padrões que podem ser reconhecidos numa mesma posição do padrão. Na tabela abaixo, mostramos uma sintaxe de definição de expressões regulares, supondo a e b também expressões regulares. 

letra -> "a"|"b"|"c"|"d"| ...|"Z"
dígito -> "0"|"1"|"2"| ... |"9"
identificador -> letra (letra | dígito)*
número -> dígito+ (".")? dígito*

Determine os padrões que identificados pelo analisador léxico do applet anterior.

O reconhecimento de uma expressão regular por parte do analisador léxico pode ser descrito na forma de diagramas de transições, que definem mudanças de estados de acordo com símbolos recebidos. Por exemplo, o reconhecimento de um identificador pode ser descrito como mostrado na Figura 7.

Na figura, o estado 2 representa um estado final, quando o diagrama reconhece a sequência de entrada. No nosso caso isso ocorre quando depois da sequência letra(letra|dígito)*, recebemos um caracter que não é letra nem dígito, significando que um identificador acaba de ser reconhecido. Este outro caracter não deve ser descartado; entretanto, deve passar novamente pelo o diagrama de estados a partir do estado de partida para que o reconhecimento possa continuar. No diagrama de estados para reconhecimento dos operadores relacionais, Figura 8, observamos a situação de reconhecimento de operadores relacionais, quando em estados intermediários o reconhecedor precisa tomar decisão quanto ao atributo do token relop identificado.

Do ponto de vista do projeto de analisadores léxicos é muito mais interessante pensar nos tokens a serem reconhecidos na forma de diagrama de estados, pois é uma representação mais próxima de implementação computacional, que é realizada na forma de máquinas de estados chamados autômatos finitos. Estes podem ser construídos na forma de autômatos finitos determinísticos ou não-determinísticos.

Autômatos finitos não-determinísticos são autômatos em que no mínimo em um estado, para um dado caracter, ou não existe transição definida ou existe mais de uma transição para diferentes estados. É o caso do autômato da Figura 9, que define o reconhecimento de número inteiros e reais (sem expoente).

Caso um dígito seja reconhecido no estado inicial, existe 2 estados para os quais o AFND pode transitar: o estado 1 ou o estado 3. Suponha que por algum motivo o autômato tenha resolvido passar para o estado 1 ao reconhecer um dígito. Se após um número qualquer de reconhecimento de dígitos, o autômato ler o caracter ".", ele irá para o estado 2, retornando que reconheceu um número inteiro. Por conseguinte, se a entrada era na realidade um número real, nas transições seguintes o autômato fará reconhecimentos errados. No AFND é necessário portanto que sejam verificadas todas as possibilidades de reconhecimento de padrões, avaliando os demais caminhamentos do diagrama de estados. O token aceito, caso exista alguma possibilidade, será aquele associado ao maior lexema possível reconhecido pela máquina.

Os AFDs - autômatos finitos determinísticos - exigem que cada estado tenha uma única transição para cada um dos caracteres do seu alfabeto. AFDs por não permitirem essa redundância, facilitam o processo de reconhecimento correto de tokens. Na prática, um analisador léxico implementado via AFND é mais lento do que um implementado por AFD, por precisam ser computadas essas outras possibilidades de reconhecimento de tokens. Dadas as expressões regulares que descrevem os tokens de uma linguagem, facilmente conseguimos implementar AFD que efetuam o reconhecimento correto. Esse algoritmo de conversão preferimos não demonstrar aqui.

No applet seguinte, você pode observar o mesmo analisar léxico implementado anteriormente, agora com o diagrama de transições exibido. Entre com várias entradas e verifique como o autômato se comporta.

Autômatos finitos são máquinas de fácil computação e implementação. Formalmente, podemos descrever um autômato como um conjunto de estados Q, um alfabeto S , um estado inicial q₀, um conjunto de estados finais F e um conjunto de transições d na forma d(q_k,c)=q_j que definem que se o autômato está no estado q_k, ao ler o caracter c irá para o estado q_j. Se conseguirmos implementar um autômato finito genérico que recebe como parâmetros Q, S , d , q₀ e F, teremos um analisador léxico genérico.

Como o esforço de programação de analisadores léxicos para linguagens usuais é relativamente grande, dada a simplicidade da tarefa e sua pequena dimensão dentro do projeto de um compilador, é importante dispormos de analisadores léxicos genéricos ou geradores de analisadores léxicos, que garantem sua perfeita funcionalidade dada a relação dos tokens da linguagem.

Mais adiante, serão vistas algumas ferramentas de para construção de analisadores léxicos. Elas são ferramentas poderosas na construção e no ensino de compiladores.