Gramaticas
Class GIC

java.lang.Object
  extended by Gramaticas.GramaticaAbstracta
      extended by Gramaticas.GIC

public class GIC
extends GramaticaAbstracta

Clase que implementa una Gramatica Independiente del Contexto (GIC). Dicha implementacion interna se realiza en base a diferentes atributos que almacenan los no terminales, terminales, reglas, etc. de la gramatica. Estos atributos se describen pormenorizadamente mas abajo.

Version:
Revision 1.2.0, 17/03/07
Author:
Jesus Vilares ( jvilares@udc.es)

Field Summary
protected  No_terminal axioma
          Axioma o simbolo inicial de la gramatica.
protected  java.util.LinkedHashSet noTerminales
          Conjunto de no terminales de la gramatica.
protected  java.util.LinkedHashSet reglas
          Conjunto de reglas o producciones de la gramatica.
protected  java.util.LinkedHashSet terminales
          Conjunto de terminales de la gramatica.
 
Constructor Summary
GIC(java.lang.String s)
          Las gramaticas se pueden construir a partir de una especificacion en modo texto como esta:

S A B; a b c; S; S -> a A; A -> a b c A | b B; B -> b c B | $;


Describiremos la sintaxis a seguir.
 
Method Summary
private  ReglaGIC busca_S_Epsilon()
          Comprueba si la gramatica contiene una regla S->Epsilon (i.e. genera la palabra Epsilon directamente) y devuelve dicha regla
 boolean check_regla(ReglaGIC r)
          Comprueba si una regla/produccion es valida
 boolean contains_noTerminal(No_terminal n)
          Comprueba si la GIC contiene o no un no terminal dado
 boolean contains_terminal(Terminal t)
          Comprueba si la GIC contiene o no un terminal dado
private  boolean contiene_S_Epsilon()
          Comprueba si la gramatica genera la palabra Epsilon directamente (i.e. contiene una regla S->Epsilon)
 boolean es_FNC()
          Comprueba, desde un punto de vista estrictamente sintactico, que la gramatica esta en FNC (i.e. si todas sus reglas son de la forma A->a o A->BC), permitiendo tambien el caso S->Epsilon
 boolean es_regular_derecha()
          Comprueba si la gramatica es o no regular por la derecha.
 boolean es_regular()
          Comprueba si la gramatica es o no regular (por la derecha).
 No_terminal getAxioma()
          Devuelve el axioma o simbolo inicial de la gramatica.
 java.util.LinkedHashSet getNoTerminales()
          Devuelve el conjunto de no terminales de la gramatica.
 java.util.LinkedHashSet getReglas()
          Devuelve el conjunto de reglas o producciones de la gramatica.
 java.util.LinkedHashSet getTerminales()
          Devuelve el conjunto de terminales de la gramatica.
static GIC loadGIC()
          Carga y crea una GIC a partir de su descripcion almacenada en un fichero de texto.
static GIC loadGIC(java.lang.String path)
          Carga una GIC a partir de su descripcion almacenada en un fichero de texto.
 boolean parse_CYK3(Cadena cadena, java.util.List lista)
          Comprueba si la cadena de entrada pertenece al lenguaje generado por esta gramatica aplicando el algoritmo CYK y devuelve los arboles de analisis correspondientes.
 void saveGIC()
          Almacena en un fichero de texto la representacion en formato string de la GIC.
 void saveGIC(java.lang.String path)
          Almacena en un fichero de texto la representacion en formato string de la GIC
 boolean scan_CYK(Cadena cadena)
          Comprueba si la cadena de entrada pertenece al lenguaje generado por esta gramatica aplicando el algoritmo CYK.
 AF toAF()
          Devuelve el automata finito asociado a la gramatica regular.
 java.lang.String toString()
          Devuelve la especificacion de la gramatica en formato string (vease GIC(String)).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

noTerminales

protected java.util.LinkedHashSet noTerminales
Conjunto de no terminales de la gramatica. Se implementa mediante un LinkedHashSet de objetos de tipo No_terminal.


terminales

protected java.util.LinkedHashSet terminales
Conjunto de terminales de la gramatica. Se implementa mediante un LinkedHashSet de objetos de tipo Terminal.


reglas

protected java.util.LinkedHashSet reglas
Conjunto de reglas o producciones de la gramatica. Se implementa mediante un LinkedHashSet de objetos de tipo ReglaGIC.


axioma

protected No_terminal axioma
Axioma o simbolo inicial de la gramatica. Se implementa mediante un objeto de tipo No_terminal.

Constructor Detail

GIC

public GIC(java.lang.String s)
    throws G_Exception
Las gramaticas se pueden construir a partir de una especificacion en modo texto como esta:

S A B; a b c; S; S -> a A; A -> a b c A | b B; B -> b c B | $;


Describiremos la sintaxis a seguir. Primeramente, deberan aparecer una lista con el conjunto de identificadores de los simbolos no terminales, separados por espacios y cerrada por un punto y coma. el conjnto de identificadores validos para los nombres de los simbolos no terminales es el de los caracteres en mayuscula entre la 'A' y la 'Z' (vease No_terminal).

Seguidamente, debera aparecer una lista con los identificadores de los simbolos terminales, finalizada tambien con un punto y coma. Los identificadores validos son los caracteres en minuscula entre la 'a' y la 'z', los digitos entre el '0' y el '9', y el caracter especial epsilon (vease Terminal.EPSILON).
NOTA: Al ser creado e inicializado el objeto, el constructor anhade automatica y explicitamente el epsilon (caracter especial Terminal.EPSILON) al conjunto de terminales de la gramatica. Si bien esto no es formalmente correcto, se trata de un recurso de implementacion que permite simplificar el funcionamiento de la gramatica.

A continuacion, debera aparecer el nombre del simbolo inicial, seguido de un punto y coma. El simbolo inicial debe ser uno de los no terminales previamente declarados.

Y por ultimo, debera aparecer la secuencia de producciones o reglas de reescritura. Cada una de estas reglas debe tener el formato

no_terminal -> simbolo_1 simbolo_2 ... simbolo_n;


donde todos los simbolos que aparecen en la parte derecha de la flecha deben ser terminales o no terminales previamente declarados. Las reglas que compartan la misma parte izquierda se pueden escribir tambien de la forma

no_terminal -> parte_dcha_1 | parte_dcha_2 | ... | parte_dcha_n;


Existe la palabra reservada epsilon (vease Terminal.EPSILON) para denotar una parte derecha vacia.

Parameters:
s - Especificacion de la gramatica en formato string.
Throws:
G_Exception
Method Detail

getNoTerminales

public java.util.LinkedHashSet getNoTerminales()
Devuelve el conjunto de no terminales de la gramatica.

Returns:
Conjunto de no terminales de la gramatica.

getTerminales

public java.util.LinkedHashSet getTerminales()
Devuelve el conjunto de terminales de la gramatica.

Returns:
Conjunto de terminales de la gramatica.

getReglas

public java.util.LinkedHashSet getReglas()
Devuelve el conjunto de reglas o producciones de la gramatica.

Returns:
Conjunto de reglas o producciones de la gramatica.

getAxioma

public No_terminal getAxioma()
Devuelve el axioma o simbolo inicial de la gramatica.

Returns:
Axioma o simbolo inicial de la gramatica.

contains_noTerminal

public boolean contains_noTerminal(No_terminal n)
Comprueba si la GIC contiene o no un no terminal dado

Parameters:
n - No terminal a comprobar
Returns:
true/false segun contenga o no dicho no terminal

contains_terminal

public boolean contains_terminal(Terminal t)
Comprueba si la GIC contiene o no un terminal dado

Parameters:
t - Terminal a comprobar
Returns:
True/false segun contenga o no dicho terminal

check_regla

public boolean check_regla(ReglaGIC r)
                    throws G_Exception
Comprueba si una regla/produccion es valida

Parameters:
r - Regla/produccion a comprobar
Returns:
True/false segun sea valida o no
Throws:
G_Exception

toString

public java.lang.String toString()
Devuelve la especificacion de la gramatica en formato string (vease GIC(String)).

Overrides:
toString in class java.lang.Object
See Also:
Object.toString()

loadGIC

public static GIC loadGIC(java.lang.String path)
                   throws java.io.IOException,
                          G_Exception
Carga una GIC a partir de su descripcion almacenada en un fichero de texto. Las lineas encabezadas por '#' son ignoradas.

Parameters:
path - path completo al archivo a procesar
Returns:
GIC cargada
Throws:
java.io.IOException
AF_Exception
G_Exception

loadGIC

public static GIC loadGIC()
                   throws java.io.IOException,
                          G_Exception
Carga y crea una GIC a partir de su descripcion almacenada en un fichero de texto. Las lineas encabezadas por '#' son ignoradas. El fichero es seleccionado mediante un cuadro de dialogo.

Returns:
GIC cargada
Throws:
java.io.IOException
AF_Exception
G_Exception

saveGIC

public void saveGIC(java.lang.String path)
             throws java.io.IOException
Almacena en un fichero de texto la representacion en formato string de la GIC

Throws:
java.io.IOException

saveGIC

public void saveGIC()
             throws java.io.IOException
Almacena en un fichero de texto la representacion en formato string de la GIC. El fichero es seleccionado mediante un cuadro de dialogo.

Throws:
java.io.IOException

es_regular_derecha

public boolean es_regular_derecha()
Comprueba si la gramatica es o no regular por la derecha. La comprobacion se hace solamente a nivel del formato de las reglas de acuerdo a la definicion:
"Una gramatica independente del contexto es regular por la derecha cuando todas las partes derechas de sus reglas de produccion contienen como maximo un simbolo no terminal y, ademas, si dicho simbolo aparece, es siempre el simbolo que esta en el extremo derecho de la regla."

Returns:
true/false segun sea o no una gramatica regular por la derecha.

es_regular

public boolean es_regular()
Comprueba si la gramatica es o no regular (por la derecha).

Returns:
true/false segun sea o no una gramatica regular (por la derecha).
See Also:
es_regular_derecha()

toAF

public AF toAF()
        throws AF_Exception,
               G_Exception
Devuelve el automata finito asociado a la gramatica regular. NOTA: la gramatica debe estar binarizada

Returns:
Automata finito asociado a la gramatica, o null si no es una gramatica regular (por la derecha)
Throws:
AF_Exception
G_Exception

es_FNC

public boolean es_FNC()
Comprueba, desde un punto de vista estrictamente sintactico, que la gramatica esta en FNC (i.e. si todas sus reglas son de la forma A->a o A->BC), permitiendo tambien el caso S->Epsilon

Returns:
true/false segun este o no en FNC

busca_S_Epsilon

private ReglaGIC busca_S_Epsilon()
Comprueba si la gramatica contiene una regla S->Epsilon (i.e. genera la palabra Epsilon directamente) y devuelve dicha regla

Returns:
Regla S->Epsilon (si la hay) o null si no la hay

contiene_S_Epsilon

private boolean contiene_S_Epsilon()
Comprueba si la gramatica genera la palabra Epsilon directamente (i.e. contiene una regla S->Epsilon)

Returns:
true/false segun genere o no Epsilon directamente

scan_CYK

public boolean scan_CYK(Cadena cadena)
                 throws G_Exception
Comprueba si la cadena de entrada pertenece al lenguaje generado por esta gramatica aplicando el algoritmo CYK.

Parameters:
cadena - Cadena a comprobar
Returns:
true/false segun la cadena pertenezca o no al lenguaje generado por esta gramatica
Throws:
G_Exception - Devuelta en caso de que la gramatica no este en FNC

parse_CYK3

public boolean parse_CYK3(Cadena cadena,
                          java.util.List lista)
                   throws G_Exception
Comprueba si la cadena de entrada pertenece al lenguaje generado por esta gramatica aplicando el algoritmo CYK y devuelve los arboles de analisis correspondientes.

Parameters:
cadena - Cadena a comprobar
l - Lista donde se almacenaran las configuraciones instantaneas. AVISO: la variable debe estar inicializada
Returns:
true/false segun la cadena pertenezca o no al lenguaje generado por esta gramatica
Throws:
G_Exception - Devuelta en caso de que la gramatica no este en FNC o la lista sea nula o no vacia