PDF de programación - Construcción de un analizador léxico para ALFA con Flex

Construcción de un analizador léxico para ALFA con Flex

Índice (I)

Marina de la Cruz
Alfonso Ortega

 Funciones del analizador léxico/morfológico
 Construcción de un analizador léxico/morfológico
 Funcionamiento básico de Flex
 Descripción del primer ejemplo
 El fichero de especificación Flex

 Estructura del fichero
 La sección de definiciones
 La sección de reglas
 La sección de funciones de usuario

 Solución del primer ejemplo

 Creación del ejecutable
 Realización de pruebas

 Segundo ejemplo

 Diseño del fichero de especificación
 Creación del ejecutable y realización de pruebas
 Modificación del diseño

 Tercer ejemplo

Prácticas de Procesadores de Lenguaje 2007-2008

Construcción de un analizador léxico para ALFA con Flex

Índice (II)

 Los patrones de Flex

 Descripción
 Metacaracteres
 Cómo se identifican los patrones en la entrada

 Cuarto ejemplo

 Enunciado
 Realización de pruebas

 Los tokens del lenguaje ALFA

 Identificación
 Patrones o expresiones regulares

 Fichero de especificación Flex para el lenguaje ALFA

 Construcción
 El orden de las reglas

 Gestión de los espacios en blanco
 Control de la posición de los tokens en el fichero de entrada
 Gestión de los comentarios
 Gestión de errores
 Ficheros de entrada/salida de Flex

Prácticas de Procesadores de Lenguaje 2007-2008

1

2

Funciones del analizador léxico/morfológico

 El analizador léxico/morfológico de un compilador es el responsable de identificar en

el fichero del programa fuente las unidades sintácticas o tokens del lenguaje
particular para el que ha sido construido.

Fichero del

programa fuente

Analizador léxico

tokens

 Además de identificar los tokens, también se encarga de otras tareas como:

 Eliminar/ignorar espacios en blanco (blancos, tabuladores y saltos de línea)
 Eliminar/ignorar comentarios
 Detectar errores morfológicos (símbolo no permitido, identificador demasiado largo, etc)

Prácticas de Procesadores de Lenguaje 2007-2008

Construcción de un analizador léxico/morfológico

 Un analizador morfológico se puede desarrollar con distintos métodos:

 con un autómata finito
 con un programa a medida
 utilizando una herramienta específica como Flex

 Independientemente del método seleccionado, para construir el analizador

morfológico, hay que definir los requisitos que debe cumplir el analizador:

 los tokens que tiene que reconocer:

 identificadores
 palabras reservadas
 constantes (numéricas, lógicas,cadenas de caracteres, etc)
 símbolos simples (+, -, *, /, etc)
 símbolos múltiples (==, >=, etc)

 el formato de los comentarios
 los errores morfológicos que debe detectar

Prácticas de Procesadores de Lenguaje 2007-2008

3

4

Funcionamiento básico de Flex

 Flex es una herramienta para construir analizadores léxicos.
 Flex recibe como entrada un conjunto de descripciones de tokens, y genera la

función C yylex() que es un analizador léxico que reconoce dichos tokens.

 Los tokens se describen mediante patrones que son extensiones de las expresiones

regulares.

 Al conjunto de las descripciones de tokens se le llama especificación Flex.

Especificación

Flex

Flex

lex.yy.c

yylex()

tokens

Fichero del
programa

fuente

Prácticas de Procesadores de Lenguaje 2007-2008

Descripción del primer ejemplo (I)

 Construir un analizador léxico, utilizando la herramienta Flex, que cumpla las

siguientes especificaciones:

 reconoce en el fichero de entrada las palabras “INICIO” , “FIN”, “VECTOR”, “ENTERO” y

“LOGICO” .

 Cada vez que el analizador reconoce una de las palabras anteriores, muestra en la
salida estándar un mensaje de aviso de token reconocido. Los mensajes indican qué
token se ha identificado con el siguiente texto:

“reconocido INICIO”
“reconocido FIN”
“reconocido VECTOR”
“reconocido ENTERO”
“reconocido LOGICO”

 El fichero de especificación Flex se llamará ejemplo1.l.

Prácticas de Procesadores de Lenguaje 2007-2008

5

6

Descripción del primer ejemplo (II)

 Una visión gráfica del primer ejemplo sería:

ejemplo1.l

Especificación

Flex

Flex

lex.yy.c

yylex()

reconocido INICIO
reconocido FIN
reconocido INICIO
reconocido VECTOR
reconocido VECTOR
reconocido ENTERO
reconocido LOGICO

INICIO FIN INICIO
VECTOR
VECTOR ENTERO
LOGICO

Prácticas de Procesadores de Lenguaje 2007-2008

El fichero de especificación Flex (I)

Estructura del fichero

 La estructura del fichero de especificación Flex se compone de tres secciones

separadas por líneas que contienen el separador %%.

sección de definiciones

/* delimitadores de código C */

%{

%}

%%

sección de reglas

%%

sección de funciones de usuario

Prácticas de Procesadores de Lenguaje 2007-2008

7

8

El fichero de especificación Flex (II)

La sección de definiciones (I)

 La sección de definiciones contiene la siguiente información

 Código C encerrado entre líneas con los caracteres %{ y %} que se copia literalmente

en el fichero de salida lex.yy.c antes de la definición de la función yylex().
Habitualmente esta sección contiene declaraciones de variables y funciones que se
utilizan posteriormente en la sección de reglas así como directivas #include.

 Definiciones propias de Flex, que permiten asignar un nombre a una expresión regular o

a una parte, y posteriormente utilizar ese nombre en la sección de reglas. Estas
definiciones se verán con más detalle cuando se estudien los patrones de Flex.

 Opciones de Flex similares a las opciones de la línea de comandos.

 Definición de condiciones de inicio. Estas definiciones se verán con más detalle cuando

se estudien los patrones de Flex.

 Cualquier línea que empiece con un espacio en blanco se copia literalmente en el

fichero de salida lex.yy.c. Habitualmente se utiliza para incluir comentarios encerrados
entre /* y */. (Esta funcionalidad depende de la versión de Flex)

Prácticas de Procesadores de Lenguaje 2007-2008

9

El fichero de especificación Flex (III)

La sección de definiciones (II)

 En la figura se muestra una primera aproximación del fichero de especificación

Flex del primer ejemplo (ejemplo1.l) Únicamente se ha completado la sección de
definiciones. A medida que se construya el ejemplo se completarán las demás
secciones del fichero.

ejemplo1.l

%{
#include <stdio.h>

%}

%option noyywrap

%%

/* para utilizar printf en la

sección de reglas */

 La directiva #include <stdio.h> se necesita porque en la sección de reglas se

utiliza la función printf para mostrar en la salida estándar los mensajes de aviso de
token reconocido.

 El significado de la opción noyywrap se explica en el siguiente apartado.

Prácticas de Procesadores de Lenguaje 2007-2008

10

El fichero de especificación Flex (IV)

La sección de definiciones (III)

 Significado de la opción noyywrap:

 La función yylex() puede analizar morfológicamente varios ficheros, encadenando uno

detrás de otro con el mecanismo que se describe a continuación.

 Cuando yylex() encuentra un fin de fichero, llama a la función yywrap(). Si la función

devuelve 0, el análisis continúa con otro fichero, y si devuelve 1, el análisis termina.

 ¿Quién proporciona la función yywrap() ? En Linux, la librería de Flex proporciona una

versión por defecto de yywrap() que devuelve 1. Hay que enlazar con esa librería con la
opción -lf.

 La opción noyywrap evita se invoque a la función yywrap() cuando se encuentre un fin

de fichero, y se asuma que no hay más ficheros que analizar.
Esta solución es más cómoda que tener que escribir la función o bien enlazar con
alguna librería.

Prácticas de Procesadores de Lenguaje 2007-2008

11

El fichero de especificación Flex (V)

La sección de reglas (I)

 La sección de reglas contiene:

 Los patrones que describen los tokens y código C.

Cada patrón se sitúa en una línea, seguido de uno o más espacios en blanco y a
continuación el código C que se ejecuta cuando se encuentra dicho patrón en la
entrada que se está analizando. El código C se cierra entre llaves {}.

 Si una línea empieza por un espacio en blanco se considera código C y se copia

literalmente en el fichero de salida. También se asume que es código C todo lo que se
escriba entre %{ y %}, y se copia literalmente en el fichero de salida. (Esta funcionalidad
depende de la versión de Flex)

 ¿Cómo se comporta la rutina de análisis yylex() ?

 Busca en la entrada los patrones que se definen en la sección de reglas, es decir, los

tokens. Cada vez que se encuentra un token, se ejecuta el código C asociado con el
patrón. Si no se identifica ningún token, se ejecuta la regla por defecto : el siguiente
carácter en la entrada se considera reconocido y se copia en la salida.

 El código C asociado a cada patrón puede tener una sentencia return, que devuelve
un valor al llamador de la función yylex()cuando se identifique el patrón en la entrada.
La siguiente llamada a yylex() comienza a leer la entrada en el punto donde se quedó
la última vez. Cuando se encuentra el fin de la entrada yylex() devuelve 0 y termina.

 Si ninguna regla tiene una sentencia return, yylex() analiza la entrada hasta que

encuentra el fin de la misma.

Prácticas de Procesadores de Lenguaje 2007-2008

12

El fichero de especificación Flex (VI)

La sección de reglas (II)

 Sección de reglas del primer ejemplo:

 Los patrones de Flex para definir los tokens se estudiarán más adelante, y ya se verá que

el patrón para representar una palabra es la misma palabra.

 La sección de reglas del primer ejemplo contiene:

 Una regla para la palabra “INICIO”, que se compone de su patrón (que es la misma palabra) y
el código C que se va a ejecutar cuando se identifique en la entrada. El código muestra en la
salida estándar el aviso “reconocido INICIO”.

 Reglas similares a la anterior para las palabras “FIN”, “VECTOR”, “ENTERO” y “LOGICO” .

ejemplo1.l

%{
#include <stdio.h>

%}
%option noyywrap

/* para utilizar printf en la

sección de regla