Trabajo práctico

Algoritmo de Cocke–Younger–Kasami

Objetivos

El objetivo del trabajo es programar una aplicación en Haskell que lea la descripción de una gramática en Forma Normal de Chomsky y una cadena de entrada y analice dicha cadena por medio del algoritmo CYK. El resultado del análisis debe ser un mensaje en consola indicando si la cadena es "Correcta" o "Incorrecta". Como opción de mejora se plantea que en caso de que la cadena sea correcta la aplicación genere también los árboles de derivación que conducen a su reconocimiento.

Formato de descripción de la gramática

Las gramáticas se describirán en ficheros con la extensión ".cfg". El formato de descripción de las gramáticas utilizará una línea para cada regla de la gramática. Se admiten como válidas las líneas vacías que no contienen ninguna regla. La gramática debe estar descrita en Forma Normal de Chomsky, lo que significa que solo hay dos tipos de reglas:

• symbol ::= symbol symbol

Se trata de reglas que sustituyen un símbolo no terminal por dos símbolos no terminales. Los símbolos no terminales serán palabras expresadas con caracteres alfanuméricos. Por ejemplo, start, Comienzo, Var7, S, LISTA, etc.

• symbol ::= <terminal>

Describe una regla que sustituye un símbolo no terminal por un símbolo terminal. Los símbolos terminales serán palabras expresadas entre los signos menor y mayor. Por ejemplo, <Identificador>, <COMA>, <Num16>, etc.

El símbolo inicial de la gramática es el que se define en la primera regla del fichero. Las líneas pueden contener comentarios, que comienzan con el símbolo # y terminan al final de línea.

Este es un ejemplo de definición de una gramática con este formato:

# Ejercicio 3.7

S ::= <number>   # Este es el símbolo inicial
S ::= <id>
S ::= L N

N ::= B R
L ::= <lparen>
R ::= <rparen>

B ::= S B
B ::= <number>
B ::= <id>
B ::= L N

Formato de descripción de la entrada

La cadena de entrada que se pretende verificar se introducirá en un fichero de texto. El contenido será la secuencia de símbolos terminales que se pretenda evaluar, utilizando un símbolo por cada línea.

Este es un ejemplo de entrada:

<lparen>
<id> 
<lparen>
<id> 
<lparen> 
<number> 
<rparen> 
<rparen> 
<lparen> 
<id> 
<rparen> 
<rparen>

Formato de descripción del arbol de derivación

Como opción de mejora del trabajo se plantea que en caso de que la cadena sea correcta la aplicación genere también los árboles de derivación que conducen a su reconocimiento. Estas derivaciones se incluirán en un fichero de salida en el que se indicará en cada línea una derivación, esto es, una sustitución de un símbolo no terminal por la parte derecha de una regla. La primera línea será el símbolo inicial y las siguientes irán mostrando la derivación hasta llegar al contenido de la cadena de entrada analizada.

Por ejemplo, la gramática y la cadena de entrada indicadas en los apartados anteriores generarán la siguiente derivación:

S
L N
<lparen> N
<lparen> B R
<lparen> S B R
<lparen> <id> B R
<lparen> <id> S B R
<lparen> <id> L N B R
<lparen> <id> <lparen> N B R
<lparen> <id> <lparen> B R B R
<lparen> <id> <lparen> S B R B R
<lparen> <id> <lparen> <id> B R B R
<lparen> <id> <lparen> <id> L N R B R
<lparen> <id> <lparen> <id> <lparen> N R B R
<lparen> <id> <lparen> <id> <lparen> B R R B R
<lparen> <id> <lparen> <id> <lparen> <number> R R B R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> R B R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> B R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> L N R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> <lparen> N R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> <lparen> B R R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> <lparen> <id> R R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> <lparen> <id> 
  <rparen> R
<lparen> <id> <lparen> <id> <rparen> <number> <rparen> <rparen> <lparen> <id> 
  <rparen> <rparen>

Documentación a entregar

• Memoria explicativa del desarrollo del trabajo, describiendo los tipos de datos y las diferentes funciones que se hayan desarrollado.
• Código fuente y compilado del trabajo, en formato electrónico.
• Conjunto de pruebas realizados.
• Archivos de gramáticas y entradas utilizados en las puebas.

Plazo de entrega

La fecha límite de entrega del trabajo será el viernes, 1 de febrero de 2020.

El trabajo se podrá presentar a traves de la plataforma de enseñanza virtual o, directamente, enviándolo por correo electrónico al profesor.