PDF de programación - Tema 2. Análisis lexicográfico

Traductores, Compiladores e Intérpretes

1

Tema 2.
Análisis lexicográfico

Este capítulo estudia la primera fase de un compilador, es decir su análisis lexicográfico, o más
concisamente análisis léxico. Las técnicas utilizadas para construir analizadores léxicos también
se pueden aplicar a otras áreas, como, por ejemplo, a lenguajes de consulta y sistemas de
recuperación de información. En cada aplicación, el problema de fondo es la especificación y
diseño de programas que ejecuten las acciones activadas por palabras que siguen ciertos patrones
dentro de las cadenas a reconocer. Como la programación dirigida por patrones es de mucha
utilidad, se introduce un lenguaje de patrón-acción, llamado LEX, para especificar los
analizadores léxicos. En este lenguaje, los patrones se especifican por medio de expresiones
regulares, y un compilador de LEX puede generar un reconocedor de las expresiones regulares
mediante una autómata finito eficiente.

Por otro lado, una herramienta software que automatiza la construcción de analizadores léxicos
permite que personas con diferentes conocimientos utilicen la concordancia de patrones en sus
propias áreas de aplicación.

55

¿Que es un analizador léxico?

Se encarga de buscar los componentes léxicos o palabras que componen el programa
fuente, según unas reglas o patrones.
La entrada del analizador léxico podemos definirla como una secuencia de caracteres.

gramática (N, T, P, S)

N
Símbolos no terminales.
T
Símbolos terminales
P
Reglas de producción
S
Axioma inicial

El analizador léxico tiene que dividir la secuencia de caracteres en palabras con significado
propio y después convertirlo a una secuencia de terminales desde el punto de vista del
analizador sintáctico, que es la entrada del analizador sintáctico.

El analizador léxico reconoce las palabras en función de una gramática regular de manera
que sus NO TERMINALES se convierten en los elementos de entrada de fases
posteriores. En LEX, por ejemplo, esta gramática se expresa mediante expresiones
regulares.

Análisis Lexicográfico

Traductores, Compiladores e Intérpretes

2

Funciones del analizador léxico

El analizador léxico es la primera fase de un compilador. Su principal función consiste en leer los
caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que utiliza
el analizador sintáctico para hacer el análisis. Esta interacción, suele aplicarse convirtiendo al
analizador léxico en una subrutina o corrutina del analizador sintáctico. Recibida la orden “Dame
el siguiente componente léxico”del analizador sintáctico, el analizador léxico lee los caracteres
de entrada hasta que pueda identificar el siguiente componente léxico.

Figura 2 Interacción de un analizador léxico con el analizador sintáctico

Otras funciones que realiza :

Eliminar los comentarios del programa.
Eliminar espacios en blanco, tabuladores, retorno de carro, etc, y en general, todo
aquello que carezca de significado según la sintaxis del lenguaje.
Reconocer los identificadores de usuario, números, palabras reservadas del lenguaje, ...,
y tratarlos correctamente con respecto a la tabla de símbolos (solo en los casos que debe
de tratar con la tabla de símbolos).
Llevar la cuenta del número de línea por la que va leyendo, por si se produce algún error,
dar información sobre donde se ha producido.
Avisar de errores léxicos. Por ejemplo, si @ no pertenece al lenguaje, avisar de un error.
Puede hacer funciones de preprocesador.

Análisis Lexicográfico



Traductores, Compiladores e Intérpretes

3

Necesidad del analizador léxico

Un tema importante es el porqué se separan los dos análisis lexicográfico y sintáctico, en vez de
realizar sólo el análisis sintáctico, del programa fuente, cosa perfectamente posible aunque no
plausible. Algunas razones de esta separación son:

Un diseño sencillo es quizás la consideración más importante. Separar el análisis léxico
del análisis sintáctico a menudo permite simplificar una u otra de dichas fases. El
analizador léxico nos permite simplificar el analizador sintáctico.

Si el sintáctico tuviera la gramática de la Opción 1 , el lexicográfico sería:

Opción 1:

( 0 | 1 | 2 | ... | 9) + NUM
(“+” | “-” | ”*“ | ”/“) OPARIT

Si en cambio el sintáctico toma la Opción 2, el lexicográfico sería:

Opción 2:

( 0 | 1 | 2 | ... | 9) + NUM
“+” MAS
“-” MENOS
“*” MULT
“/” DIV

Es más, si ni siquiera hubiera análisis léxico, el propio análisis sintáctico vería
incrementado su número de reglas:

NUM 0
| 1
| 2
| 3
....
| NUM NUM

Análisis Lexicográfico


Traductores, Compiladores e Intérpretes

4

Necesidad del analizador léxico

A modo de conclusión, diremos que tenemos dos gramáticas, una que se encarga del
análisis léxico y otra que se encarga del análisis sintáctico. ¿Que consideramos
componente básico?, ¿Donde ponemos el punto divisor de qué se encarga cada
gramática?. Si las divisiones se hacen muy pequeñas estamos complicando la gramática,
por ejemplo, en la opción 2, la gramática sintáctica se nos complica un poco. Seguiremos
dos reglas para que no se nos complique. La primera es que tendremos que hacer
divisiones de forma que no perdamos información, esto quedará más claro en capítulos
posteriores, y nos veremos ayudados por el concepto de atributo. La segunda es que por
regla general el analizador lexicográfico debe de encargarse de la parte que involucra una
gramática regular (que nosotros expresaremos mediante expresiones regulares).

Se mejora la eficiencia del compilador. Un analizador léxico independiente permite
construir un procesador especializado y potencialmente más eficiente para esa función.
Gran parte del tiempo se consume en leer el programa fuente y dividirlo en componentes
léxicos. Con técnicas especializadas de manejo de buffers para la lectura de caracteres de
entrada y procesamiento de componentes léxicos se puede mejorar significativamente el
rendimiento de un compilador.

Se mejora la portabilidad del compilador. Las peculiaridades del alfabeto de entrada y
otras anomalías propias de los dispositivos pueden limitarse al analizador léxico. La
representación de símbolos especiales o no estándares, como
en Pascal, pueden ser
aisladas en el analizador léxico.

Otra razón por la que se separan los dos análisis es para que el analizador léxico se centre
en el reconocimiento de componentes básicos complejos. Por ejemplo en FORTRAN,
existen el siguiente par de proposiciones :

DO 5 I = 2.5 (Asignación de 2.5 a la variable DO5I)
DO 5 I = 2,5 (Bucle que se repite para I = 2, 3, 4, 5)

En éste lenguaje los espacios en blancos no son significativos fuera de los comentarios y
de un cierto tipo de cadenas, de modo que supóngase que todos los espacios en blanco
eliminables se suprimen antes de comenzar el análisis léxico. En tal caso, las proposiciones
anteriores aparecerían al analizador léxico como

DO5I = 2.5
DO5I = 2,5

El analizador léxico no sabe si DO es una palabra reservada o es el prefijo de una variable
hasta que llegue a la coma. El analizador ha tenido que mirar más allá de la propia palabra
a reconocer haciendo lo que se denomina lookahead (o prebúsqueda).

Análisis Lexicográfico



Traductores, Compiladores e Intérpretes

5

Conceptos de tokens, patrones y lexemas

El analizador lexicográfico puede tener la siguiente estructura:

Donde cada acción es un fragmento de programa que describe cual ha de ser la acción
del analizador léxico cuando la secuencia de entrada coincida con la expresión regular.

55

5

5

Patrón : es una expresión regular.
Token : es el terminal asociado a un patrón. Cada token se convierte en un número que
es un código identificativo de cada patrón. En algunos casos, cada número tiene asociado
un puntero a la tabla de símbolos. Utilizamos la palabra terminal desde el punto de vista
de la gramática utilizada por el analizador sintáctico.
Lexema : Es cada secuencia de caracteres concreta que encaja con un patrón, es decir,
es como una instancia de un patrón.

Ej: 8, 23, 50 ( son lexemas que encajan con el patrón ( 0 | 1 | 2 | ... | 9) + )

Una vez detectado que un grupo de caracteres coincide con un patrón, se ha detectado
un lexema. A continuación se le asocia un número, que se le pasará al sintáctico, y, si es
necesario, información adicional, como puede ser una entrada en la tabla de símbolos.

La tabla de símbolos suelen ser listas encadenadas de registros con parte variable: listas
ordenadas, árboles binarios de búsqueda, tablas hash, etc.

Ejemplo: Hacer un analizador léxico que nos reconozca los números enteros, los números
reales y los identificadores de usuario. Vamos a hacer este ejemplo en C.

Expresión Regular Terminales
( 0 ... 9) + NUM_ENT
(0 ... 9)*. (0 ... 9) + NUM_REAL
(a ... z) (a ... z 0 ... 9) * ID

Asociado a la categoría gramatical de número entero tendremos el token NUM_ENT que
puede equivaler por ejemplo al número 280; asociado a la categoría gramatical número
real tendremos el token NUM_REAL que equivale al número 281; asociado a la categoría
gramatical identificador de usuario tendremos el token ID que equivale al número 282.

( 0 ... 9) + { return 280;}
(0 ... 9)*. (0 ... 9) + { return 281;}
(a ...z) (a ...z 0...9) * { return 282;}

Análisis Lexicográfico

Traductores, Compiladores e Intérpretes

6

Conceptos de tokens, patrones y lexemas

Si tuviéramos como texto de entrada el siguiente:

95.7 9