Apéndice I. Estilo en Gramáticas #

Introducción #

A la hora de crear la gramática del lenguaje de la asignatura, es común que al alumno se le presenten dudas de cómo expresarlo en una gramática. Tal y como se dijo, existen infinitas gramáticas equivalentes para expresar dicho lenguaje.

No hay ningún algoritmo que, dado un lenguaje, produzca una gramática sencilla y fácil de implementar. Sin embargo, al menos, se pretende dar aquí alguna guía con unas reglas muy generales para tener algún criterio a la hora de crear la gramática.

Objetivo #

A la hora de establecer un estilo para crear las reglas de una gramática (sea BNF o EBNF), hay que tener claro qué se pretende obtener con él.

Para conseguir esto, se proponen los siguientes criterios:

• Minimizar el número de reglas. Será más fácil enfrentarse a una gramática cuanto más pequeña sea.
• Estructura simple de cada regla. Que sólo viendo la forma de la regla ya se vea qué pretende expresar y se tenga la mayor parte del trabajo de comprensión hecho.
• Limpieza de cada regla. Cuantas más acciones de código haya incrustadas en una regla, más difícil será de entender su estructura.

Estos son los criterios generales pero, por supuesto, hay que saber cuándo no seguirlos. A veces, para conseguir reglas más limpias (criterio 3), hay que añadir alguna regla intermedia (lo que va en contra del criterio 1). Esto sucede, por ejemplo, a la hora de definir listas, ya que ahí se recomienda utilizar una regla auxiliar sólo para las mismas.

En definitiva, los criterios anteriores deben contemplarse... hasta que el no seguirlos haga más sencilla de entender la gramática (que es el verdadero objetivo). Sin embargo, se recomienda tener al menos estos criterios, lo cual será mejor que no tener ninguno.

Minimizar el Número de Reglas #

Parece evidente que cuantas menos reglas tenga una gramática, más fácil será de entender. Sin embargo, muchas veces se añaden reglas artificiales sin un motivo justificado. Es habitual, a la hora de crear una gramáticas, el intentar clasificar las reglas innecesariamente.

Un caso de esto sería el de las expresiones. Es común verlas definidas así:

expr: constante
    | cast
    | aritméticas
    | lógicas
    | ...

coonstante: INT_CONTANT | REAL_CONSTANT;

cast: '('type')' expr

aritméticas: expr '+' exp

logicas: expr '&&' expr

...

Es cierto que los operadores anteriores, en el mundo real, se clasifican en las categorías indicadas. Pero aquí el trabajo no es crear ningún tipo de representación o modelo del mundo real; el objetivo es saber lo más rápidamente posible si se ha olvidado un operador navegando lo mínimo posible por la gramática. En ese caso, una solución como la siguiente sería más fácil de comprender y validar:

expr: INT_CONSTANT
    | REAL_CONSTANT
    | '('type')' expr
    | expr '+' expr
    | expr '&&' expr
    | ...

Es decir, que en vez de tener reglas del estilo:

a: b0
 | c0
 | d0

b0: b1 b2

c0: c1 c2

d0: d1 d2

Se recomienda, en general, que cuando una regla tenga alternativas, estas se desglosen in-situ en la misma regla padre en vez de crear una regla para cada alternativa:

a: b1 b2
 | c1 c2
 | d1 d2

Sin embargo, puede haber algunas situaciones en las que sí es necesario crear una regla independiente:

• Si dicha regla se usa en algún sitio más de la gramática (y si en ambos sitios se espera recibir el mismo nodo del AST y creado con los mismos argumentos).
• Si la regla representa una lista de elementos.
• Que el incorporar la regla en el padre dificulte entender dicha regla padre o el resto de las alternativas hermanas.

Reglas con Estructura Simple #

Al enfrentarse a una gramática, el esfuerzo para entenderla será mayor cuanto más crípticas sean sus reglas. La solución es fácil: que no haya reglas crípticas. Para ello, toda regla deberá ser una de las tres construcciones básicas ya conocidas: o es una secuencia o es una composición o es una lista.

No deberá haber ninguna regla que no sea una y sólo una de estas tres construcciones. De esta manera, será fácil entender cada regla y, por tanto, la gramática (lo mismo que un diseño orientado a objetos es más fácil de entender en cuanto se identifican sus patrones).

Si en la gramática sólo hay estas tres estructuras, las listas serán fáciles de reconocer e ignorar en una primera lectura, permitiendo centrarse en las secuencias y composiciones (que serán las que describan los elementos relevantes del lenguaje).

Sin embargo, el error más común no es que una regla no tenga una de estas tres formas; el error más común es que tenga más de una. Lo siguiente es un ejemplo de regla que mezcla más de una construcción. Comienza como una secuencia definiendo el identificador y el paréntesis pero, en mitad de la regla, aparece una repetición.

func
    : IDENT '(' (IDENT ':' tipo (',' IDENT ':' tipo)* )? ')' '{' sentences '}'

Los inconvenientes son:

• Dicha regla es más difícil de entender al no poder separar mentalmente sus partes de inmediato. Obliga a intentar entenderla sin ninguna ayuda más que nuestra capacidad de análisis.
• Cuando se añadan las acciones en Java que creen el AST, la regla quedará realmente oscurecida entre las acciones.

Lo siguiente sería otro ejemplo de mezcla de dos construcciones. En params, que es una construcción repetición, también se está definiendo, mediante una secuencia, la forma que debe tener un parámetro.

func
    : IDENT '(' params ')' '{' sentences '}'

params
    : (IDENT ':' tipo  (',' IDENT ':' tipo)* )?     // Lista con secuencias dento

Esto tiene el inconveniente de que la forma que tiene un parámetro (su nombre y su tipo separado por punto y coma) aparece dos veces en la regla. Esto supone que:

• Entender la forma que tienen los parámetros es más difícil, ya que habrá que comprobar mentalmente si se ha repetido porque haya alguna diferencia (que no hay).
• Si posteriormente se decide cambiar la sintaxis de los parámetros, habrá que modificarlo en ambos sitios de la regla.
• A la hora de construir el AST, las acciones harán una regla muy difícil de leer, ya que estarán dentro de la regla.

Todos los problemas de los dos ejemplos anteriores se solucionarían si cada regla siguiera una sola construcción:

func
    : IDENT '(' params ')' '{' sentences '}'    // Secuencia

params
    : (param (',' param)*)?                     // Lista

param
    : IDENT ':' tipo                            // Secuencia

Ventajas:

• Se ve que func es una construcción secuencia inmediata de entender.
• Se ve fácilmente que params es la habitual estructura de lista, lo que nos permite saltarla mentalmente, ya que todas las listas son iguales.
• Se ve que param es una construcción secuencia limpia y, por tanto, ahora se ve más fácilmente, y en un único sitio, cómo es un parámetro en este lenguaje.

Limpieza en las Reglas #

A la hora de entender una gramática, las acciones en Java es algo secundario que, en un primer momento, se debe ignorar para centrarse en los símbolos terminales y no-terminales que constituyen cada regla. Por tanto, la tarea de comprender una gramática será más difícil:

• Cuantas más acciones Java haya en cada regla.
• Si las acciones, además, están situadas entre los símbolos de las reglas y no al final. Cada acción supone un obstáculo ya que hay que estar constantemente buscando los límites de las llaves para intentar extraerlas mentalmente de las regla. Esto dificulta mucho su comprensión.

Por ejemplo, en el siguiente fragmento ¿qué está expresando en EBNF la regla n?

n returns [NNode ast]
  locals[List<ENode> list = new ArrayList<ENode>()]
    : a (e { $list.add($e.ast); } (',' e { $list.add($e.ast); })*)? b { $ast = new NNode($a.ast, $list, $b.ast); };

Es complicado de entender con tanto código incrustado. En realidad, en una primera lectura de la gramática, la único que se querría ver es la regla limpia de código para entenderla primero:

n
    : a (e (',' e)*)? b

Por tanto, el objetivo ideal sería tener reglas con una sola acción y que esté al final de la regla. Cuanto más se acerque una gramática a este objetivo, más fácil de leer será la gramática.

Resumen #

Una forma de obtener una gramática fácil de entender es, generalmente, hacer lo siguiente:

• Pocas reglas. Pensar, para cada regla, si realmente es necesaria o se puede incrustar en la regla que la llama.
• Que la forma de cada regla sea la de una y sólo una de las tres construcciones básicas.
• Intentar que las reglas tengan una sola acción Java y que esté al final.