Bison - Archivos de Gramatica de Bison (II)

Definiendo la Semántica del Lenguaje

Las reglas gramaticales para un lenguaje determinan únicamente la sintaxis. La semántica viene determinada por los valores semánticos asociados con varios tokens y agrupaciones, y por las acciones tomadas cuando varias agrupaciones son reconocidas.

Por ejemplo, la calculadora calcula bien porque el valor asociado con cada expresión es el número apropiado; ésta suma correctamente porque la acción para la agrupación `x + y' es sumar los números asociados con x e y.

Tipos de Datos para Valores Semánticos

En un programa sencillo podría ser suficiente con utilizar el mismo tipo de datos para los valores semánticos de todas las construcciones del lenguaje. Esto fue cierto en los ejemplos de calculadora RPN e infija (see section Calculadora de Notación Polaca Inversa).

Por defecto Bison utiliza el tipo int para todos los valores semánticos. Para especificar algún otro tipo, defina YYSTYPE como una macro, de esta manera:

#define YYSTYPE double

Esta definición de la macro debe ir en la sección de declaraciones en C del fichero de la gramática (see section Resumen de una Gramática de Bison).

Más de Un Tipo de Valor

En la mayoría de los programas, necesitará diferentes tipos de datos para diferentes clases de tokens y agrupaciones. Por ejemplo, una constante numérica podría necesitar el tipo int o long, mientras que una cadena constante necesita el tipo char *, y un identificador podría necesitar un puntero a la tabla de símbolos.

Para utilizar más de un tipo de datos para los valores semánticos en un analizador, Bison le pide dos cosas:

• Especificar la colección completa de tipos de datos posibles, con la declaración de Bison %union (see section La Colección de Tipos de Valores).
• Elegir uno de estos tipos para cada símbolo (terminal o no terminal) para los valores semánticos que se utilicen. Esto se hace para los tokens con la declaración de Bison %token (see section Nombres de Tipo de Token) y para las agrupaciones con la declaración de Bison %type (see section Símbolos No Terminales).

Acciones

Una acción acompaña a una regla sintáctica y contiene código C a ser ejecutado cada vez que se reconoce una instancia de esa regla. La tarea de la mayoría de las acciones es computar el valor semántico para la agrupación construida por la regla a partir de los valores semánticos asociados a los tokens o agrupaciones más pequeñas.

Una acción consiste en sentencias de C rodeadas por llaves, muy parecido a las sentencias compuestas en C. Se pueden situar en cualquier posición dentro de la regla; esta se ejecuta en esa posición. La mayoría de las reglas tienen sólo una acción al final de la regla, a continuación de todos los componentes. Las acciones en medio de una regla son difíciles y se utilizan únicamente para propósitos especiales (see section Acciones a Media Regla).

El código C en una acción puede hacer referencia a los valores semánticos de los componentes reconocidos por la regla con la construcción $n, que hace referencia al valor de la componente n-ésima. El valor semántico para la agrupación que se está construyendo es $$. (Bison traduce ambas construcciones en referencias a elementos de un array cuando copia las acciones en el fichero del analizador.)

Aquí hay un ejemplo típico:

exp: ...
| exp '+' exp
{ $$ = $1 + $3; }

Esta regla contruye una exp de dos agrupaciones exp más pequeñas conectadas por un token de signo más. En la acción, $1 y $3 hacen referencia a los valores semánticos de las dos agrupaciones exp componentes, que son el primer y tercer símbolo en el lado derecho de la regla. La suma se almacena en $$ de manera que se convierte en el valor semántico de la expresión de adición reconocida por la regla. Si hubiese un valor semántico útil asociado con el token `+', debería hacerse referencia con $2.

Si no especifica una acción para una regla, Bison suministra una por defecto: $$ = $1. De este modo, el valor del primer símbolo en la regla se convierte en el valor de la regla entera. Por supuesto, la regla por defecto solo es válida si concuerdan los dos tipos de datos. No hay una regla por defecto con significado para la regla vacía; toda regla vacía debe tener una acción explícita a menos que el valor de la regla no importe.

$n con n cero o negativo se admite para hacer referencia a tokens o agrupaciones sobre la pila antes de aquellas que empareja la regla actual. Esta es una práctica muy arriesgada, y para utilizarla de forma fiable debe estar seguro del contexto en el que se aplica la regla. Aquí hay un donde puede utilizar esto de forma fiable:

foo: expr bar '+' expr { ... }
| expr bar '-' expr { ... }
;

bar: /* vacío */
{ previous_expr = $0; }
;

Siempre que bar se utilice solamente de la manera mostrada aquí, $0 siempre hace referencia a la exp que precede a bar en la definición de foo.

Tipos de Datos de Valores en Acciones

Si ha elegido un tipo de datos único para los valores semánticos, las construcciones $$ y $n siempre tienen ese tipo de datos.

Si ha utilizado %union para especificar una variedad de tipos de datos, entonces debe declarar la elección de entre esos tipos para cada símbolo terminal y no terminal que puede tener un valor semántico. Entonces cada vez que utilice $$ o $n, su tipo de datos se determina por el símbolo al que hace referencia en la regla. En este ejemplo,

exp: ...
| exp '+' exp
{ $$ = $1 + $3; }

$1 y $3 hacen referencia a instancias de exp, de manera que todos ellos tienen el tipo de datos declarado para el símbolo no terminal exp. Si se utilizase $2, tendría el tipo de datos declarado para el símbolo terminal '+', cualquiera que pudiese ser.

De forma alternativa, puede especificar el tipo de datos cuando se hace referencia al valor, insertando `<tipo>' después del `$' al comienzo de la referencia. Por ejemplo, si ha definido los tipos como se muestra aquí:

%union {
int tipoi;
double tipod;
}

entonces puede escribir $<tipoi>1 para hacer referencia a la primera subunidad de la regla como un entero, o $<tipod>1 para referirse a este como un double.

Acciones a Media Regla

Ocasionalmente es de utilidad poner una acción en medio de una regla. Estas acciones se escriben como las acciones al final de la regla, pero se ejecutan antes de que el analizador llegue a reconocer los componentes que siguen.

Una acción en mitad de una regla puede hacer referencia a los componentes que la preceden utilizando $n, pero no puede hacer referencia a los componentes subsecuentes porque esta se ejecuta antes de que sean analizados.

Las acciones en mitad de una regla por sí mismas cuentan como uno de los componentes de la regla. Esto produce una diferencia cuando hay otra acción más tarde en la misma regla (y normalmente hay otra al final): debe contar las acciones junto con los símbolos cuando quiera saber qué número n debe utilizar en $n.

La acción en la mitad de una regla puede también tener un valor semántico. La acción puede establecer su valor con una asignación a $$, y las acciones posteriores en la regla pueden hacer referencia al valor utilizando $n. Ya que no hay un símbolo que identifique la acción, no hay manera de declarar por adelantado un tipo de datos para el valor, luego debe utilizar la construcción `$<...>' para especificar un tipo de datos cada vez que haga referencia a este valor.

No hay forma de establecer el valor de toda la regla con una acción en medio de la regla, porque las asignaciones a $$ no tienen ese efecto. La única forma de establecer el valor para toda la regla es con una acción corriente al final de la regla.

Aquí hay un ejemplo tomado de un compilador hipotético, manejando una sentencia let de la forma `let (variable) sentencia' y sirve para crear una variable denominada variable temporalmente durante la duración de la sentencia. Para analizar esta construcción, debemos poner variable dentro de la tabla de símbolos mientras se analiza sentencia, entonces se quita después. Aquí está cómo se hace:

stmt: LET '(' var ')'
{ $<contexto>$ = push_contexto ();
declara_variable ($3); }
stmt { $$ = $6;
pop_contexto ($<contexto>5); }

Tan pronto como `let (variable)' se haya reconocido, se ejecuta la primera acción. Esta guarda una copia del contexto semántico actual (la lista de variables accesibles) como su valor semántico, utilizando la alternativa contexto de la union de tipos de datos. Entonces llama a declara_variable para añadir una nueva variable a la lista. Una vez que finalice la primera acción, la sentencia inmersa en stmt puede ser analizada. Note que la acción en mitad de la regla es la componente número 5, así que `stmt' es la componente número 6.

Después de que la sentencia inmersa se analice, su valor semántico se convierte en el valor de toda la sentencia let. Entonces el valor semántico de la acción del principio se utiliza para recuperar la lista anterior de variables. Esto hace quitar la variable temporal del let de la lista de manera que esta no parecerá que exista mientras el resto del programa se analiza.

Tomar una acción antes de que la regla sea reconocida completamente a veces induce a conflictos ya que el analizador debe llegar a un análisis para poder ejecutar la acción. Por ejemplo, las dos reglas siguientes, sin acciones en medio de ellas, pueden coexistir en un analizador funcional porque el analizador puede desplazar el token de llave-abrir y ver qué sigue antes de decidir si hay o no una declaración:

compuesta: '{' declaracion sentencias '}'
| '{' sentencias '}'
;

Pero cuando añadimos una acción en medio de una regla como a continuación, la regla se vuelve no funcional:

compuesta: { prepararse_para_variables_locales (); }
'{' declaraciones sentencias '}'
| '{' sentencias '}'
;

Ahora el analizador se ve forzado a decidir si ejecuta la acción en medio de la regla cuando no ha leído más alla de la llave-abrir. En otras palabras, debe decidir si utilia una regla u otra, sin información suficiente para hacerlo correctamente. (El token llave-abrir es lo que se llama el token de preanálisis en este momento, ya que el analizador está decidiendo aún qué hacer con él. See section Tokens de Preanálisis.)

Podría pensar que puede corregir el problema poniendo acciones idénticas en las dos reglas, así:

compuesta: { prepararse_para_variables_locales (); }
'{' declaraciones sentencias '}'
| { prepararse_para_variables_locales (); }
'{' sentencias '}'
;

Pero esto no ayuda, porque Bison no se da cuenta de que las dos acciones son idénticas. (Bison nunca intenta comprender el código C de una acción.)

Si la gramática es tal que una declaración puede ser distinguida de una sentencia por el primer token (lo que es cierto en C), entonces una solución que funciona es poner la acción después de la llave-abrir, así:

compuesta: '{' { prepararse_para_variables_locales (); }
declaraciones sentencias '}'
| '{' sentencias '}'
;

Ahora el primer token de la siguiente declaración o sentencia, que en cualquier caso diría a Bison la regla a utilizar, puede hacerlo aún.

Otra solución es introducir la acción dentro de un símbolo no terminal que sirva como una subrutina:

subrutina: /* vacío */
{ prepararse_para_variables_locales (); }
;

compuesta: subrutina
'{' declaraciones sentencias '}'
| subrutina
'{' sentencias '}'
;

Ahora Bison puede ejecutar la acción en la regla para subrutina sin decidir qué regla utilzará finalmente para compuesta. Note que la acción está ahora al final de su regla. Cualquier acción en medio de una regla puede convertirse en una acción al final de la regla de esta manera, y esto es lo que Bison realmente hace para implementar acciones en mitad de una regla.