Table of Contents

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

Parsing de Lenguaje con Funciones top-level

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.

Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101. Recuerden que tienen que seguir la metodología vista en las primeras clases y dejar sus funciones debidamente documentadas.

Deben desarrollar su tarea en base a los siguientes archivos:

Deben entregar vía U-Cursos un único archivo .zip que contenga los archivos t1a.rkt y t1a-test.rkt.


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.

<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:

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.

;; <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:

Nuevos nodos para el AST

  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.

Extender el Parser

  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.
  • 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].