Tabla de Estados #

La tabla de estados consiste en tomar la especificación léxica mediante autómatas finitos (o crearlos a partir de las expresiones regulares) y unificar todos los autómatas. Posteriormente, el autómata resultante se hace determinista y se simplifica.

Por ejemplo, supóngase la siguiente especificación léxica:

Una vez unificados todos los autómatas en uno sólo, dicho autómata resultante se haría determinista y se simplificaría quedando de la siguiente forma:

Una vez hecho esto, el autómata se pasa a una tabla con la siguiente estructura:

• Una fila por cada estado.
• Una columna por cada carácter que pueda aparecer a la entrada.
• En cada celda, se pone el estado al que se cambiaría si estando en el estado de la fila de la celda llegara el carácter que indique la columna de la misma. Si no existe una transición en ese estado para esa entrada, se pondría un código de error en la celda.

Por ejemplo, supóngase la siguiente tabla con parte de la implementación del autómata:

Se puede ver en el autómata que, estando en el estado 2, si llega el carácter f, se debe ir al estado 3. Eso es lo que expresa, mediante el valor 3, la celda de la fila 2 y la columna f.

Una vez hecha esta tabla completa, sólo quedaría recorrerla hasta encontrar un lexema válido o un error. Esa es precisamente la implementación del método nextToken. En cada llamada a dicho método, a grandes rasgos, éste realiza los siguientes pasos:

1. Comienza en el estado 1 (fila 1).
2. Va pasando de estado en estado usando el siguiente carácter de la entrada como índice de la columna para determinar el nuevo estado al que ir.
3. Si en la celda del siguiente estado hay un error (la entrada no coincide con ninguna transición de salida del estado):
   • Si se ha pasado por algun estado final, se ha encontrado un lexema válido y el último estado final encontrado indica a qué token pertenece.
   • Si no se ha pasado por un estado final, se ha detectado una entrada que no pertenece al lenguaje y se debe notificar el error.