Gramaticas
Class TablaParseCYK3

java.lang.Object
  Gramaticas.TablaCYK
      Gramaticas.TablaParseCYK3

public class TablaParseCYK3
extends TablaCYK

Clase que implementa los metodos y atributos especificos a la tabla de parsing CYK empleando el tercer algoritmo explicado en clase.

Author:

jvilares

Field Summary

Fields inherited from class Gramaticas.TablaCYK

cad, gram, tabla, tam

Constructor Summary

TablaParseCYK3(Cadena cadena, GIC gramatica)
El constructor crea la tabla de analisis de tamanho |cadena|*|cadena| y almacena la cadena y la gramatica a emplear

Method Summary

void	add(int i, int j, ReglaCYK3 r) Inserta/anhade un simbolo a la tabla en las coordenadas dadas.
void	calcular_Ni1(int i) Calcula la celda N(i,1) de la tabla de analisis: i.e. para cada i=1..N, sea N(i,1)={A / A->w(i,1) }
void	calcular_Nij(int i, int j) Calcula la celda N(i,j) de la tabla de analisis: i.e. para k=1..j-1, anhadir a N(i,j) todos los no terminales A para los cuales A->BC es una regla de P, con B perteneciente a N(i,k) y C perteneciente a N(i+k,j-k)
boolean	contiene_S_N1n() Comprueba si el axioma S esta o no en el top de la tabla (i.e. si la cadena pertenece o no al lenguaje)
java.util.ArrayList	get_parseTree(No_terminal raiz, int i, int j) Devuelve la lista de arboles de analisis (en formato string parentizado) con raiz en el no terminal indicado, siendo este la parte izqda de una de las reglas de la celda con las coordenadas indicadas
java.lang.String	toString()

Methods inherited from class Gramaticas.TablaCYK

getCelda, getTam, getTerminal, hLine, terminal2String

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

TablaParseCYK3

public TablaParseCYK3(Cadena cadena,
                      GIC gramatica)

El constructor crea la tabla de analisis de tamanho |cadena|*|cadena| y almacena la cadena y la gramatica a emplear

Parameters:

cadena - Cadena a analizar

gramatica - Gramatica a emplear en el analisis

Method Detail

add

public void add(int i,
                int j,
                ReglaCYK3 r)

Inserta/anhade un simbolo a la tabla en las coordenadas dadas. Dado que el algoritmo trabaja con coordenadas 1..N pero los indices de la tabla son 0..N-1, hemos creado este metodo auxiliar para evitar confusiones con las coordenadas.

Parameters:

i - Coordenada XX' de la tabla

j - Coordenada YY' de la tabla

r - Regla anotada a insertar en es posicion

toString

public java.lang.String toString()

Specified by:

toString in class TablaCYK

calcular_Ni1

public void calcular_Ni1(int i)

Calcula la celda N(i,1) de la tabla de analisis: i.e. para cada i=1..N, sea N(i,1)={A / A->w(i,1) }

Specified by:

calcular_Ni1 in class TablaCYK

Parameters:

i - Coordenada XX' de la celda a procesar

calcular_Nij

public void calcular_Nij(int i,
                         int j)

Calcula la celda N(i,j) de la tabla de analisis: i.e. para k=1..j-1, anhadir a N(i,j) todos los no terminales A para los cuales A->BC es una regla de P, con B perteneciente a N(i,k) y C perteneciente a N(i+k,j-k)

Specified by:

calcular_Nij in class TablaCYK

Parameters:

i - Coordenada XX' de la celda a procesar

j - Coordenada YY' de la celda a procesar

contiene_S_N1n

public boolean contiene_S_N1n()

Comprueba si el axioma S esta o no en el top de la tabla (i.e. si la cadena pertenece o no al lenguaje)

Specified by:

contiene_S_N1n in class TablaCYK

Returns:

true/false segun este o no

get_parseTree

public java.util.ArrayList get_parseTree(No_terminal raiz,
                                         int i,
                                         int j)

Devuelve la lista de arboles de analisis (en formato string parentizado) con raiz en el no terminal indicado, siendo este la parte izqda de una de las reglas de la celda con las coordenadas indicadas

Parameters:

raiz - No terminal raiz buscado

i - Coordenada XX' de la celda en la que buscar

j - Coordenada YY' de la celda en la que buscar

Returns:

Lista de strings de los arboles generados