style="display:inline-block;width:728px;height:90px"
data-ad-client="ca-pub-5164839828746352"
data-ad-slot="7563230308">

AYUDA SOBRE COMO EMPEZAR UN COMPILADOR?

Hola a todos!!...estoy en un problema, me han encargado hacer un compilador en java, he leido como funciona un compilador y todo eso teoricamente, mas sin embargo no tengo idea de como empezar a programarlo, por el momento me han encargado:

***Crear un alfabeto(valido).
***Crear palabras reservadas(10).
***Crear una interfaz para poder trabajar.
***Crear dos reglas de sintaxis.
***Compilar

Espero y me puedan orientar un poco, de antemano se los agradezco!!

Comentarios

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.

Supongo que esto lo necesitas

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:

10100101

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.

// "Compilador" hyper-simplista.

class Oi {
    // alfabeto:
    char _0 = '0';
    char _1 = '1';

    // palabras reservadas
    String _1010 = "1010";
    String _0101 = "0101";

   
    // reglas
    public boolean reglaUno( String codigo ) {
        // La regla es:
        //1010 debe de ir seguido de elementos del alfabeto

        // Si no empieza con 1010 no cumple la regla.
        if(! codigo.startsWith(_1010) ) {
            return false;
        }
        // Si comienza con 1010, revisar el resto de la cadena
        boolean valido = false;
        for( char c : codigo.substring( _1010.length() ).toCharArray() ) {
            // si alguno de ellos no es 0 o 1 no es valido
            valido =  c == _0 || c == _1 ;
        }
        return valido;
    }
    public boolean reglaDos( String codigo ) {
        // 0101 debe de ir precedido por elementos del alfabeto.
        // si no termina en 0101
        if( !codigo.endsWith( _0101 ) ) {
            // no cumple la regla
            return false;
        }
        // Si termina en 0101 hay que revisar que vaya precedido por 0 o 1's
        boolean valido = false;
        for( char c : codigo.substring( 0, _0101.length()).toCharArray() ) {
            valido = ( c == _0 || c == _1 ); // si no es 0 o 1 no es valido
        }
        // si la cumplio
        return valido;
    }

    // programa principal
    public static void main( String ... args ) {
        String codigo = args[0];
        Oi oi = new Oi();
       
        String resultado = "";

        // revisar las reglas
        if( oi.reglaUno( codigo ) ) {
            resultado = "Hola ";
        }
        if( oi.reglaDos( codigo ) ) {
            resultado += ", mundo!";
        }

        // generar el resultado
        if( resultado == "" ) {
            System.out.println( "Error de sintaxis: " + codigo );
        } else {
            System.out.println( resultado );
        }
    }
}

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

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.

class Oi2 {
    public static void main( String ... args ) {
        String c = args[0];
        if(c.matches("1010[01]+|[01]+0101")){
            String s = c.startsWith( "1010" ) ? "Hello" : "";
            s += c.endsWith("0101") ? ", world!" : "";
            System.out.println( s );
        }else{
            System.out.println("Error de sintaxis " + c);
        }
    }
}

( 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 :)

Imagen de Jose_Gastelum

tengo el lexico

:P ya me lo machaque haa voy por el sintactico --- si gustas aqui esta mi msn

jose_gastelum@live.com.m

Imagen de IRr3v3rsible

Referencia

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.

Imagen de IRr3v3rsible

Muy buena aportacion.

-->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)

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:if reglaA() && reglaB(), 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:

variable : tipo ;

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

variable ::= identificador ':'  identificador ';'  ;

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.

identificador= letra letra*;

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

Y que es una letra?

letra = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z';

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:

Token {
  type
  name
}

Parser {
   validaReglaDeDeclaracionDeVariable()  {
     // se pone la regla tal cual:
    verQueElTokenSea( IDENTIFICADOR )
    verQueElTokenSea( DOSPUNTOS       )
    verQueElTokenSea( IDENTIFICADOR  )
    verQueElTokenSea( PUNTOYCOMA     )
 }
  verQueElTokenSea( detipo ) {
     token = Tokenizer.nextToken()
     token.type != deTipo ?  ErrorDeSintaxis("Se esperaba un " + deTipo )
  }    
}

Tokenizer {
   nextToken() : Token  {
      esLetra? Token( leeIdentificador() )
      esDosPuntos ?  Token(":")
      esPuntoYComa ? Token( ";")
    }
}

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:

import java.util.List;
import java.util.Arrays;

class Token {
   // tipos de token
   static final int EOF = -1;
   static final int IDENTIFICADOR = 0;
   static final int COLON   = 1;
   static final int SEMICOLON  = 2;  
   
   // devuelve la descripcion del token:
   static String toString( int id ) {
       switch( id ) {
           case EOF : return "EOF";
           case IDENTIFICADOR : return "IDENTIFICADOR";
           case COLON : return ":";
           case SEMICOLON : return ";";
           default: return "";
       }

   }
 
   // Un token tiene un tipo y un valor
   int type;
   String value;
   // constructor
   Token( int type  ) {
       this( type, toString(type));
   }
   Token( int type, String value ) {
       this.type = type;
       this.value = value;
   }
   public String toString() {
       return "<"+toString(this.type)+","+value+">";
   }
}
// Toma una entrada y la parte en tokens
class Tokenizer {
    String input;
    Tokenizer( String input ) {
        this.input = input;
    }

    int index = 0;
    List<Character> letras = Arrays.asList(
             'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h' , 'i' ,
              'j' , 'k' , 'l' , 'm' , 'n' , 'o' , 'p' , 'q' , 'r' ,
              's' , 't' , 'u' , 'v' , 'w' , 'x' , 'y' , 'z');

    // devuelve el siguiente token en la entrada
    Token nextToken() {
        while( index < input.length() ) {
            char c = input.charAt( index );
            switch( c ) {
                case ':': consumir();return new Token(Token.COLON);
                case ';': consumir();return new Token(Token.SEMICOLON);
                default: if( letras.contains(c)  ) {
                    return identificador();
                } else {
                    throw new ErrorDeSintaxis("Caracter inválido: " + c );
                }
            }
        }
        return new Token(Token.EOF);
    }
    // avanza el indice
    private void consumir() {
        index++;
    }
    // Devuelve un token de tipo identificador
    private Token identificador() {
        StringBuilder sb = new StringBuilder();
        char c;
        while(  index < input.length() && letras.contains( ( c = input.charAt( index )))) {  
            consumir();
            sb.append( c );
        }
        return  new Token( Token.IDENTIFICADOR, sb.toString() );
    }
}

// Valida que la regla se cumpla

class Parser {
   Tokenizer tokenizer;
   Parser( Tokenizer tokenizer ) {
       this.tokenizer = tokenizer;
   }

   // valida la regla de la variable
   void reglaVariable() {
        match( Token.IDENTIFICADOR );
        match( Token.COLON);
        match( Token.IDENTIFICADOR );
        match( Token.SEMICOLON);
        match( Token.EOF);
    }
    // comprueba que el siguiente token sea del tipo esperado.
   void match( int tokenType ) {
       Token t = tokenizer.nextToken();
       //System.out.println( t );
       if( t.type != tokenType ) {
           throw new ErrorDeSintaxis(" Se esperaba un " + Token.toString( tokenType ));
       }
   }
   // prueba el progaam
   public static void main( String ... args ) {
       Parser parser = new Parser( new Tokenizer( args[0] ));
       parser.reglaVariable();
   }
}

class ErrorDeSintaxis extends RuntimeException {
    ErrorDeSintaxis( String mensaje ) {
        super( mensaje );
    }
}

Solo que es más largo, pero funciona:

C:\>java Parser "Hola"
Exception in thread "main" ErrorDeSintaxis: Caracter invßlido: H
        at Tokenizer.nextToken(Rule.java:55)
        at Parser.match(Rule.java:88)
        at Parser.reglaVariable(Rule.java:81)
        at Parser.main(Rule.java:96)

C:\>java Parser "hola"
Exception in thread "main" ErrorDeSintaxis:  Se esperaba un :
        at Parser.match(Rule.java:91)
        at Parser.reglaVariable(Rule.java:82)
        at Parser.main(Rule.java:96)

C:\>java Parser "hola:"
Exception in thread "main" ErrorDeSintaxis:  Se esperaba un IDENTIFICADOR
        at Parser.match(Rule.java:91)
        at Parser.reglaVariable(Rule.java:83)
        at Parser.main(Rule.java:96)

C:\>java Parser "hola:Mundo"
Exception in thread "main" ErrorDeSintaxis: Caracter invßlido: M
        at Tokenizer.nextToken(Rule.java:55)
        at Parser.match(Rule.java:88)
        at Parser.reglaVariable(Rule.java:83)
        at Parser.main(Rule.java:96)

C:\>java Parser "hola:mundo"
Exception in thread "main" ErrorDeSintaxis:  Se esperaba un ;
        at Parser.match(Rule.java:91)
        at Parser.reglaVariable(Rule.java:84)
        at Parser.main(Rule.java:96)

C:\>java Parser "hola:mundo;"
C:\>

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.

Imagen de IRr3v3rsible

Duda!??

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

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:

java Parser "hola:mundo;"

O "invalido" en

java Parser "invalido"

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 )

Imagen de CybJer

Respecto al pattern y matcher

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

import java.util.regex.*;

public class ExpresioReg {

    public static void main(String args[]) {
        //expresion regular
        Pattern patron = Pattern.compile("([a-z])+:{1}([a-z])+;{1}");
        Matcher compara = patron.matcher(args[0]);
        if (compara.matches())//Se compara tu cadena contra el patron y define si cumple o no con el
            System.out.println("Valida");
        else
            System.out.println ("invalida");
}

}

@Cyber, yeap, es

@Cyber, yeap, es precisamente lo que digo aquí: http://www.javamexico.org/blogs/irr3v3rsible/ayuda_sobre_como_empezar_un...

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.

https://github.com/cletus/jmd/blob/master/src/main/java/com/cforcoding/j...

Imagen de ezamudio

abreviaciones

CybJer, te sobran dos tres cosas. Puede ser simplemente [a-z]+:[a-z]+;. 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.

Imagen de CybJer

Tienes razón solo lei algunos

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.

Imagen de CybJer

Ok lo tomare en cuenta, asi

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

Imagen de ezamudio

paréntesis en regex

Los paréntesis en regex son para grupos de captura y agrupaciones. Por ejemplo si quieres definir en vez de solamente cadenas tipo a:b; que se pudiera a:b:c:d:e; pondrías algo como ([a-z]+:)+[a-z]+;

Imagen de paula91

espero que me ayuden

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

Imagen de Jose Manuel

Crea un tema nuevo y

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.

style="display:inline-block;width:728px;height:90px"
data-ad-client="ca-pub-5164839828746352"
data-ad-slot="7563230308">