lexico

4o Ingenier´ıa Inform´
atica
II26 Procesadores de lenguaje
Analizador l´exico
Esquema del tema
1. Introducci´
on
2. Repaso de conceptos de lenguajes formales
3. Categor´ıas l´exicas
4. Especificaci´
on de las categor´ıas l´exicas
5. Aut´
omatas de estados finitos
6. Implementaci´
on del analizador l´exico
7. Algunas aplicaciones de los analizadores l´exicos
8. Resumen del tema

1.

Introducci´on

Vimos que la primera fase del an´
alisis es el an´alisis l´exico. El principal objetivo del analizador
l´exico es leer el flujo de caracteres de entrada y transformarlo en una secuencia de componentes
l´exicos que utilizar´
a el analizador sint´
actico.
Al tiempo que realiza esta funci´
on, el analizador l´exico se ocupa de ciertas labores de “limpieza”.
Entre ellas est´
a eliminar los blancos olos comentarios. Tambi´en se ocupa de los problemas que
pueden surgir por los distintos juegos de caracteres o si el lenguaje no distingue may´
usculas y
min´
usculas.
Para reducir la complejidad, los posibles s´ımbolos se agrupan en lo que llamaremos categor´ıas
l´exicas. Tendremos que especificar qu´e elementos componen estas categor´ıas, para lo que emplearemos expresiones regulares. Tambi´enser´a necesario determinar si una cadena pertenece o no a
una categor´ıa, lo que se puede hacer eficientemente mediante aut´omatas de estados finitos.

2.
2.1.

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

Como acabamos de comentar, para transformar la secuencia de caracteres de entrada en una
secuencia de componentes l´exicos utilizamos aut´omatas de estadosfinitos. Sin embargo, estos
aut´
omatas los especificaremos utilizando expresiones regulares. Tanto unos como otras son ejemplos
de utilizaci´
on de la teor´ıa de lenguajes formales. Es natural preguntarse si es necesario dar este
rodeo. Existen varias razones que aconsejan hacerlo.
La primera raz´
on para emplear herramientas formales es que nos permiten expresarnos con
precisi´
on y,generalmente, de forma breve. Por ejemplo, para describir la categor´ıa de los enteros,
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 al
siete). Cambiamos entonces a “secuencias de d´ıgitos, cada uno de los cuales puede ser un 0, un 1,
un 2, un 3, un 4, un5, un 6, un 7, un 8 o un 9”. Todav´ıa queda otro problema m´as, ¿valen las
cadenas vac´ıas? Normalmente no, as´ı que llegamos a “un n´
umero entero consiste en una secuencia
de uno o m´
as 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”. Sin embargo, con expresiones regulares, podemos decir lo mismo con [0–9]+ .

2

II26 Procesadores delenguaje

Otra ventaja de las herramientas formales, es que nos permiten razonar sobre la correcci´on
de nuestros dise˜
nos y permiten conocer los l´ımites de lo que podemos hacer. Por ejemplo, el
lema de bombeo nos permite saber que no podremos utilizar expresiones regulares para modelar
componentes l´exicos que tengan el mismo n´
umero de par´entesis abiertos que cerrados, por lo que
averiguar sialgo est´
a bien parentizado ser´a tarea del analizador sint´actico.
Como u
´ltima ventaja del empleo de lenguajes formales, comentaremos la existencia de herramientas para automatizar la implementaci´on. Por ejemplo, el paso de las expresiones regulares
a un programa que las reconozca se puede hacer mediante un generador de analizadores l´exicos
como flex.

2.2.

Alfabetos y lenguajes

Al trabajarcon lenguajes formales, utilizaremos una serie de conceptos b´asicos. En primer
lugar, un alfabeto Σ es un conjunto finito de s´ımbolos. No nos interesa la naturaleza de los s´ımbolos. Dependiendo de la aplicaci´
on que tengamos en mente, ´estos pueden ser: caracteres, como
al especificar el analizador l´exico; letras o palabras, si queremos trabajar con lenguaje natural;
categor´ıas l´exicas,...