Métodos computacionales

Proyecto: Resaltador de léxico

Objetivo

Durante esta actividad, los alumnos serán capaces de:


Subcompetencias a demostrar con esta evidencia

Competencia Subcompetencia
y nivel de dominio
STC0100:
Desarrollo de algoritmos computacionales

Soluciona problemas generando algoritmos computacionales eficientes bajo modelos y herramientas de las ciencias computacionales.

STC0101A:
Implementación de algoritmos computacionales

Implementa algoritmos computacionales confiables y correctos que solucionan problemas.

STC0102A:
Optimización de algoritmos computacionales

Optimiza algoritmos computacionales robustos y eficientes que se aplican en el desarrollo de soluciones.

STC0103A:
Generación de modelos computacionales

Genera modelos computacionales verificables y correctos para la solución de problemas.

STC0104A:
Implementación de modelos computacionales

Implementa modelos computacionales en la solución de un problema que permiten su interoperatividad con otros modelos.


Introducción

A lo largo de la historia de la computación se han creado una gran cantidad de lenguajes de programación siempre con el objetivo de resolver algún problema que no ha logrado ser resuelto adecuadamente por ninguno de los lenguajes existentes. Algunos de los puntos más comunes que han motivado la creación de nuevos lenguajes de programación son:

Algunos han logrado ser exitosos en el objetivo que perseguían y llegan a ser utilizados por una gran cantidad de personas en la comunidad de desarrollo. Otros solo han logrado sobrevivir en comunidades muy pequeñas o, inclusive, han desaparecido. Sin embargo, muchos han logrado hacer algún tipo de aportación para que los nuevos lenguajes creados sean mejores, al menos en algún aspecto.

A continuación se listan algunos ejemplos de lenguajes relevantes que aparecieron hace relativamente poco tiempo:

Gran parte de éxito de un lenguaje depende de sus características, y estas son establecidas por sus diseñadores después de analizar a fondo el o los problemas que quieren resolver con este lenguaje. Una vez que el lenguaje ha sido diseñado y sus características han sido establecidas, se debe crear un software traductor que permita ejecutar los programas escritos en dicho lenguaje y en caso de que contengan errores ayude a los programadores a detectarlos.

Pero enfoquémonos ahora en algo relacionado pero más fundamental. Cuando se comienza a conocer un nuevo lenguaje, ya sea un lenguaje de programación o un lenguaje natural (e.g. español, inglés, mandarín), lo primero con lo que uno usualmente se familiariza es con el léxico del lenguaje, es decir, las palabras que lo conforman.

Desde la perspectiva de nuestra materia, nos pueden surgir las siguientes preguntas:

Descripción del proyecto

En los equipos ya conformados, realizar en orden la Parte 1 y Parte 2, detalladas a continuación. En una actividad posterior (póster argumentativo de reflexión) deberán reflexionar y documentar sus resultados, así como justificar el porqué de las diferentes decisiones que tomaron durante el desarrollo de este proyecto integrador.

Parte 1: Resaltador léxico secuencial

  1. Revisar cada uno de los siguientes rankings de popularidad de lenguajes de programación:

    Seleccionar un lenguaje de programación que aparezca en las primeras 20 posiciones de cada uno de los cuatro rankings de arriba y del cual también tengan disponible su especificación léxica.

  2. Determinar al menos diez categorías léxicas (tipos de tokens ) distintas del lenguaje seleccionado (por ejemplo: identificadores, comentarios, literales de diferentes tipos, palabras reservadas, operadores, signos de puntación, etc.).

  3. Elaborar un Notebook de Clojupyter que tome como entrada un archivo fuente del lenguaje de programación seleccionado. El correspondiente código de Clojure debe producir como salida un documento de HTML que contenga el mismo código fuente de la entrada pero con su léxico resaltado, a partir de las categorías léxicas determinadas en el punto anterior.

    Consideraciones:

    • El reconocimento de los tokens debe hacerse a través de expresiones regulares.
    • El documento de salida debe tener el mismo nombre que el archivo de entrada pero reemplazando su extensión por .html. Por ejemplo, si el archivo de entrada se llama ejemplo.cpp, entonces la salida debe ser ejemplo.html.
    • El código fuente de la entrada debe convertirse a HTML y colocarse completamente dentro de un elemento <pre>...</pre> en el cuerpo del documento de salida. A su vez, cada token que deba ser resaltado debe quedar dentro de un elemento <span>...</span>. El coloreado de los tokens se debe llevar a cabo usando CSS, ya sea embebido directamente en el HTML o combinado con un documento CSS externo.
    • Los colores utilizados para resaltar cada tipo de token quedan al gusto y criterio de cada equipo. Sin embargo, es importante que se pueda distinguir fácilmente una categoría léxica de cualquier otra. Así mismo, debe existir un buen contraste entre los colores del texto y su fondo.
    • Todo el whitespace (espacios, tabuladores, saltos de línea) del archivo de entrada debe quedar exactamente igual en el documento de salida.
    • Ciertos caracteres en el archivo de entrada deben ser reemplazados en el documento de salida por sus correspondientes secuencias de escape de HTML:
      • < (menor que)   ➔   &lt;
      • > (mayor que)   ➔   &gt;
      • & (ampersand)   ➔   &amp;

Parte 2: Resaltador léxico paralelo

  1. Extender el Jupyter Notebook de la Parte 1 para que realice el proceso de resaltado de léxico de manera paralela (aprovechando los múltiples núcleos disponibles en los CPUs modernos) sobre múltiples archivos contenidos en un directorio específico y todos sus subdirectorios anidados.
  2. Probar el programa con un directorio que contenga al menos 1,000 archivos a procesar. Los archivos deben ser códigos fuentes de por lo menos 200 líneas de código cada uno. Pueden ser de su propia autoría u obtenidos de repositorios públicos como Github. Los archivos no requieren ser todos diferentes. Al menos debe haber 20 archivos originales y todos los demás pueden ser copias de estos.
  3. Medir los tiempos de varias ejecuciones del programa usando un solo thread y múltiples threads. Calcular el speedup promedio obtenido.

Tanto para la parte Parte 1 y la Parte 2, es necesario cumplir también con los siguientes puntos:

¿Qué se debe entregar?

Colocar en un archivo ZIP llamado proyecto_integrador.zip tanto el Notebook como todos los archivos utilizados para las pruebas. Entregar como se indica a continuación.

Instrucciones para subir archivo

Para entregar el archivo proyecto_integrador.zip, ingresa los siguientes datos:

Solicitar NIP

Solo es necesario que lo entregue un miembro del equipo.

La fecha límite es el jueves 10 de junio, antes de la presentación correspondiente.