Este documento y su código fuente asociado están bajo una licencia de Creative Commons.

Dedicaremos esta sección a comentar todos los aspectos prácticos del desarrollo de la etapa de análisis semántico del compilador para nuestro lenguaje FKScript. Veremos en primer lugar las modificaciones necesarias que hay que realizar al árbol AST construido en la fase anterior, posteriormente describiremos el tipo de comprobaciones que se realizarán en esta fase del análisis y por último veremos cómo podemos implementarlas con ANTLR.

Todas las tareas del analizador semántico se realizarán mediante el recorrido de árboles AST, lo que en ANTLR se llama tree grammar. Veremos más adelante cómo implementar un analizador de este tipo con ANTLR v3.

1. Tareas del análisis semántico

Durante la etapa de análisis semántico nuestro compilador realizará una serie de comprobaciones que ya nada tienen que ver con la sintaxis del lenguaje, y que en nuestro caso serán las siguientes:

• Comprobación de la existencia de variables y funciones.
• Cálculo de tipos en expresiones.
• Chequeo de tipos en instrucciones.
• Chequeo de tipos en expresiones.

Iremos enumerando todas esas comprobaciones a medida que vayamos comentando la implementación sobre ANTLR por lo que no entraremos por el momento en más detalle.

2. Enriqueciendo los nodos del árbol AST

Por defecto, el tipo de árbol construido por ANTLR es del tipo CommonTree cuyos nodos únicamente contienen un tipo (atributo Type) y un valor (atributo Text). Esta información no suele ser suficiente en la mayoría de las ocasiones por lo que se hace necesario definir un tipo de árbol personalizado con toda la información que necesite nuestro compilador.

En nuestro caso vamos a necesitar para los elementos simples (identificadores y literales) toda la información contenida en la clase Symbol que ya definimos y dos campos adicionales para almacenar el tipo de las expresiones compuestas expType y el tipo de sus subexpresiones expSecType. Para conseguir esto simplemente tendremos que definir una clase derivada de CommonTree que contenga toda esta información y un constructor adecuado que inicialice todo lo necesario y llame al constructor de la clase padre. Veamos cómo quedaría esta clase a la que llamaremos FkvmAST:

using Antlr.Runtime;
using Antlr.Runtime.Tree;

public class FkvmAST : Antlr.Runtime.Tree.CommonTree
{
    public Symbol symbol;
    public string expType = "";
    public string expSecType = "";

    public FkvmAST(IToken t) : base(t)
    {
        //Nada que inicializar
    }
}

Una vez tenemos definida la clase que describirá nuestros nodos del árbol AST debemos indicar a ANTLR que use ésta para construir el árbol durante la fase de análisis sintáctico. Para ello deberemos modificar el valor asignado a la opción ASTLabelType indicando nuestra nueva clase.

options {
	output=AST;
	ASTLabelType=FkvmAST;
	language=CSharp;
}

Pero no nos basta con esto. Debemos crear también un adaptador para nuestro nuevo tipo de árbol. Este adaptador debe derivar de la clase CommonTreeAdaptor y tan sólo deberemos redefinir el método Create para devolver un árbol de tipo FkvmAST. Veamos cómo quedaría nuestro adaptador:

class FKTreeAdaptor : CommonTreeAdaptor
{
    public override object Create(IToken payload)
    {
        return new FkvmAST(payload);
    }
}

Una vez creado el nuevo adaptador debemos indicar a ANTLR en el programa principal que debe hacer uso de éste para la construcción del árbol de sintaxis abstracta durante la fase de análisis sintáctico. Para ello asignaremos la propiedad TreeAdaptor de nuestro parser antes de comenzar el análisis:

CommonTokenStream tokens = new CommonTokenStream(lexer);
FKVMParser parser = new FKVMParser(tokens);

ITreeAdaptor adaptor = new FKTreeAdaptor();
parser.TreeAdaptor = adaptor;

FKVMParser.programa_return result = parser.programa();

3. Implementación del analizador en ANTLR v3

Como indicamos anteriormente, para la fase de análisis semántico vamos a utilizar un analizador de árboles AST, lo que en ANTLR se define como tree grammar. Las opciones de este analizador serán las mismas que las establecidas en la fase anterior, con la excepción de la opción tokenVocab que indicará a ANTLR que debe utilizar los mismos tokens que se generaron para la fase de análisis sintáctico. De esta forma, ANTLR importará estos tokens desde el fichero FKVM.tokens generado en la fase anterior.

tree grammar FKVMSem;

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

Por otro lado, el analizador semántico recibirá como entrada, además del árbol AST, la tabla de símbolos generada anteriormente por lo que deberá declararse la variable que la contendrá. Como siempre haremos esto en las secciones @header y @members. Incluiremos también la variable numErrors para ir realizando el recuento de errores de forma análoga a la fase anterior.

@header {
using System.Collections.Generic;
}

@members {
public Dictionary<string,Symbol> symtable;
public int numErrors = 0;
}

El paso de parámetros a una regla en ANTLR se indica a continuación de la regla y entre corchetes, y la asignación de dicho parámetro a nuestra variable interna la podemos realizar en la sección @init de nuestra regla principal. Vemos cómo quedaría por la primera regla de nuestra gramática:

programa[Dictionary<string,Symbol> symtable] 
@init { 
    this.symtable = symtable; 
} 
: ^(PROGRAMA declaraciones_api principal) ; 

En el último apartado de esta sección veremos cómo podemos pasar en el programa principal la tabla de símbolos construida durante el analisis sintáctico como parámetro del analizador semántico.

4. Cálculo y chequeo de tipos

El cálculo y chequeo de tipos de una expresión se realizará comenzando por las expresiones más simples de nuestra gramática, es decir, los literales e identificadores. Una vez calculado el tipo de una expresión se asiganará éste a su nodo del árbol y además se devolverá como valor de retorno para que pueda ser consultado por la reglas superiores a la actual. El valor de retorno se indica en ANTLR mediante la cláusula returns seguida de la declaración entre corchetes de la variable a devolver.

expresion returns [String type]

Esta variable se inicializará en la sección @init de la regla y se asignará convenientemente dentro de cada subregla. Además, dentro de esta sección también obtendremos una referencia al nodo principal del arbol de la expresión para poder asignarlo al fializar la regla. Este nodo lo obtendremos mediante el método LT() del objeto input, que representa la secuencia de nodos del árbol que estamos analizando. De esta forma, el siguiente nodo de la secuencia, lo obtendremos mediante la llamada input.LT(1). Por último, en la sección @after de la regla asignaremos a este nodo el tipo calculado y que será devuelto como retorno. Veamos pues como queda la regla por el momento:

expresion returns [String type]
@init {
    $type="";
    FkvmAST root = (FkvmAST)input.LT(1);
}
@after {
    root.expType = $type;
}

Todo el cálculo de tipos se realizará en la regla que analiza las expresiones, donde están contenidos tanto los elementos más simples como los literales o identificadores, como las expresiones más complejas, donde habrá que calcular su tipo en función de los elementos que la componen. Empecemos por tanto por los elelemtos más sencillos.

Literales

El cálculo del tipo de un literal será tan sencillo como consultar el tipo de token devuelto por el analizador sintáctico y asignar directamente un tipo u otro en la subregla correspondiente. Como puede verse en el código siguiente, la técnica seguida en la regla literal para devolver el tipo calculado a la regla superior y asignarlo a su vez al nodo del árbol es la misma que la descrita para las expresiones.

expresion returns [String type]
...
    | literal {$type=$literal.type;}
    ;
	
literal returns [String type] 
@init {
    $type="";
    FkvmAST root = (FkvmAST)input.LT(1);
}
@after {
    root.expType = $type;
}
    : LIT_ENTERO {$type="int";}
    | LIT_REAL {$type="float";}
    | LIT_CADENA {$type="string";}
    | LIT_LOGICO {$type="bool";}
    ;

Identificadores

El cálculo de tipo para un identificador es más sencillo aún que en el caso de los literales ya que nos basaremos directamente en el tipo almacenado en la tabla de símbolos para dicho identificador. Además, en caso de no encontrar en la tabla de símbolos algún identificador informaremos del error al usuario, de forma que no permitiremos en nuestro lenguaje el uso de variables que no hayan sido declaradas.

expresion returns [String type]
...
    | IDENT {
          if(symtable.ContainsKey($IDENT.text))
          {
               root.symbol = (Symbol)symtable[$IDENT.text]; $type=root.symbol.type;
          }
          else
          {
               registrarError(root.Line, "Identifier '" + $IDENT.text + "' has not been declared.");
          }
    }
    | literal {$type=$literal.type;}
    ;

Llamadas a función externa

El tipo de una llamada a una función externa se calcula de la misma forma que el de los identificadores ya que el mecanismo que hemos utilizado para registrar su tipo durante el análisis sintáctico ha sido el mismo, la tabla de símbolos. Veamos por tanto cómo queda esta regla:

expresion returns [String type]
...
    | IDENT {root.symbol = (Symbol)symtable[$IDENT.text]; $type=root.symbol.type;}
    | literal {$type=$literal.type;}
    | llamada {$type=$literal.type;}
    ;
    
llamada returns [String type] 
@init {
$type="";
FkvmAST root = (FkvmAST)input.LT(1);
}
@after {
root.expType = $type;
}
: ^(LLAMADA IDENT lista_expr) {
        if(symtable.ContainsKey($IDENT.text))
        {
             root.symbol = (Symbol)symtable[$IDENT.text]; $type=root.symbol.type;
        }
        else
        {
             registrarError(root.Line, "Api function '" + $IDENT.text + "' has not been declared.");
        }
} ;

Expresiones complejas

Una vez hemos calculado el tipo de las expresiones más simples de nuestro lenguaje ya deberíamos ser capaces de calcular y chequear el de una expresión compuesta por estos elementos. Así, por ejemplo, para las expresiones lógicas consideraremos que su tipo es siempre bool y que ésta es correcta si los tipos de las dos subexpresiones son iguales o uno entero y otro real. Esto lo comprobaremos mediante el método comprobarTipoExpComp(tipo1, tipo2) que definiremos en la sección @members y si se determina que la combinación de tipos no es correcta se reportará al usuario el error correspondiente.

expresion returns [String type]
...
    | ^(opComparacion e1=expresion e2=expresion) {
            $type="bool";

            if(!comprobarTipoExpComp($e1.type, $e2.type))
            {
                 registrarError(root.Line, "Incorrect types in expression.");
            }
      }
    | IDENT {root.symbol = (Symbol)symtable[$IDENT.text]; $type=root.symbol.type;}
    | literal {$type=$literal.type;}
    | llamada {$type=$literal.type;}
    ;

@members {
public Dictionary symtable;
public int numErrors = 0;

public bool comprobarTipoExpComp(string t1, string t2)
{
    bool res = false;
	
    if(t1.Equals(t2) ||
      (t1.Equals("int") && t2.Equals("float")) ||
      (t1.Equals("float") && t2.Equals("int")) )
    {
         res = true; 
    }
	
    return res;
}
}    

El resto de expresiones incluidas en el analizador (expresiones aritméticas, operador menos-unario y operador no-lógico) las definiremos de forma análoga:

expresion returns [String type]
   : ^(opComparacion e1=expresion e2=expresion) {
            $type="bool";

            if(!comprobarTipoExpComp($e1.type, $e2.type))
            {
                 registrarError(root.Line, "Incorrect types in expression.");
            }
      }
    | ^(opAritmetico e1=expresion e2=expresion) {
            $type=$e1.type;
          			
            if(!comprobarTipoExpArit($e1.type, $e2.type))
            {
                 registrarError(root.Line, "Incorrect types in expression.");
            }
      }
    | ^(MENOSUNARIO e1=expresion) {
            $type=$e1.type;
          			
            if(!($e1.type.Equals("int") || $e1.type.Equals("float")))
            {
                 registrarError(root.Line, "Incorrect types in expression.");
            }
      }
      | ^('!' e1=expresion) {
            $type=$e1.type;
          			
            if(!$e1.type.Equals("bool"))
            {
                 registrarError(root.Line, "Incorrect types in expression.");
            }
      }
    | IDENT {root.symbol = (Symbol)symtable[$IDENT.text]; $type=root.symbol.type;}
    | literal {$type=$literal.type;}
    | llamada {$type=$literal.type;}
    ;

Instrucciones

El tipo de algunos de los elementos contenidos en instrucciones de nuestro lenguaje también debe ser comprobado durante la fase de análisis semántico. Así, por ejemplo, en las instrucciones de asignación deberemos comprobar que el tipo de la expresión derecha coincide con el de la variable que estamos asignando o que al menos es compatible. El tipo de la variable lo recuperaremos de la tabla de símbolos y el de la expresión accediendo a su atributo $type que ya debería haber sido calculado en la regla expresion. Las combinaciones válidas de tipos las comprobaremos como en el caso de las expresiones mediante un método definido en la sección @members. Veamos cómo quedaría esta regla:

inst_asig 
@init {
FkvmAST root = (FkvmAST)input.LT(1);
}
   : ^(ASIGNACION IDENT e1=expresion) {
          root.expType = $e1.type; 
	
          if(symtable.ContainsKey($IDENT.text))
          {
               $IDENT.symbol = (Symbol)symtable[$IDENT.text];
		
               if(!comprobarTipoAsig(root.expType, $IDENT.symbol.type)) 
               {
                    registrarError(root.Line, "Incorrect type in assignment.");
               }
          }
          else
          {
               registrarError(root.Line, "Identifier '" + $IDENT.text + 
		                                           "' has not been declared.");
          }	
};

Por su parte, para las instrucciones IF y WHILE deberemos comprobar que la condición viene expresada por una expresión de típo lógico. Para ello tan sólo deberemos comprobar el atributo $type de la expresión que hemos calculado en la regla expresion. Veamos por ejemplo la instrucción IF:

inst_if : ^(ins='if' e1=expresion lista_instrucciones lista_instrucciones) {
      if(!$e1.type.Equals("bool"))
      {
            registrarError($ins.Line, "Incorrect type in IF instruction.");
      }
};

5. Programa principal

Una vez finalizado nuestro analizador semántico podemos llamarlo desde el programa principal pasándole la tabla de símbolos calculada durante la fase anterior. Para ello, simplemente se creará el objeto FKVMSem con las estructuras necesarias procedentes del analisis sintáctico y se llamará a su método principal cuyo nombre debe coincidir con la regla principal de nuestra gramática, en este caso programa(). La tabla de símbolos se le pasará como parámetro de esta llamada ya que así lo definimos en la gramática.

//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);
}

Podéis descargar la gramática ANTLR completa y los ficheros auxiliares pulsando aquí.