Ahora presentaremos y explicaremos tres programas de ejemplo escritos utilizando Bison; una calculadora de notación polaca inversa, una calculadora de notación algebraica (infija), y una calculadora multi-función. Los tres han sido comprobados bajo BSD Unix 4.3; cada uno produce una utilizable, aunque limitada, calculadora de escritorio.
Estos ejemplos son simples, pero las gramáticas de Bison para lenguajes de programación reales se escriben de la misma manera.
Calculadora de Notación Polaca Inversa
El primer ejemplo es el de una simple calculadora de doble precisión de
notación polaca inversa (una calculadora que utiliza operadores postfijos). Este ejemplo provee un buen punto de partida, ya que no hay problema con la precedencia de operadores. El segundo ejemplo ilustrará cómo se maneja la precendencia de operadores.
El código fuente para esta calculadora se llama
`rpcalc.y'. La extensión `.y' es una convención utilizada para los archivos de entrada de Bison.
Declaraciones para rpcalc
Aqui están las declaraciones de C y Bison para la calculadora de notación polaca inversa. Como en C, los comentarios se colocan entre `/*...*/'.
/* Calculadora de notación polaca inversa. */
%{
#define YYSTYPE double
#include <math.h>
%}
%token NUM
Las agrupaciones del "lenguaje" de rpcalc definidas aquí son la expresión (con el nombre
exp), la línea de entrada (
line), y la transcripción completa de la entrada (
input). Cada uno de estos símbolos no terminales tiene varias reglas alternativas, unidas por el puntuador `|' que se lee como "o". Las siguientes secciones explican lo que significan estas reglas.
La semántica del lenguaje se determina por las acciones que se toman cuando una agrupación es reconocida. Las acciones son el código C que aparecen entre llaves. See section Acciones.
Debe especificar estas acciones en C, pero Bison facilita la forma de pasar valores semánticos entre las reglas. En cada acción, la pseudo-variable
$$ representa el valor semántico para la agrupación que la regla va a construir. El trabajo principal de la mayoría de las acciones es la asignación de un valor para
$$. Se accede al valor semántico de los componentes de la regla con
$1,
$2, y así sucesivamente.
Explicación para input
Considere la definición de
input:
input: /* vacío */
| input line
;
Esta definición se interpreta así: "Una entrada completa es o una cadena vacía, o una entrada completa seguida por una línea de entrada". Note que "entrada completa" se define en sus propios términos. Se dice que esta definición es
recursiva por la izquierda ya que
input aparece siempre como el símbolo más a la izquierda en la secuencia. See section Reglas Recursivas.
La primera alternativa está vacía porque no hay símbolos entre los dos puntos y el primer `|'; esto significa que
input puede corresponder con una cadena de entrada vacía (sin tokens). Escribimos estas reglas de esa manera porque es legítimo escribir
Ctrl-d después de arrancar la calculadora. Es clásico poner una alternativa vacía al principio y escribir en esta el comentario `/* vacío */'.
La segunda alternativa de la regla (
input line) maneja toda la entrada no trivial. Esta significa, "Después de leer cualquier número de líneas, leer una más si es posible". La recursividad por la izquierda convierte esta regla en un bucle. Ya que la primera alternativa concuerda con la entrada vacía, el bucle se puede ejecutar cero o más veces.
La función
yyparse del analizador continúa con el procesamiento de la entrada hasta que se encuentre con un error gramatical o el analizador diga que no hay más tokens de entrada; convendremos que esto último sucederá al final del fichero.
Explicación para line
Ahora considere la definición de
line:
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
La primera alternativa es un token que es un caracter de nueva-línea; esta quiere decir que rpcalc acepta un línea en blanco (y la ignora, ya que no hay ninguna acción). La segunda alternativa es una expresión seguida de una línea nueva. Esta es la alternativa que hace que rpcalc sea útil. El valor semántico de la agrupación
exp es el valor de
$1 porque la
exp en cuestión es el primer símbolo en la alternativa. La acción imprime este valor, que es el resultado del cálculo que solicitó el usuario.
Esta acción es poco común porque no asigna un valor a
$$. Como consecuencia, el valor semántico asociado con
line está sin inicializar (su valor será impredecible). Se trataría de un error si ese valor se utilizara, pero nosotros no lo utilizaremos: una vez que rpcalc haya imprimido el valor de la línea de entrada del usuario, ese valor no se necesitará más.
Explicación para expr
La agrupación
exp tiene varias reglas, una para cada tipo de expresión. La primera regla maneja la expresiones más simples: aquellas que son solamente números. La segunda maneja una expresión de adición, que tiene el aspecto de dos expresiones seguidas de un signo más. La tercera maneja la resta, y así sucesivamente.
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
...
;
Hemos utilizado `|' para unir las tres reglas de
exp, pero igualmente podríamos haberlas escrito por separado:
exp: NUM ;
exp: exp exp '+' { $$ = $1 + $2; } ;
exp: exp exp '-' { $$ = $1 - $2; } ;
...
La mayoría de las reglas tienen acciones que computan el valor de la expresión en términos del valor de sus componentes. Por ejemplo, en la regla de la adición,
$1 hace referencia al primer componenete
exp y
$2 hace referencia al segundo. El tercer componente,
'+', no tiene un valor semántico asociado con significado, pero si tuviese alguno podría hacer referencia a este con
$3. Cuando
yyparse reconoce una expresión de suma usando esta regla, la suma de los valores de las dos subexpresiones producen el valor de toda la expresión. See section Acciones.
Usted no tiene de dar una acción para cada regla. Cuando una regla no tenga acción, por defecto Bison copia el valor de
$1 en
$$. Esto es lo que sucede en la primera regla (la que usa
NUM).
El formato mostrado aquí es la convención recomendada, pero Bison no lo requiere. Puede añadir o cambiar todos los espacios en blanco que desee. Por ejemplo, esto:
exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
expresa lo mismo que esto:
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| ...
El último, sin embargo, es mucho más legible.
