Ejecución de un autómata no determinista

-          Hilera de ejemplo: “aabbabb”

1.      Se inicia colocando en una línea al estado inicial con los estados a los que se puede llegar por medio de transiciones épsilon (cerradura).

    { 0  } + { 1 2 4 7 }

 

2.      En la siguiente línea se coloca la primera letra de la hilera. Luego el grupo de estados a los que se puede llegar desde los estados de la línea anterior reconociendo la letra actual, agregando después la cerradura de los estados anteriores.

a | { 3 8 } + { 6 7 1 2 4 }

 

Ejecución de un autómata no determinista (cont)

3.      Se repite el paso anterior para las siguientes letras de la hilera conservando su orden hasta acabar con las letras de la hilera obteniendo lo siguiente.

   | { 0    } + { 1 2 4 7 }

 a | { 3 8 } + { 6 7 1 2 4 }

 a | { 8 3 } + { 1 2 4 6 7 }

 b | { 9 5 } + { 6 7 1 2 4 }

 b | {10 5 } + { 6 7 1 2 4 }

 a | { 8 3 } + { 1 2 4 6 7 }

 b | { 9 5 } + { 1 2 4 6 7 }

 b | {10 5 } + { 1 2 4 6 7 }

 

4.      Si la ejecución se detiene antes de llegar a la última letra de la hilera o en la última línea no se encuentra un estado final dentro del grupo de estados incluyendo la cerradura significa que la hilera no está en el lenguaje del autómata, si no la hilera sí está en el lenguaje.

 

 

Tokens, patrones y lexemas

-          Token: par que consiste en un nombre de token y un valor de atributo opcional. El nombre es un símbolo abstracto que representa un tipo de unidad léxica, una palabra clave o una secuencia de caracteres de entrada que denotan un identificador.

 

-          Patrón: descripción de la forma que pueden tomar los lexemas de un token. En el caso de las palabras clave, el patrón es la secuencia de caracteres que forman tal palabra clave.

 

-          Lexema: secuencia de caracteres en el programa fuente que coinciden con el patrón de un token y que es identificado por el analizador léxico como una instancia de dicho token.

 

 

Ejemplos

 

Creación de analizadores léxicos con Lex

 

 

Estructura de los programas Lex

Declaraciones

%%

Reglas de traducción

%%

Funciones auxiliares

 

- Declaraciones: incluye la declaración de variables, constantes manifiestas como los nombres de tokens, y definiciones regulares.

 

- Reglas de traducción: tienen la forma  Patrón {Acción}

Los patrones son expresiones regulares y las acciones son fragmentos de código normalmente escritos en C.

 

- En la última sección se incluyen cualquier función adicional que se utilice en las acciones o que se vaya a necesitar en el analizador léxico final. El código escrito en esta sección será copiado literalmente en el analizador léxico final.

 

Ejemplo