Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
teaching:cc4101:tareas:xyz:tarea1a [2024/03/20 20:56] – [Definición del Lenguaje] fdiazteaching:cc4101:tareas:xyz:tarea1a [2024/03/26 16:09] (current) – [Tarea 1a (Entrega: 28 de marzo del 2024)] fdiaz
Line 1: Line 1:
-====== Tarea 1a (Entrega: 28 de marzo del 2024) ======+====== Tarea 1a (Entrega: Miércoles 3 de abril del 2024) ======
  
 ==== Parsing de Lenguaje con Funciones top-level ==== ==== Parsing de Lenguaje con Funciones top-level ====
  
-En esta primera parte de la tarea 1, implementaremos el parser para un lenguaje funcional con funciones top-level, tipos de datos básicos e identificadores locales (with).+En esta tarea, implementaremos el parser para un lenguaje funcional con funciones top-level, tipos de datos básicos e identificadores locales (with). Para hacer una aproximación más gradual al problema, dividiremos el desarrollo en un lenguaje core que luego extenderemos.
  
 <note important> <note important>
Line 12: Line 12:
 Deben desarrollar su tarea en base a los siguientes archivos: Deben desarrollar su tarea en base a los siguientes archivos:
   * ''{{ :teaching:cc4101:tareas:2024-1:t1a.rkt |t1a.rkt}}'': Aquí deberán implementar todas las funcionalidades pedidas en cada pregunta.   * ''{{ :teaching:cc4101:tareas:2024-1:t1a.rkt |t1a.rkt}}'': Aquí deberán implementar todas las funcionalidades pedidas en cada pregunta.
-  * ''{{ :teaching:cc4101:tareas:2024-1:t1a-test.rkt |t1a-test.rkt}}'': Aquí deberán escribir los tests para las funciones desarrolladas.+  * ''{{ :teaching:cc4101:tareas:2024-1:t1a-test.rkt |t1a-test.rkt}}'': Aquí se le proveen tests iniciales para el lenguaje core, y deberán añadir nuevos tests para las funciones desarrolladas o extendidas.
  
 Deben entregar vía U-Cursos **un único archivo .zip** que contenga los archivos **t1a.rkt** y **t1a-test.rkt**. Deben entregar vía U-Cursos **un único archivo .zip** que contenga los archivos **t1a.rkt** y **t1a-test.rkt**.
Line 18: Line 18:
 ---- ----
  
-==== Definición del Lenguaje ==== 
  
-En esta parte, vamos a implementar un lenguaje que incluye primitivas útiles (números, booleanos, y operadores simples), identificadores locales (with con una cantidad arbitraria de bindings), y definiciones de funciones top-level de múltiples argumentos. +===== 1) Parser del Lenguaje Core [0.8 pts] ===== 
 + 
 +En esta parte, vamos a implementar el parser para un lenguaje que incluye primitivas útiles (números, y operadores simples), y definiciones de funciones top-level de múltiples argumentos. 
  
 El lenguaje con el que trabajaremos está definido por la siguiente gramática en BNF. El lenguaje con el que trabajaremos está definido por la siguiente gramática en BNF.
Line 28: Line 29:
  
 <fundef> ::= {define {<id> <id>*} <expr>} <fundef> ::= {define {<id> <id>*} <expr>}
- 
-<bool> ::= true | false 
- 
-<binding> ::= {<id> <expr>} 
  
 <expr>   ::= <num> <expr>   ::= <num>
            | <id>            | <id>
-           | <bool> 
            | {add1 <expr>}            | {add1 <expr>}
            | {+ <expr> <expr>}            | {+ <expr> <expr>}
-           | {< <expr> <expr>} +           | {- <expr> <expr>}
-           | {= <expr> <expr>} +
-           | {! <expr>} +
-           | {if <expr> <expr> <expr>} +
-           | {with {<binding>*} <expr>}+
            | {<id> <expr>*}            | {<id> <expr>*}
-            
 </code> </code>
  
 Un programa está compuesto de 0 o más definiciones de funciones, además de una expresión final que sirve de punto de entrada (como el main en C y Java). Una definición de función incluye el nombre de la función, el nombre de los parámetros formales, y finalmente la expresión del cuerpo de la función. Las expresiones siguen la presentación estándar vista en clases. Un programa está compuesto de 0 o más definiciones de funciones, además de una expresión final que sirve de punto de entrada (como el main en C y Java). Una definición de función incluye el nombre de la función, el nombre de los parámetros formales, y finalmente la expresión del cuerpo de la función. Las expresiones siguen la presentación estándar vista en clases.
  
-Algunos ejemplos de programas válidos para este lenguaje pueden ser:+Algunos ejemplos de programas válidos para este lenguaje core pueden ser:
  
 <code scheme> <code scheme>
 { {
-   {define {sum x y z} {+ x {+ y z}}} +   {+ 3 {- 5 -4}}
-   {with {{x 9} {y 10} {z 11}} +
-        {sum x y z} }+
 } }
 { {
-   {with {{x 5} {y 42} {z true}} +   {define {sum x y z} {+ x {- y z}}} 
-         z}+   {add1 {sum -2 5 1}}
 } }
 { {
Line 66: Line 55:
    {add2 {triple 2}}    {add2 {triple 2}}
 } }
 +</code>
 +
 +Para esta parte, se proveen las definiciones de los tipos de datos que representan los nodos del AST y los tests necesarios para el lenguaje core.
 +
 +Para desarrollar el parser, dividiremos su implementación en las siguientes funciones:
 +  - **[0.4 pts]** ''parse-expr'' que recibe una s-expression y retorna un nodo ''Expr''.
 +  - **[0.2 pts]** ''parse-fundef'' que recibe una s-expression y retorna un nodo ''Fundef''.
 +  - **[0.2 pts]** ''parse-prog'' que recibe una s-expression y retorna un nodo ''Prog''.
 +
 +**Observaciones importantes**:
 +  * Cuando el BNF incluye un nodo con * (cero o más ocurrencias), el nodo del AST correspondiente lleva una lista de los elementos. Luego, pueden usar ''map'' para procesar esos elementos.
 +  * Fíjese en los tests provistos para ver ejemplos de nodos construidos por las distintas funciones de parsing.
 +
 +
 +===== 2) Parser del Lenguaje Extendido [1.2 pts] =====
 +
 +
 +En esta parte, vamos a extender el lenguaje core con algunas primitivas extra (booleanos, y operadores booleanos simples), la expresión condicional ''if'', e identificadores locales (''with'' con una cantidad arbitraria de bindings). 
 +
 +Las extensiones sintácticas del lenguaje se presentan en el siguiente BNF.
 +
 +<code scheme>
 +;; <prog> y <fundef> no cambian
 +
 +<expr>   ::= ...
 +           | <bool>
 +           | {< <expr> <expr>}
 +           | {= <expr> <expr>}
 +           | {! <expr>}
 +           | {if <expr> <expr> <expr>}
 +           | {with {<binding>*} <expr>}
 +
 +<binding> ::= (<id> <expr>)
 +</code>
 +
 +Algunos ejemplos de programas válidos para este lenguaje extendido pueden ser:
 +
 +<code scheme>
 { {
-   {with {{x 3} {y {+ 1 2}}} +   {define {>= x y} {! {< x y}}} 
-         {if {= x y} x y}}+   {define {relu x} {if {>= x 0} x 0}} 
 +   {relu 42} 
 +} 
 +{ 
 +   {define {sum x y z} {+ x {- y z}}} 
 +   {with {{x 9} {y 10} {z 11}} 
 +       {sum x y z} } 
 +} 
 +{ 
 +   {with {{x 5} 
 +          {y 42} 
 +          {z #t}} 
 +       {if z 
 +           {add1 x} 
 +           {- y 2}}} 
 +} 
 +{ 
 +   {with {{x 3} 
 +          {y {+ 1 2}}} 
 +       {if {= x y} x y}}
 } }
 </code> </code>
Line 75: Line 121:
 **Observaciones importantes**: **Observaciones importantes**:
   * Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.   * Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.
-  * Al definir el nombre de los constructores del lenguaje, verifica que no corresponda con uno ya utilizado por algún procedimiento de Racket. +  * Puede incluir los booleanos de una manera similar a como se introducen los números, reutilizando los booleanos de Racket. 
-  * Recuerda que incluir tests por cada función, con cobertura de todos los casos relevantes, es parte de la metodología de programación, y se considerará en la evaluación.+  * Al definir los nombres de los constructores del lenguaje, verifique que no sean ya utilizados por Racket, para evitar confusiones. 
 +  
  
 +=== Nuevos nodos para el AST ===
 +  - **[0.1 pts]** Defina el tipo ''Binding'' que corresponde al nodo ''<binding>'' en el BNF, que representa la asociación entre un identificador y una expresión.
 +  - **[0.2 pts]** Extienda el tipo de datos ''Expr'' con nuevos constructores para las expresiones que se añadieron al lenguaje.
  
-===== Parte 1: Definición del AST [0.5 pts] =====  +=== Extender el Parser === 
-En esta parte, definiremos los tipos de datos que representarán a los diversos nodos del AST de nuestro lenguaje. +  - **[0.1 pts]** Implemente la función ''parse-binding'' que recibe una s-expression y retorna un nodo ''Binding''. 
-Siguiendo la gramática presentada anteriormente, defina lo siguiente:+  - **[0.4 pts]** Extienda la función ''parse-expr'' con casos para las nuevas expresiones.
  
-  - **[0.1 pts]** El tipo ''Fundef'' que representa a la definición de una función top-level. +<note important> 
-  - **[0.1 pts]** El tipo ''Binding'' que representa la asociación entre un identificador y un valor. +  * Recuerde incluir tests para las funciones ''parse-binding'' y ''parse-expr'', con cobertura de todos los casos relevantes, pues se considerará en la evaluación **[0.4 pts]**. 
-  - **[0.2 pts]** El tipo ''Expr'' que representa a una expresión del lenguaje. +</note>
-  - **[0.1 pts]** El tipo ''Prog'' que representa a un programa.+
  
-===== Parte 2: Implementación del Parser [1.5 pts] =====  
-En esta parte, implementaremos el parser para nuestro lenguaje. Para poner en práctica la metodología del curso, dividiremos la implementación del parser en las siguientes funciones: 
  
-  - **[0.2 pts]** ''parse-fundef'' que recibe una s-expression y retorna un nodo ''Fundef''. 
-  - **[0.2 pts]** ''parse-binding'' que recibe una s-expression y retorna un nodo ''Binding''. 
-  - **[0.8 pts]** ''parse-expr'' que recibe una s-expression y retorna un nodo ''Expr''. 
-  - **[0.3 pts]** ''parse-prog'' que recibe una s-expression y retorna un nodo ''Prog''.