Fundamentos de Autómatas Finitos y Procesamiento Léxico en Compiladores

Autómatas Finitos y Expresiones Regulares

Un autómata finito o máquina de estados finitos es un modelo matemático de un sistema que recibe una cadena compuesta por símbolos de un alfabeto y determina si dicha cadena pertenece al lenguaje que el autómata reconoce.

Formalmente, un autómata finito puede ser descrito como una quíntupla (S, Σ, T, s, A) donde:

S:

Representa un conjunto de estados.

Σ:

Es un alfabeto.

T:

Es la función de transición.

s:

Es el estado inicial.

A:

Es el conjunto de estados de aceptación o finales.

Formas de Representación de los Autómatas Finitos

Además de poder presentar un autómata finito a través de su definición formal, es posible representarlo mediante otras notaciones que resultan más cómodas y, en ocasiones, intuitivas. Las más usuales son las tablas de transición, los diagramas de transición y las expresiones regulares.

Analizador Léxico

El analizador léxico tiene como función principal tomar una secuencia de caracteres o símbolos del alfabeto del lenguaje y clasificarla en categorías conocidas como unidades léxicas. Estas unidades son empleadas por el analizador gramatical para determinar si lo escrito en el programa fuente es gramaticalmente correcto o incorrecto. Algunas de las unidades léxicas no son empleadas por el analizador gramatical, sino que son filtradas, como los comentarios que documentan el programa pero no tienen uso gramatical, o los espacios en blanco que sirven para dar legibilidad al código.

En la terminología empleada en la construcción de un analizador léxico se encuentran los siguientes términos:

Patrón:

Representa la regla para que una secuencia de caracteres sea considerada una unidad léxica específica.

Lexema:

Es la secuencia de caracteres que satisface un patrón.

Token:

Es el valor asociado a una unidad léxica, a menudo representado como un número entero.

Alfabeto:

Son los caracteres válidos para un lenguaje.

Unidades Léxicas:

Son las categorías en que se clasifican las cadenas de caracteres válidos en un lenguaje.

El Rol del Analizador Léxico

Aunque el analizador léxico es la primera etapa del proceso de compilación, no es quien lo inicia. Este realiza su procesamiento y envía sus resultados al analizador gramatical, que es quien, en realidad, inicia el proceso solicitando un token al analizador léxico para poder comenzar su labor.
Durante estas etapas se mantiene una estrecha comunicación con la tabla de símbolos, la cual concentra información sobre las entidades empleadas en los programas.

Descripción de Patrones

Existen tres formas principales para describir los patrones: la descripción informal (que emplea el lenguaje natural para describir el comportamiento de la regla léxica), las expresiones regulares y los autómatas finitos (como los diagramas de transición).

Diagramas de Transición

Un diagrama de transición es la representación gráfica de un conjunto de estados (que pueden ser iniciales, intermedios o finales) y que, además, pueden tener una o más transiciones hacia otros estados.

Los estados iniciales se representan con un doble círculo y un cero; los intermedios, mediante un círculo y un número; y los finales, mediante doble círculo y el último número.
Los estados se relacionan entre sí con flechas (o arcos) que tienen un nombre (el cual es el carácter o conjunto de caracteres que provocan la transición de un estado a otro).

Características de los Diagramas de Transición

• A cada estado se debe llegar con el mismo conjunto de caracteres en todas las ocasiones que haya una transición.
• Cada patrón posee un carácter selector que permite reconocer de manera única el patrón que debe aplicarse.
• Para llegar a un estado de aceptación debe existir una transición sobre el carácter que "rompe" el patrón de la unidad léxica.

Descripciones Informales de las Unidades Léxicas

Identificador:

Es una letra seguida o no de otras letras, dígitos o guiones bajos.

Comentarios:

Comienzan con /* y terminan con */; entre ellos puede haber cualquier símbolo, excepto el fin de archivo.

EOF (End Of File):

Indica el fin del archivo.

Error:

Cualquier símbolo que no cumpla con los patrones anteriores.