Dominando el Análisis Léxico: Lex, Tokens y Autómatas Finitos

Conceptos Fundamentales del Análisis Léxico

Definiciones Clave

¿Qué es un Token?

Es el “nombre” que se da a cada componente léxico.

¿Qué es un Lexema?

Es la secuencia de caracteres de la entrada que corresponden a un token.

¿Qué es un Patrón?

Es la forma compacta de describir conjuntos de lexemas.

Ejemplos de Tokens Habituales

• Palabras reservadas
• Identificadores
• Operadores
• Constantes
• Símbolos de puntuación:
  • ;
  • ,
  • .
  • :
• Símbolos especiales:
  • ( )
  • [ ]

El Analizador Léxico (Escáner)

Función Principal del Analizador Léxico

Es agrupar caracteres de la entrada en tokens.

Otros Roles del Analizador Léxico

• Procesar directivas al compilador.
• Introducir información preliminar en la tabla de símbolos.
• Eliminar separadores innecesarios (cuando no lo ha hecho un preprocesador).
• Sustituir macros.
• Formatear y listar el código fuente.

Fases del Analizador Léxico

• Fase de examen.
• Fase de análisis (propiamente dicho).

Información Requerida por los Tokens para su Identificación

• Constantes: Su valor.
• Identificadores: El string.
• Operadores relacionales: Su identificación.

Funciones del Escáner

• Identificar el token.
• “Evaluar” el token.

Tipo de Información que Devuelve el Escáner

• Si es un token constante, su valor.
• Si es un identificador, el string correspondiente.
• Si es un símbolo de puntuación, cuál.

¿Cómo Devuelve la Información el Escáner?

Se devuelve mediante “atributos”.

Características del Escáner

• Un conjunto de funciones: una para cada símbolo a reconocer.
• Estas funciones son controladas/invocadas por una función que selecciona, en función de los caracteres de entrada, qué función invocar.

Lex y sus Premisas

Premisas de Lex para Reconocer Lexemas

• Lex toma el lexema más largo posible.
• En caso de conflicto, toma siempre el patrón que aparezca en la primera posición.
• Como consecuencia de la segunda premisa, las palabras reservadas se colocan siempre antes que el patrón de identificador de usuario.

Caracteres Especiales Manejados por Lex

• (*
• \
• []
• -
• ^
• ?
• .
• |
• *
• +
• ()
• {}

Caracteres de Sensibilidad al Contexto en Lex

• $
• ^
• /
• <ID>

Funciones y Variables Suministradas por Lex

• yylex()
• yytext
• yyleng
• yylval
• yyerror()
• yywrap()
• yyless(n)
• input()
• output()
• echo
• yymore()
• reject

Teoría de Lenguajes Formales

¿Qué es un Alfabeto?

Es un conjunto finito de símbolos.

¿Qué es una Cadena?

Es una secuencia finita de elementos del alfabeto.

¿Qué es la Longitud de una Cadena?

Es el número de elementos del alfabeto que la componen.

¿Qué es un Lenguaje?

Dado un alfabeto, es cualquier conjunto de cadenas formadas con dicho alfabeto.

¿Qué es una Expresión Regular?

Es la forma compacta para definir un lenguaje regular, también llamado conjunto regular.

¿Qué es un Lenguaje Regular?

Es el generado a partir de una expresión regular.

Autómatas Finitos (AF)

Utilidad de los Autómatas Finitos

Pueden ser utilizados para reconocer los lenguajes definidos mediante expresiones regulares.

Nombres Alternativos para los Autómatas Finitos

Se les conoce también como reconocedores.

Misión de un Autómata Finito

Reconocer si un string de entrada respeta las reglas determinadas por una expresión regular.

¿Qué es un Autómata Finito Determinista (AFD)?

Es un caso particular de AFN que es mejor en cuanto a velocidad de reconocimiento.

Implementación de un Autómata Finito No Determinista (AFN)

Dado un string, debe determinar si lo acepta o no. El string c1, c2, … cn es aceptado por un AFN cuando existe en el grafo de transiciones un camino s0 → s1 → s2 → … → sm-1 de manera que sm es un estado final (de aceptación).

Componentes Léxicos para Evaluar Expresiones

• Constantes enteras sin signo.
• Operadores relacionales: <, <=, >, >=, <>, =.
• Identificadores de variables.

Componentes Léxicos Utilizados por el Analizador

• Menor (<)
• Igual (=)
• Identificador
• Mayor (>)
• Distinto (<>)
• Letra (letra|dígito*)
• Menor o igual (<=)
• Letra (a|b|…|z)
• Constante entera
• Mayor o igual (>=)
• Dígito (0|1…9)
• Dígito · Dígito*

Ventajas de los Autómatas Finitos

• Fácil de programar.
• Tiene un acceso rápido.

Desventajas de los Autómatas Finitos

• Despilfarro de memoria.

Métodos de Implementación de Autómatas Finitos

Primer Método de Implementación

Basado en que muchas columnas/filas suelen ser idénticas.

Segundo Método de Implementación

Especialmente útil cuando la matriz de transición es muy dispersa.

Errores Léxicos Comunes

Tipos de Errores Léxicos Más Comunes

• Debidos a un carácter extraño (suelen aparecer al principio del lexema).
• Desbordamiento de variables/constantes.
• Fin de línea antes de cerrar un string.
• Problemas al cerrar/abrir comentarios.