PDF de programación - Tema 2 - Análisis Léxico

Tema 2

Análisis Léxico

Bibliografía:

Aho, A.V., Sethi, R., Ullman, J.D. (1990), Compiladores:
principios, técnicas y herramientas, Tema 3, páginas: 85-158.

Louden, K.C. (1997), Compiler Construction: Principles and
Practice, Tema 2, páginas: 31-93.

Contenido:

1. Funciones del analizador léxico.

2. Especificación de los componentes léxicos: expresiones regulares.

3. Reconocimiento de los componentes léxicos: autómatas finitos.

4.

Implementación de un analizador léxico:

a) Dirigido por tabla

b) Mediante bucles anidados.

5. Aspectos prácticos en la implementación de un análisis léxico:

a) Principio de máxima longitud.

b) Palabras reservadas versus identificadores.

c) Gestión del buffer de entrada.

6. Errores léxicos y su tratamiento.

7. Generadores automáticos de analizadores léxicos: Lex.

35

36

TEMA 2. AN ÁLISIS L ÉXICO

2.1. Funciones del analizador léxico.

Analizador léxico (scanner): lee la secuencia de caracteres del
programa fuente, caracter a caracter, y los agrupa para formar
unidades con significado propio, los componentes léxicos (tokens
en inglés). Estos componentes léxicos representan:

palabras reservadas: if, while, do, . . .

identificadores: asociados a variables, nombres de funciones,
tipos definidos por el usuario, etiquetas,... Por ejemplo: posicion,
velocidad, tiempo, . . .

operadores: = * + - / == > < & ! = . . .
símbolos especiales: ; ( ) [ ] { } ...

constantes numéricas: literales que representan valores en-
teros, en coma flotante, etc, 982, 0xF678, -83.2E+2,...

constantes de caracteres: literales que representan cadenas
concretas de caracteres, “hola mundo”,...

El analizador léxico opera bajo petición del analizador sintáctico
devolviendo un componente léxico conforme el analizador sintácti-
co lo va necesitando para avanzar en la gramática. Los com-
ponentes léxicos son los símbolos terminales de la gramática.
Suele implementarse como una subrutina del analizador sintácti-
co. Cuando recibe la orden obtén el siguiente componente léxico,
el analizador léxico lee los caracteres de entrada hasta identificar
el siguiente componente léxico.

analizador léxicoanalizadorsintácticoprogramafuenteléxicocomponenteobtén siguientecomponente léxicosintácticoárbol de anál. 2.1. FUNCIONES DEL ANALIZADOR L ÉXICO.

37

Otras funciones secundarias:

Manejo del fichero de entrada del programa fuente: abrirlo,
leer sus caracteres, cerrarlo y gestionar posibles errores de
lectura.

Eliminar comentarios, espacios en blanco, tabuladores y saltos
de línea (caracteres no válidos para formar un token).

Inclusión de ficheros: # include ...

La expansión de macros y funciones inline: # define ...

Contabilizar el número de lineas y columnas para emitir men-
sajes de error.

Reconocimiento y ejecución de las directivas de compilación
(por ejemplo, para depurar u optimizar el código fuente).

Ventajas de separar el análisis léxico y el análisis sintáctico:

Facilita transportabilidad del traductor (por ejemplo, si de-
cidimos en un momento dado cambiar las palabras reservadas
begin y end de inicio y fin de bloque, por { y }, sólo hay que
cambiar este modulo.

Se simplifica el diseño: el analizador es un objeto con el que
se interactúa mediante ciertos métodos. Se localiza en un
único módulo la lectura física de los caracteres, por lo que
facilita tratamientos especializados de E/S.

Componentes Léxicos, Patrones, Lexemas
Patrón: es una regla que genera la secuencia de caracteres que
puede representar a un determinado componente léxico (una ex-
presión regular).

Lexema: cadena de caracteres que concuerda con un patrón
que describe un componente léxico. Un componente léxico puede
tener uno o infinitos lexemas. Por ejemplo: palabras reservadas
tienen un único lexema. Los números y los identificadores tienen
infinitos lexemas.

38

TEMA 2. AN ÁLISIS L ÉXICO

Compon. léxico Lexema

Patrón

identificador
num entero
if
do
op div
op asig

indice, a, temp letra seguida de letras o dígitos
1492, 1, 2
if
do
/
=

dígito seguido de más dígitos
letra i seguida de letra f
letra d seguida de o
carácter /
carácter =

Los componentes léxicos se suelen definir como un tipo enumer-
ado. Se codifican como enteros. También se suele almacenar la
cadena de caracteres que se acaba de reconocer (el lexema), que
se usará posteriomenete para el análisis semántico.
typedef enum{ TKN IF, TKN THEN, TKN NUM, TKN ID, TKN OPADD,...} TokenType;

Es importante conocer el lexema (para construir la tabla de símbo-
los). Los componentes léxicos se representan mediante una estruc-
tura registro con tipo de token y lexema:
typedef struct {

TokenType token;

char *lexema; //se reserva memoria dinámicamente

} TokenRecord;
TokenRecord getToken(void);

2.1. FUNCIONES DEL ANALIZADOR L ÉXICO.

39

a[indice]= 2 + 4

Cada componente léxico va acompañado de su lexema:
<TKN ID, a>

<TKN CORAPER, [>

<TKN ID, indice>

<TKN CORCIERRE, ]>

<TKN NUM, 2>

<TKN OPADD, +>

<TKN NUM, 4>

a[indice]=24+buffer de entrada 40

TEMA 2. AN ÁLISIS L ÉXICO

2.2. Especificación de los componentes léxi-

cos: expresiones regulares.

Los componentes léxicos se especifican haciendo uso de expre-
siones regulares. Además de las tres operaciones básicas: concate-
nación, repetición (*) y alternativas (|) vamos a usar los siguientes
metasímbolos:

Una o más repeticiones +
r+ indica una o más repeticiones de r
(0|1)+ = (0|1)(0|1)*
Cualquier carácter .
.*b.* indica cualquier cadena que contiene una letra b
Un rango de caracteres [

] (clase)

[a-z] indica cualquier carácter entre la a y z minúsculas
[a-zA-Z] indica cualquier letra del abecedario minúscula o mayúscu-
la
[0-9] indica cualquier dígito de 0 a 9
[abc] indica a|b|c

Cualquier carácter excepto un conjunto dado ˜
˜ (a|b) indica cualquier carácter que no sea una a ó b
Opcionalidad ?
r? indica que la expresión r puede aparecer o no. En el caso de

que aparezca sólo lo hará una vez.
Cuando queremos usar estos símbolos con su significado ten-
emos que usar la barra de escape, [a\-z] significaría cualquier letra
que sea a, guión o z.

Algunos ejemplos:
Números
nat = [0-9]+
signedNat = ( + | -)? nat
number = signedNat(‘‘.’’nat)? (E signedNat)?

Identificadores

letter = [a-zA-Z]
digit = [0-9]

2.3. RECONOCIMIENTO DE LOS COMPONENTES L ÉXICOS: AUT ÓMATAS FINITOS.41

identifier = letter (letter | digit)*

Palabras Reservadas

tkn if = ‘‘if’’

tkn while = ‘‘while’’

tkn do = ‘‘do’’

Comentarios

{ (˜ })* } comentarios en Pascal

Delimitadores

delimitadores = (newline | blank | tab | comment)+

2.3. Reconocimiento de los componentes léxi-

cos: autómatas finitos.

Los AFD se pueden utilizar para reconocer las expresiones regu-
lares asociadas a los componentes léxicos.
Identificadores
identifier = letter (letter | digit)*

Números naturales y reales
nat = [0-9]+

signedNat = (-)? nat

number = signedNat(‘‘.’’nat)? (E signedNat)?

123letterotherdigitletterreturn id 42

TEMA 2. AN ÁLISIS L ÉXICO

Operadores relacionales
Operadores < | = | <= | <> | >= | >

El símbolo * indica que se debe hacer un retroceso en la entrada
pues se ha consumido un símbolo demás, que no pertenece al
lexema del componente léxico que se devuelve.

--EEreturn signedNatdigitdigitdigitdigitdigitdigitdigitdigitreturn numberreturn signedRealreturn opmenorigreturn opdistreturn opmenor<=>otro=return opigual=otro>return opmayorigreturn opmayor** 2.4. IMPLEMENTACI ÓN DE UN ANALIZADOR L ÉXICO.

43

2.4.

Implementación de un analizador léxico.

Supongamos que queremos reconocer identificadores:

Mediante bucles anidados
Usamos una variable para almacenar el estado actual y una
estructura tipo case doble anidada. El primer case comprueba
el estado actual y el siguiente el carácter en la entrada. Las tran-
siciones se corresponden con asociar un nuevo estado a la variable
y avanzar en la entrada.
ch=next input char;

state = 1;

while (state == 1 o 2) do

case state

1: case ch

letter : avanzar en la entrada; state=2;

otro caso : state = error u otro

fin case;

2: case ch

letter, digit : avanzar en la entrada; state=2 (no necesario);

otro caso : state = 3;

fin case;

fin case;

fin while;

if (state==3) then aceptar else error;
El código que se genera es largo y difícil de mantener en el caso
de que se introduzcan nuevos caracteres en el alfabeto de entrada
o nuevos estados.

123letterotherdigitletterreturn id 44

TEMA 2. AN ÁLISIS L ÉXICO

Mediante una tabla de transiciones

input/state

letter digit

other Accepting

1
2
3

2
2

2

[3]

no
no
yes

Se asume que los campos en blanco son errores. Los estados de
aceptación se marcan con una columna adicional. Los corchetes
representan que no se tiene que consumir un carácter en la entrada
(no avanzar).
state = 1;

ch = next input character;

while (not Accept[state]) and (not error(state)) do

newstate = T[state,ch];
if Advance[state,ch] then ch=next input char;

state=newstate;

end while;
if Accept[state] then accept;

Advance y Accept son dos arrays booleanos indexados por
el estado y por el carácter en la entrada. El primero indica si
tenemos que avanzar en la entrada. El segundo si tenemos un
estado de aceptación.
Ventajas: el código es reducido y fácil de mantener, sirve para
cualquier analizador, las modificaciones se realizan sólo en la
tabla.

Desventajas: tablas de gran tamaño, se incrementa el espacio
necesario (velocidad algo reducida respecto al método anterior).
Este método es el que utiliza Flex (Linux) y Lex (Unix).
Coste: O(|x|), es independiente del tamaño del autómata.

2.5. ASPECTOS PR ÁCTICOS EN LA IMPLEMENTACI ÓN DE UN ANALIZADOR L ÉXICO45

2.5. Aspectos prácticos en la implementación

de un analizador léxico

Principio de máxima longitud

Se da prioridad al componente léxico de máxima longitud.
Por ejemplo: <> se interpreta como el operador “distinto de”, en
vez de “menor que” y “mayor que”.
Por ejemplo: ende se interpreta como el identifica