2.5.1. Diagrama de Transiciones

Como paso intermedio en la construcción de un analizador léxico, primero se produce un diagrama de flujo estilizado, llamado diagrama de transiciones. Los diagramas de transiciones representan las acciones que tienen lugar cuando el analizador léxico es llamado por el analizador sintáctico para obtener el siguiente componente léxico.

Se utiliza un diagrama de transición para localizar la información sobre los caracteres que se detectan a medida que el apuntador delantero examina la entrada. Esto se hace cambiando de posición en el diagrama según se leen los caracteres.

Las posiciones en un diagrama de transición se representan con un círculo y se llaman estados. Los estados se conectan mediante flechas, llamadas aristas. Las aristas que salen del estado s tienen etiquetas que indican los caracteres de entrada que pueden aparecer después de haber llegado el diagrama de transición al estado s. La etiqueta otro se refiere a todo carácter que no haya sido indicado por ninguna de las otras aristas que salen de s. Un estado se etiqueta como el estado de inicio; es en el estado inicial del diagrama de transición donde reside el control cuando se empieza a reconocer un componente léxico. Ciertos estados pueden tener acciones que se ejecutan cuando el flujo del control alcanza dicho estado. Al entrar en un estado se lee el siguiente carácter de entrada. Si hay una arista del estado en curso de ejecución cuya etiqueta concuerde con ese carácter de entrada, entonces se va al estado apuntado por la arista. De otro modo, se indica un fallo.

En la figura se muestra un diagrama de transiciones para los patrones >= y >. El diagrama de transiciones funciona de la siguiente forma. Su estado de inicio es el estado 0. En el estado 0 se lee el siguiente carácter de entrada. La arista etiquetada con >del estado O se debe seguir hasta el estado 6 si este carácter de entrada es >. De otro modo, significa que no se habrá reconocido ni > ni >=.

Al llegar al estado 6 se lee el siguiente carácter de entrada. La arista etiquetada con = que sale del estado 6 deberá seguirse hasta el estado 7 si este carácter de entrada es un =. De otro modo, la arista etiquetada con otro indica que se deberá ir al estado 8. El circulo doble del estado 7 indica que éste es un estado de aceptación, un estado en el cual se ha encontrado el componente léxico >=.

Obsérvese que el carácter > y otro carácter adicional se leen a medida que se sigue La secuencia de aristas desde el estado inicial al estado de aceptación 8. Como el carácter adicional no es parte del operador relacional >, se debe retroceder un carácter el apuntador delantero. Se usa un * para indicar los estados en que se debe llevar a cabo este retroceso en la entrada.

En general, puede haber varios diagramas de transiciones, cada uno de los cuales especifique un grupo de componentes léxicos. Si surge un fallo mientras se está siguiendo un diagrama de transiciones, se debe retroceder el apuntador delantero hasta donde estaba en el estado inicial de dicho diagrama, y activar el siguiente diagrama de transiciones. Dado que los apuntadores de inicio de lexema y los delanteros marcaban la misma posición en el estado inicial del diagrama,  se retrocede el apuntador delantero hasta la posición que marca el apuntador al inicio de lexema. Si el fallo surge en todos los diagramas de transiciones, es que se ha detectado un error léxico y se invoca una rutina de recuperación de errores.