Gramaticas
Class GIC

java.lang.Object
  Gramaticas.GramaticaAbstracta
      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