Análisis Léxico-Sintáctico 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 comentaremos la construcción mediante ANTLR 3 de los analizadores léxico y sintáctico para nuestro lenguaje FKScript.

En primer lugar escribiremos los analizadores básicos, es decir, sin acciones, de forma que podamos reconocer fragmentos de código escritos en FKScript, y posteriormente definiremos las acciones a incluir en cada regla para la construcción del árbol de sintáxis abstracta (AST) y la tabla de símbolos que serán utilizados en las fases posteriores de nuestro compilador (análisis semántico y generación de código). Por último también hablaremos un poco sobre cómo se informa de los posibles errores al usuario y cómo los contabilizamos.

Empecemos. En primer lugar cabe destacar que ANTLR v3 permite definir los analizadores léxico (lexer) y sintáctico (parser) en ficheros independientes o en un solo fichero donde aparezcan ambos. Dado que en nuestro caso ambos analizadores son relativamente sencillos vamos a optar por la segunda opción.

Lo primero que debemos especificar en el fichero ANTLR será el tipo de gramática a definir (lexer grammar, parser grammar, o grammar para combinar análisis léxico y sintáctico en un mismo fichero) y el nombre que recibirá la gramática, en nuestro caso “FKVM”.

En segundo lugar indicaremos las opciones del analizador, donde sólo incluiremos la opción language, que indica el lenguaje en el que se generará el código de los analizadores, utilizaremos C#, y el tipo de salida producida por el analizador sintáctico, en nuestro caso un árbol AST (opción output) de tipo CommonTree (opción ASTLabelType).

grammar FKVM;

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

1. Analizador Léxico

El analizador léxico se encargará de reconocer y separar convenientemente los elementos básicos (tokens) del lenguaje que estamos construyendo. En la mayoría de los casos deberemos distinguir: literales de los distintos tipos de datos que existan en el lenguaje, identificadores (ya sean palabras clave o no) y deberemos definir qué se entenderá como espacio en blanco entre elementos.

Literales

En FKScript existen 4 tipos de datos: enteros, reales, lógicos y cadenas. Deberemos definir por tanto cómo reconocer cada uno de estos literales en nuestro código. Para ayudar a que las definiciones de estos elelementos no sean demasiado complejas y repetitivas definiremos dos reglas auxiliares (para las cuales se utiliza la palabra clave fragment) para reconocer dígitos y letras. Una vez definidas estas reglas auxiliares, el resto son muy sencillas. Por ejemplo, un literal entero estará formado por cualquier combinación de 1 o más dígitos (lo que se indica con el operador ‘+’ de ANTLR). Los literales cadena estarán formados por una doble comilla seguida de cualquier combinación de caracteres distintos a dobles comillas, saltos de linea o tabuladores y por último otra doble comilla de cierre. Por su parte, un literal lógico tan sólo podrá tomar dos valores: true o false.

fragment LETRA : ‘a’..’z'|’A’..’Z’ ;
fragment DIGITO : ’0′..’9′ ;

LIT_ENTERO : DIGITO+ ;

LIT_REAL : LIT_ENTERO ‘.’ LIT_ENTERO ;

LIT_CADENA : ‘”‘ (~(‘”‘|’\n’|'\r’|'\t’))* ‘”‘ ;

LIT_LOGICO : ‘true’|'false’ ;

Identificadores

Los identificadores en FKScript, como ya se indicó en la especificación del lenguaje, estarán formados por cualquier letra o caracter subrayado seguida de cualquier combinación de dígitos, letras o caracteres de cubrayado.

IDENT : (LETRA|’_')(LETRA|DIGITO|’_')* ;

Comentarios

Los comentarios permitidos serán de una sola línea y se utilizará la sintaxis de C++ o Java, es decir, precederlos de los caracteres “//”. Como puede observarse en la regla se le indicará además a ANTLR que estos tokens no deben ser pasados al analizador sintáctico ya que no son de utilidad. Esto lo indicaremos mediante la acción $channel=HIDDEN;

COMENTARIO : ‘//’ (~(‘\n’|'\r’))* ‘\r’? ‘\n’ {$channel=HIDDEN;};

Espacio en blanco

Se considerará espacio en blanco entre elementos del lenguaje a toda combinación de caracteres espacio, saltos de línea o tabuladores. Además, estos elementos tampoco serán pasados como tokens al analizador sintáctico.

WS : (‘ ‘|’\r’|'\n’|'\t’)+ {$channel=HIDDEN;} ;

2. Analizador Sintáctico

A partir de los tokens pasados por el analizador léxico, el analizador sintáctico se encargará de reconocer las combinaciones correctas de tokens que forman instrucciones o expresiones válidas en nuestro lenguaje. Por tanto deberemos definir cuál es la estructura general de un programa FKScript y la estrutura concreta de cada una de las construcciones (instrucciones y expresiones) aceptadas en el lenguaje.

Programa

Tal como se indicó en la especificación del lenguaje, un programa FKScript estará formado por una serie de declaraciones de funciones API (opcionales) seguidas del programa principal que se identifica mediante la palabra clave program seguida de un identificador que indicará el nombre del programa y una lista de instrucciones delimitadas por llaves (‘{‘ y ‘}’). Las instrucciones a su vez podrán ser: declaraciones, asignaciones, condicionales if, bucles while o instrucciones de retorno. Abajo podemos ver lo sencillo que resulta definir todo esto en ANTLR v3, y lo que es mejor, utilizando la misma sintáxis usada ya para el analizador léxico.

programa : declaraciones_api principal ;

declaraciones_api : declaracion_api* ;

declaracion_api : ‘api’ tipo IDENT ‘(‘ lista_decl ‘)’ ‘;’ ;

principal : ‘program’ tipo IDENT ‘{‘ lista_instrucciones ‘}’ ;

lista_instrucciones : instruccion* ;

instruccion : inst_decl
| inst_asig
| inst_if
| inst_while
| inst_return
| inst_expr;

Instrucciones

La definición de las instrucciones no implica ninguna dificultad. Así, por ejemplo, la instrucción IF de nuestro lenguaje estará formada por la palabra clave if, una expresión (regla que definiremos más tarde) entre paréntesis, una lista de instrucciones para el caso de que se cumpla la condición, y opcionalmente (operador ? de ANTLR) otra lista de instrucciones para el caso de que no se cumpla dicha condición precedida de la palabra clave else. Nótese como las palabras clave y símbolos de puntuación los indicamos directamente entre comillas simples, los tokens devueltos por el analizador léxico con mayúsculas y las reglas del analizador sintáctico en minúsculas.

inst_decl : tipo IDENT ‘;’ ;

inst_asig : IDENT ‘=’ expresion ‘;’ ;

inst_if : ‘if’ ‘(‘ expresion ‘)’ ‘{‘ lista_instrucciones ‘}’ else_otras? ;

else_otras : ‘else’ ‘{‘ lista_instrucciones ‘}’ ;

inst_while : ‘while’ ‘(‘ expresion ‘)’ ‘{‘ lista_instrucciones ‘}’ ;

inst_return : ‘return’ expresion ‘;’ ;

inst_expr : expresion ‘;’ ;

Expresiones

La definición de las expresiones en ANTLR sí es más interesante. Dado que ANTLR 3 no porvee ningún mecanismo explícito para indicar la precedencia de cada uno de los operadores debemos buscar la forma de que ésta se tenga en cuenta por la propia definición de las reglas. Para ello, el método utilizado será definir cada una de las posibles expresiones (según operadores) de forma que un tipo de expresión quede definido en función del siguiente tipo en el orden de precedencia (siempre de menor a mayor). Así, por ejemplo, como las operaciones de multiplicación y división tienen mayor precedencia que la suma y la resta definiremos ésta última en función de la primera, así nos aseguramos de que las operaciones se asocien siempre de forma correcta.

expMasMenos : expMultDiv (
(‘+’|'-’) expMultDiv)* ;

Para el resto de expresiones se seguiría la misma técnica:

expresion : expOr ;

expOr : expAnd (‘||’^ expAnd)* ;

expAnd : expComp (‘&&’^ expComp)* ;

expComp : expMasMenos (
(‘==’|'!=’|'>’|'<’|'>=’|'<=’) expMasMenos)* ;

expMasMenos : expMultDiv (
(‘+’|'-’) expMultDiv)* ;

expMultDiv : expMenos (
(‘*’|'/’) expMenos)* ;

expMenos : ‘-’ expNo
| ‘+’? expNo ;

expNo : ‘!’? acceso ;

acceso : IDENT
| literal
| llamada
| ‘(‘ expresion ‘)’ ;

Llamadas a funciones

Las llamadas a función seguirán la sintáxis clásica compuesta por el nombre de la función seguido de una lista de parámetros (expresiones) entre paréntesis y separados por comas.

llamada : IDENT ‘(‘ lista_expr ‘)’ ;

lista_expr : expresion (‘,’ expresion)*
| //Sin parámetros ;

Otras reglas

Por último, tan sólo quedan definir el resto de reglas auxiliares, como los tipos de datos o los tipos de literales. Estas reglas suelen ser muy sencillas ya que se limitan a enumerar cada uno de los elementos aceptados en el lenguaje.

tipo : ‘int’|'float’|'string’|'bool’|'void’ ;

literal : LIT_ENTERO
| LIT_REAL
| LIT_CADENA
| LIT_LOGICO ;

Programa de prueba

Hemos finalizado nuestros analizadores básicos. Con esto ya deberíamos ser capaces de comprobar si la sintaxis de un programa escrito en FKScript es o no válida. Para ello, necesitamos disponer de un programa de prueba, en el que se llame convenientemente a las clases generadas por ANTLR a partir de nuestra gramática.

using System;
using Antlr.Runtime;
using Antlr.Runtime.Tree;
using Antlr.StringTemplate;

namespace PruAntlr
{
class Program
{
static void Main(string[] args)
{
ANTLRFileStream input = new ANTLRFileStream("prueba.fks");
FKVMLexer lexer = new FKVMLexer(input);

CommonTokenStream tokens = new CommonTokenStream(lexer);
FKVMParser parser = new FKVMParser(tokens);
FKVMParser.programa_return result = parser.programa();

Console.WriteLine("Analisis finalizado.");
}
}
}

De esta forma, utilizando el programa principal anterior y un fichero de entrada válido como el que se muestra a continuación deberíamos obtener como única salida del programa el mensaje de “Analisis finalizado”, ya que si los analizadores no encuentran ningún error no muestran nada a la salida.

program Prueba
{
int a;
a = 1;
}

Sin embargo, si introducimos un error en el fichero de entrada, por ejemplo en este caso hemos eliminado la variable ‘a’ de la primera declaración, el analizador sintáctico debería mostrarnos el mensaje de error correspondiente.

program Prueba
{
int ;
a = 1;
}

El resultado del análisis debería ser el siguiente:

line 2:5 mismatched input ‘;’ expecting IDENT
Analisis finalizado.

En el mesaje se informa al usuario de que en la posición 5 de la línea 2 del fichero de entrada se ha encontrado un carácter ‘;’ cuando se esperaba un identificador.

3. Recuento y reporte de errores

Vamos a ir ahora un poco más allá y además de mostrar los errores al usuario vamos a mostrar un último mensaje con el número de errores encontrados por los analizadores léxico y sintáctico. Para ello, la técnica que vamos a utilizar será sobescribir los métodos de ANTLR encargados de generar los mensajes de error (GetErrorMessage). La modificación que vamos a realizar a estos métodos será simplemente incrementar una variable propia cada vez que sean llamados y llamar por último al metodo padre para que ANTLR realice el resto de tareas necesarias. El código de estos métodos y la declaración de nuestras variables lo incluiremos en las secciones @lexer::members y @members

@lexer::members {
public int numErrors = 0;

public override string GetErrorMessage(RecognitionException e, string[] tokenNames)
{
numErrors++;
return base.GetErrorMessage(e,tokenNames);
}
}

@members {
public int numErrors = 0;

public override string GetErrorMessage(RecognitionException e, string[] tokenNames)
{
numErrors++;
return base.GetErrorMessage(e,tokenNames);
}
}

A partir de este momento, desde nuestro programa principal tendremos acceso a nuestra nueva variable que tras llamar a los analizadores contendrán el número de errores encontrados. Así, podríamos modificar la última línea de nuestro programa principal por la siguiente:

Console.WriteLine(“Analisis finalizado. Errores: ” + parser.numErrors);

Y ante este fichero de entrada:

program Prueba
{
int ;
= 1;
}

La salida sería la siguiente:

line 2:5 mismatched input ‘;’ expecting IDENT
line 3:2 mismatched input ‘=’ expecting ‘}’
Analisis finalizado. Errores: 2

4. Construcción del AST

Una vez que ya somos capaces de reconocer correctamente ficheros de entrada válidos para nuestro lenguaje y de informar de los posibles errores en caso de producirse el siguiente paso será modificar convenientemente la gramática para construir durante el análisis el árbol de sintáxis abstracta (AST) y la tabla de símbolos que serán utilizados por el analizador semántico y el generador de código.

ANTLR v3 proporciona dos mecanismos básicos de construcción de árboles AST:

  1. Mediante operadores.
  2. Mediante reglas de reescritura.

Ambos mecanismos pueden mezclarse en una misma gramática y el uso de uno u otro dependerá de la complejidad del árbol que queramos construir. En nuestro caso mezclaremos ambos métodos por lo que veamos en primer lugar un par de ejemplos.

La construcción mediante operadores consiste en incluir en las propias reglas del analizador una serie de operadores que indiquen a ANTLR cómo debe tratarlos para construir el árbol devuelto por la regla. Estos operadores son tan sólo dos: ^ y !. El primero de ellos se utilizará para indicar qué elemento de la regla se utilizará como raíz del árbol (todos los demás pasarán a ser hijos directos de éste) y el segundo operador se añadirá a los elementos que no deben formar parte del árbol.

Así, por ejemplo, en la regla inst_while podremos indicar que la palabra clave while se utilizará como raíz del árbol y que los paréntesis y llaves no deben incluirse en el árbol ya que no aportan ningún valor para las fases siguientes.

inst_while : ‘while’^ ‘(‘! expresion ‘)’! ‘{‘! lista_instrucciones ‘}’! ;

En reglas más complejas o donde haya que utilizar nodos ficticios (elementos que no aparecen en la regla pero se incluyen en el árbol AST por conveniencia) se pueden utilizar las reglas de reescritura de árboles. Éstas se incluyen a la derecha de la regla precedida por el operador -> y utilizan la sintáxis siguiente:

regla -> ^(raiz hijo1 hijo2 …)

En nuestro caso podemos poner como ejemplo la regla para definir las asignaciones inst_asig, donde indicaremos mediante una regla de reescritura que queremos construir un árbol con un nodo raíz ficticio llamado ASIGNACION y dos hijos, uno con el identificador y otro con la expresión asignada.

inst_asig : IDENT ‘=’ expresion ‘;’ -> ^(ASIGNACION IDENT expresion);

Los nodos ficticios deben declararse al principio de la gramática en la sección tokens. En nuestro caso utilizaremos los siguientes:

tokens {
PROGRAMA;
DECLARACION;
DECLARACIONPARAM;
LISTADECLARACIONESAPI;
DECLARACIONAPI;
ASIGNACION;
MENOSUNARIO;
LISTAINSTRUCCIONES;
LLAMADA;
LISTAEXPRESIONES;
LISTAPARAMETROS;
}

5. Construcción de la Tabla de Símbolos

Otra de las tareas a realizar durante el análisis sintáctico será la construcción de la tabla de símbolos. Esta estructura deberá contener al finalizar el análisis una relación fácilmente accesible que contenga todos los identificadores utilizados en el programa junto cualquier información asociada a dicho identificador que sea relevante para las etapas posteriores, como por ejemplo el tipo de dato de la variable.

En nuestro caso, construiremos una tabla de símbolos que contenga cada identificador junto a su tipo y su número de orden dentro del programa. Para ello definiremos en primer lugar una clase para encapsular toda la información asociada a cada identificador:

public class Symbol
{
public int numvar;  //Número de orden la variable
public string type; //Tipo de la variable

//Constructor de la clase
public Symbol(string t, int n)
{
type = t;
numvar = n;
}
}

El siguiente paso será declarar la estructura que contendrá la tabla de símbolos. Nosotros utilizaremos una colección genérica de tipo Dictionary con claves de tipo string para el nombre de a variable y valores de tipo Symbol que acabamos de crear. La declaración de esta estructura debe incluirse en la sección @members y los includes necesarios en la sección @header de la gramática.

@header {
using System.Collections.Generic;
}

@members {
public Dictionary<string,Symbol> symtable = new Dictionary<string,Symbol>();
int numVars = 0;

}

En nuestro lenguaje FKScript, el único lugar válido donde pueden definirse variables es dentro de las declaraciones, por lo que la única regla donde debemos ir actualizando la tabla de símbolos será inst_decl. Por tanto, dentro de esta regla, además de la regla de reescritura para construir el árbol AST deberemos incluir una acción (entre llaves) donde se añada el identificador declarado a la tabla de símbolos. Esta acción se limitará a comprobar si el identificador ya existe en la tabla y añadirlo en caso de no existir. Veamos cómo:

inst_decl : tipo IDENT ‘;’ {
if(!symtable.ContainsKey($IDENT.text))
{
symtable.Add($IDENT.text, new Symbol($tipo.text, numVars++));
}
} -> ^(DECLARACION tipo IDENT);

6. Finalizando el analizador léxico-sintáctico

Una vez completada la implementación de nuestra gramática tan sólo nos queda probarla mediante el programa principal que ya comenzamos en apartados anteriores. En esta ocasión vamos a modificarlo para que al finalizar el análisis nos muestre el árbol AST construido y la tabla de símbolos con nuestras variables y su información asociada.

using System;
using Antlr.Runtime;
using Antlr.Runtime.Tree;
using Antlr.StringTemplate;
using System.Collections.Generic;

namespace PruAntlr
{
class Program
{
static void Main(string[] args)
{
ANTLRFileStream input = new ANTLRFileStream("C:\\pruantlr\\prueba.fks");
FKVMLexer lexer = new FKVMLexer(input);

CommonTokenStream tokens = new CommonTokenStream(lexer);
FKVMParser parser = new FKVMParser(tokens);
FKVMParser.programa_return result = parser.programa();

if (parser.numErrors == 0)
{
CommonTree t = (CommonTree)result.Tree;

Console.WriteLine("Arbol AST:");
Console.WriteLine(t.ToStringTree() + "\n");

Console.WriteLine("Tabla de Simbolos:");

foreach (string k in parser.symtable.Keys)
{
Console.WriteLine(((Symbol)parser.symtable[k]).numvar +
" - " + k + " -> " + ((Symbol)parser.symtable[k]).type);
}
}
else
{
Console.WriteLine("Errores: " + parser.numErrors);
}

Console.ReadLine();
}
}
}

El árbol AST lo obtenemos mediante la propiedad Tree del objeto que representa a la regla principal de nuestra gramática programa_return y lo imprimimos por pantalla mediante el método toStringTree(). Por su parte, a la tabla de símbolos podemos acceder como a un atributo más del objeto parser ya que la declaramos en la sección @members.

De esta forma, para el siguiente fichero de entrada:

program Prueba {
int a;
float b;

a = 1;
}

Obtendríamos la siguiente salida (la formateo para que sea legible):

Arbol AST:

(program Prueba
(LISTAINSTRUCCIONES
(DECLARACION int a)
(DECLARACION float b)
(ASIGNACION a 1)
)
)

Tabla de Simbolos:

0 – a -> int
1 – b -> float

Podéis descargar la gramática ANTLR completa más el programa principal y las clases auxiliares 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