Gramática Libre de Contexto en Java
En la escuela me dejaron hacer un programa en java que valide una cadena a través de una gramática libre de contexto. ¿Pero no tengo idea de como hacer las tranciones?
Los elementos que me dan son:
-Terminales
-No Terminales
-Alfabeto
-No terminal Inicial
-Tranciones o la gramática o Produciones
-La cadena
Ejemplo:
L={I seguida de I(inversa)} //Esto no es un elemento
Alfabeto= {a,b}
NT={X,Y}
NTI=X
T={a,b,vacio}
P={X-X
Y-aYa
Y-bYb
Y-(Vacio) }
Cadena valida :ababaaaababa
Cadena no valida: ababababa
Y lo único que puedo pedir al usuario es:
Los no terminales, los terminales, el alfabeto, el no terminal inicial, las produciones y la cadena a validar
y validar la cadena a través de las produciones, esa es toda la información.
Agradecería alguna idea de como hacerla no estoy pidiendo un programa ya echo solo
ideas que me ayuden a validar yo se programar en java gracias por su atención y pronta respuesta
Los elementos que me dan son:
-Terminales
-No Terminales
-Alfabeto
-No terminal Inicial
-Tranciones o la gramática o Produciones
-La cadena
Ejemplo:
L={I seguida de I(inversa)} //Esto no es un elemento
Alfabeto= {a,b}
NT={X,Y}
NTI=X
T={a,b,vacio}
P={X-X
Y-aYa
Y-bYb
Y-(Vacio) }
Cadena valida :ababaaaababa
Cadena no valida: ababababa
Y lo único que puedo pedir al usuario es:
Los no terminales, los terminales, el alfabeto, el no terminal inicial, las produciones y la cadena a validar
y validar la cadena a través de las produciones, esa es toda la información.
Agradecería alguna idea de como hacerla no estoy pidiendo un programa ya echo solo
ideas que me ayuden a validar yo se programar en java gracias por su atención y pronta respuesta
1 Respuesta
Respuesta de fbluisg
1
Pues no se si te entiendo la gramática ya esta predefinida o el usuario podrá ingresar su propia gramática y de ahí le darás la opción de validarla.
El usuario debe de ingresar su propia gramática junto con una cadena, para con la gramática dada validar la cadena.
O ya te entendí ahora puedes usar un metacompilador como lo es JLex y Cup, o lo tienes que hacer todo así como que a mano y que tan extensa se permite la gramática y todos los datos que me pudieras dar siendo un poco más especifico
Nos piden una gramática libre de contexto con esto también engloba a las regulares y el programa lo tengo que programar yo pero quisiera alguna idea como que métodos usar
Mmmm ya, lo que sucede es que para las gramáticas regulares pues es algo sencillo hacer un como compilador verdad, incluso java te provee de clases (Matches) para ver si palabras corresponde a un modelo, pero para las gramáticas libres de contexto hay varios métodos verdad, hay SLR, LL(1), LALR entre otros, puede ser gramática reconocida ascendente o descendente por eso te pedía que fueras un poco más especifico dependiendo de que tipo de analizador quieres generar para tu gramática. Lo tienes que tener para todos los analizador es como un diagrama de estados que te diga si viene esto en la pila vete a tal estado, y una pila como ya la he mencionado anteriormente en donde ir metiendo los tokens que te devolviera el analizador léxico o en este tu caso el mismo analizador reconociera.
L={I seguida de I(inversa)} //Esto no es un elemento del programa es solo refencia
Alfabeto= {a,b}
NT={X,Y}
NTI=X
T={a,b,vacio}
P={X-X
Y-aYa
Y-bYb
Y-(Vacio) }
Cadena valida :ababaaaababa
Cadena no valida: ababababa
Este seria un ejemplo de lo que tengo que validar con mi programa pero lo que no se hacer son las tranciones o produciones("P"). Ese ese es mi problema en si o duda
Alfabeto= {a,b}
NT={X,Y}
NTI=X
T={a,b,vacio}
P={X-X
Y-aYa
Y-bYb
Y-(Vacio) }
Cadena valida :ababaaaababa
Cadena no valida: ababababa
Este seria un ejemplo de lo que tengo que validar con mi programa pero lo que no se hacer son las tranciones o produciones("P"). Ese ese es mi problema en si o duda
Aja pero dependiendo de que método queras hacer es como vas a hacer las transiciones yo te entiendo que esa es la gramática pero eso puede tener varios métodos para resolverla, no se si me logro explicar dependiendo del método que elijas es las transiciones que vas hacer.
A ok eso es lo que quiero yo que me expliquen un método para daerme una idea de como lo puedo hacer
Mmmm ya si pues pues de los métodos más sencillos son los descente, pero también se pueden hacer con ascendentes solo es cuestión que decidas cual es que quisieras implementar y de que tipo para yo poder ayudarte en eso, porque todo se trata de lo que uno quiera aprender verdad, y la verdad todos se tratan de case e If
Si me gustaría el descendente
Bueno lo primero es que es el método en el cual la programación es poca, pero no acepta todas las gramáticas, ya que no acepta gramáticas antiguasm y la gramática tiene que estar factorizada y no ser recursiva por la derecha. Ya teniendo esto lo que haces es generar la tabla de análisis sintáctico, viendo cual es el Primero, y el Segundo y después creas la tabla esto es lo que tendrías que hacer pero en la programación, pero para saber hacerlo primero aprenderlo a sacar en papel y veras que siempre hay como que un patrón. Si te cuesta entenderle al método preguntame y te ayudo, pero este método si esta en internet fácilmente.
azlan7 podrías ayudarme con respecto a la gramática libre de contexto en el programa de java - Flavia Moscoso