Reconhecimento de tokens
Anteriormente vimos como se podem expressar padrões utilizando expressões regulares.
Assim sendo, vamos definir as expressões regulares para os tokens do seguinte excerto duma linguagem:
Os símbolos terminais desta gramática são: if, then, else, relop, id e number.
Os padrões para reconhecer estes tokens podem ser descritos com expressões regulares:
Adicionalmente, o analisador léxico deve reconhecer e eliminar os caracteres correspondentes ao espaço em branco:
ws -> (blank | tab | newline)+
Vamos tentar construir um analisador léxico que para além de reconhecer os tokens crie a seguinte informação:
Diagramas de transição
Como passo intermédio para a construção do analisador léxico, vamos converter “à mão” as expressões regulares em máquinas de estados (representadas por diagramas de transição).
Veremos mais à frente que este processo pode ser sistematizado recorrendo a autómatos finitos.
Os diagramas de transição contêm uma colecção de estados (representados por círculos).
Cada estado representa uma sequência de condições que ocorreram no processo de reconhecimento léxico.
Isto é, cada estado representa o que já aconteceu até esse ponto no reconhecimento da sequência de caracteres de entrada no analisador.
As transições são dirigidas de um estado para outro, e são anotadas com a entrada que lhes corresponde.
As convenções a aplicar a estes diagramas são as seguintes:
Cada estado é representado por um círculo e tem a si associado um rótulo que o identifica (em geral, um número ou uma letra).
Alguns estados são considerados como finais (ou de aceitação). Estes estados indicam que um token foi reconhecido. Estes estados são representados com um círculo duplo.
Se, por necessidade, tiver sido consumido um carácter a mais nesse processo de aceitação final, o nó que lhe corresponde será anotado com um asterisco.
As transições entre estados são representadas por setas anotadas com o carácter que a despoleta.
Um estado é designado como estado inicial, sendo indicado por uma transição (seta) sem estado de origem.
Na construção destes diagramas vamos simplesmente enumerar novos estados por cada transição resultante de um carácter que, de alguma forma, avance no reconhecimento do token.
O diagrama de transição para reconhecer os operadores relacionais pode ser o seguinte:
Note que, para este tipo de tokens, este diagrama é uma estrutura de dados tipo árvore (deitada). Isso acontece em tokens fixos como o exemplificado ou as palavras reservadas.
O diagrama de transição para identificadores:
O reconhecimento de identificadores pode levantar um problema de ambiguidade.
De facto, as palavras reservadas da linguagem (ex: then) também podem ser reconhecidas como identificadores.
Para resolver este problema, os analisadores léxicos dão prioridade a tokens que consomem mais caracteres e, em caso de conflito, estabelecem diferentes prioridades entre estes.
Assim, o conflito entre identificadores e palavras reservadas é resolvido dando mais prioridade a estas.
O diagrama de transição para palavras reservadas é aqui exemplificado com o token then:
O diagrama de transição para números:
O diagrama de transição para espaço em branco:
Agora podemos traduzir de uma forma quase automática os diagramas de transição para analisadores léxicos:
Note que nos estados que requerem um carácter para fazerem uma transição {0;1;6}, é invocada a função nextChar; assim como os estados com asterisco, o carácter a mais é reposto com a função retract.
Podemos implementar uma função por tipo de token (getID, getReserved, getWS, getnumber), e depois invocar sequencialmente cada uma delas (até que uma seja bem sucedida).
No entanto, esta solução não é a mais eficiente já quem na presença de falhas, estamos a rebobinar a fila de caracteres de entrada.
Alternativamente, podemos tentar executar os vários diagramas em paralelo.
Se se utilizar uma numeração diferente nos estados de cada token (como foi feito neste exemplo), a melhor solução será simplesmente juntar todas as máquinas de estados numa única.
Esta solução não só pode ser automatizada, como também é bastante eficiente (isso pode ser medido pelo número de vezes em que é necessário voltar atrás no consumo de caracteres, i.e. nas invocações da função retract).
As máquinas que permitem uma aproximação automática a este problema são os chamas autómatos finitos (como veremos, os diagramas de transição apresentados descrevem autómatos finitos deterministas incompletos).
Last updated
