Compilador

Buenas tardes, soy nuevo en el campo de compiladores y espero me puedan ayudar. Resulta que me han dejado un trabajo en el cual debo definir una gramática simple y luego crear un programa en java con estructura de datos (pilas, listas, colas, etc..) que analize una cadena ingresada por el usuario si pertenece o no a la gramática definida.

Mi idea fue en un principio esta:
G = (VN, VT, S, P)
Siendo:
• VARIABLES NO TERMINALES (VN) = { A, B, C }

• VARIABLES TERMINALES (VT) = { x, +, (, ) }

• AXIOMA PRINCIPAL (S) = { A }
Teniendo como reglas de producción:
• (1) A -> x | (B) // first_rule

• (2) B -> AC // second_rule

• (3) C -> {+A} // third_rule

Lo he logrado hacer en C pero reconociendo caracter por caracter, y resultó que de esa manera no debía de ser sino usando estructura de datos.

Gracias de antemano.

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

Puedes ir creando tokens por

Puedes ir creando tokens por cada elemento que identifiques e irlos anexando a una lista. Luego recorrer la lista y ver que cumple las reglas.

Si no te importa leer varias conversaciones, acá puse varios links a varios posts

http://www.javamexico.org/blogs/gelo1002/compilador

Todos estos son como "ejemplos" sencillos, nada que pudiera llamarse "compilador" como tal.

Revisa si algo te sirve de ahí.

Gracias OscarRyz. He estado

Gracias OscarRyz. He estado leyendo los link que me has enviado y entiendo que lo que tendría que hacer sería un tokenizer para separar los caracteres de la cadena ingresada, y un parser para el análisis de los token. Y por lo que me dices que los tokens vayan a una estructura de datos como listas, pero ¿cómo haría eso? ¿Mi gramática planteada estarpia bien para ese tipo de análisis o es muy compleja?

Gracias.

Imagen de paranoid_android

¿Ya lo programaste?

Hola IvanMedina.
Espero que no te ofendas, te ayudaré haciendo preguntas para que avances en tu lógica.
-"Y por lo que me dices que los tokens vayan a una estructura de datos como listas, pero ¿cómo haría eso?"
¿Ya lo programaste?, ¿Ya descubriste como usar un ArrayList y un Iterator? - Si es un ejercicio academico no pongas tu código ;)

-"¿Mi gramática planteada estaría bien para ese tipo de análisis o es muy compleja?"
¿Tienes certeza de que tus reglas no tienen referencias cíclicas o algún problema oculto?, ¿Cómo podrías demostrarlo?

Hola paranoid_android,

Hola paranoid_android, anteriormente lo hice en un programa en C, pero al mostrar al profesor me dijo que no lo haga de esa manera por que debía de utilizar una estructura de datos y que sea en java.

El código que hice fue el siguiente:

// Librerías
#include
#include
/*
* G = ( VN, VT, S, P )
* VN = { A, B, C }
* VT = { x, +, (, ) }
* S = A
* REGLAS DE PRODUCCIÓN(P)
* A -> x | (B)
* B -> AC
* C -> {+A}
*/
// Variables
char token, cadena[80];
int i=0;

// Métodos
int first_rule(void);
int second_rule_rule(void);
int third_rule(void);

// Primera regla de derivación
int first_rule(void) {
if (token=='x') {
i+=1;
token=cadena[i];
return (1);
}
else if (token == '(')
if (second_rule()) {
if (token == ')') return (1);
else return (0);
}
else return (0);
else return (0);
}

// Segunda regla de derivación
int second_rule(void) {
i+=1;
token=cadena[i];
if (first_rule())
if (third_rule()) return (1);
else return (0);
else return(0);
}

// Tercera regla de derivación
int third_rule(void) {
while (token == '+') {
i+=1;
token = cadena[i];
if (!a()) return(0);
}
return (1);
}

// Método principal
int main(void) {
printf("Introduzca la cadena a reconocer \n");
printf("=>");
scanf("%s",cadena);
token=cadena[0];
if (first_rule()) printf("\nCadena Reconocida");
else printf("\nCadena No Reconocida");
getch();
}

La gramática en su tercera regla de derivación hace que sea recursiva debido a que puede salir (x+x+x+x+x x+x+x+x, etc..

En este caso, mi pregunta es: ¿Cómo puedo utilizar listas para la gramática? y ¿cuál sería su función?

Imagen de paranoid_android

Dividiendo la logica

Abría que re diseñarlo un poco para pensar en Programación orientada a objetos.
Como el que sugirió Oscar Rys, podrías cortar los tokens y después evaluarlos.

 
Aqui hay un ejemplo que puedes seguir para dividir esta cadena con la clase StringTokenizer

Ya dividiendo los tokens lo que queda es evaluarlos
 

Gracias paranoid_android,

Gracias paranoid_android, para ser sincero me estoy bloqueando un poco y pienso volver a hacer todo y plantearlo de otra manera quizás. Por si alguien me puede dar una mano voy a dejar escrito lo que me estpan pidiendo:

Dada una cadena ingresada, se pide validar si esta pertenece a la gramática propuesta, donde se deberá definir los símbolos no terminales, terminales, axioma principal y reglas de derivación.

Para lo cual se debe realizar lo siguiente:

Proponer una gramática.
Plantear la solución del problema realizando un diagrama de flujo o pseudocódigo, indicando los métodos que intervendrán y las estructuras de datos a implementar

Gracias de antemano.

¿Cómo puedo almacenar los

¿Cómo puedo almacenar los caracteres que leo de una cadena ingresada en una lista? y ¿cómo añado las reglas de derivación y verifico si cumple?

A) con el método "add" de la

A) con el método "add" de la lista:
 

B) Pues validas primero una regla y luego otra.
 

Dependiendo de la seriedad que busques en tu programa puedes o no utilizar una herramienta que lea una gramática y genere el analizador por tí. ANTLR es el más popular y es muy completo.

Si quieres entender como crear este tipo de programas te recomiendo ampliamente el libro Language Implementation Patterns