Tarea 1a (Entrega: Miércoles 3 de abril del 2024)

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.

Deben desarrollar su tarea en base a los siguientes archivos:

• t1a.rkt: Aquí deberán implementar todas las funcionalidades pedidas en cada pregunta.
• 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.

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.

<prog>   ::= {<fundef>* <expr>}
 
<fundef> ::= {define {<id> <id>*} <expr>}
 
<expr>   ::= <num>
           | <id>
           | {add1 <expr>}
           | {+ <expr> <expr>}
           | {- <expr> <expr>}
           | {<id> <expr>*}

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 core pueden ser:

{
   {+ 3 {- 5 -4}}
}
{
   {define {sum x y z} {+ x {- y z}}}
   {add1 {sum -2 5 1}}
}
{
   {define {triple x} {+ x {+ x x}}}
   {define {add2 x} {+ 2 x}}
   {add2 {triple 2}}
}

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:

1. [0.4 pts] parse-expr que recibe una s-expression y retorna un nodo Expr.
2. [0.2 pts] parse-fundef que recibe una s-expression y retorna un nodo Fundef.
3. [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.

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.

;; <prog> y <fundef> no cambian
 
<expr>   ::= ...
           | <bool>
           | {< <expr> <expr>}
           | {= <expr> <expr>}
           | {! <expr>}
           | {if <expr> <expr> <expr>}
           | {with {<binding>*} <expr>}
 
<binding> ::= (<id> <expr>)

Algunos ejemplos de programas válidos para este lenguaje extendido pueden ser:

{
   {define {>= 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}}
}

Observaciones importantes:

• Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.
• Puede incluir los booleanos de una manera similar a como se introducen los números, reutilizando los booleanos de Racket.
• Al definir los nombres de los constructores del lenguaje, verifique que no sean ya utilizados por Racket, para evitar confusiones.

1. [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.
2. [0.2 pts] Extienda el tipo de datos Expr con nuevos constructores para las expresiones que se añadieron al lenguaje.

1. [0.1 pts] Implemente la función parse-binding que recibe una s-expression y retorna un nodo Binding.
2. [0.4 pts] Extienda la función parse-expr con casos para las nuevas expresiones.