Description
I need make the task, Its very urgent.
Unformatted Attachment Preview
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
PEC3
Presentación
En esta Prueba de Evaluación Continua se trabajan las fases de análisis semántico y de sı́ntesis de
código (el back-end ) de un compilador. La PEC combina preguntas teóricas (análisis semántico,
generación de código, optimización de código) con un ejercicio práctico de análisis semántico sobre
CUP.
Competencias
En esta PEC se trabajarán las siguientes competencias del Grado de Ingenierı́a Informática:
Capacidad para analizar un problema en el nivel de abstracción adecuado a cada situación y
aplicar las habilidades y conocimientos adquiridos para resolverlo.
Capacidad para diseñar y construir aplicaciones informáticas mediante técnicas de desarrollo,
integración y reutilización.
Capacidad para aplicar las técnicas especı́ficas de tratamiento, almacenamiento y administración de datos.
Capacidad para proponer y evaluar diferentes alternativas tecnológicas para resolver un problema concreto.
Objetivos
Los objetivos de esta PEC son:
Entender el papel del análisis semántico en un compilador.
Ser capaz de realizar el análisis semántico de un programa mediante gramáticas atribuidas.
Conocer las representaciones de código intermedio más importantes, ası́como sus ventajas e
inconvenientes.
1
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
Ser capaz de desarrollar un analizador semántico mediante CUP.
Conocer las diferentes fases del back-end de un compilador.
Entender las problemáticas en el proceso de generación de código para una plataforma concreta.
Conocer y saber aplicar métodos de optimización de código para mejorar el rendimiento del
código resultante.
Descripción de la PEC a realizar
1. Generación y optimización de código (Valoración de un 30 %)
Dado el siguiente fragmento de código escrito en lenguaje C:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int myMethod ( int par ) {
int x ;
int y ;
int z ;
x = ( par + 1 ) ∗ 2 ;
y = 17 + 12 ;
while ( x > 1 5 ) {
i f ( y != x ) {
z = 17 + 1 ;
x = y − z;
y = y ∗ 2;
}
x = (x ∗ x) − (x − 1)∗(x − 1);
}
y = 7 ∗ 12 + x ∗ x ;
z = y − par + 2 ;
return z ;
}
Os pedimos lo siguiente:
a) Proporcionad la traducción de las lı́neas 5-16 de esta función a código de tres direcciones,
sin optimizar. A continuación tenéis una plantilla de ejemplo con la estructura para
presentar vuestra solución:
2
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
#
5
…
16
Código C
x = (par + 1) * 2;
…
z = y – par + 2;
Código de 3 direcciones
…
…
…
b) La página web Compiler Explorer (https://godbolt.org/) permite explorar el código que generan diversos compiladores para diversos lenguajes de programación. Vamos
a usar este servicio para estudiar cómo funciona la optimización de código.
Seguiremos los siguientes pasos:
Seleccionar C como lenguaje de programación (desplegable en la parte superior
derecha).
Escribimos nuestro código C en el editor de la parte izquierda.
En la parte derecha veremos el código generado en ensamblador para la plataforma
x86 (64 bits).
En la parte superior derecha, en la opción de “Compiler options” podemos indicar
“-O2” para aplicar optimizaciones.
Os pedimos lo siguiente: comparar el código generado con/sin usar la opción de compilación “-O2”, explicando qué optimizaciones se han usado para conseguir el resultado
final. Para cada optimización, mostrad un ejemplo de en qué linea del código original
se ha aplicado y cuál ha sido el resultado obtenido.
2. Analizador semántico CUP (Valoración de un 70 %)
En esta actividad continuaremos desarrollando un compilador para el lenguaje de filtros de
mensajes que definimos en las dos primeras PEC. En esta PEC nos centraremos en desarrollar
el analizador semántico para este lenguaje. Recordamos un ejemplo de especificación en este
lenguaje:
MACRO largePDF() { ATTACHMENT.TYPE = “pdf” AND ATTACHMENT.SIZE > 1 MB }
MACRO Not_2Day() { SENT != TODAY }
SENDER = [email protected],
SENT > 07/2010,
LASTREAD BETWEEN ( 21/10/2011 , 10/2013),
largePDF(),
INCLUDES “penguin”
Para realizar el análisis semántico, nos centraremos en comprobar las declaraciones y usos
de identificadores (parámetros y macros) y los tipos de las expresiones.
Con respecto a las declaraciones y usos de identificadores, comprobaremos las siguientes
propiedades:
3
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
No pueden existir dos macros con el mismo nombre.
Siempre quer llamemos a una macro, esta debe estar declarada previamente.
No podemos llamar a una macro dentro de su propia declaración (llamada recursiva).
Cuando llamamos a una macro, debemos pasar el mismo número de parámetros que se
declarado.
Dentro de una macro, no pueden existir dos parámetros con el mismo nombre. No hay
inconveniente en repetir nombres de parámetros usados en otras macros o bien dar a un
parámetro el mismo nombre que a una macro.
Siempre que referenciemos un parámetro en una expresión, este debe haber sido declarado previamente.
En relación a los tipos, comprobaremos lo siguiente:
El lenguaje dispone de seis tipos de datos: booleano (BOOLEAN), entero (INT), direcciones
de correo (EMAIL), tamaño (SIZE), cadenas de texto (STRING) y fechas (DATE).
Un filtro (las expresiones que aparecen al final del fichero separadas por comas) debe
ser una expresión de tipo booleano.
Las constantes tienen el tipo que corresponde a su valor. Por ejemplo, 15 es de tipo INT,
“hello” es de tipo STRING, 2 MB es de tipo SIZE y 01/01/2010 es de tipo DATE. Las
constantes especiales ME y TODAY son de tipos dirección de correo y fecha, respectivamente.
Los sı́mbolos especiales tienen el tipo siguiente: SENDER y RECEIVER son de tipo dirección
de correo, ATTACHMENT.TYPE es de tipo STRING y ATTACHMENT.SIZE es de tipo tamaño.
No se comprobará el tipo en el paso de parámetros a macros (pero recordad que sı́
deberéis comprobar el número de parámetros). Se asumirá siempre que los parámetros
y el resultado de una llamada a macro son de tipo STRING, pero no se emitirán errores
en caso de no ser ası́.
En los operadores booleanos (and, or, not) seguiremos las siguientes reglas:
• Los operandos deben tener tipo booleano.
• El resultado será de tipo booleano. Si encontramos un error de tipo, seguiremos
asumiendo que el resultado es de tipo booleano para poder seguir con el análisis.
En los operadores aritméticos (suma, resta, división, producto) seguiremos las siguientes
reglas:
• Los operandos deben tener tipo entero (INT).
• El resultado será de tipo entero. Si encontramos algún error de tipo, asumiremos
que el resultado es de tipo INT para poder seguir con el análisis.
4
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
En los operadores relacionales (mayor/menor, mayor/menor o igual) y en los de igualdad
(=) y desigualdad (!=) seguiremos las siguientes reglas:
• Los dos operandos deben tener el mismo tipo.
• El resultado será siempre de tipo booleano. Si encontramos un error de tipo, asumiremos que el resultado es de tipo booleano para poder seguir con el análisis.
• En caso de error, notificaremos que el tipo esperado era el de la primera subexpresión
y el tipo erróneo es el de la segunda expresión.
En las sentencias AFTER, BEFORE y BETWEEN hay que comprobar que las expresiones recibidas son de tipo fecha. El resultado de estas sentencias siempre será de tipo booleano.
En caso de error de tipos, asumiremos que el resultado es de tipo booleano para poder
seguir con el análisis.
Las sentencias INCLUDES y EXCLUDES tienen un resultado de tipo booleano. No hay que
hacer ninguna comprobación sobre el tipo de la expresión recibida como parámetro.
Partiendo de la plantilla Java/JLex/CUP que os proporcionamos junto con este enunciado,
os pedimos que completéis el analizador semántico CUP. Este analizador deberá realizar
las comprobaciones sobre las declaraciones de identificadores y los tipos de expresiones y
sentencias realizando las siguientes acciones:
La gramática deberá mantener todas las instrucciones Eval.emit (para macros, parámetros y subexpresiones) que aparecen en la plantilla de solución que os proporcinamos.
¡No las eliminéis! A la hora de emitir posibles errores, hacedlo siempre después del
Eval.emit correspondiente a la macro/parámetro/expresión que estéis reconociendo en
aquel momento.
Cuando encuentre un error de declaración o uso de un identificador, deberá llamar a la
función correspondiente pasando como parámetro el nombre del identificador afectado:
• Nombres de macros o parámetros repetidos: Eval.emitDuplicateIdentError()
• Nombre de macros o parámetros sin declarar: Eval.emitUndeclaredIdentError()
• Llamadas recursivas: Eval.emitRecursionError()
• Número de parámetros incorrecto: Eval.emitParamsMismatchError()
Si encuentra un error de tipos, deberá llamar a la función Eval.emitTypeMismatchError()
indicando cuál era el tipo esperado y cuál es el tipo encontrado.
Disponéis de la enumeración Eval.Type para representar los posibles tipos de una expresión. Podéis usar sus valores en vuestro código con una sintaxis como la siguiente:
Eval.Type.BOOLEAN.
Deberéis crear y gestionar las tablas de sı́mbolos necesarias para implementar las funcionalidades anteriores.
5
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
En caso que una misma expresión o sentencia contenga varios errores, hay que notificarlos todos, en el orden en que se han descrito en este enunciado.
Estructura de la plantilla. La plantilla consta de los siguientes ficheros:
Parser.cup: Este fichero contiene la gramática CUP para construir el analizador semántico. Inicialmente este fichero contiene la gramática sin reglas semánticas y deberéis completarla para cumplir todos los requisitos del lenguaje. Éste es el único fichero que debéis
entregar como solución de este ejercicio de la PEC.
Lexer.lex: En este fichero os proporcionamos el analizador léxico. No debéis modificar
este fichero.
Eval.java: Este fichero contiene el programa principal (main) que llama al parser y, en
caso que lo indiquéis, comprueba los juegos de prueba. No debéis modificar este fichero.
Dado que no podéis modificar el main, la plantilla CUP para el Parser.cup incluye dos
métodos (initParser y endParser) que se llamarán antes y después de realizar el análisis
sintáctico y semántico. Si lo necesitáis, aquı́ podéis inicializar los atributos que vayáis a usar
o bien mostrar mensajes que os ayuden a depurar vuestro programa. Necesitaréis usar
alguno de estos métodos para gestionar la tabla de sı́mbolos.
Compilando y ejecutando la plantilla. Podéis compilar la plantilla con las siguientes
instrucciones (donde CP es el classpath, que debe incluir al menos el directorio del código
del enunciado y el path donde tenéis instalado JLex y CUP):
> java -classpath java_cup.Main -parser Parser Parser.cup
> java -classpath JLex.Main Lexer.lex
> mv Lexer.lex.java Lexer.java
> javac -classpath *.java
La plantilla puede ejecutarse en dos modos diferentes: run (llama al analizador sintáctico con
una entrada determinada) y evaluate (como run, pero además compara el resultado con
la salida esperada de un juego de pruebas). El modo de ejecución será el primer parámetro
que pasaremos en la llamada al programa. El segundo parámetro será el nombre del juego de
pruebas que usaremos como entrada, que debe incluir el path pero sin la extensión, por
ejemplo TestCases/Everything:
> java -classpath Eval run
> java -classpath Eval evaluate
Juegos de prueba. La plantilla incluye un directorio TestCases con juegos de pruebas
que os permitirán comprobar si vuestro analizador semántico funciona correctamente. Cada
6
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
juego de pruebas consta de dos ficheros: un fichero de entrada .ml y un fichero de resultado
esperado .test. Los juegos de prueba disponibles son los siguientes:
Juego de pruebas
Basic
Arith
Relational
Macros
Programs
Everything
Contenidos
Tipos en expresiones constantes
Tipos en operaciones aritméticas
Tipos en operadores relacionales
Declaración y uso de parámetros y macros
Un programa completo
Todos los casos anteriores en un único juego de pruebas
Podéis aprovechar estos juegos de pruebas para desarrollar vuestro analizador de forma incremental. Tened en cuenta que añadir reglas a la gramática puede cambiar el comportamiento
del analizador. Aseguraos de pasar el juego de prueba Everything antes de la entrega para
comprobar que todo sigue funcionando correctamente.
MUY IMPORTANTE: Para evaluar este ejercicio práctico de la PEC se utilizará corrección automática en el entorno DSLab. Es muy importante que leáis atentamente y sigáis las
instrucciones de entrega (al final de este enunciado). Una ventaja de este sistema es que al
hacer la entrega podréis comprobar si habéis superado los juegos de prueba.
7
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
Recursos
Recursos Básicos
Módulo didáctico 4. Análisis sintáctico
Módulo didáctico 5. Fases de sı́ntesis
Manual de JLex y CUP
Recursos Complementarios
Aula de Laboratorio de Java de Compiladores
Ejemplos de ejercicios de semestres anteriores
Criterios de valoración
La PEC se tiene que resolver de forma individual.
El peso de cada ejercicio se indica en el enunciado.
Es necesario obtener una valoración mı́nima de C- en la PEC para hacer media en la evaluación continua.
En los ejercicios teóricos, se valorará la justificación de las respuestas.
En el ejercicio práctico con CUP se valorará:
• El uso correcto de los atributos y las acciones semánticas CUP.
• La definición y gestión adecuada de la(s) tabla(s) de sı́mbolos.
• La corrección y legibilidad del código propuesto.
• La consecución de los requisitos descritos en el enunciado.
En concreto, se penalizará la implementación de funcionalidades en Java que ya son ofrecidas
por JLex/CUP.
8
75.580 · Compiladores · PEC3
2023-24-Sem.1 · Grado de Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación
Formato y fecha de entrega
Debéis realizar la entrega en dos partes: en el aula de teorı́a y en el entorno de corrección automática
DSLab.
En el aula de teorı́a debéis entregar un PDF que contenga la respuesta a los ejercicios teóricos
y el código de vuestro fichero Parser.cup. Como nombre del fichero debéis usar el siguiente:
“Apellido1_Apellido2_Nombre_PEC3.pdf”.
En el entorno DSLab debéis entregar el fichero Parser.cup. Para hacerlo:
Acceded al entorno DSLab: https://sd.uoc.edu/dslab/
Seleccionad la asignatura “Compiladores” del Grado de Ingenierı́a Informática.
Identificaos con vuestro nombre de usuario y contraseña del Campus de la UOC.
Subid el fichero que queréis entregar con la opción Projects/New Project. Podéis asignarle
una etiqueta para diferenciar diferentes entregas, pero es muy importante no cambiar el
nombre del fichero Parser.cup (si lo hacéis, recibiréis un error diciendo que no podéis subir
este fichero al proyecto).
Seleccionad Create/Build y después Submit.
Hay una tarea (Task) para cada juego de pruebas. El profesorado valorará el número de
juegos de pruebas que superéis en DSLab, por lo que es importante hacer la submission en
todos los juegos de pruebas que superéis. Sin embargo, si superáis correctamente la tarea
Everything, se considerarán superados todos los juegos de pruebas, por lo que no hace falta
hacer más submissions.
Podéis ver en cada momento qué juegos de pruebas habéis superado (Successful) y cuáles
no (Failed). Si el juego de pruebas tiene como resultado ERROR, hay algún problema en
vuestro fichero CUP que hace fallar la generación del parser o la compilación del Parser.java
generado. Podéis ver más información sobre el problema en los ficheros de log adjuntos que
podéis descargar desde DSLab.
Podéis hacer tantas entregas como queráis para cada tarea (dentro del plazo). Sólo se tendrá
en cuenta la última entrega realizada.
La entrega debe realizarse (tanto en el aula de teorı́a como en DSLab) antes de las 23:59 del
dı́a 03/01/2024. No se aceptarán entregas fuera de plazo.
9
Purchase answer to see full
attachment
