miércoles, noviembre 10, 2010

Gramática de Lenguaje con Acciones Semánticas en ANTLR

La siguiente gramática en AntLR permite reconocer un pequeño lenguaje de programación que implementa desde el punto de vista léxico, números (enteros o reales positivos), variables y cadenas de caracteres.

Desde el punto de vista sintáctico, los programas se ven como una lista de instrucciones que, a su vez, pueden ser del tipo asignación, escritura, condicional, iterativa, de incremento o de decremento. La asignación de variables se hace sobre expresiones algebraicas que permiten el uso de variables, números, sumas, restas, multiplicaciones, divisiones y potencias, al igual que subexpresiones entre paréntesis.

Desde el punto de vista semántico, esta gramática traduce el texto recibido en un conjunto de instrucciones para ser ejecutado por una máquina virtual.

@header{
 package analizadores;
 import java.util.Vector;
 import java.util.HashSet;
}
@lexer::header{
 package analizadores;
}


// FUNCIONES PROPIAS DEL LENGUAJE
@members {
 Vector< String > vectorSalida=new Vector< String >();
 HashSet< String > variablesInicializadas=new HashSet< String >();
 
 public void escribir(String mensaje) {
  vectorSalida.add(mensaje);
 }
 public String getSalida() {
  String salida="";
  for(String x: vectorSalida) {
   salida+=(x+"\n");
  }
  return salida;
 }
 String errores="";
 public void emitErrorMessage(String mensaje) {
  errores+=(mensaje+"\n");
 }
 public String getErrores() { return errores; }
}

// REGLAS GRAMATICALES O SINTACTICAS
programa    : instruccion+ { System.out.println(getSalida()); };

instruccion   : v=VARIABLE '=' expresion ';'   { escribir("store \t"+$v.text); variablesInicializadas.add($v.text); } 
      | WRITE elemento (',' elemento)* ';' { escribir("writeln"); }
      |  condicional
      | iterativa
      | incremento
      | decremento
      ;
      
condicional   : IF '(' condicion ')' { int linea1 = vectorSalida.size(); escribir("jeq"); }
         bloque      { int linea2 = vectorSalida.size(); escribir("jump"); }
                { vectorSalida.set(linea1, "jeq\t" + (linea2+2)) ; }
         ( ELSE bloque )?  { vectorSalida.set(linea2, "jump\t" + (vectorSalida.size()+1)); }
      ;
      
iterativa   : WHILE       { int linea1 = vectorSalida.size(); }
        '('condicion ')'   { int linea2 = vectorSalida.size(); escribir("jeq"); }
        bloque      { escribir("jump\t"+ (linea1+1)); vectorSalida.set(linea2, "jeq\t"+(vectorSalida.size()+1));}
      ;
      
bloque    : instruccion 
      | '{' instruccion* '}'
      ;      
      
elemento    : expresion { escribir("write"); }
      | s=STRING  { escribir("write\t"+ $s.text); }
      ;      
      
expresion   : termino ( '+' termino {escribir("add");}
                             | '-' termino {escribir("sub");})* 
                  ;
                                  
termino    : factor ( '*' factor  {escribir("mul");}
          | '/' factor  {escribir("div");})* 
          ;
          
factor    : valor ( '^' valor {escribir("exp");} )*
      ;          
          
valor     : a=NUMERO      { escribir("push \t"+ $a.text); }
      | v=VARIABLE     { if(variablesInicializadas.contains($v.text)) escribir("push \t"+ $v.text); 
                 else emitErrorMessage($v.line+", "+$v.getCharPositionInLine()+": Variable no inicializada: " + $v.text);}
      | '(' expresion ')'
      ;

condicion   : expresion ( '>=' expresion { escribir("ge"); }
           | '<=' expresion { escribir("le"); }
           | '>'  expresion  { escribir("gt"); }
           | '<'  expresion  { escribir("lt"); }
           | '==' expresion  { escribir("eq"); }
           | '!=' expresion  { escribir("ne"); }
           ) ;

incremento   : v=VARIABLE '++' ';' {escribir("inc\t"+$v.text); } ;
decremento   : v=VARIABLE '--' ';' {escribir("dec\t"+$v.text); } ;

// REGLAS LEXICAS
fragment DIGITO : '0'..'9';
fragment LETRA  : 'a'..'z'|'A'..'Z';
NUMERO    : DIGITO+ '.'? DIGITO* ;
WRITE     : 'write'|'escriba'|'imprima'|'print';
IF      : 'if'|'si';
ELSE     : 'sino'|'else';
WHILE     : 'while'|'mientras'|'mientras que';
VARIABLE    : LETRA ( LETRA|DIGITO)* ;
ESPACIO    : (' '|'\t'|'\r'|'\n')  { skip(); } ;

COMMENT    :   '//' ~('\n'|'\r')* '\r'? '\n'      {$channel=HIDDEN;}
         |   '/*' ( options {greedy=false;} :  . )* '*/' {$channel=HIDDEN;}
         ;

STRING    :  '"' ( ESC_SEQ | ~('\\'|'"') )* '"'  ;

fragment ESC_SEQ :  '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
      |   UNICODE_ESC
      |   OCTAL_ESC
      ;
fragment UNICODE_ESC
      : '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
      ;
fragment HEX_DIGIT: ('0'..'9'|'a'..'f'|'A'..'F') ;
fragment OCTAL_ESC: '\\' ('0'..'3') ('0'..'7') ('0'..'7')
      |  '\\' ('0'..'7') ('0'..'7')
      |   '\\' ('0'..'7')
      ;
OTROCARACTER  : .        { System.out.println("error"); } ;

En una próxima entrada se estará publicando el cógido en AntLR también de la máquina virtual y las instrucciones para compilar, ejecutar y probar el lenguaje.

6 comentarios:

  1. Jefferson ramirez giraldo9:39 a.m.

    Profesor la verdad es que el codigo no nos esta corriendo en ANTLR ayer estuvimos reunidos unos compañeros dandole a el trabajo y la verdad no pudimos hacer que corriera hoy de nuevo nos reuniremos y queriamos saber si suted tiene clase en la noche para que nos pueda colaborar con esto.. puesto que no hemos podido realizar el taller no por falta de ganas sino quisas por falta de entendimiento le agradesco su atencion.

    ResponderBorrar
  2. Anónimo10:47 a.m.

    ola pz io pasaba x aqi y no hay nada d lo q io qria asi q nos vemos y un gusto XP

    ResponderBorrar
  3. Anónimo2:03 p.m.

    GAZZZZ ESTO NO SIVE PARA NADA JMMM .l.

    ResponderBorrar
  4. Anónimo7:26 p.m.

    GENIO! Sos un groso

    ResponderBorrar
  5. what is "fragment"? when do you use it and when do you not?

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...