Prácticas de Procesadores de Lenguaje

Curso 2007/2008

Práctica 1: Analizador Léxico

Objetivo de la Práctica

Esta práctica tiene como objetivo la codificación de un analizador léxico mediante el uso del lenguaje de programación C y la herramienta de ayuda a la generación de analizadores léxicos flex.
Este analizador será utilizado por el compilador del lenguaje ALFA que va a desarrollarse durante el curso.

Desarrollo de la Práctica

Estudio de la Gramática

Inicialmente se tratará de identificar en la gramática completa del lenguaje, incluida al final de este enunciado, el conjunto de unidades sintácticas o tokens existentes.

Codificación de una Especificación para flex

El alumno deberá diseñar el conjunto de expresiones regulares que representa cada unidad sintáctica.
Observación muy importante: Recuerde, que algunas tareas que el analizador léxico puede y suele realizar son:

Ignorar los espacios en blanco y tabuladores, que actúan como separadores entre unidades sintácticas.
Ignorar los comentarios, que no aportan código ejecutable al programa.
Hacer una primera gestión de errores morfológicos.

El alumno deberá escribir un fichero de nombre alfa.l que sea una especificación correcta para la entrada de la herramienta flex.
Se recomienda al alumno que se familiarice primero con flex mediante las explicaciones que su profesor de prácticas realizará en su laboratorio y posteriormente diseñe el conjunto final de expresiones regulares.

Codificación de un Programa de Prueba

El alumno también deberá escribir (en C) un programa de prueba del analizador léxico generado con flex, con los siguientes requisitos:

Nombre del programa fuente: prueba_lexico.c
Al ejecutable correspondiente se le invocará de la siguiente manera: prueba_lexico [<nombre_fichero_entrada> [<nombre_fichero_salida>]]
Es decir, el programa se puede ejecutar:

Con 0 argumentos: entonces se utilizan la entrada y la salida estándares.
Con 1 argumento: entonces se utiliza la salida estándar y el argumento como nombre del fichero de entrada.
Con 2 argumentos: entonces el primer argumento se interpreta como el nombre del fichero de entrada y el segundo como el nombre del fichero de salida.

La estructura de los ficheros de entrada/salida se explican a continuación.

Descripción del Fichero de Entrada

El fichero de entrada contiene un programa escrito en lenguaje ALFA (no necesariamente correcto)

Funcionalidad del Programa

El programa de prueba, haciendo uso del analizador léxico construido con flex, deberá identificar en el fichero de entrada las siguientes unidades sintácticas:

Identificadores: que siguen la sintaxis descrita en la gramática para el símbolo no terminal <identificador>.
Constantes numéricas: que siguen la sintaxis descrita en la gramática para el símbolo no terminal <numero>.
Palabras reservadas: cualquier otra palabra o símbolo ALFA correcto.
Cualquier otra cosa se considerará errónea.

Por cada unidad sintáctica identificada en el fichero de entrada, el programa de prueba debe generar una línea en el fichero de salida según se describe a continuación.

Descripción del Fichero de Salida

El fichero de salida se compone de un conjunto de líneas, una por cada unidad sintáctica del fichero de entrada. La estructura de la línea es la siguiente:

El primer elemento de la línea será, según corresponda:

TOKEN_ID: para los identificadores.
TOKEN_NUM: para los números.
TOKEN_KEY: para todas las palabras reservadas y símbolos.
ERROR: para los errores.

El segundo elemento será un número entero, que identificará la unidad sintáctica (debe ser distinto para cada unidad sintáctica). En la página web del laboratorio de Procesadores de Lenguaje está disponible un enlace para descargar el fichero tokens.h que contiene las definiciones de los tokens de la gramática de ALFA.
El tercer elemento será el lexema (el fragmento del programa fuente) analizado como la unidad sintáctica correspondiente.
Muy importante: cada elemento de la línea estará separado por un tabulador y ningún otro carácter más, aunque ofrezca un aspecto visualmente indistinguible.

Ejemplos

Ejemplo 1: Si el fichero de entrada es el siguiente:

// Programa que eleva un número entero al cuadrado

INICIO
ENTERO x, resultado;

   LEER x;
   resultado=x*x;
   ESCRIBIR resultado
FIN

El fichero de salida es el siguiente:

TOKEN_KEY	1	INICIO
TOKEN_KEY	3	ENTERO
TOKEN_ID	100	x
TOKEN_KEY	25	,
TOKEN_ID	100	resultado
TOKEN_KEY	23	;
TOKEN_KEY	15	LEER
TOKEN_ID	100	x
TOKEN_KEY	23	;
TOKEN_ID	100	resultado
TOKEN_KEY	26	=
TOKEN_ID	100	x
TOKEN_KEY	33	*
TOKEN_ID	100	x
TOKEN_KEY	23	;
TOKEN_KEY	16	ESCRIBIR
TOKEN_ID	100	resultado
TOKEN_KEY	2	FIN

Ejemplo 2: Si el fichero de entrada es el siguiente:

// Programa que eleva un número x a la potencia y

INICIO
ENTERO x, y;
ENTERO i, total;

   LEER x;
LEER y;
i=1;
total=1;
MIENTRAS (i<=y) HACER
    total=total*x;
    i=i+1
FIN;
ESCRIBIR total
FIN

El fichero de salida es el siguiente:

TOKEN_KEY	1	INICIO
TOKEN_KEY	3	ENTERO
TOKEN_ID	100	x
TOKEN_KEY	25	,
TOKEN_ID	100	y
TOKEN_KEY	23	;
TOKEN_KEY	3	ENTERO
TOKEN_ID	100	i
TOKEN_KEY	25	,
TOKEN_ID	100	total
TOKEN_KEY	23	;
TOKEN_KEY	15	LEER
TOKEN_ID	100	x
TOKEN_KEY	23	;
TOKEN_KEY	15	LEER
TOKEN_ID	100	y
TOKEN_KEY	23	;
TOKEN_ID	100	i
TOKEN_KEY	26	=
TOKEN_NUM	101	1
TOKEN_KEY	23	;
TOKEN_ID	100	total
TOKEN_KEY	26	=
TOKEN_NUM	101	1
TOKEN_KEY	23	;
TOKEN_KEY	13	MIENTRAS
TOKEN_KEY	34	(
TOKEN_ID	100	i
TOKEN_KEY	38	<=
TOKEN_ID	100	y
TOKEN_KEY	35	)
TOKEN_KEY	14	HACER
TOKEN_ID	100	total
TOKEN_KEY	26	=
TOKEN_ID	100	total
TOKEN_KEY	33	*
TOKEN_ID	100	x
TOKEN_KEY	23	;
TOKEN_ID	100	i
TOKEN_KEY	26	=
TOKEN_ID	100	i
TOKEN_KEY	31	+
TOKEN_NUM	101	1
TOKEN_KEY	2	FIN
TOKEN_KEY	23	;
TOKEN_KEY	16	ESCRIBIR
TOKEN_ID	100	total
TOKEN_KEY	2	FIN

Autocorrección de la práctica

En la página web del laboratorio de Procesadores de Lenguaje hay disponible un enlace para que el alumno se descargue el fichero comprimido autocorreccion_lexico.zip. Este fichero contiene 15 programas escritos en ALFA y sus correspondientes 15 ficheros de salida que debe generar el programa prueba_lexico desarrollado en esta primera práctica. El alumno debe comparar las salidas que obtiene de su programa prueba_lexico con las salidas proporcionadas en el fichero autocorreccion_lexico.zip. Para realizar la comparación en Linux se puede utilizar el comando diff que compara el contenido de dos ficheros.

Evaluación de la práctica

La evaluación de los conocimientos adquiridos por el alumno durante el desarrollo de esta primera práctica se hará mediante una prueba individual realizada en una sesión de laboratorio en los días que se detallan en la lista adjunta.

La normativa de evaluación que se aplicará está publicada en la página web del laboratorio de Procesadores de Lenguaje.

grupos de lunes: 3 de marzo de 2008
grupos de martes: 4 de marzo de 2008
grupos de miércoles: 5 de marzo de 2008
grupos de jueves: 6 de marzo de 2008
grupos de viernes: 7 de marzo de 2008

Sugerencia

Se sugiere al alumno que escriba un fichero compatible con la herramienta make y con el nombre makefile que para el objetivo all genere el ejecutable de nombre prueba_lexico.

Gramática del Lenguaje de Programación ALFA

1:	<programa>	::=	INICIO <declaraciones> <funciones> <sentencias> FIN
2:	<declaraciones>	::=	<declaracion>
3:		\|	<declaracion> <declaraciones>
4:	<declaracion>	::=	<clase> <identificadores> ;
5:	<clase>	::=	<clase_escalar>
6:		\|	<clase_puntero>
7:		\|	<clase_vector>
8:	<tipo>	::=	ENTERO
9:		\|	LOGICO
10:	<clase_escalar>	::=	<tipo>
11:	<clase_puntero>	::=	<tipo> #
12:		\|	<clase_puntero> #
13:	<clase_vector>	::=	VECTOR <tipo> DE <constante_entera>
14:		\|	VECTOR <tipo> DE <constante_entera> POR <constante_entera>
15:	<identificadores>	::=	<identificador>
16:		\|	<identificador> , <identificadores>
17:	<funciones>	::=	<funcion> <funciones>
18:		\|
19:	<funcion>	::=	FUNCION <tipo> <identificador> ( <parametros_funcion> ) INICIO <declaraciones_funcion> <sentencias> FIN
20:	<parametros_funcion>	::=	<parametro_funcion> <resto_parametros_funcion>
21:		\|
22:	<resto_parametros_funcion>	::=	; <parametro_funcion> <resto_parametros_funcion>
23:		\|
24:	<parametro_funcion>	::=	<tipo> <identificador>
25:	<declaraciones_funcion>	::=	<declaraciones>
26:		\|
27:	<sentencias>	::=	<sentencia>
28:		\|	<sentencia> ; <sentencias>
29:	<sentencia>	::=	<asignacion>
30:		\|	<condicional>
31:		\|	<bucle>
32:		\|	<lectura_escritura>
33:		\|	<liberacion>
34:		\|	<retorno>
35:		\|	<seleccion>
36:	<seleccion>	::=	SELECCIONAR ( <exp> ) <casos_seleccion> FIN
37:	<casos_seleccion>	::=	<casos_estandar> <caso_defecto>
38:	<casos_estandar>	::=	<caso_estandar>
39:		\|	<casos_estandar> <caso_estandar>
40:	<caso_estandar>	::=	CASO <constante_entera> : <sentencias>
41:	<caso_defecto>	::=	DEFECTO <sentencias>
42:	<retorno>	::=	DEVOLVER <exp>
43:	<asignacion>	::=	<identificador> = <exp>
44:		\|	<elemento_vector> = <exp>
45:		\|	<acceso> = <exp>
46:		\|	<identificador> = RESERVAR
47:		\|	<identificador> = <- <identificador>
48:	<elemento_vector>	::=	<identificador> [ <exp> ]
49:		\|	<identificador> [ <exp> , <exp> ]
50:	<condicional>	::=	SI <exp> ENTONCES <sentencias> FIN
51:		\|	SI <exp> ENTONCES <sentencias> SINO <sentencias> FIN
52:	<bucle>	::=	MIENTRAS <exp> HACER <sentencias> FIN
53:		\|	DESDE <identificador> = <exp> HASTA <exp> HACER <sentencias> FIN
54:	<lectura_escritura>	::=	LEER <identificador>
55:		\|	LEER <elemento_vector>
56:		\|	ESCRIBIR <exp>
57:	<liberacion>	::=	LIBERAR <identificador>
58:	<acceso>	::=	-> <identificador>
59:		\|	-> <acceso>
60:	<exp>	::=	<exp> + <exp>
61:		\|	<exp> - <exp>
62:		\|	<exp> / <exp>
63:		\|	<exp> * <exp>
64:		\|	- <exp>
65:		\|	<exp> Y <exp>
66:		\|	<exp> O <exp>
67:		\|	NO <exp>
68:		\|	<identificador>
69:		\|	<constante>
70:		\|	( <exp> )
71:		\|	( <comparacion> )
72:		\|	<acceso>
73:		\|	<elemento_vector>
74:		\|	<identificador> ( <lista_exp> )
75:	<lista_exp>	::=	<exp> <resto_lista_exp>
76:		\|
77:	<resto_lista_exp>	::=	, <exp> <resto_lista_exp>
78:		\|
79:	<comparacion>	::=	<exp> == <exp>
80:		\|	<exp> != <exp>
81:		\|	<exp> <= <exp>
82:		\|	<exp> >= <exp>
83:		\|	<exp> < <exp>
84:		\|	<exp> > <exp>
85:	<constante>	::=	<constante_logica>
86:		\|	<constante_entera>
87:	<constante_logica>	::=	VERDADERO
88:		\|	FALSO
89:	<constante_entera>	::=	<numero>
90:	<numero>	::=	<digito>
91:		\|	<numero> <digito>
92:	<identificador>	::=	<letra>
93:		\|	<letra> <cola_identificador>
94:	<cola_identificador>	::=	<alfanumerico>
95:		\|	<alfanumerico> <cola_identificador>
96:	<alfanumerico>	::=	<letra>
97:		\|	<digito>
98:	<letra>	::=	a \| b \| ... \| z \| A \| B \|...\| Z
99:	<digito>	::=	0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9

Consideraciones Adicionales

El lenguaje permite incluir comentarios con un formato similar al del lenguaje de programación C:

Entre // y el final de la línea.

Los identificadores se limitan a una longitud de 50 caracteres.

Prácticas de Procesadores de Lenguaje

Curso 2007/2008

Práctica 1: Analizador Léxico

Objetivo de la Práctica

Desarrollo de la Práctica

Estudio de la Gramática

Codificación de una Especificación para flex

Codificación de un Programa de Prueba

Descripción del Fichero de Entrada

Funcionalidad del Programa

Descripción del Fichero de Salida

Ejemplos

Autocorrección de la práctica

Evaluación de la práctica

Sugerencia

Gramática del Lenguaje de Programación ALFA

Consideraciones Adicionales

El lenguaje permite incluir comentarios con un formato similar al del lenguaje de programación `C`:

Entre `//` y el final de la línea.

Los identificadores se limitan a una longitud de 50 caracteres.

Prácticas de Procesadores de Lenguaje

Curso 2007/2008

Práctica 1: Analizador Léxico

Objetivo de la Práctica

Desarrollo de la Práctica

Estudio de la Gramática

Codificación de una Especificación para flex

Codificación de un Programa de Prueba

Descripción del Fichero de Entrada

Funcionalidad del Programa

Descripción del Fichero de Salida

Ejemplos

Autocorrección de la práctica

Evaluación de la práctica

Sugerencia

Gramática del Lenguaje de Programación ALFA

Consideraciones Adicionales

El lenguaje permite incluir comentarios con un formato similar al del lenguaje de programación C:

Entre // y el final de la línea.

Los identificadores se limitan a una longitud de 50 caracteres.

El lenguaje permite incluir comentarios con un formato similar al del lenguaje de programación `C`:

Entre `//` y el final de la línea.