Generación de Código FKScript

Esta entrada forma parte de una serie de artículos dedicados al proyecto FKScript, construcción de un compilador y una máquina virtual para un lenguaje de script con C# y ANTLR, entre los cuales podrás encontrar una descripción detallada de cada módulo, documentación técnica, ejemplos y tutoriales de uso que pueden ser de tu interés. No olvides consultar la página principal de FKScript para más información.

En esta sección abordaremos la última fase del proceso de compilación de nuestro legunaje FKScript, la generación de código. Este paso se encargará de generar el código intermedio FKIL a partir del árbol de sintaxis abstracta generado en la fase de análisis sintáctico y enriquecido durante el análisis semántico.

1. Máquina Virtual FKVM

Antes de comenzar a ver cómo se va a realizar la generación de código para los distintos elementos de nuestro lenguaje debemos comentar algunos detalles acerca de la máquina virtual que va a ejecutar nuestro código y cuya implementación veremos más adelante.

Es importante indicar que nuestra máquina virtual (en adelante VM) estará basada en la pila, en contraposición a máquinas virtuales más clásicas basadas en registros. Con esto queremos decir que todas las operaciones ejecutadas por la VM se realizarán sobre datos que se encuentren con anterioridad en las posiciones superiores de la pila o bien que afectarán de una u otra forma al valor almacenado en la cima de la pila. Una vez ejectada la instrucción la VM se encargará de eliminar automáticamente sus parámetros de la pila si es necesario y de apilar el resultado obtenido si procede según el tipo de instrucción.

Esto se entiende más fácilmente con un ejemplo. Tomemos como muestra la instrucción IADD para realizar la suma de dos enteros. Para realizar esta suma nuestro programa deberá colocar en la cima de la pila sus dos parámetros, bien mediante la carga de un valor inmediato (PUSH) o bien recuperando el dato de alguna variable (LOAD). Una vez apilados los dos parámetros ya se podrá ejecutar la instrucción IADD para realizar la suma, cuyo resultado se almacenará en la cima de la pila tras haber eliminado en primer lugar los dos parámetros. Veámoslo gráficamente:

Ejecución Instrucción IADD

Ejecución Instrucción IADD

2. Primeros pasos

El paso de generación de código se implementará haciendo uso de ANTLR v3, mediante una gramática de tipo tree grammar al igual que la fase anterior, y utilizando la librería StringTemplate para generar los ficheros de salida a partir de plantillas predefinidas.

Empecemos como siempre por ver las opciones del analizador. En este caso, las opciones serán las mismas que las definidas en el analizador semántico más una adicional para indicar que la salida no será un árbol AST sino una plantilla de StringTemplate. Esta última opción se indicará con output=template.

tree grammar FKVMGen;

options {
tokenVocab=FKVM;
ASTLabelType=FkvmAST;
output=template;
language=CSharp;
}

En los siguientes apartados veremos cómo definir con ANTLR+StringTemplate la generación de código para cada uno de los elementos significativos de nuestro leguaje FKScript.

3. Generación de código para literales e identificadores

Vamos a empezar a comentar el proceso de análisis por las expresiones más simples del lenguaje como son los literales y los identificadores.

Veamos en primer lugar un ejemplo de cómo se traduciría a código intermedio una sencilla instrucción de asignación en la que tan sólo interviene un literal entero:

//Código en FKScript
int a; //Variable número 1
a = 3;

#Código traducido a FKIL
ipush 3 #Almacena el valor 3 en la cima de la pila
istore 1 #Almacena la cima de la pila en la variable 1

Como puede observarse, para el literal la única instrucción de código FKIL que se genera es una instrucción de tipo PUSH con su tipo correspondiente, en este caso de tipo entero (IPUSH), seguida del literal correspondiente. La plantilla a definir para la generación de código de un literal entero será por tanto de la siguiente forma:

lit_entero(v) ::= “ipush <v>”

Para el resto de tipos de literales estas plantillas serán análogas, cambiando únicamente el tipo de la instrucción PUSH. Por su parte, en la gramática ANTLR tan sólo deberemos indicar la plantilla correspondiente dependiendo del tipo de literal leído y le pasaremos como argumento el texto del propio literal:

expresion

|literal -> {$literal.st}
;

literal : LIT_ENTERO -> lit_entero(v={$LIT_ENTERO.text})
| LIT_REAL -> lit_real(v={$LIT_REAL.text})
| LIT_CADENA -> lit_cadena(v={$LIT_CADENA.text})
| LIT_LOGICO -> lit_logico(v={$LIT_LOGICO.text})
;

Ampliemos ahora el ejemplo anterior para que también intervenga un identificador en la parte derecha de una asignación y veamos cómo quedaría su traducción a código FKIL:

//Código en FKScript
int a; //Variable número 1
int b; //Variable número 2
a = 3;
b = a;

#Código traducido a FKIL
ipush 3 #Almacena el valor 3 en la cima de la pila
istore 1 #Almacena la cima de la pila en la variable 1
iload 1 #Recupera el valor de la variable 1 a la cima de la pila
istore 2 #Almacena la cima de la pila en la variable 2

El código generado en este caso para la variable “a” en la asignación “b=a” ha sido tan sólo una instrucción de tipo LOAD (en este caso de tipo entero, ILOAD) seguida del número de orden de la variable dentro el programa. La plantilla a definir y la generación de código por tanto será tan sencilla como en el caso de los literales. Veamos en primer lugar la plantilla que hemos definido:

ident(op,nv) ::= <<
<op> <nv>
>>

Vemos que en este caso le pasaremos dos argumentos a la plantilla, el primero de ellos indicando el operador que utilizaremos para recuperar la variable (ILOAD, FLOAD, SLOAD o BLOAD), que dependerá del tipo del identificador, y el segundo que contendrá el número de orden de la variable en el programa. La gramática quedaría de la siguiente forma:

expresion

|IDENT {oper=traducirTipo($IDENT.expType)+”load”;} -> ident(op={oper},nv={$IDENT.symbol.numvar})
|literal -> {$literal.st}
;

Para generar el operador hemos utilizado un método propio llamado traducirTipo() que devolverá el prefijo correcto del operador LOAD dependiendo del tipo del tipo del identificador pasado como parámetro, es decir, para un identificador de tipo entero devolverá “i”, para uno de tipo real devolverá “f” y de forma análoga para el resto de tipos. Por otro lado, el número de la variable lo obtendremos directamente del atributo symbol.numvar del identificador, dato que generamos durante la fase de análisis sintáctico.

4. Generación de código para expresiones aritméticas

Veamos en primer lugar un ejemplo de generación de código para una expresión de este tipo:

//Código en FKScript
int a; //Variable número 1
int b; //Variable número 2
a = 3;
b = a + 5;

#Código traducido a FKIL
ipush 3 #Almacena el valor 3 en la cima de la pila
istore 1 #Almacena la cima de la pila en la variable 1
iload 1 #Recupera el valor de la variable 1 a la cima de la pila
ipush 5 #Almacena el valor 3 en la cima de la pila
iadd #Realiza la suma de los dos valores superiores de la pila
#y almacena el resultado en la cima de la pila.
istore 2 #Almacena la cima de la pila en la variable 2

Como se observa en el ejemplo, para la expresiones aritméticas lo que se hará será generar en primer lugar el código de las subexpresiones, en este caso un identificador (ILOAD 1) y un literal (IPUSH 5) y posteriormente llamar al operador correspondiente según el tipo de expresión (en nuestro caso IADD). El patrón para generar la plantilla parece por tanto claro:

op_aritmetico(op,e1,e2) ::= <<
<e1>
<e2>
<op>
>>

La plantilla recibirá tres argumentos: el operador aritmético a utilizar y el código de las dos subexpresiones de la expresión que estamos generando. En la gramática se seguirá un proceso muy parecido al de los identificadores:

expresion

| ^(opa=opAritmetico e1=expresion e2=expresion)
{oper=traducirTipo($opa.opType)+$opa.st.ToString();}
-> op_aritmetico(op={oper}, e1={$e1.st}, e2={$e2.st})

opAritmetico returns [string opType]
: op=’+’ -> {%{“add”}; $opType=$op.expType;}
| op=’-‘ -> {%{“sub”}; $opType=$op.expType;}
| op=’*’ -> {%{“mul”}; $opType=$op.expType;}
| op=’/’ -> {%{“div”}; $opType=$op.expType;}
;

El prefijo del operador lo obtendremos de la misma forma que para el caso de los identificadores, haciendo uso del método traducirTipo(), y el operador en concreto lo generaremos en la regla opAritmetico, donde también devolveremos el tipo de la expresión (que calculamos durante el análisis semántico) para que sirva como parámetro al método de traducción de tipos.

5. Generación de código para expresiones lógicas

El proceso de generación de código para una expresión lógica no será tan directo como para el resto de elementos que hemos comentado hasta el momento, y para tratar de explicar el por qué empecemos como siempre por ver un ejemplo de traducción de una expresión lógica a código FKIL:

Expresión lógica:  a > 3

#Traducción a FKIL
ipush 1 #Valor por defecto de la expresión = 1 (true)
iload 1 #Se recupera el valor de la variable 1 a la cima de la pila
ipush 3 #Se coloca el valor 3 en la cima de la pila
ncmp #Se comparan los dos valores superiores de la pila
ifgt etiq1 #Si el resultado de la comparación es >0 se salta a “etiq1″
pop #Se desapila el valor por defecto
ipush 0 #Se apila el valor contrario =0 (false)
etiq1: #Etiqueta de salida

Como vemos, la estrategia a seguir para calcular el resultado de este tipo de expresiones será siempre suponiendo que la expresión es verdadera, realizar la comparación, y en caso de ser falsa desapilar el resultado por defecto (true) y apilar el contrario (false).

En este patrón sin embargo hay mucho elementos variables que se deberán tener en cuenta a la hora de definir la plantilla a utilizar para la generación de expresiones lógicas. El primero de ellos es el tipo de comparación. En el ejemplo hemos utilizado el operador ncmp (comparación numérica) debido a que las dos subexpresiones (la variable “a” y el literal “3”) eran de tipo entero. Sin embargo, en el caso de comparaciones de cadenas debería utilizarse el operador scmp y para los valores lógicos el operador bcmp. El segundo parámetro a considerar será el operador utilizado para saltar a la etiqueta de salida. Así, para el operador “>” se utilizará ifgt, para “<” usaríamos iflt y de forma análoga para el resto de operadores lógicos. Por último, un factor importante será el nombre de la etiqueta de salida, ya que debemos asegurarnos de que en el programa resultante no se repita el nombre de ninguna etiqueta.

Teniendo todo esto en cuenta veamos cómo quedaría la gramática y la plantilla para estas expresiones:

@members {
int nEtiqueta = 1;

private string operadorComparacion(String t)
{
string op = “”;

if(t.Equals(“int”) || t.Equals(“float”))
op = “ncmp”;
else if(t.Equals(“string”))
op = “scmp”;
else if(t.Equals(“bool”))
op = “bcmp”;

return op;
}
}

expresion

: ^(opc=opComparacion e1=expresion e2=expresion) {operc = operadorComparacion($opc.opSecType);}
-> op_comparacion(opc={operc}, op={$opc.st}, e1={$e1.st}, e2={$e2.st}, et1={nEtiqueta++})

opComparacion returns [string opSecType]
: op=’==’ -> {%{“ifeq”}; $opSecType=$op.expSecType;}
| op=’!=’ -> {%{“ifne”}; $opSecType=$op.expSecType;}
| op=’>=’ -> {%{“ifge”}; $opSecType=$op.expSecType;}
| op='<=’ -> {%{“ifle”}; $opSecType=$op.expSecType;}
| op=’>’ -> {%{“ifgt”}; $opSecType=$op.expSecType;}
| op='<‘ -> {%{“iflt”}; $opSecType=$op.expSecType;}
;

El primero de los problemas a resolver, la elección del operador de comparación, lo solventamos mediante el método propio operadorComparacion() (definido en la sección @members) al que le pasaremos el tipo de las subexpresiones de la expresión lógica que estamos generando. Este tipo lo almacenamos durante el análisis semántico en el atributo expSecType por lo que sólo tenemos que recuperarlo en la regla opComparacion. El operador IF a utilizar para el salto a la etiqueta de salida también lo decidimos en dicha regla y se asignará directamente dependiendo del tipo de expresión que hayamos leido de nuestro programa. Por ultimo, el nombre de la etiqueta se generará a partir de un secuencial que iremos incrementando durante la ejecución de nuestro analizador acada vez que haga falta generar una etiqueta. Eset secuencial lo declararemos una vez más en la sección @members y en nuestro caso se llamará nEtiqueta. La plantilla por su parte quedaría de la siguiente forma:

op_comparacion(opc,op,e1,e2,et1) ::= <<
ipush 1
<e1>
<e2>
<opc>
<op> etiq<et1>
pop
ipush 0
etiq<et1>:
>>

6. Generación de código para asignaciones

La generación de código para las asignaciones es muy similar al ya visto para los identificadores ya que la única dificultad a salvar será el operador STORE a utilizar para almacenar el valor de la variable, y éste se calculará a partir del tipo de la expresión derecha mediante el método ya comentado traducirTipo().

inst_asig
@init {
string oper = “”;
} : ^(ASIGNACION IDENT expresion) {oper = traducirTipo($ASIGNACION.expType)+”store”;}
-> asignacion(op={oper}, nv={$IDENT.symbol.numvar}, val={$expresion.st});

El número de orden de la variable se recuperará del atributo symbol.numvar que calculamos durante el análisis sintáctico. La plantilla, muy sencilla en este caso, quedaría así:

asignacion(op, nv, val) ::= <<
<val>
<op> <nv>
>>

7. Generación de código para instrucciones condicionales y bucles

Vemos ahora la generación de código para las instrucciones if y while de FKScript. Ninguna de ellas añade ninguna dificultad a las ya comentadas por lo que las trataremos muy brevemente. Veamos en primer lugar un ejemplo de traducción de cada una de ellas:

//Instrucción IF
if(…expresion-logica…)
{
//instrucciones-si
}
else
{
//instrucciones-else
}

#Traducción a FKIL
…expresión-logica…
ifeq etiq1
…instrucciones-si…
goto etiq2
etiq1:
…instrucciones-else…
etiq2:

//Instrucción WHILE
while(…expresion-logica…)
{
//instrucciones-while
}

#Traducción a FKIL
etiq1
…expresion-logica…
ifeq etiq2
…instrucciones-while…
goto etiq1
etiq2:

A partir de estos patrones, las plantillas de StringTemplate a definir son prácticamente directas:

instif(cond,instsi,instelse,et1,et2) ::= <<
<cond>
ifeq etiq<et1>
<instsi>
goto etiq<et2>
etiq<et1>:
<instelse>
etiq<et2>:
>>

instwhile(cond,instrucciones,et1,et2) ::= <<
etiq<et1>
<cond>
ifeq etiq<et2>
<instrucciones>
goto etiq<et1>
etiq<et2>:
>>

La gramática por su parte tampoco añade ninguna particularidad extra a las ya comentadas en apartados anteriores por lo que no nos pararemos demasiado en comentarla:

inst_if : ^(‘if’ expresion isi=lista_instrucciones ielse=lista_instrucciones)
-> instif(cond={$expresion.st},instsi={$isi.st},instelse={$ielse.st},
et1={nEtiqueta++},et2={nEtiqueta++});

inst_while : ^(‘while’ expresion li=lista_instrucciones)
-> instwhile(cond={$expresion.st},instrucciones={$li.st},
et1={nEtiqueta++},et2={nEtiqueta++});

8. Generación de código para el programa principal FKIL

Una vez comentada la generación de código para cada uno de los elementos principales de nuestro lenguaje ya sólo nos queda ver cómo generar la estructura principal del programa. Esto lo haremos en la regla principal de la gramática.

principal[int locales] : ^(‘program’ tipo IDENT li=lista_instrucciones)
-> principal(nom={$IDENT.text}, loc={locales}, instr={$li.st});

Como vemos, esta regla recibirá un parámetro externo llamado locales que contendrá el número de variables locales utilizadas por el programa. Este dato lo usaremos para generar la directiva .locals de FKIL. El parámetro lo deberemos pasar convenientemente desde el programa principal a la hora de llamar al analizador que acabamos de crear. Por lo demás, el único dato adicional necesario será el nombre del programa que lo obtendremos directamente del texto del identificador correspondiente en la regla. La plantilla nos quedaría de la siguiente forma:

principal(nom, loc,instr) ::= <<
.program <nom>
.locals <loc>
<instr>
>>

9. Programa principal

En este punto ya hemos finalizado nuestra gramática y nuestro fichero de plantillas por lo que estamos en condiciones de completar nuestro programa principal para llamar al generador de codigo al final del proceso.

//Análisis léxico semántico
FKVMLexer lexer = new FKVMLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
FKVMParser parser = new FKVMParser(tokens);
parser.TreeAdaptor = adaptor;
FKVMParser.programa_return result = parser.programa();

//Si no hay errores léxicos ni sintácticos ==> Análisis Semántico
if (lexer.numErrors + parser.numErrors == 0)
{
//Analisis Semántico
CommonTree t = ((CommonTree)result.Tree);
CommonTreeNodeStream nodes2 = new CommonTreeNodeStream(t);
nodes2.TokenStream = tokens;
FKVMSem walker2 = new FKVMSem(nodes2);
walker2.programa(parser.symtable);

//Si no hay errores en el análisis semántico ==> Generación de código
if (walker2.numErrors == 0)
{
//Plantillas
TextReader groupFileR = new StreamReader("FkvmIL.stg");
StringTemplateGroup templates = new StringTemplateGroup(groupFileR);
groupFileR.Close();

//Generación de Código
CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
nodes.TokenStream = tokens;
FKVMGen walker = new FKVMGen(nodes);
walker.TemplateLib = templates;
FKVMGen.programa_return r2 = walker.programa(parser.numVars);
}
}

En primer lugar leeremos el fichero de plantillas FkvmIL.stg para generar el objeto templates. Este objeto se pasará como entrada a nuestro analizador a traves del atributo TemplateLib para indicar las plantillas a utilizar durante la generación de código. Por último, no deberemos olvidar pasar como parámetro de entrada el número de variables locales del programa, dato que obtendremos directamente del analizador sintáctico donde como ya comentamos definimos un atributo llamado numVars que contenía precisamente ese dato.

Podéis descargar la gramática ANTLR completa y el fichero de plantillas pulsando aquí.

Esta entrada forma parte de una serie de artículos dedicados al proyecto FKScript, construcción de un compilador y una máquina virtual para un lenguaje de script con C# y ANTLR, entre los cuales podrás encontrar una descripción detallada de cada módulo, documentación técnica, ejemplos y tutoriales de uso que pueden ser de tu interés. No olvides consultar la página principal de FKScript para más información.

Powered by WordPress. Designed by Woo Themes