Procesadores de lenguaje

4o Ingeniera Informatica

II26 Procesadores de lenguaje

Analizador lexico

Esquema del tema

1. Introduccion

2. Repaso de conceptos de lenguajes formales

3. Categoras lexicas

4. Especicacion de las categoras lexicas

5. Automatas de estados nitos

6. Implementacion del analizador lexico

7. Introduccion a un generador automatico de analizadores lexicos:

ex

8. Algunas aplicaciones de los analizadores lexicos

9. Resumen del tema

1. Introduccion

Vimos que la primera fase del analisis es el analisis lexico. El principal objetivo del analizador

lexico es leer el

ujo de caracteres de entrada y transformarlo en una secuencia de componentes

lexicos que utilizara el analizador sintactico.

Al tiempo que realiza esta funcion, el analizador lexico se ocupa de ciertas labores de \limpieza".

Entre ellas esta eliminar los blancos o los comentarios. Tambien se ocupa de los problemas que

pueden surgir por los distintos juegos de caracteres o si el lenguaje no distingue mayusculas y

minusculas.

Para reducir la complejidad, los posibles smbolos se agrupan en lo que llamaremos categoras

lexicas. Tendremos que especicar que elementos componen estas categoras, para lo que emplearemos

expresiones regulares. Tambien sera necesario determinar si una cadena pertenece o no a

una categora, lo que se puede hacer ecientemente mediante automatas de estados nitos.

2. Repaso de conceptos de lenguajes formales

2.1. Por que utilizamos lenguajes formales

Como acabamos de comentar, para transformar la secuencia de caracteres de entrada en una

secuencia de componentes lexicos utilizamos automatas de estados nitos. Sin embargo, estos

automatas los especicaremos utilizando expresiones regulares. Tanto unos como otras son ejemplos

de utilizacion de la teora de lenguajes formales. Es natural preguntarse si es necesario dar este

rodeo. Existen varias razones que aconsejan hacerlo.

La primera razon para emplear herramientas formales es que nos permiten expresarnos con

precision y, generalmente, de forma breve. Por ejemplo, para describir la categora de los enteros,

podemos intentar utilizar el castellano y decir algo as como que son \secuencias de dgitos". Pero

entonces no queda claro cuales son esos dgitos (por ejemplo, en octal, los dgitos van del cero al

siete). Cambiamos entonces a \secuencias de dgitos, 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". Todava queda otro problema mas, >valen las

cadenas vacas? Normalmente no, as que llegamos a \un numero entero consiste en una secuencia

de uno o mas dgitos, 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 de lenguaje

Otra ventaja de las herramientas formales, es que nos permiten razonar sobre la correccion

de nuestros dise~nos y permiten conocer los lmites de lo que podemos hacer. Por ejemplo, el

lema de bombeo nos permite saber que no podremos utilizar expresiones regulares para modelar

componentes lexicos que tengan el mismo numero de parentesis abiertos que cerrados, por lo que

averiguar si algo esta bien parentizado sera tarea del analizador sintactico.

Como ultima ventaja del empleo de lenguajes formales, comentaremos la existencia de herramientas

para automatizar la implementacion. Por ejemplo, el paso de las expresiones regulares

a un programa que las reconozca se puede hacer mediante un generador de analizadores lexicos

como flex.

2.2. Alfabetos y lenguajes

Al trabajar con lenguajes formales, utilizaremos una serie de conceptos basicos. En primer

lugar, un alfabeto  es un conjunto nito de smbolos. No nos interesa la naturaleza de los smbolos.

Dependiendo de la aplicacion que tengamos en mente, estos pueden ser: caracteres, como

al especicar el analizador lexico; letras o palabras, si queremos trabajar con lenguaje natural;

categoras lexicas, al especicar el analizador sintactico; direcciones en el plano, al hacer OCR,

etc. Justamente esta abstraccion es lo que hace que los lenguajes formales se puedan aplicar ampliamente.

Una cadena es una secuencia nita de smbolos del alfabeto. Nuevamente, no estamos interesados

en la naturaleza precisa de las cadenas. Si estamos especicando el analizador lexico, podemos

ver la entrada como una cadena; si trabajamos con lenguaje natural, la cadena puede ser una

pregunta a una base de datos; para el analizador sintactico, una cadena es el programa una vez

pasado por el analizador lexico; en OCR, una cadena es la descripcion de una letra manuscrita,

etc.

La cadena de longitud cero se denomina cadena vaca y se denota con . Para referirnos al

conjunto de cadenas de longitud k, utilizamos k. Si nos referimos al conjunto de todas las cadenas

que se pueden escribir con smbolos del alfabeto, usamos . Se cumplira que:

 =

1[

k=0

k = 0 [ 1 [ 2 [ : : :

Date cuenta de que  es un conjunto innito, pero que cualquiera de sus cadenas es nita.

Finalmente, un lenguaje formal es un subconjunto de . Tal como esta denido, puede ser

nito o innito. Es mas, la denicion no impone la necesidad de que el lenguaje tenga algun sentido

o signicado; un lenguaje formal es simplemente un conjunto de cadenas.

...