AYUDA SOBRE COMO EMPEZAR UN COMPILADOR?

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

Supongo que esto lo necesitas para la escuela, correcto?

Si es así, si estás en un problema. Lo que te pudiera decir quizá solo te confunda y/o no te sirva y/o sea lo que ya leíste anteriormente.

Básicamente:

1) Un alfabeto es el conjunto de símbolos que vas a usar en tu lenguaje, por ejemplo podrías elegir que tu alfabeto fuera 0 y 1 :) Sería muy chiquito y seguiría siendo válido.

2) Palabras reservadas, pueden ser las que quieras, basta que se construyan con los elementos de tu alfabeto. En el ejemplo anterior ( muy malo ) puedes definir que tus palabras reservadas sean "1010" y "0101" ... no requieren tener sentido, son arbitrarias, pero si lo tienen es mucho mejor.

3) Paso. No entiendo muy bien a que te refieres, pero supongo que será algo como un IDE... esto a veces va de la mano. Pregunta: ¿Que es lo que TU entiendes por esto?

4) Una regla de sintaxis te dice como es válido que los elementos de tu lenguaje se usen. Entonces basta con que crees dos. En el ejemplo anterior ( muy malo ) puedes decir que la palabra reservada 1010 siempre debe de ir seguida de uno o varios elementos del alfabeto y que la palabra reservada 0101 debe de ir antecedida por uno o varios elementos del alfabeto

Validar estas dos reglas debe de ser trivial.

5) Compilar es básicamente traducir o "juntar" estos elementos en otro lenguaje, generalmente en ensamblador o a otro lenguaje?

Por ejemplo, podrías traducir tu regla uno ( 1010 seguido de elementos del alfabeto ) como "Hola" y podrías traducir la regla dos ( 0101 seguido de elementos del alfabeto ) como ", mundo!"

Así que:

Resulta en "Mundo hola"

¿Como hacer esto?

Como harías cualquier otro programa en Java, pero si quieres algo más robusto, rápido, serio y en forma, la estructura general o pipeline de una "aplicación de lenguaje" como esta, sería: Tokenizer -> Parser -> AST -> Generador/Interprete -> OBJ.

Donde el:

Tokenizer .- Te ayuda a reconocer partes del lenguaje según tus reglas.
Parser .- Te ayuda a ver si esas partes que reconociste son váildas.
AST .- ( Arbol de sintaxis abstracto o Abstract syntax tree en inglés ) Te ayuda a que si necesitas re-pasar tu código fuente, no tengas que ejecutar los dos pasos anteriores innecesariamente.
Generador .- Traduce tu AST a el lenguaje objetivo.
OBJ -> el lenguaje objetivo ( ensamblador o algún otro )

Oooo, puedes hacerlo de manera intuitiva, por ejemplo lo siguiente es válido.

Este es un ejemplo trivial, pero funciona. Que el lenguaje en sí mismo sea inútil ya es otra cosa.

Acá la salida:

Importante Hacer un compilador de esta forma es muy poco recomendable. El problema radica en que es inflexible, difícil de crecer y se vuelve cada vez más complejo conforme el alfabeto y las reglas crecen. Lo mejor es hacer el pipeline que te mencione anteriormente: tokenizer -> parser -> ast -> code

La única ventaja ( si se le puede llamar ) es que es muy fácil de programar y puede servir hasta cierto punto con cosas simples. Yo mismo estoy haciendo algo con una estructura así.

Si tienes más interés en el tema y quieres aprender de una forma sencilla, como funciona el pipeline ese y puedes invertir algunos cientos de pesos te recomiendo este libro:

Language implementation patterns escrito por Terence Parr, quién es también autor de la herramienta ANTRL, que sirve para generar tokenizer y parsers en forma automática.

Suerte.

Por cierto.

Todo el choro que puse ahí en mi programa de ejemplo es para hacerlo un "tanto formal" ( definir las reglas, el alfabeto etc ) la siguiente implementación del lenguaje Oi es equivalente.

( Salvo que dice Hello, world! en vez de "Hola , mundo" )

La razón por la que lo menciono, es que, hay que usar las mejores herramientas para el trabajo. En el caso del ejemplo, una expresion regular, en la vida real, un generador de compiladores como ANTRL :)

Gracias Sr. Negativo, ya lo habia visto, a decir verdad lo tome como referencia para estudiar algunos conceptos que ahi se comentan, ademas de ver algunos comentarios de personas que para mi son como "Monstrous de la programacion" y que de ahi se aprende mucho.

-->Si es verdad es un trabajo para la escuela...mmm ps hasta el momento mas que confundir me ha ayudado, OscarRys. Detallando:

*El primer y segundo punto me quedaron claros gracias a tu explicacion.

*En el punto 3) exactamente me referia a la IDE en la que funcionara mi compilador, que iconos tendra, botones, el espacio para codificar, menus, submenus, en fin todo eso.

*En el 4) Creo que ejemplo fue sencillo pero efectivo, mas sin embargo a que te refieres con TRIVIAL?...Por ejemplo como hacer para que en cada linea de codigo al finalizar la instruccion se deba colocar un punto y coma (;) o que al poner comentarios se use en vez de // o /* */ se use algo como esto -->

*En el 5) Entonces la compilacion va de acuerdo a las reglas? Tenemos que traducir primero ya con las palabras reservadas, reglas y despues lo que se codifique a lenguaje ensamblador?

"La estructura general o pipeline de una "aplicación de lenguaje" como esta, sería: Tokenizer -> Parser -> AST -> Generador/Interprete -> OBJ."
Para ello tengo que usar otros lenguajes de programacion por separado? o puedo hacerlo en Java, o es ahi donde entra lo de LEX y YACC.

Si entiendo que la complejidad del compilador aumenta en cuanto a las reglas de sintaxis, tipos y estructuras de datos que se manejen, pero de todas formas me agrado tu codigo aunque sea ilustrativo.

En la segunda implementacion me doy cuenta que es literalmente mas " sencillo" y te da el mismo resultado. De nuevo gracias OscarRys

-->Jose_Gastelum gracias lo tomare en cuenta y te contactare para aclarar un poco mi problema.

Ahí va un pared de código.

3) Es lo que pensé, pero mejor tenerlo claro.

Me parece que intentar hacer el compilador y el IDE al mismo tiempo es mucho más difícil que hacerlo por separado. Lo que se puede hacer es mejor crear una interfaz con el compilador para que se pueda hacer una herramienta sobre él.

La graaaaaan mayoría de los IDE's lo que hace es construir algo similar al compilador para el lenguaje, pero en vez de hacer que compile, hacen validación de sintaxis por ejemplo. Es así que, cuando el compilador te dice: "Error de sintaxis blah blah blah" un IDE te pone la linea en rojo.

4) Me refiero que validar dos reglas es trivial. Tan simple como escribir: , validar más reglas ya es más complejo.

Por ejemplo para lo del ";" tu defines una regla de producción diciendo: una declaración de variable va así, así y asá. Luego escribes el código para ver que esa regla se cumpla.

Para validar más reglas, pones tantas reglas de producción como necesites.

Por ejemplo, una regla para la declaración de una variable como esta:

Podría definirse con una notación similar a BNF así:

Y se lee tal cual: una variable es un identificador seguido del caracter ":" seguido un identificador, seguido del caracter ";"

Si te fijas, los dos puntos ( colon en inglés ) y el punto y coma ( semicolon en inglés ) están entre comillas simples. Eso significa que se tomen tal cual.

Luego, queda la pregunta ¿ y que es un identificador ? Hay que definirlo también.

Osea, un identificador es al menos una letra, seguido de cero o más letras.

Y que es una letra?
 

O sea cualquier de la a a la z ( minúscula en este caso ).

Con esto ya definiste de una manera no ambigua tu regla para declarar una variable. Luego hay que escribir el código que la cumpla. Una forma ( la que yo hice ) fue casi a prueba y horror. Otra manera ( la correcta ) es hacer un tokenizer que separe la entrada en tokens ( elementos que definiste arriba ) y un parser, que revise si la regla se cumple:

Algo como el siguiente pseudo-codigo:
 
Es decir se declara un tipo token, luego con un tokenizer se divide la entrada en tokens y luego el parser se encarga de ver que la regla se cumpla ( o sea que los tokens vengan en orden )

El pseudo código que puse se ve como "ahh claro, así pues si funciona", pero el código para hacer esto jalar en Java no es muy distinto:

Solo que es más largo, pero funciona:

Regla cumplida!!

Este micro parser valida el orden de la regla y por ejemplo que la letra "H" ( hache mayúscula) , no está en el alfabeto.

5 No necesariamente. Se deben primero cumplir las reglas, pero eso concluye el análisis sintáctico, aún falta el análisis semántico ( que es lo que le da sentido al lenguaje ) y luego puede haber varias transformaciones, o productos. En un IDE, basta con subrayar en rojo. En un interprete se ejecuta al vuelo, en un traductor, se escribe al lenguaje objetivo, en el compilador, se vincula con otros objetos y se escribe al lenguaje objetivo.

6 No necesariamente, se puede utilizar siempre Java y/o complementarlo con herramientas de Java para hechas para el fin. Por ejemplo ANTRL puede tomar una gramática como la anterior y generar todo el código necesario para el tokenizer y el parser.

La segunda implementación ( usando regexp ) refleja más fielmente la forma en la que yo estoy haciendo Ryz por ahora. Pero eventualmente lo haré como aquí te describo, con un pipeline de tokenizer->parser->IL->OBJCODE.

Bueno pues terminó el horario de comida. Chau!

P.D: Acá está el ejemplo de como está definida ( incompletemente ) la regla para declaración de atributo en Ryz.

Con respecto al ultimo codigo que publicaste, lo compile en JCreator y en la parte de la compilacion esta perfecto, solo que me arroja estos resultados:

--------------------Configuration: --------------------
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
at Parser.main(Com.java:109)

Process completed.

Como puedo obtener la salida, que tu obtienes?...

Has llegado a utilizar el Pattern y el Matcher, en el primero iria todo mi alfabeto?...y en el Matcher hace las comparaciones de acuerdo a nuestra cadena?
...las palabras reservadas van en el Pattern tambien?

Espero y me puedas ayudar!! Gracias de antemano!

Ahhh pues tienes que pasarle algún valor.

No sé como se haga en JCreator pero en la línea comandos simplemente le pasas la cadena que vas a parsear:

Como "hola:mundo;" en:

O "invalido" en
 

Supongo que en el JCreator hay una opción para pasarle argumentos a tu programa.

Esto solamente es para que te des una idea, hacer algo más grande así es bastante problemático. Para eso lo recomendable es que uses una herramienta que escriba el parser por tí como ANTRL ( pero seguro ya lo había mencionado antes )

Respecto al pattern y matcher me parece una manera mas facil de hacer esto, este codigo hace lo mismo que se especifico arriba bueno amenos que mi expresion regular este mal diseñada saludos

@Cyber, yeap, es precisamente lo que digo aquí:

Solo hay que tomar en cuenta que las expresiones regulares son muy limitadas en comparación con un parser, sobre todo al momento de crear la representacion intermedia. Para cosas muy sencillas sirven tremendamente bien. Incluso para cosas que son bastante más complejas.

Por ejemplo el proyecto jmd, que es un "parser" de markdown ( un formato de texto ) está escrito con puras expresiones regulares.

CybJer, te sobran dos tres cosas. Puede ser simplemente  . No necesitas poner el {1} porque eso es el default, una sola ocurrencia. Si pones + es una o más, si pones * es ninguna o más.

OscarRyz Tienes razón solo lei algunos comentarios, sin embargo cabe mencionar que la clase Matcher tiene funciones mas especializadas que el matches de string por ejemplo el group puede evitar mucha talacha.

ezamudio Ok lo tomare en cuenta me imaginaba que los parentesis se podian evitar pero no el {1}, asi se entiende mucho mejor

Los paréntesis en regex son para grupos de captura y agrupaciones. Por ejemplo si quieres definir en vez de solamente cadenas tipo   que se pudiera   pondrías algo como  

disculpen necesit hacer un compilador que lea como minimo 5 palabras reservadas ....tenia pensado hacerlo en java y que leyera c++ pero pues no se si puedan ayudame a como empezar a hacerlo ..no say tan buena programando....please

Crea un tema nuevo y especifica punto por punto cual es el problema a resolver, que ideas tienes y algún pseudo código existente.
Y suerte.