Tarea 2

CC41A Lenguajes de Programación

Martes 3 Abril

Los siguientes problemas deben ser enviados en un solo archivo de nombre abc2.sml (donde abc son las inciales de su nombre y dos apellidos; por ejemplo el archivo de José Fernández Herrera será jfh2.sml; el 2 es por tarea 2) en attachment a cgutierr@dcc.uchile.cl con subject abc1.sml. Si el archivo no compila directamente, la tarea tiene un 1.

Considere la gramática formal

E -> E and E | E or E | not E | (E)

E -> true | false

donde la precedencia es: not > and > or. Para este ejercicio no consideraremos asociatividad (de hecho no influye en la evaluación final). Definamos los siguientes tipos de datos:

datatype Simbolo = AND | OR | NOT | TRUE | FALSE | Pder | Pizq

datatype Arbol = T | F | Nodo of Simbolo*Arbol*Arbol | Neg of Arbol

Para cada item más abajo escriba una función con el nombre dado que compute el problema respectivo.

1.

Función procLexico . Tipo string -> Simbolo list que tome una expresión escrita en la gramática y retorne la lista de Simbolos que forman la expresión. Por ejemplo procLexico "true or (not false)" = [TRUE, OR, Pder, NOT, FALSE, Pizq] .

2.

Función procSintactico . Tipo Simbolo list -> Arbol . Toma una lista de símbolos y computa el arbol sintáctico correspondiente. Ejemplo: procSintactico [TRUE, OR, Pder, NOT, FALSE, Pizq] = Nodo (OR, T, Neg F) .

3.

Función eval . Tipo Arbol -> bool . Evalua el arbol sintáctico. Ejemplo: eval Nodo (OR, T, Neg F) = true .