Generadores automaticos de analizadores lexicos

4o Ingenier´ Inform´tica ıa a
II26 Procesadores de lenguaje
Analizador l´xico e Esquema del tema
1. Introducci´n o 2. Repaso de conceptos de lenguajes formales 3. Categor´ l´xicas ıas e 4. Especificaci´n de las categor´ l´xicas o ıas e 5. Aut´matas de estados finitos o 6. Implementaci´n del analizador l´xico o e 7. Introducci´n a un generador autom´tico de analizadores l´xicos: flex o a e 8.Algunas aplicaciones de los analizadores l´xicos e 9. Resumen del tema

1.

Introducci´n o

Vimos que la primera fase del an´lisis es el an´lisis l´xico. El principal objetivo del analizador a a e l´xico es leer el flujo de caracteres de entrada y transformarlo en una secuencia de componentes e l´xicos que utilizar´ el analizador sint´ctico. e a a Al tiempo que realiza esta funci´n, el analizadorl´xico se ocupa de ciertas labores de “limpieza”. o e Entre ellas est´ eliminar los blancos o los comentarios. Tambi´n se ocupa de los problemas que a e pueden surgir por los distintos juegos de caracteres o si el lenguaje no distingue may´sculas y u min´sculas. u Para reducir la complejidad, los posibles s´ ımbolos se agrupan en lo que llamaremos categor´ ıas l´xicas. Tendremos que especificarqu´ elementos componen estas categor´ para lo que empleae e ıas, remos expresiones regulares. Tambi´n ser´ necesario determinar si una cadena pertenece o no a e a una categor´ lo que se puede hacer eficientemente mediante aut´matas de estados finitos. ıa, o

2.
2.1.

Repaso de conceptos de lenguajes formales
Por qu´ utilizamos lenguajes formales e

Como acabamos de comentar, para transformar lasecuencia de caracteres de entrada en una secuencia de componentes l´xicos utilizamos aut´matas de estados finitos. Sin embargo, estos e o aut´matas los especificaremos utilizando expresiones regulares. Tanto unos como otras son ejemplos o de utilizaci´n de la teor´ de lenguajes formales. Es natural preguntarse si es necesario dar este o ıa rodeo. Existen varias razones que aconsejan hacerlo. Laprimera raz´n para emplear herramientas formales es que nos permiten expresarnos con o precisi´n y, generalmente, de forma breve. Por ejemplo, para describir la categor´ de los enteros, o ıa podemos intentar utilizar el castellano y decir algo as´ como que son “secuencias de d´ ı ıgitos”. Pero entonces no queda claro cuales son esos d´ ıgitos (por ejemplo, en octal, los d´ ıgitos van del cero alsiete). Cambiamos entonces a “secuencias de d´ ıgitos, cada uno de los cuales puede ser un 0, un 1, un 2, un 3, un 4, un 5, un 6, un 7, un 8 o un 9”. Todav´ queda otro problema m´s, ¿valen las ıa a cadenas vac´ ıas? Normalmente no, as´ que llegamos a “un n´mero entero consiste en una secuencia ı u de uno o m´s d´ a ıgitos, cada uno de los cuales puede ser un 0, un 1, un 2, un 3, un 4, un 5, un 6, un7, un 8 o un 9”. Sin embargo, con expresiones regulares, podemos decir lo mismo con [0–9]+ .

2

II26 Procesadores de lenguaje

Otra ventaja de las herramientas formales, es que nos permiten razonar sobre la correcci´n o de nuestros dise˜os y permiten conocer los l´ n ımites de lo que podemos hacer. Por ejemplo, el lema de bombeo nos permite saber que no podremos utilizar expresionesregulares para modelar componentes l´xicos que tengan el mismo n´mero de par´ntesis abiertos que cerrados, por lo que e u e averiguar si algo est´ bien parentizado ser´ tarea del analizador sint´ctico. a a a Como ultima ventaja del empleo de lenguajes formales, comentaremos la existencia de herra´ mientas para automatizar la implementaci´n. Por ejemplo, el paso de las expresiones regulares o a unprograma que las reconozca se puede hacer mediante un generador de analizadores l´xicos e como flex.

2.2.

Alfabetos y lenguajes

Al trabajar con lenguajes formales, utilizaremos una serie de conceptos b´sicos. En primer a lugar, un alfabeto Σ es un conjunto finito de s´ ımbolos. No nos interesa la naturaleza de los s´ ımbolos. Dependiendo de la aplicaci´n que tengamos en mente, ´stos pueden...