lunes, noviembre 22, 2010

Máquina Virtual con AntLR

A continuación se presenta una primera versión de una máquina virtual escrita en ANTLR que reconoce un lenguaje con las siguientes posibles instrucciones: ADD, SUB, MUL, DIV, EXP, AND, OR, PUSH, STORE, WRITE, WRITELN, GOTO y JZERO:

grammar maquinavirtual;

@header {
 import java.util.Vector;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Stack;
}
@members{
 enum TipoInstruccion { vPUSH, cPUSH, STORE, ADD, SUB, MUL, DIV, EXP, AND, OR, cWRITE, WRITE, vWRITE, WRITELN, GOTO, JZERO }
 class Instruccion{
  TipoInstruccion tipo;
  int     operador;
  Instruccion(TipoInstruccion t, int o) { tipo = t; operador = o; }
  Instruccion(TipoInstruccion t)   { this(t,-1); }
 }
 
 Vector<Instruccion> tablaPrograma  = new Vector<Instruccion>();
 Vector<String>   tablaCadenas   = new Vector<String>();
 Vector<Double>   tablaConstantes = new Vector<Double>();
 Vector<String>   tablaVariables  = new Vector<String>();
 Stack<Double>   pila     = new Stack<Double>();
 Map<String,Double> memoria    = new HashMap<String,Double>();
 
 public void agregar(TipoInstruccion t) { tablaPrograma.add(new Instruccion(t)); }
 public void agregarStore(String var) {
  if(!tablaVariables.contains(var)) tablaVariables.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.STORE, tablaVariables.indexOf(var)));
 }
 public void agregarVPush(String var) {
  if(!tablaVariables.contains(var)) tablaVariables.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.vPUSH, tablaVariables.indexOf(var)));
 }
 public void agregarcPush(String val) {
  double num = Double.parseDouble(val);
  if(!tablaConstantes.contains(num)) tablaConstantes.add(num);
  tablaPrograma.add(new Instruccion(TipoInstruccion.cPUSH, tablaConstantes.indexOf(num)));
 }
 public void agregarWrite(String var) {
  var=var.substring(1,var.length()-1);
  if(!tablaCadenas.contains(var)) tablaCadenas.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.cWRITE, tablaCadenas.indexOf(var)));
 }
 public void agregarGoto(String val) {
  int num = (int) Double.parseDouble(val);
  tablaPrograma.add(new Instruccion(TipoInstruccion.GOTO, num));
 }
 public void agregarJZero(String val) {
  int num = (int) Double.parseDouble(val);
  tablaPrograma.add(new Instruccion(TipoInstruccion.JZERO, num));
 }
 public void ejecutar() {
  double a, b;
  for(int i=0; i<tablaPrograma.size(); i++) {
   Instruccion ins = tablaPrograma.get(i);
   switch(ins.tipo) {
    case ADD: b=pila.pop(); a=pila.pop(); pila.push(a+b); break;
    case SUB: b=pila.pop(); a=pila.pop(); pila.push(a-b); break;
    case DIV: b=pila.pop(); a=pila.pop(); pila.push(a*b); break;
    case MUL: b=pila.pop(); a=pila.pop(); pila.push(a/b); break;
    case EXP: b=pila.pop(); a=pila.pop(); pila.push(Math.pow(a,b)); break;
    case AND: b=pila.pop(); a=pila.pop(); pila.push(a==1.0 && b==1.0 ? 1.0: 0.0); break;
    case OR:  b=pila.pop(); a=pila.pop(); pila.push(a==1.0 || b==1.0 ? 1.0: 0.0); break;
    case WRITE:  System.out.print(pila.pop()); break;
    case WRITELN: System.out.println(); break;
    case cWRITE: System.out.print(tablaCadenas.get(ins.operador)); break;
    case cPUSH: pila.push(tablaConstantes.get(ins.operador)); break;
    case vPUSH: pila.push(memoria.get(tablaVariables.get(ins.operador))); break;
    case STORE: memoria.put(tablaVariables.get(ins.operador), pila.pop()); break;
    case GOTO: i=(int) ins.operador-2; break;
    case JZERO: if(pila.pop()==0) i=(int) ins.operador-2; break;
   }
  }
 }
}

programa  : instruccion+  { ejecutar(); } ;

instruccion : 'push' VARIABLE { agregarVPush($VARIABLE.text); }
    | 'push' NUMERO { agregarcPush($NUMERO.text); }
    | 'store' VARIABLE { agregarStore($VARIABLE.text); }
    | 'add'     { agregar(TipoInstruccion.ADD);}
    | 'sub'     { agregar(TipoInstruccion.SUB);}
    | 'mul'     { agregar(TipoInstruccion.MUL);}
    | 'div'     { agregar(TipoInstruccion.DIV);}
    | 'exp'     { agregar(TipoInstruccion.EXP);}
    | 'and'     { agregar(TipoInstruccion.AND);}
    | 'or'     { agregar(TipoInstruccion.OR);}
    | 'write' CADENA { agregarWrite($CADENA.text); }
    | 'write'    { agregar(TipoInstruccion.WRITE); }
    | 'writeln'  { agregar(TipoInstruccion.WRITELN); }
    | 'goto' NUMERO { agregarGoto($NUMERO.text); }
    | 'jzero' NUMERO { agregarJZero($NUMERO.text); }
    ;
    
fragment DIGITO : '0'..'9';
fragment LETRA  : 'a'..'z'|'A'..'Z';
NUMERO    :  DIGITO+('.' DIGITO+)?;
VARIABLE    : LETRA ( LETRA|DIGITO)*;
CADENA    : '"'.*'"';
ESPACIO    : (' '|'\t'|'\n'|'\r') { skip(); } ;
RESTO     : . ;      

Puede probar la máquina virtual desde AntLR con el siguiente programa de prueba:
push 4
store  a
push 3
store b
push a
push b
add
write
writeln
write "El fin"

1 comentario:

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