Gramaticas
Class TablaCYK

java.lang.Object
  Gramaticas.TablaCYK

Direct Known Subclasses:

TablaParseCYK3, TablaScanCYK

public abstract class TablaCYK
extends java.lang.Object

Superclase para la implementacion de los metodos, atributos y estructuras asociados a una tabla/parsing mediante el algoritmo CYK. Contiene los metodos y atributos comunes a las diferentes implementaciones.

Author:

jvilares

Field Summary

(package private) Cadena	cad Cadena a analizar
(package private) GIC	gram Gramatica a emplear en el analisis
(package private) java.util.LinkedHashSet[][]	tabla Estructura de almacenaje de los simbolos de la tabla.
(package private) int	tam Longitud de la cadena / tamanho de la matriz triangular

Constructor Summary

TablaCYK(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

abstract 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) }
abstract 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)
abstract 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.LinkedHashSet	getCelda(int i, int j) Devuelve el contenido de la tabla en las coordenadas dadas.
int	getTam() Devuelve la longitud de la cadena a analizar
(package private) Terminal	getTerminal(int i) Devuelve el i-esimo terminal de la cadena a analizar.
(package private) java.lang.String	hLine(int fila, int longcelda) Devuelve un separador horizontal para la impresion de la tabla de analisis
(package private) java.lang.String	terminal2String(Terminal t, int longcelda) Formatea el terminal de entrada rellenando con blanks hasta obtener la longitud deseada
abstract java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

tabla

java.util.LinkedHashSet[][] tabla

Estructura de almacenaje de los simbolos de la tabla. Se trata de una matriz triangular inferior de tamano |cadena|*|cadena|

cad

Cadena cad

Cadena a analizar

gram

GIC gram

Gramatica a emplear en el analisis

tam

int tam

Longitud de la cadena / tamanho de la matriz triangular

Constructor Detail

TablaCYK

public TablaCYK(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

getTam

public int getTam()

Devuelve la longitud de la cadena a analizar

Returns:

Longitud de la cadena

getCelda

public java.util.LinkedHashSet getCelda(int i,
                                        int j)

Devuelve el contenido de 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

Returns:

Contenido de esa posicion de la tabla

getTerminal

Terminal getTerminal(int i)

Devuelve el i-esimo terminal de la cadena a analizar. Dado que el algoritmo trabaja con coordenadas 1..N pero los indices de la cadena son 0..N-1, hemos creado este metodo auxiliar para evitar confusiones con las coordenadas.

Parameters:

i - Indice del terminal a devolver

Returns:

Terminal en dicha posicion

hLine

java.lang.String hLine(int fila,
                       int longcelda)

Devuelve un separador horizontal para la impresion de la tabla de analisis

Parameters:

fila - Coordenada YY' de la fila de la tabla de analisis a la que corresponde

longcelda - Longitud total deseada del string correspondiente a una celda

Returns:

Separador horizontal

terminal2String

java.lang.String terminal2String(Terminal t,
                                 int longcelda)

Formatea el terminal de entrada rellenando con blanks hasta obtener la longitud deseada

Parameters:

t - Terminal a formatear

longcelda - Longitud total deseada del string de salida (se rellenara con blanks)

Returns:

String formateado

toString

public abstract java.lang.String toString()

Overrides:

toString in class java.lang.Object

calcular_Ni1

public abstract 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) }

Parameters:

i - Coordenada XX' de la celda a procesar

calcular_Nij

public abstract 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)

Parameters:

i - Coordenada XX' de la celda a procesar

j - Coordenada YY' de la celda a procesar

contiene_S_N1n

public abstract 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)

Returns:

true/false segun este o no