Manual de Bison - Los Conceptos de Bison

Este capítulo introduce muchos de los conceptos básicos sin los que no tendrán sentido los detalles de Bison. Si no conoce ya cómo utilizar Bison o Yacc, le sugerimos que comience por leer este capítulo atentamente.

Lenguajes y Gramáticas independientes del Contexto∞

Para que Bison analice un lenguaje, este debe ser descrito por una gramática independiente del contexto. Esto quiere decir que debe especificar uno o más grupos sintácticos y dar reglas para contruirlos desde sus partes. Por ejemplo, en el lenguaje C, un tipo de agrupación son las llamadas `expresiones'. Una regla para hacer una expresión sería, "Una expresión puede estar compuesta de un signo menos y otra expresión". Otra regla sería, "Una expresión puede ser un entero". Como puede ver, las reglas son a menudo recursivas, pero debe haber al menos una regla que lleve fuera la recursión.

El sistema formal más común de presentar tales reglas para ser leidas por los humanos es la Forma de Backus-Naur o "BNF", que fue desarrollada para especificar el lenguaje Algol 60. Cualquier gramática expresada en BNF es una gramática independiente del contexto. La entrada de Bison es en esencia una BNF legible por la máquina.

No todos los lenguajes independientes del contexto pueden ser manejados por Bison, únicamente aquellos que sean LALR(1). Brevemente, esto quiere decir que debe ser posible decir cómo analizar cualquier porción de una cadena de entrada con un solo token de preanálisis. Hablando estrictamente, esto es una descripción de una gramática LR(1), y la LALR(1) implica restricciones adicionales que son difíciles de explicar de manera sencilla; pero es raro en la práctica real que se encuentre una gramática LR(1) que no sea LALR(1). See section Conflictos Misteriosos de Reducción/Reducción∞, para más información a cerca de esto.

En las reglas gramaticales formales para un lenguaje, cada tipo de unidad sintáctica o agrupación se identifica por un símbolo. Aquellos que son construidos agrupando construcciones más pequeñas de acuerdo a reglas gramaticales se denominan símbolos no terminales; aquellos que no pueden subdividirse se denominan símbolos terminales o tipos de tokens. Denominamos token a un fragmento de la entrada que corresponde a un solo símbolo terminal, y grupo a un fragmento que corresponde a un solo símbolo no terminal.

Podemos utilizar el lenguaje C como ejemplo de qué significan los símbolos, terminales y no terminales. Los tokens de C son los identificadores, constantes (numéricas y cadenas de caracteres), y las diversas palabras reservadas, operadores aritméticos y marcas de puntuación. Luego los símbolos terminales de una gramática para C incluyen `identificador', `número', `cadena de caracteres', más un símbolo para cada palabra reservada, operador o marca de puntuación: `if', `return', `const', `static', `int', `char', `signo-más', `llave-abrir', `llave-cerrar', `coma' y muchos más. (Estos tokens se pueden subdividir en caracteres, pero eso es una cuestión léxica, no gramatical.)

Aquí hay una función simple en C subdividida en tokens:

int /* palabra reservada `int' */
cuadrado (x) /* identificador, paréntesis-abrir */
/* identificador, paréntesis-cerrar */
int x; /* palabra reservada `int', identificador, punto y coma */
{ /* llave-abrir */
return x * x; /* palabra reservada `return', identificador, */
/* asterisco, identificador, punto y coma */
} /* llave-cerrar */

Las agrupaciones sintácticas de C incluyen a las expresiones, las sentencias, las declaraciones, y las definiciones de funciones. Estas se representan en la gramática de C por los símbolos no terminales `expresión', `sentencia', `declaración' y `definición de función'. La gramática completa utiliza docenas de construcciones del lenguaje adicionales, cada uno con su propio símbolo no terminal, de manera que exprese el significado de esos cuatro. El ejemplo anterios es la definición de una función; contiene una declaración, y una sentencia. En la sentencia, cada `x' es una expresión y también lo es `x * x'.

Cada símbolo no terminal debe poseer reglas gramaticales mostrando cómo está compuesto de construcciones más simples. Por ejemplo, un tipo de sentencia en C es la sentencia return; esta sería descrita con una regla gramatical que interpretada informalmente sería así:

Una `sentencia' puede estar compuesta de una parabra clave `return', una `expresión' y un `punto y coma'.

Aquí existirían muchas otras reglas para `sentencia', una para cada tipo de sentencia en C.

Se debe distinguir un símbolo no terminal como el símbolo especial que define una declaración completa en el lenguaje. Este se denomina símbolo de arranque. En un compilador, este representa un programa completo. En el lenguaje C, el símbolo no terminal `secuencia de definiciones y declaraciones' juega este papel.

Por ejemplo, `1 + 2' es una expresión válida en C--una parte válida de un programa en C--pero no es válida como un programa en C completo. En la gramática independiente del contexto de C, esto se refleja en el hecho de que `expresión' no es el símbolo de arranque.

El analizador de Bison lee una secuencia de tokens como entrada, y agrupa los tokens utilizando las reglas gramaticales. Si la entrada es válida, el resultado final es que la secuencia de tokens entera se reduce a una sola agrupación cuyo símbolo es el símbolo de arranque de la gramática. Si usamos una gramática para C, la entrada completa debe ser una `secuencia de definiciones y declaraciones'. Si no, el analizador informa de un error de sintaxis.

De las Reglas Formales a la Entrada de Bison∞

Una gramática formal es una construcción matemática. Para definir el lenguaje para Bison, debe escribir un archivo expresando la gramática con la sintaxis de Bison: un archivo de gramática de Bison. See section Archivos de Gramática de Bison∞.

Un símbolo no terminal en la gramática formal se representa en la entrada de Bison como un identificador, similar a un identificador en C. Por convención, deberían estar en minúsculas, tales como expr, stmt o declaracion.

La representación en Bison para un símbolo terminal se llama también un tipo de token. Los tipos de tokens también se pueden representar como identificadores al estilo de C. Por convención, estos identificadores deberían estar en mayúsculas para distinguirlos de los no terminales: por ejemplo, INTEGER, IDENTIFICADOR, IF o RETURN. Un símbolo terminal que represente una palabra clave en particular en el lenguaje debería bautizarse con el nombre después de pasarlo a mayúsculas. El símbolo terminal error se reserva para la recuperación de errores. See section Símbolos, Terminales y No Terminales∞.

Un símbolo terminal puede representarse también como un caracter literal, al igual que una constante de caracter en C. Debería hacer esto siempre que un token sea simplemente un único caracter (paréntesis, signo-más, etc.): use el mismo caracter en un literal que el símbolo terminal para ese token.

Una tercera forma de representar un símbolo terminal es con una cadena de caracteres de C conteniendo varios caracteres. See section Símbolos, Terminales y No Terminales∞, para más información.

Las reglas gramaticales tienen también una expresión en la sintaxis de Bison. Por ejemplo, aquí está la regla en Bison para una sentencia return de C. El punto y coma entre comillas es un token de caracter literal, representando parte de la sintaxis de C para la sentencia; el punto y coma al descubierto, y los dos puntos, es puntuación de Bison que se usa en todas las reglas.

stmt: RETURN expr ';'
;

See section Sintaxis de las Reglas Gramaticales∞.

Valores Semánticos∞

Una gramática formal selecciona tokens únicamente por sus clasificaciones: por ejemplo, si una regla menciona el símbolo terminal `constante entera', quiere decir que cualquier constante entera es gramaticalmente válida en esa posición. El valor preciso de la constante es irrelevante en cómo se analiza la entrada: si `x+4' es gramatical entonces `x+1' o `x+3989' es igualmente gramatical.

Pero el valor preciso es muy importante para lo que significa la entrada una vez que es analizada. ¡Un compilador es inservible si no puede distinguir entre 4, 1 y 3989 como constantes en el programa! Por lo tanto, cada token en una gramática de Bison tiene ambos, un tipo de token y un valor semántico. See section Definiendo la Semántica del Lenguaje∞, para detalles.

El tipo de token es un símbolo terminal definido en la gramática, tal como INTEGER, IDENTIFICADOR o ','. Este dice todo lo que se necesita para saber decidir dónde podría aparecer válidamente el token y cómo agruparlo con los otros tokens. Las reglas gramaticales no saben nada acerca de los tokens excepto de sus tipos.

El valor semántico tiene todo el resto de información a cerca del significado del token, tal como el valor de un entero, o el nombre de un identificador. (Un token tal como ',' que es solo un signo de puntuación no necesita tener ningún valor semántico.)

Por ejemplo, un token de entrada podría clasificarse como un tipo de token INTEGER y tener el valor semántico 4. Otro token de entrada podría tener el mismo tipo de token INTEGER pero valor 3989. Cuando una regla gramatical dice que se admite un INTEGER, cualquiera de estos tokens se acepta porque cada uno es un INTEGER. Cuando el analizador acepta el token, este no pierde la pista del valor semántico del token.

Cada agrupación puede tener también un valor semántico al igual que su símbolo no terminal. Por ejemplo, en una calculadora, una expresión típicamente tiene un valor semántico que es un número. En un compilador para un lenguaje de programación, una expresión típicamente tiene un valor semántico que es una estructura en árbol describiendo el significado de la expresión.

Acciones Semánticas∞

Para que sea útil, un programa debe hacer algo más que analizar la entrada; este debe producir también alguna salida basada en la entrada. En una gramática de Bison, una regla gramatical puede tener una acción compuesta de sentencias en C. Cada vez que el analizador reconozca una correspondencia para esa regla, se ejecuta la acción. See section Acciones∞. La mayor parte del tiempo, el propósito de una acción es computar el valor semántico de la construcción completa a partir de los valores semánticos de sus partes. Por ejemplo, suponga que tenemos una regla que dice que una expresión puede ser la suma de dos expresiones. Cuando el analizador reconozca tal suma, cada una de las subexpresiones posee un valor semántico que describe cómo fueron elaboradas. La acción para esta regla debería crear un tipo de valor similar para la expresión mayor que se acaba de reconocer.

Por ejemplo, he aquí una regla que dice que una expresión puede ser la suma de dos subexpresiones:

expr: expr '+' expr { $$ = $1 + $3; }
;

La acción dice cómo producir el valor semántico de la expresión suma a partir de los valores de las dos subexpresiones.

La Salida de Bison: el Archivo del Analizador∞

Cuando ejecuta Bison, usted le da un archivo de gramática de Bison como entrada. La salida es un programa fuente en C que analiza el lenguaje descrito por la gramática. Este archivo se denomina un analizador de Bison. Tenga en cuenta que la utilidad Bison y el analizador de Bison son dos programas distintos: la utilidad Bison es un programa cuya salida es el analizador de Bison que forma parte de su programa.

El trabajo del analizador de Bison es juntar tokens en agrupaciones de acuerdo a las reglas gramaticales--por ejemplo, construir expresiones con identificadores y operadores. A medida que lo hace, este ejecuta las acciones de las reglas gramaticales que utiliza.

Los tokens provienen de una función llamada el analizador léxico que usted debe proveer de alguna manera (por ejemplo escribiéndola en C). El analizador de Bison llama al analizador léxico cada vez que quiera un nuevo token. Este no sabe qué hay "dentro" de los tokens (aunque sus valores semánticos podrían reflejarlo). Típicamente el analizador léxico construye los tokens analizando los caracteres del texto, pero Bison no depende de ello. See section La Funcion del Analizador Léxico ##yylex##∞.

El fichero del analizador de Bison es código C que define una función llamada yyparse que implementa esa gramática. Esta función no forma un programa completo en C: debe proveer algunas funciones adicionales. Una es el analizador léxico. Otra es una función de informe de errores a la que el analizador llama para informar de un error. Además, un programa completo en C debe comenzar con una función llamada main; debe facilitarla, y colocar en esta una llamada a yyparse o el analizador no será ejecutado nunca. See section Interfaz del Analizador en Lenguaje C∞.

A parte de los nombres de tipo de token y los símbolos en las acciones que escriba, todos los nombres de variable y funciones usados en el archivo del analizador de Bison comienzan con `yy' o `YY'. Esto incluye las funciones de interfaz tales como la función del analizador léxico yylex, la función de informe de errores yyerror y la propia función del analizador yyparse. Esto también incluye un gran número de identificadores utilizados para uso interno. Por lo tanto, debería evitar utilizar identificadores de C que comiencen con `yy' o `YY' en el archivo de la gramática de Bison excepto para aquellos definidos en este manual.

Etapas en el Uso de Bison∞

El proceso real de diseño de lenguajes utilizando Bison, desde la especificación de la gramática hasta llegar a un compilador o intérprete funcional, se compone de estas etapas:

1. Especificar formalmente la gramática en un formato que reconozca Bison (see section Archivos de Gramática de Bison∞). Para cada regla gramatical en el lenguaje, describir la acción que se va a tomar cuando una instancia de esa regla sea reconocida. La acción se descibe por una secuencia de sentencias en C.
2. Escribir un analizador léxico para procesar la entrada y pasar tokens al analizador sintáctico. El analizador léxico podría escribirse a mano en C (see section La Funcion del Analizador Léxico ##yylex##∞). Este puede también generarse utilizando Lex, pero el uso de Lex no se trata en este manual.
3. Escibir una función de control que llame al analizador producido por Bison.
4. Escribir las rutinas de infome de errores.

Para hacer que este código fuente escrito se convierta en un programa ejecutable, debe seguir estos pasos:

1. Ejecutar Bison sobre la gramática para producir el analizador.
2. Compilar el código de salida de Bison, al igual que cualquier otro fichero fuente.
3. Enlazar los ficheros objeto para producir el producto final.

El Formato Global de una Gramática de Bison∞

El fichero de entrada para la utilidad Bison es un archivo de gramatica de Bison. La forma general de una gramática de Bison es la siguiente:

%{
declaraciones en C
%}

Declaraciones de Bison


Código C adicional

Los `%%', `%{' y `%}' son signos de puntuación que aparecen en todo archivo de gramática de Bison para separar las secciones.

Las declaraciones en C podrían definir tipos y variables utilizadas en las acciones. Puede también usar comandos del preprocesador para definir macros que se utilicen ahí, y utilizar #include para incluir archivos de cabecera que realicen cualquiera de estas cosas.

Las declaraciones de Bison declaran los nombres de los símbolos terminales y no terminales, y también podrían describir la precedencia de operadores y los tipos de datos de los valores semánticos de varios símbolos.

Las reglas gramaticales definen cómo construir cada símbolo no terminal a partir de sus partes.

El código C adicional puede contener cualquier código C que desee utilizar. A menudo suele ir la definición del analizador léxico yylex, más subrutinas invocadas por las acciones en la reglas gramaticales. En un programa simple, todo el resto del programa puede ir aquí.