Compilador universal de objetos usando reglas BNF I

En esta serie de artículos voy a mostrar una librería de clases que implementa un compilador que utiliza un lenguaje cualquiera definido mediante reglas BNF y que genera como resultado objetos de una librería de clases escrita por el usuario, los cuales deben implementar un sencillo interfaz para que el compilador pueda construirlos e inicializarlos a partir del código fuente.

En este enlace puedes descargar el código fuente del proyecto BNFUP, con la librería de clases que implementa el compilador, el editor de reglas BNF y tres ejemplos de librerías de clases que implementan objetos compilables a partir de tres lenguajes diferentes. Está escrito en CSharp usando Visual Studio 2015.

Sintaxis del lenguaje

En primer lugar, voy a definir el formato de las reglas BNF que he utilizado para definir cada uno de los lenguajes, usando también reglas BNF:

<<rulelist>> ::= <rule> [<rulelist>]
<rule> ::= <rulename> '::=' <defrule> ';'
<rulename> ::= <ruleid>
| '<<' <identifier> '>>'
<defrule> ::= <defrulech> ['|' <defrule>]
<defrulech> ::= <item> [<defrulech>]
<ruleid> ::= '<' <identifier> '>'
<identifier> ::= {a-zA-Z} [<rid>]
<rid> ::= {a-zA-Z0-9} [<rid>]
<item> ::= <token>
| <ltoken>
| <charset>
| <ruleid>
| '[' <item> ']'
<token> ::= ''' {.} [<rtoken>] '''
| ''' '\'' [<rtoken>] '''
<rtoken> ::= {.} [<rtoken>]
| '\'' [<rtoken>]
<ltoken> ::= <token> [',' <ltoken>]
<charset> ::= '{' <charlist> '}'
<charlist> ::= '\}' [<charlist>]
| <char> [<charlist>]

La regla raíz por la que se empieza a interpretar el código está marcada utilizando un doble signo << y >>, en este caso es rulelist, una lista de reglas.

La regla rule define la sintaxis de cada una de las reglas de la lista. Se define su nombre y se utiliza el toquen ::= para separarla de su definición. Se utiliza el toquen ; para marcar el final de la definición. Los toquen pertenecientes al lenguaje se deben escribir entre comillas simples.

Se utiliza el toquen | para separar varias definiciones alternativas para una misma regla. Si una parte de la regla es opcional, se debe escribir entre corchetes [ y ].

Los elementos que pueden formar la definición de una regla son los toquen, una lista de toquen (ltoken), que define varios posibles toquen para una misma posición del código, un conjunto de caracteres, encerrado entre llaves { y }, que se debe escribir utilizando la sintaxis de conjunto de caracteres de las expresiones regulares que utiliza el .NET framework, y el nombre de una regla cualquiera, que puede ser la propia regla que estamos definiendo.

Por ejemplo, esta sería la gramática correspondiente al lenguaje del artículo sobre el diseño de la gramática para un analizador de expresiones:

<number>::=<sdigit>[<rnumber>];
<rnumber>::=<digit>[<rnumber>]
|<decimalsep><rdecimal>;
<rdecimal>::=<digit>[<rdecimal>];
<sdigit>::={-0-9};
<digit>::={0-9};
<decimalsep>::={,\.};
<var>::={xyz};
<const>::=<letter>[<rconst>];
<rconst>::=<allchar>[<rconst>];
<letter>::={a-w};
<allchar>::={0-9a-z};
<<expr>>::=<expr2>['+','-'<expr>];
<expr2>::=<expr1>['*','/'<expr2>];
<expr1>::=<expr0>['^'<expr1>];
<expr0>::=['-']<element>;
<element>::=<pexpr>
|<number>
|<const>
|<var>;
<pexpr>::='('<expr>')';

La librería de clases BNFUP

La librería de clases BNFUP.dll implementa el compilador de objetos y define los interfaces necesarios para que los objetos de una librería de clases se puedan construir compilando un archivo de código fuente del lenguaje que hayamos diseñado para nuestros objetos.

En primer lugar, nuestra librería de clases deberá contener una única clase que implemente el interfaz ICompilableObjectFactory, definido en el espacio de nombre BNFUP.Interfaces y que debe implementar un constructor sin parámetros:

public interface ICompilableObjectFactory
{
ICompilableObject Object { get; }
void Init();
ICompilableObject CreateObject(string ctype, IRuleItem item);
}

Mediante la propiedad Object se devuelve el objeto final construido por el compilador, Init es un método que permite realizar acciones de inicialización al comienzo de la compilación, y CreateObject es el método al que se llamará cada vez que sea necesario crear un objeto. El parámetro ctype es una cadena de texto con el identificador único del tipo de objeto que es necesario crear, que veremos cómo se define al hablar del editor de reglas, y el parámetro ítem contiene el elemento del lenguaje que ha disparado la creación del objeto, aunque por lo general no será necesario utilizarlo.

Cada uno de los objetos que serán manejados por el compilador deberá implementar el interfaz ICompilableObject, definido también en el espacio de nombres BNFUP.Interfaces:

public interface ICompilableObject
{
string Text { get; set; }
bool AddItem(ICompilableObject item);
ICompilableObject Simplify();
void Test(Form fmain);
}

El compilador utiliza la propiedad Text para leer y escribir el texto del código fuente que ha dado lugar al objeto. Mediante el método AddItem se le pasan a un objeto compuesto sus objetos componentes, como podrían ser por ejemplo los argumentos y el operador en una expresión aritmética. El método Simplify se puede utilizar para devolver una versión simplificada del objeto. Podemos devolver el propio objeto, si no necesita simplificación, o bien una versión simplificada del mismo. Por ejemplo, una expresión aritmética compuesta solo por un número, puede devolver el propio número como resultado.

Por último, existe un método Test que permite realizar una implementación para probar el objeto una vez construido.

Podemos implementar nuestra propia versión del método ToString del objeto para proporcionar información de depuración al compilador integrado en el editor de reglas.

El compilador en sí está implementado en la clase RuleTable, en el espacio de nombres BNFUP.Rules. Se puede construir un objeto de este tipo utilizando el método estático RuleTable.FromFile, pasándole como parámetro un archivo generado con el editor de reglas que veremos a continuación.

La clase RuleTable tiene una propiedad Factory a la que deberemos asignarle una instancia de la clase ICompilableObjectFactory antes de poder utilizarla. Después solo es necesario llamar al método Build, pasando como parámetro un objeto TextReader con el código fuente a compilar, que nos devolverá el objeto generado.

El editor de reglas BNFUPEditor

Para facilitar la definición de las reglas del lenguaje, he implementado un editor en el proyecto BNFUPEditor que nos permitirá hacerlo de manera rápida y sencilla.

Aunque podemos crear la definición del lenguaje regla por regla usando el editor, con la opción Nuevo del menú Archivo, la forma más rápida de comenzar es escribir las reglas en un archivo de texto y utilizar la opción Abrir… del menú Archivo para construirlas a partir de este fichero. Con esta opción también podremos abrir los archivos binarios con extensión bnf propios del programa.

En la parte izquierda del formulario se encuentra la lista con las reglas. En la parte superior derecha se encuentra la definición de la regla seleccionada en forma de lista jerárquica, y en la parte inferior derecha podemos editar las propiedades del elemento seleccionado en esta lista.

Los elementos con los que podemos construir una regla son los siguientes:

• Regla: una regla simple cualquiera. Se puede utilizar una regla cualquiera de las definidas en el lenguaje.
• Reglas alternativas: Las reglas alternativas son simplemente una lista de reglas simples, de entre las cuales se puede encontrar una cualquiera en la posición correspondiente del código fuente. Las reglas que las componen no aparecen en la lista de la parte derecha.
• Token: un toquen cualquiera del lenguaje.
• Lista de tokens: Una lista de tokens, uno de los cuales se debe encontrar en la posición correspondiente del código fuente.
• Conjunto de caracteres: que determina un carácter de entre los definidos en el conjunto que debe aparecer en la posición correspondiente del código fuente.
• Lista de elementos: Se trata de un componente auxiliar que nos permite agrupar otros componentes. La función principal es marcar uno o más componentes como opcionales en un punto cualquiera del código fuente.

Todos los componentes tienen una propiedad ID del objeto compilado, que permite definir el tipo de objeto que generará el elemento al ser encontrado en el código fuente. Si esta propiedad está en blanco, no se generará ningún objeto.

Todos los elementos, excepto las reglas, tienen una propiedad Opcional que nos permite marcarlos como opcionales al compilar, pudiendo aparecer o no en el código fuente. Si queremos marcar una regla como opcional, deberá utilizarse una lista de elementos que la contenga.

El nombre de las reglas se define con la propiedad Nombre. Este nombre debe ser único. Para los toquen la propiedad equivalente es Token, y para los conjuntos de caracteres Caracteres.

Las reglas tienen además una propiedad Raiz que permite marcar una de ellas como la regla principal por la que comienza a interpretarse el código fuente.

Por último, con la propiedad Color podremos destacar un elemento cualquiera con un color determinado en la lista de reglas.

Para editar el contenido de una regla o los elementos que la componen, se debe seleccionar el elemento en la lista jerárquica y mostrar el menú contextual de opciones con el botón derecho del ratón.

Las opciones que aparecen en este menú dependen del tipo de elemento que tengamos seleccionado. La opción Nuevo elemento… permite añadir un nuevo componente del tipo apropiado a los objetos compuestos, que son las reglas y las listas. Se mostrará un cuadro de diálogo con todos los tipos de elementos que podemos añadir:

En este cuadro de diálogo encontramos dos tipos de elementos. Los que ya se encuentran definidos aparecen con su nombre o contenido. Si seleccionamos un elemento vacío del tipo que sea, se creará un nuevo elemento de ese tipo.

Si aparece el control Insertar en, podremos indicar la posición en la que queremos insertar el nuevo elemento.

Con la opción Eliminar podremos eliminar el elemento seleccionado. Esto no hará que el elemento sea borrado por completo, solo se elimina del elemento que estamos editando.

Las opciones Cortar, Copiar y Pegar tienen el uso habitual.

La opción Liberar elementos eliminará la lista y sus componentes quedarán situados en el nivel que antes ocupaba la lista.

La opción Enlistar creará una lista de elementos y pondrá el elemento seleccionado en su interior.

La opción Extraer permite extraer un elemento de la lista que lo contiene, pasándolo al nivel superior.

Mover arriba y Mover abajo permiten desplazar la posición de un elemento dentro de una lista.

Las reglas simples se pueden transformar en reglas alternativas mediante la opción Añadir alternativas, para las reglas compuestas, existe la opción Simplificar que realiza la operación contraria, convirtiéndolas en una regla simple una vez que solo contienen una única alternativa.

Para crear nuevas reglas o eliminar alguna regla existente disponemos de tres botones en la barra de herramientas del formulario, uno para crear una nueva regla simple, otro para crear una nueva regla compuesta y otro para eliminar la regla seleccionada. Si eliminamos una regla, desaparecerá por completo de la lista y de todas las posiciones de otras reglas que la utilicen.

En el próximo artículo mostraré como utilizar el editor para compilar y probar objetos y unos cuantos ejemplos.