Especificación de un AST #

En el capítulo anterior se diseñaron los nodos del AST de una manera informal, utilizando una notación gráfica. Sin embargo, esto no es práctico a la hora de describir un árbol.

En este capítulo se abordará cómo hacer una especificación formal de los nodos de un AST, es decir, cómo documentar qué nodos se pueden encontrar en un AST y qué hijos tienen.

Gramáticas Abstractas #

Introducción #

A estas alturas, como se ha hecho en todas las fases anteriores, ya se sabe que la manera más adecuada de documentar un AST será un metalenguaje. En concreto, el metalenguaje que se utilizará para documentar árboles AST es la gramática abstracta. La notación que se usará en este tema está basada en la de Scott.

Las gramáticas abstracta se definen mediante texto en vez de usar diagramas. Una especificación en este metalenguaje consiste en definir una regla por cada nodo. La estructura de cada regla es la siguiente:

• Comienza por el nombre del nodo.
• Si pertenece a categorías sintácticas, se ponen todas ellas detrás del nombre separadas por dos puntos.
• A continuación, separados por una flecha, aparecen los tipos de los hijos del nodo.

<nodo>:<categorías> -> <tipos hijos>

Una gramática abstracta puede verse como una forma de representar en texto el diagrama de clases que forman los nodos del AST. Al fin y al cabo, ambos formatos representan la información esencial de este: qué clases tiene y cómo se relacionan entre sí. Pero, aunque ambos representan la información necesaria sobre el AST, las ventajas de las gramáticas abstractas son:

• Al ser texto, no requieren de herramientas específicas para su creación, mientras que los diagrama de clases requieren de un editor gráfico.
• Son más compactas que los diagramas de clases.

Ejemplo #

En el capítulo anterior se llegó al siguiente diseño de nodos expresado de forma gráfica:

Se describen ahora dichos nodos usando la notación de las gramáticas abstractas:

Nótese que lo obligatorio es poner el tipo de los hijos (no el nombre). Sin embargo, cuando varios hijos tienen el mismo tipo, puede ser de ayuda asignar nombres a los hijos para facilitar la lectura de la gramática. Para poner un nombre a un hijo basta con ponerlo delante del tipo separándolos con dos puntos. La siguiente gramática es el resultado de añadir nombres (en gris) a ciertos hijos para facilitar su comprensión.

Nótese que no se trata de poner nombre a todos los hijos. Cuando el tipo es autoexplicativo es mejor no cargar la gramática y reservar el poner nombres sólo a aquellos hijos que realmente aclaren su función. Por ejemplo, aquí se ha utilizado en el nodo exprBinaria para diferenciar qué son sus dos hijos expr.

Aclaraciones adicionales:

• No confundir el operador '*' con el uso que se da a dicho carácter en EBNF y en las expresiones regulares. En estas últimas, dicho operador indica la repetición de cero o más elementos. Aquí simplemente significa que dicha rama, en vez de un sólo nodo, debe tener una lista de ellos. Por tanto, no hay — y no se necesita — el operador '+'. Una vez indicado que dicha rama es una lista, no es relevante si en esa lista habrá al menos un elemento o no.
• Recuérdese que, tal y como se dijo en el capítulo anterior, el tipo no es texto libre, sino que debe ser un nodo, una categoría sintáctica o un tipo propio del lenguaje de implementación (los tres casos vistos en el capítulo anterior).

Especificación de las Gramáticas Abstractas #

Una gramática abstracta no deja de ser un lenguaje. En el apartado anterior se ha explicado su sintaxis de manera informal en lenguaje natural. Pero, como lenguaje que es, se puede especificar de manera formal utilizando una gramática libre de contexto.

Sintaxis de las gramáticas abstractas en EBNF.

gramaticaAbstracta: regla*              // 0+ss

regla: IDENT (':' categorias)? '->' atributo*

categorias:	IDENT (',' IDENT)*          // 1+cs

atributo: (IDENT ':')? IDENT '*'?

Y el equivalente en BNF.

gramaticaAbstracta: reglas_opt

reglas_opt: ε | reglas_opt regla                // 0+ss

regla: IDENT categorias_opt '->' atributos_opt

categorias_opt:  ε | ':' categorias

categorias:	IDENT | categorias ',' IDENT        // 1+cs

atributos_opt: ε | atributos_opt atributo       // 0+ss

atributo: IDENT ':' IDENT asterisco_opt
		| IDENT asterisco_opt

asterisco_opt: ε | '*'

GLC vs Gramática Abstracta #

A lo largo del curso han salido dos tipos de gramáticas: las gramáticas libres de contexto (también llamada GLC o gramáticas a secas) y las gramáticas abstractas. Aunque se han explicado ya por separado, en este apartado se va a hacer un resumen rápido de ambas para asentar los términos.

La misión del sintáctico es transformar una secuencia de caracteres (el fichero de entrada) en un árbol.

• La GLC es la que determina cómo tiene que ser la entrada del sintáctico. Describe la estructura de textos. Es la forma de indicar al usuario del compilador cómo debe escribir una entrada válida. Se expresa en BNF o EBNF y se crea utilizando las construcciones vistas.
• La gramática abstracta es la que determina cómo va a ser la salida del sintáctico. Describe la estructura de árboles. Es la forma de indicar a los diseñadores de las demás fases del traductor cómo van a ser los árboles que reciban. Se crea considerando las necesidades de dichas fases.