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.

Una vez hemos decidido que vamos a utilizar un lenguaje formal, nos enfrentaremos a dos

problemas: especicarlo y reconocerlo. En nuestro caso, las especicaciones seran de dos tipos: por

un lado expresiones regulares para los lenguajes que emplearemos en el analisis lexico y por otro

gramaticas incontextuales en el analisis sintactico.

Una vez especicado el lenguaje sera necesario encontrar la manera de reconocerlos, esto es,

resolver la pregunta si una cadena dada pertenece al lenguaje. Veremos que los metodos de analisis

que emplearemos seran capaces de responder a la pregunta de forma eciente: con un coste lineal

con la talla de la cadena.

3. Categoras lexicas

3.1. Conceptos basicos

Para que el analizador lexico consiga el objetivo de dividir la entrada en partes, tiene que poder

decidir por cada una de esas partes si es un componente separado y, en su caso, de que tipo.

De forma natural, surge el concepto de categora lexica, que es un tipo de smbolo elemental

del lenguaje de programacion. Por ejemplo: identicadores, palabras clave, numeros enteros, etc.

Analizador lexico 3

Los componentes lexicos (en ingles, tokens) son los elementos de las categoras lexicas. Por

ejemplo, en C, i es un componente lexico de la categora identicador, 232 es un componente

lexico de la categora entero, etc. El analizador lexico ira leyendo de la entrada y dividiendola en

componentes lexicos.

Para algunos componentes, fases posteriores del analisis necesitan informacion adicional a la

categora a la que pertenece. Por ejemplo, el valor de un entero o el nombre del identicador.

Utilizamos los atributos de los componentes para guardar esta informacion.

Un ultimo concepto que nos sera util es el de lexema: la secuencia concreta de caracteres que

corresponde a un componente lexico.

Por ejemplo, en la sentencia altura=2; hay cuatro componentes lexicos, cada uno de ellos de

una categora lexica distinta:

Categora lexica Lexema Atributos

identicador altura |

asignacion = |

entero 2 valor: 2

terminador ; |

3.2. Categoras lexicas mas usuales

Algunas familias de categoras lexicas tpicas de los lenguajes de programacion son:

Palabras clave Palabras con un signicado concreto en el lenguaje. Ejemplos de palabras clave

en C son while, if, return. . . Cada palabra clave suele corresponder a una categora lexica.

Habitualmente, las palabras clave son reservadas. Si no lo son, el analizador lexico necesitara

informacion del sintactico para resolver la ambiguedad.

Identicadores Nombres de variables, nombres de funcion, nombres de tipos denidos por el

usuario, etc. Ejemplos de identicadores en C son i, x10, valor_leido. . .

Operadores Smbolos que especican operaciones aritmeticas, logicas, de cadena, etc. Ejemplos

de operadores en C son +, *, /, %, ==, !=, &&. . .

Constantes numericas Literales1 que especican valores numericos enteros (en base decimal,

octal, hexadecimal. . . ), en coma

otante, etc. Ejemplos de constantes numericas en C son

928, 0xF6A5, 83.3E+2. . .

Constantes de caracter o de cadena Literales que especican caracteres o cadenas de caracteres.

Un ejemplo de literal de cadena en C es "una cadena"; ejemplos de literal de caracter

son 'x', '\0'. . .

Smbolos especiales Separadores, delimitadores, terminadores, etc. Ejemplos de estos smbolos

en C son {, }, ;. . . Suelen pertenecer cada uno a una categora lexica separada.

Hay tres categoras lexicas que son especiales:

Comentarios Informacion destinada al lector del programa. El analizador lexico los elimina.

Blancos En los denominados \lenguajes de formato libre" (C, Pascal, Lisp, etc.) los espacios en

blanco, tabuladores y saltos de lnea solo sirven para separar componentes lexicos. En ese

caso, el analizador lexico se limita a suprimirlos. En otros lenguajes, como Python, no se

pueden eliminar totalmente.

Fin de entrada Se trata de una categora cticia emitida por el analizador lexico para indicar

que no queda ningun componente pendiente en la entrada.

1Los literales son secuencias de caracteres que representan valores constantes.

c Universitat Jaume I 2008-2009

4 II26 Procesadores de lenguaje

4. Especicacion de las categoras lexicas

El conjunto de lexemas que forman los componentes lexicos que podemos clasicar en una

determinada categora lexica se expresa mediante un patron. Algunos ejemplos son:

Categora lexica Lexemas Patron

entero 12 5 0 192831 Secuencia de uno o mas dgitos.

identicador x x0 area Letra seguida opcionalmente de letras y/o dgitos.

operador + - Caracteres +, -, * o /.

asignacion := Caracter : seguido de =.

while while La palabra while.

Ya hemos comentado las dicultades de especicar correctamente las categoras mediante lenguaje

natural, as que emplearemos expresiones regulares.

4.1. Expresiones regulares

Antes de describir las expresiones regulares, recordaremos dos operaciones sobre lenguajes. La

concatenacion de dos lenguajes L y M es el conjunto de cadenas que se forman al tomar una del

primero, otra del segundo y concatenarlas. Mas formalmente: la concatenacion de los lenguajes L

y M es el lenguaje LM = fxy j x 2 L ^ y 2 Mg. La notacion Lk se utiliza para representar la

concatenacion de L consigo mismo k

...