Ejercicios · FLP · Datatypes y arboles sintaxis abstracta¶
Datatypes y árboles de sintaxis abstracta. Cada enlace abre una actividad que se trabaja directo en el navegador, sin instalar nada. Los ejemplos no son los de la sesión: mismo tema, ronda nueva.
Van en el orden en que la sesión ve los temas, y en cada tema hay de analizar
y de escribir. En las de analizar cada respuesta muestra su razón, se acierte
o no; en las de código, las pruebas dicen qué pasó y los tropiezos frecuentes
traen su explicación. El evaluador de la página entiende define-datatype y
cases con las mismas exigencias de DrRacket: un cases sin else tiene
que cubrir todas las variantes.
Dos lenguajes pequeños recorren la página completa, del datatype al parser:
los comandos de un robot, con la palabra clave adelante, y las expresiones
booleanas, que se escriben con el conectivo en medio, (p and q).
Un programa visto como dato¶
Leer el programa como lista¶
Una expresión lambda guardada como lista de Scheme y tres bloques sobre ella.
Primero qué devuelve cada acceso con car y cdr, hasta un (caadr (cadr
(caddr e))) que trae una sola letra. Después qué hace occurs-free? con
listas que no son expresiones: una de un elemento, una de tres, un lambda sin
cuerpo; a veces sale un error y a veces una respuesta, y cuál de las dos no
depende de la lista. Al final el equipo cambia la representación y hay que
decir qué accesos fallan, cuáles siguen bien y cuáles devuelven otra cosa sin
avisar, que son los peores. La consola trae la expresión cargada.
La forma define-datatype¶
¿Compila este datatype?¶
Nueve declaraciones con define-datatype, unas bien y otras con el error que
aparece cada semestre: el tipo con el mismo nombre que su predicado, dos
campos con el mismo nombre, un campo sin predicado. Después siete
expresiones sobre un datatype ya cargado, para predecir qué acepta el
constructor y qué rechaza: el número de campos, el predicado de cada uno y
la lista que list-of revisa elemento por elemento. Lo que se juzga es lo
que DrRacket responde, con sus mensajes.
Escribir el datatype¶
Tres gramáticas y, para cada una, la declaración que le corresponde: las
expresiones booleanas, con dos variantes sin campos y tres recursivas; un
directorio, donde los puntos suspensivos piden list-of; y las s-lists de
EOPL §2.4, que son dos tipos que se nombran el uno al otro. Los nombres los
da la gramática; el predicado de cada campo lo decide quien declara, y las
pruebas construyen valores y preguntan por los predicados.
Análisis por casos con cases¶
Recorrer con cases¶
Un datatype nuevo, los comandos de un robot que avanza, gira y repite un
bloque de comandos, y cuatro procedimientos que lo analizan por casos:
cuánto avanza en total, cuántas veces gira, qué tan hondo se anidan los
repite y cómo se desdoblan en una lista plana. Los valores no son listas,
así que la única forma de abrirlos es cases, y la variante con list-of
obliga a recorrer la lista de comandos con un procedimiento aparte.
Evaluar y reescribir¶
Cuatro procedimientos con cases sobre las expresiones booleanas. Los dos
primeros devuelven un valor de Scheme: evalua, con una lista de los
símbolos que valen verdad, y negaciones, que cuenta. Los dos últimos
devuelven otra expresión booleana, reconstruida variante por variante:
quitar las dobles negaciones y empujar el not hasta las hojas con las
leyes de De Morgan. En esos dos la cláusula del not lleva un cases
anidado, y el árbol que se espera va dibujado bajo cada prueba.
De la gramática al tipo de dato¶
¿Cuál datatype le corresponde?¶
Producciones de varios lenguajes pequeños, print, set, while, call,
lambda con varios parámetros, un condicional con signos en medio, y para
cada una tres variantes candidatas: una sigue la receta y las otras dos
guardan una palabra clave como campo, pierden un no terminal o ponen un
list-of donde no va. Después al revés, de la variante a la producción, y
al final el predicado que lleva cada campo: number?, symbol?, el del
propio tipo o list-of de alguno de ellos.
Del árbol a la gramática¶
La receta al revés, que es lo que se hace al extender un lenguaje: los
árboles están dibujados y lo que falta es la gramática. Primero una
producción por árbol, en un lenguaje de figuras: cuántos hijos tiene el nodo
y si cada uno es una hoja con un número, una hoja con una palabra, otro nodo
del mismo lenguaje o el nodo lista. Después la gramática completa de un
lenguaje de listas de reproducción, leída de varios de sus árboles a la vez,
que es lo que hace falta para saber si una lista puede ir vacía o si un campo
admite más variantes de las que se ven en uno solo. Al final, un árbol que la
gramática no genera y la producción que hay que agregarle.
Árboles de sintaxis abstracta¶
¿Cuál árbol es?¶
Programas del lenguaje de la sesión y tres árboles candidatos para cada uno, dibujados; después al revés, un árbol dibujado y tres programas. Los dos errores que acompañan a cada respuesta correcta son los que aparecen cada semestre: hojas sin envolver en su variante, palabras clave que sobreviven en el árbol, campos en otro orden.
Construir el árbol a mano¶
Tres programas del lenguaje del curso y, para cada uno, la expresión con los
constructores que arma su árbol: una resta dentro de otra, un if con una
resta en la prueba y dos let anidados, donde el identificador que se
declara va suelto y el que se usa va en var-exp. El árbol esperado va
dibujado y, si el código construye otro, aparece al lado. Después la
dirección contraria: un lenguaje de figuras del que solo se tienen los
árboles, y hay que escribir el define-datatype que los construye, contando
los hijos de cada nodo y mirando qué es cada uno. Al cierre, hojas, el
recorrido que devuelve las hojas del árbol de izquierda a derecha.
El parser, el unparser y la ida y vuelta¶
Parser y unparser de comandos¶
De la sintaxis concreta del robot al datatype y de vuelta. Cada prueba de
parse-cmd muestra dibujado el árbol que se espera según la gramática; si el
código construye otro, aparece al lado el que construyó, para comparar forma
contra forma. Primero avanza y gira, después el repite con su lista de
comandos, y al cierre unparse-cmd, con la prueba de que parsear y
desparsear devuelve el programa con el que se empezó.
Parser y unparser con sintaxis infija¶
Las expresiones booleanas se escriben con el conectivo en medio, y el parser
tiene que mirar (cadr d) en lugar de (car d). Primero las hojas y el
not, donde true y false son símbolos que la gramática nombra aparte;
después and y or en medio; al cierre unparse-bexp y la ida y vuelta.
Los árboles dibujados muestran que (p and q) tiene la misma forma que un
(- x 1) del lenguaje del curso: la sintaxis abstracta no sabe dónde iba la
palabra.