Desarrollando un analizador léxico básico

Hola a todos bueno pues voy a empesar a desarrollar en el transcurso de la noche un compilador.

A lo que pretendo llegar sera a esto:

 
Lo que se trata es simular un compilador.
 

Saludos quien tenga una sugerencia de algun metodo que usar o algo parecido sera agredecido.
Yo seguiré haciéndolo y posteando el avance.

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.
Imagen de JaimeItlzc

Como identificar saltos de linea

Tengo un problema no se como identificar los saltos de linea osea que el TextArea me se divida en lineas.
por ejemplo:
 

Saludos.

Cual textarea?

Cual textarea?

Imagen de JaimeItlzc

TextArea

 
Lo que busco es alguna manera de obtener linea por linea del TextArea.

Obten todo el string y luego

Obten todo el string y luego partelo por retornos de carro:

 

Pero no deberías de mezclar a esa altura la interfaz gráfica .. eso no es lo importante .. estoy escribiendo un poco más sobre esto...

Imagen de Jose Manuel

Jeje yo ando en lo mismo

Que onda Jaime yo ando aca en lo mismo.

Edit: Las tonterias que uno dice cuando tiene 7 tazas de cafe encima...
Perdon por el post sin sentido :S

Pues como que no me quedo muy

Pues como que no me quedo muy claro que es lo que quieres hacer, pero ahí te va un choro.

Un compilador es una "aplicación de lenguaje" y aplicaciones de lenguaje hay muchas, por ejemplo el resaltador de sintaxis en los editores de texto, un debugger, un ofuscador, un interprete, un compilador, un transformador etc.

La graaaan mayoría de estas aplicaciones tienen un esquema similar a:

entrada -> reconocedor -> analizador semantico -> producto -> salida.

A graandes rasgos es eso.

Reconocedor

Dependiendo de la aplicación tienen más detalladas cada parte o menos e incluso algunos ni lo tienen ( y/o cambian de nombre )

Entonces si quieres hacer una aplicación de lenguaje ( como un compilador ) tienes que empezar por reconocer ( lexer + parser ) la entrada.

Se puede hacer de una forma optima, con un tokenizer ( lexer ) o así como lo estás intentando, con if's, pero obvio te va a costar muchísimo más trabajo con if's que con un tokenizer.

Si quieres saber como hacer un tokenizer mínimo lee este otro choro:

La segunda parte del reconocimiento es el parser, que es ver si los tokens que ya leíste cumplen o no tus reglas.

Analizador Semántico

Lo siguiente es ver si lo que reconociste tiene sentido o no, este es el analizador semántico y como vas a recorrer varias veces la entrada, pues entonces almacenas la información en una estructura de datos óptima y para los lenguajes nada mejor que un arbol, estos árboles se llaman "Arboles de Sintaxis Abstractos" ( AST por sus siglas en inglés )

En al analizador semántico se hacen cosas como ver si una variable esta declarada o no, ejemplo:

 

Esto puede ser válido a nivel de sintáxis, pero no tiene sentido porque la variable C no estaba declarada

Interprete o Generador

Al finalizar el analizador semántico puedes tomar el AST e interpretarlo mientras caminas ( usando una pila o un registro por ejemplo ) o bien generar otra representación de tu AST en tu lenguaje objetivo, puede ser código ensamblador, bytecode o otro lenguaje ( por ejemplo GWT traduce Java a JavaScript )

De nuevo esto es a muy grandes rasgos.

Te recomiendo muchisisimo que compres el libro Language Implementation Patterns de Tarence Parr, vale muchísimo la pena y esta fácil fácil de entender y es muy completo.

Otro libro que no es tan recomendable a menos que te sobren $500 pesos es:

Si te sobran, compralo, está muy bueno para tener un "big picture" de lo que se trata pero con como 40 hojas o algo así y no vale mucho la pena.

Por lo pronto yo en mi proyecto no estoy haciendo NADA de esto que te acabo de platicar y me fui por una forma más sencilla al inicio pero que tiene limitantes fuertes y que las tuve en consideración desde el inicio. Es un patrón que se llama Syntax directed translator pero mi objetivo inicial es crear una línea base con la cual luego poder crear todo lo que te acabo de platicar.

Imagen de Jose Manuel

Cafeina --

Ahora que el efecto de la cafeina ya esta pasando te puedo dar un consejo.
Supongo que ya definiste tus tokens y que lo que haces ahorita es desarrollar el lexer.
Para ver si el texto introducido tiene alguna palabra reservada a mi se me ocurrio lo siguiente.
 

Imagen de Jose Manuel

Solo la sintaxis

Oye Oscar ya que Jaime y yo vamos en la misma escuela y hasta en el mismo salón. Te puedo decir que solo nos han pedido que lo único que sea evaluado sea la sintaxis.
Realmente no necesitamos mandarle nada al parser ni Bytecode. Solo hacer establecer los tokens y hacer que el Lexer recoja los lexemas.
Si( en lo personal) me puedes dar algún consejo de como realizar el lexer seria genial.

Mi idea era establecer una sintaxis mas o menos asi
 
Y ya de alli ingeniarmelas para ir evaluando los tokens.
Realmente no nos han pedido crear el parser, en realidad no es un compilador. Todavía no llegamos a esa materia, solo es una especie de introducción.
Saludos!

Imagen de JaimeItlzc

Gracias oscar

Gracias por la explicación. Lo voy a checar y luego te cuento que resultados me dio.

Tu String palabras no esta mal?
Que si quieres hacer eso no deberia ser asi: {"int","float","double","long"}

Saludos.

Como leanse esto:

Como no, leanse esto:

Es una implementación de un analizador léxico para un lenguaje de programación llamado "Oi" cuyo alfabeto es 0 y 1 y con dos palabras reservadas:   y   cuya... bueno mejor leanlo, sino voy a escribir lo mismo.

Aquí está un ejemplo de la salida:

Y nomás para completar, les dejo un diagrama del "big picture" tomado del libro ese de "create your own freaking awesome programming language"

Imagen de Jose Manuel

Amm no, ya lo revise.

Esta bien, lo revise y me sale un resultado correcto.
Creo que ni siquiera necesita estar separado, ya que busca la ocurrencia de la palabra en la cadena.

Saludos

Bueno, yo implemtaría listas, dónde guardaría todas las palabras reservadas, despúes analizaría rapidamente el texto buscando declaraciones de objetos, variables, y todo aquello con lo que pudiese iniciar una linea, estas las guardaría en una nueva lista, y decláro un int que manejará el estado del programa finalmente teniendo todo empezaría a anlizar el texto nuevamente línea por línea hasta y dependiendo del inicio de linea, es decir, si el inicio de linea es un ciclo, una variable u otra palabra reservada, movería el estado del programa.

Los cambios de estado de programa los haría dentro de un ciclo, el cúal se detendrá cuando llégue a un estado final de éxito o un estado de error. El manejo de cambios los haría con un switch, dependiendo del estado dónde se encuentre el programa se hará una comproboación para verificar que la linea sea correcta, ejemplo: sea estado=6(asignado previamente al suceso de inicio de linea sea una variable), corroborar que le proceda un operador, posteriormente corroborar otra variable del mismo tipo que la anterior preceda al operador y finalmente verificar un punto y coma final, si ha sido exitosa la operacion mandar a un estado 0(que significaría esperando otra linea).

Finalemente cuando se llegue a la última linea y si esta es correcta regresar una estado de éxito y listo un compilador funcional.

También sería bueno verificar que llaves y paréntesis se abre y cierran correctmente.

Bueno espero te sea de ayuda y como te habrás imaginado me base en autómatas para una solución rápida y no ocupas nada mas que estructuras de control y estructuras de datos, bueno suerte y que te salga bien tu proyecto para trasnochadores jajaja espero haber sido de ayuda.

Imagen de Jose Manuel

Hasta que el cuerpo aguante :D

Gracias aunque se que el post no es mio, sin embargo tenemos el mismo trabajo. Y hay que aprovechar los consejos jeje.
Voy a ver lo que comento Oscar y lo que has comentado tu FernandoGuerrero, tratare de usar al máximo sus consejos.
Con tu permiso Jaime.
Saludos.

Imagen de JaimeItlzc

Gracias FernandoGuerrero

Gracias por tu colaboración eso mismo estoy haciendo yo.
con este obtengo letra por letra que vaya introduciendo.
 

Jose Manuel

Creo si yo envio este parametro a tu metodo: >int float double long<
Me va decir que es correcto o tal vez me equivoco.

Saludos.

Pregunta.. ¿que es

Pregunta.. ¿que es exactamente lo que necesitan parsear?

Hay algún ejemplo de la entrada?

Imagen de JaimeItlzc

Por ejemplo es que yo digo

Por ejemplo es que yo digo que no es un compilador.

Ejemplo: Sintaxis Correcta
public class Javamexico{
}

Ejemplo: Sintaxis Incorrecta
public class %JavaMexico!*{ //Me tiene que decir que mi clase esta mal
}
}//Me tiene que decir que sobra una llave

O Simplemente "Error!"

por eso digo que no es un compilador. O si? S:

Imagen de JaimeItlzc

Voy a crear

Voy a crear un TextArea le voy a meter esto:
 
Y me tiene que decir Error.

Imagen de Jose Manuel

Ahh osea lo que pasa es que

Ahh osea lo que pasa es que nos pidieron que se evaluaran por lo menos 5 lineas, nada mas, donde cada quien escogería que tipo de instrucciones aceptaría su analizador.
Es por eso que yo te dije, en el comentario de arriba que esa es mi idea de hacerlo.

Y Jaime, lo que pasa es que andaba haciendo pruebas y métodos hace unas horas y en el programa donde uso ese método la cadena que recibe es tratada antes de tal manera que solo llega una palabra, no puede llegarle una cadena con varias palabras.

Pero no tiene que ser con GUI

Pero no tiene que ser con GUI o sí? Digo puede ser desde la línea de comandos.

Imagen de Jose Manuel

Como ves que se nos puso

Como ves que se nos puso "roñosa" la querida profesora, lo quiere con UI. =P

Y es para mañana? je!... :)

Y es para mañana? je!... :) :) Bieeeeen

Ok.

1.- Cual es el problema? R. Hacer un analizador lexico ( efectivamente no es un compilador ) que me diga si un trozo de código esta bien o mal no?
2.- Cual es la entrada? Cual es la salida? Como se identifican las variables? Que métodos tienen que generar?
3.- Cual es el algoritmo? Como lo harían a mano, por ejemplo ¿Por que dicen que   es inválido? Cuales son las reglas?
4.- Codificar... ( neta esto es lo fácil )

Imagen de Jose Manuel

Bueno...

Me gustaría decir que no, que tenemos muuucho tiempo pero....
Ahora que es jueves si, si es para mañana.
Le estamos dando mas credibilidad al buen dicho sobre los mexicanos, que vergüenza...
Ni tanta verdad? sino lo hubiéramos hecho antes :D
Pero es que con presión se trabaja mejor ja ja ja....

Imagen de JaimeItlzc

Si.

Si. Así es pues nos lo pidió con GUI.
D:

Imagen de JaimeItlzc

Asii

Entrada:
 
Compilacion Incorrecta...

Basicamente las reglas las pones tu.

Pues yo creo que deberían de

Pues yo creo que deberían de reducir el alcance a lo mínimo posible por ejemplo si es de 5 lineas que sea algo como:

 

Que se parece por cierto a Scala :P

Imagen de Jose Manuel

En mi caso

1.- Exacto, con que diga si esta bien o mal estaría haciendo su trabajo.
2.- La entrada(de nuevo, en mi caso) es importar una librería y crear una estructura de una clase(public class Clase) típica con un cuerpo de un if en un método. En la salida solo dar un mensaje si es correcta la declaración o no lo es.
El como se identifican las variables, pues pensaba hacerlo lo mas parecido a Java o al menos lo mas parecido que yo pudiera. Los métodos(mi caso) solo seria uno y no necesariamente tendría que ser el principal.

3.-El algoritmo....huh?

Así rápidamente se me ocurre;
 
Hay que "algoritmo" tan feo, bueno osea esa es la idea abstracta, mucho, y las reglas las pondremos nosotros, te decia que yo tratare de usar las de Java hasta donde pueda.
4.- En eso todavia no llego pero ya casi :D

Gracias por la ayuda Oscar.

Imagen de Jose Manuel

Pues creo que lo tendre que

Pues creo que lo tendre que hacer.
Por ejemplo limitar los identificadores a puras letras y los nombres de las clases también.
Meter todo en un StringTokenizer y que obviando los espacios de los que se encarga el StringTokenizer me quedarían las palabras, después irles almacenando en una lista o arreglo.
Y crear métodos basados en las reglas que busquen los tokens en la lista o arreglo e ir evaluándolos.

Exaaacto, pero porque por

Exaaacto, pero porque por linea, mejor sería por espacios de tal forma que:

 

Sea igualmente válido ( se habían preguntado porque Java usaba el ';' )

Esa el la primera parte tokenizar ( oich )

Tienes que terminar con algo como:

 

Esos son los tokens del programa, lo siguiente es ver si cumplen o no con las reglas. Es decir que el class no aparezca antes del import por ejemplo, o que las llaves no aparezcan antes del class etc.

Ahi va ahi va

Si ponen algo como Java se

Si ponen algo como Java se complican la vida porque tienen más palabras reservadas, no? Hay que empezar desde poquito, por ejemplo como puse: var para variables y "def" para metodos.

Si es var no lleva parentesis
Si es def si lleva.

Luego la regla se puede definir así:

 

Ejemplo:

 

Y cada regla lleva un método

Y cada regla lleva un método donde se revisan que se cumpla lo que dice la regla.

Ejemplo

 

Que es básicamente lo mismo no? Es decir, la reglaImportStatement es igual a validar import, validar import id y validar punto y coma.

Para hacer el método valida es algo tipo:

 

De talforma que si antes del 'import' se pone un punto y coma va a tronar.

Para hacer el método "nextToken" nomás hay que regresar el siguiente elemento de la lista que se genera al tokenizer.

Imagen de Jose Manuel

Y que tal?...

Sabes que recordé con el ejemplo del import, las expresiones regulares para validar, pero no se usarlas bien. Crees que nos sirvan para buscar los tokens?

posi.. esa es otra.. por

posi.. esa es otra.. por ejemplo en el del import es:

 

Que se lee:
 

Pero creo que deberías de seguir con lo del tokenizer y el parser, no está nada difícil y por otro lado es mucho muy fácil perderse con las expresiones regulares.

Finalmente aquí está el ejemplo de como validar una declaración de variable tipo:
 

Con salida de "Se esperaba un ; " y toda la cosa.

Ahora sí ya los dejo listos!

El GUI ponganlo hasta el final.

Suerte!

Imagen de Jose Manuel

Ok! Dejamelo a mi :D

Muchas gracias OscarRyz por la ayuda, seguire con los tokenizers y como a eso de las 2 o 3 pm me reporto :P
De nuevo, gracias por tu tiempo y por los consejos.

Analizador léxico en Ryz

Como eventualmente voy a hacer algo como esto, aproveche la oportunidad
para hacer un analizador léxico escrito en Ryz para una gramática
sencilla como esta:

 

Contenido inicial:
 

El contenido de cada archivo:
 

Token.ryz
Un token tiene un tipo y un nombre ( o valor ) y nada más:

 

Tokenizer.ryz

Este tokenizer muy sencillo parte la entrada por espacios y le asigna a cada elemento
un tipo de token segun corresponda. Por ejemplo si el elemento es "class" crea un token
con el id CLASS

Cada elemento de matcheo se debía haber escrito así:

 

Pero como aún no evaluo las expresiones bien, entonces tengo
que declarar variables intermedias.

 

Parser.ryz
El parser es el que tiene las reglas.

Por cada regla intenta hacer un match con el token en el orden que le corresponda.

Si un token no está en el orden adecuado entonces imprime el mensaje
y termina la ejecución ( acá aparece el ID del token, debe de aprecer algo más entendible )

 

Main.ryz
Código main, crea el tokenizer, y el parser y matchea la regla "classRule"

 

Probar

Compilamos
 

Y ejecutamos algunas pruebas
 
 
 
 

Aunque está escrito en Ryz, esté código debería se der fácil de entender ( al menos ese es mi objetivo ) y fácil de pasar a Java.

Saludos!

Imagen de Jose Manuel

Gracias por la base para el

Gracias por la base para el programa Oscar, me voy a poner a tratar de pasarlo a java y ajustarlo a mi programa.
Y si me quieres seguir ayudando cuando lleve un avance o me quede atorado en algo regreso.
Saludos! :D

Imagen de Jose Manuel

Como dar formato...

Estoy intentando obtener de un JTextArea su contenido y asignarlo a una variable. Pero me da saltos de linea.
¿Como puedo hacer que me los de en una sola linea?

Osea si yo en TextArea escribo;
 
Y cuando imprimo para comprobar, obvio me sale con saltos de linea pero yo nesecito que este en una sola linea para poder trabajar con ella, ya es lo unico que me falta :D
Asi deberia ser;
 
¿Como lo hago?
Saludos!

Imagen de Jose Manuel

Se me ocurrio...

Pues en vista de que era muy tarde supongo que no pudieron responderme D:
Se me ocurrio hacer esto
 
De esta manera ya me quedaba el String varNueva con el contenido de lo que se obtuvo del areaTexto y en una sola linea que era lo que queria
Gracias gente bonita!!! :D

Imagen de Jose Manuel

Por fin :D

Bueno solo escribo el post para avisar que ya eh terminado el "analizador léxico" y aunque es muy sencillo y tiene muchas limitaciones/errores sin mencionar que me hice bolas y metí demasiadas cosas innecesarias.
Pero por lo menos hace lo que le pido, no muy bien pero lo hace.

Gracias OscarRyz por tu tiempo, paciencia y consejos. También gracias a FernandoGuerrero que de una parte de lo que aconsejo me surgió una idea que me evito algunos problemas.

Pensaba postear mi programa como un aporte pero esta tan feo y deficiente que no se si ponerlo aquí como una "solución" o que onda.
Gracias de nuevo chicos, y no me despido sin mencionar a Jaime quien es el creador del hilo y que gracias al cual pude participar y preguntar.

Saludos!! ñ_ñ

Te falto, Gracias... totales!

Te falto, Gracias... totales! jejej

Que bien, quizá no necesariamente el código pero si estaría padre un screnshot de la salida :) :)

Saludos.

Imagen de Jose Manuel

Pues claro

Bueno desde pequeño fui acostumbrado a ser agradecido con todos especialmente con aquellos que me ayudaran. Por eso es que escribo mucho el "gracias" pero tampoco quiere decir que es solo costumbre, yo creo en el gracias. Y cuando agradezco es de manera sincera :D

Y pues bueno aqui unas shot del programa, no cubri todos los espacios que puede abarcar el programa por que seria una cantidad de imagenes exagerada, como unas 15 y mejor estas. =P

Uploaded with ImageShack.us

Saludos chic@s!!

Je je estaba bromeando, es

Je je estaba bromeando, es algo que espero que nunca se nos quite a los Mecsicanous ...

Esta padrísmio tu programa.

Vas a decir que "exigente" ( bueno en ralidad otra cosa ) , pero por favor, pon tus llaves que abren en la misma linea y no dejes if's sin llaves:

 

Y no así:

 

Cada vez que lo haces, un flamingo muere!

+1 de nuevo por los screenshots!

Imagen de Jose Manuel

No pueder ser..

Yo siempre las había escrito así D:
Nadie me dijo que era incorrecto o visto como una mala practica u otra cosa, eh visto que la mayoría escribe como tu mencionas pero ya me había acostumbrado a la otra forma.

Con lo de las llaves de los if's lo que pasa es que ya se me cerraban los ojos y se me suspendía el cerebro y tenia el tiempo encima, pero bueno aun así y todos los pretextos malos del mundo no hay razón para no cerrar las instrucciones como dios manda.

Me pregunto...¿Cuantos flamingos habré matado hasta ahora?

Y con tu broma, no es que me haya molestado o me haya sentido ofendido, en realidad me hizo reír(me recordó una película cómica). Di la explicación porque hay veces que hasta a mi me parece raro estar diciendo tanto gracias cuando comparo mi comportamiento con otras personas jeje.

En verdad, aunque hay algunas bromas tuyas que no entiendo, la mayoría me hacen reír, tu si eres chido XD.

Saludos!

Quizá no eran bromas :) No

Quizá no eran bromas :)

No es que esté "maal" en el sentido de que sea peligroso ni nada. Está mal en el sentido del estilo.

Si todos en tu proyecto deciden programar poniendo el punto y coma en la siguiente linea:

Así
 

Pues ni modo, hay que aceptar esa conveción, pero si no hay una convención establecida lo mejor es seguir la "default" que es la que tiene Java ( más o menos como al mencioné ) desde el inicio.

Como noto que estás empezando es un muy buen tiempo de crear bueno hábitos, pero es perfectamente legal.

Esto ayuda a leer mejor el código de otros y le da un estilo de Java.

Es como aprender otro idioma, puedes hablarlo y hablarlo bien pero en el acento se nota quién lo domina y quién es foráneo.

Lo mismo hay que hacer al aprender otros lenguajes de programación, hay que respetar las convenciones existentes, por ejemplo en C# es perectamente aceptable el estilo que ponías.

Esto claro es un tema un tanto subjetivo y solo es mi opinión, hay quién pensará lo contrario.

Pero te imaginas que vieras un código formateado así?

Imagen de Jose Manuel

Quizá...

No pos si, ese código hace que te sangren los ojos pero según el tema el tipo prefería el formato de python y ahora que me fijo mejor en mi código de java se parece al que escribo en python :S
...dios me libre de llegar a esos extremos, aunque para los que están acostumbrados al estilo default de Java ver mi código puede resultarles similar :x

Pero tomare muy enserio tus comentarios para ir forjando y fortaleciendo buenos hábitos de programación.

Por cierto que onda con este tema, ya esta la "solución" al menos la miá solo falta la de Jaime, haber si se anima a poner unas screens de su programa y colocar algo que diga que ya esta terminado o algo así.

Saludos!

Codigo:

Disculpa ami podrias enviarme tu proyecto de analizador Lexico porfavor , te lo agradecere !!

ayuda analizador lexico

Buenas tardes,
Necesito hacer un analizador léxico, sintáctico y semántico de un código que ya poseo de un repositorio. Podrían ayudarme por favor
Gracias