·
Esta práctica tiene como primer objetivo la codificación de un analizador
sintáctico mediante el uso del lenguaje de programación C
y la herramienta de ayuda a la generación de analizadores sintácticos bison.
·
Este analizador será utilizado por el compilador del lenguaje ALFA
que va a desarrollarse durante el curso.
· El segundo objetivo es la codificación de una tabla de símbolos. El alumno conoce el tipo de datos llamado tabla hash, los algoritmos para su gestión y su rendimiento de la asignatura de segundo Metodología y tecnología de la programación II (MTPII) y su uso como tabla de símbolos de la parte de teoría de la asignatura Procesadores de lenguaje.
bison·
El alumno deberá escribir un fichero de nombre alfa.y
que sea una especificación correcta para la entrada de la herramienta bison.
Se recomienda al alumno que se familiarice primero con bison
mediante las explicaciones que su profesor de prácticas realizará en su
laboratorio.
·
Cuando se compile el fichero alfa.y pueden aparecer mensajes de
conflictos. Estos conflictos se refieren a los que encuentra el autómata a pila
generado por la herramienta bison.
Para obtener información acerca de ellos, se debe compilar el fichero alfa.y de la siguiente manera:
bison -d -y -v alfa.y
con el flag -v se genera el fichero y.output que contiene la descripción completa del autómata y de los conflictos (si existieran).
El alumno debe asegurarse de eliminar los conflictos siguiendo las indicaciones
de su profesor de prácticas.
flex·
El alumno debe modificar el fichero alfa.l de la práctica 1 para poder ser enlazado con el
fichero alfa.y. Para ello, utilizará como guía las
explicaciones que su profesor de prácticas realizará en su laboratorio.
·
El alumno también deberá escribir (en C)
un programa de prueba del analizador sintáctico generado con bison, con los siguientes requisitos:
o
Nombre del programa fuente: prueba_sintactico.c
o
Al ejecutable correspondiente, se le invocará de la siguiente manera:
prueba_sintactico [<nombre
fichero entrada> [<nombre fichero salida>]]
o
Es decir, el programa se puede ejecutar:
§
Con 0 argumentos, entonces se utilizan la entrada y la salida
estándares.
§
Con 1 argumentos, entonces se utiliza la salida estándar y el
argumento como nombre del fichero de entrada.
§
Con 2 argumentos, entonces el primero se interpreta como el nombre del
fichero de entrada y el segundo como el nombre del fichero de salida.
o
La estructura de los ficheros de entrada/salida se explican a
continuación.
·
El fichero de entrada contiene un programa escrito en lenguaje ALFA
(no necesariamente correcto).
·
El fichero de salida se compone de un conjunto de líneas de dos tipos.
En concreto:
o
Una línea por cada Token
reconocido (desplazado) por el analizador léxico.
o
Una línea por cada producción
reducida en el proceso de análisis sintáctico.
·
Cada línea correspondiente a un Token
desplazado debe
contener la siguiente información y formato:
D: <token>
donde <token> es el fragmento de entrada reconocido por el
analizador léxico y “D:” y “<token>” van
separados por un tabulador.
·
Cada línea correspondiente a una regla
reducida tendrá el formato siguiente:
R<nº
regla>: <regla>
donde <nº regla> es el número que
identifica la regla que se reduce en la gramática de ALFA especificada en el
enunciado de la primera práctica, y <regla>
es el texto de la regla reducida según aparece en la gramática. “R<nº
regla>” y “<regla>” van separados por un tabulador.
Los elementos que forman “<regla>” irán separados por
espacios.
·
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 sería el siguiente:
D: INICIO
D: ENTERO
R8: <tipo>
::= ENTERO
D: x
R10: <clase_escalar>
::= <tipo>
R5: <clase>
::= <clase_escalar>
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ,
D: resultado
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R15: <identificadores>
::= <identificador>
R16: <identificadores>
::= <identificador> , <identificadores>
R4: <declaracion>
::= <clase> <identificadores> ;
D: LEER
R2: <declaraciones>
::= <declaracion>
R18: <funciones>
::=
D: x
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R54: <lectura_escritura>
::= LEER <identificador>
R32: <sentencia>
::= <lectura_escritura>
D: resultado
R90: <identificador>
::= TOK_IDENTIFICADOR
D: =
D: x
R90: <identificador>
::= TOK_IDENTIFICADOR
D: *
R68: <exp>
::= <identificador>
D: x
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R68: <exp>
::= <identificador>
R63: <exp>
::= <exp> * <exp>
R43: <asignacion>
::= <identificador> = <exp>
R29: <sentencia>
::= <asignacion>
D: ESCRIBIR
D: resultado
R90: <identificador>
::= TOK_IDENTIFICADOR
D: FIN
R68: <exp>
::= <identificador>
R56: <lectura_escritura>
::= ESCRIBIR <exp>
R32: <sentencia>
::= <lectura_escritura>
R27: <sentencias>
::= <sentencia>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R1: <programa>
::= INICIO <declaraciones> <funciones> <sentencias> 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 sería el siguiente:
D: INICIO
D: ENTERO
R8: <tipo>
::= ENTERO
D: x
R10: <clase_escalar>
::= <tipo>
R5: <clase>
::= <clase_escalar>
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ,
D: y
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R15: <identificadores>
::= <identificador>
R16: <identificadores>
::= <identificador> , <identificadores>
R4: <declaracion>
::= <clase> <identificadores> ;
D: ENTERO
R8: <tipo>
::= ENTERO
D: i
R10: <clase_escalar>
::= <tipo>
R5: <clase>
::= <clase_escalar>
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ,
D: total
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R15: <identificadores>
::= <identificador>
R16: <identificadores>
::= <identificador> , <identificadores>
R4: <declaracion>
::= <clase> <identificadores> ;
D: LEER
R2: <declaraciones>
::= <declaracion>
R3: <declaraciones>
::= <declaracion> <declaraciones>
R18: <funciones>
::=
D: x
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R54: <lectura_escritura>
::= LEER <identificador>
R32: <sentencia>
::= <lectura_escritura>
D: LEER
D: y
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R54: <lectura_escritura>
::= LEER <identificador>
R32: <sentencia>
::= <lectura_escritura>
D: i
R90: <identificador>
::= TOK_IDENTIFICADOR
D: =
D: 1
R89: <constante_entera>
::= TOK_NUMERO
R86: <constante>
::= <constante_entera>
R69: <exp>
::= <constante>
D: ;
R43: <asignacion>
::= <identificador> = <exp>
R29: <sentencia>
::= <asignacion>
D: total
R90: <identificador>
::= TOK_IDENTIFICADOR
D: =
D: 1
R89: <constante_entera>
::= TOK_NUMERO
R86: <constante>
::= <constante_entera>
R69: <exp>
::= <constante>
D: ;
R43: <asignacion>
::= <identificador> = <exp>
R29: <sentencia>
::= <asignacion>
D: MIENTRAS
D: (
D: i
R90: <identificador>
::= TOK_IDENTIFICADOR
D: <=
R68: <exp>
::= <identificador>
D: y
R90: <identificador>
::= TOK_IDENTIFICADOR
D: )
R68: <exp>
::= <identificador>
R81: <comparacion>
::= <exp> <= <exp>
R71: <exp>
::= ( <comparacion> )
D: HACER
D: total
R90: <identificador>
::= TOK_IDENTIFICADOR
D: =
D: total
R90: <identificador>
::= TOK_IDENTIFICADOR
D: *
R68: <exp>
::= <identificador>
D: x
R90: <identificador>
::= TOK_IDENTIFICADOR
D: ;
R68: <exp>
::= <identificador>
R63: <exp>
::= <exp> * <exp>
R43: <asignacion>
::= <identificador> = <exp>
R29: <sentencia>
::= <asignacion>
D: i
R90: <identificador>
::= TOK_IDENTIFICADOR
D: =
D: i
R90: <identificador>
::= TOK_IDENTIFICADOR
D: +
R68: <exp>
::= <identificador>
D: 1
R89: <constante_entera>
::= TOK_NUMERO
R86: <constante>
::= <constante_entera>
R69: <exp>
::= <constante>
D: FIN
R60: <exp>
::= <exp> + <exp>
R43: <asignacion>
::= <identificador> = <exp>
R29: <sentencia>
::= <asignacion>
R27: <sentencias>
::= <sentencia>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R52: <bucle>
::= MIENTRAS <exp> HACER <sentencias> FIN
R31: <sentencia>
::= <bucle>
D: ;
D: ESCRIBIR
D: total
R90: <identificador>
::= TOK_IDENTIFICADOR
D: FIN
R68: <exp>
::= <identificador>
R56: <lectura_escritura>
::= ESCRIBIR <exp>
R32: <sentencia>
::= <lectura_escritura>
R27: <sentencias>
::= <sentencia>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R28: <sentencias>
::= <sentencia> ; <sentencias>
R1: <programa> ::= INICIO <declaraciones> <funciones> <sentencias> FIN
· El alumno debe escribir los ficheros y módulos C que
considere necesarios para la definición e implementación de la tabla de símbolos.
Para todas sus decisiones de diseño utilizará como referencia las indicaciones
que conoce de la parte de teoría y las
explicaciones que su profesor de prácticas realizará en su laboratorio.
· 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_sintactico.zip. Este fichero contiene los 15 ficheros de salida a generar por el programa prueba_sintactico desarrollado en esta segunda práctica, tomando como entrada los mismos 15 programas escritos en lenguaje ALFA que se utilizaron en la primera práctica. El alumno deberá comparar las salidas que obtiene de su programa prueba_sintactico con las salidas proporcionadas en el fichero autocorreccion_sintactico.zip. Para realizar la comparación en Linux se puede utilizar el comando diff que compara el contenido de dos ficheros.
La evaluación de los conocimientos
adquiridos por el alumno durante el desarrollo de esta segunda 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.
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_sintactico.