Bison toma como entrada la especificación de una gramática independiente del contexto y produce una función en lenguaje C que reconoce las instancias correctas de la gramática.
El archivo de entrada de la gramática de Bison tiene un nombre que finaliza por convención en `.y'.
Resumen de una Gramática de Bison
Un archivo de gramática de Bison tiene cuatro secciones principales, mostradas aquí con los delimitadores apropiados:
%{
Declaraciones en C
%}
Declaraciones en Bison
Código C adicional
Los comentarios encerrados entre `/* ... */' pueden aparecer en cualquiera de las secciones.
La Sección de Declaraciones en C
La sección de declaraciones en C contiene definiciones de macros y declaraciones de funciones y variables que se utilizan en las acciones en las reglas de la gramática. Estas se copian al principio del archivo del analizador de manera que precedan la definición de
yyparse. Puede utlilizar `#include' para obtener las declaraciones de un archivo de cabecera. Si no necesita ninguna declaración en C, puede omitir los delimitadores `%{' y `%}' que delimitan esta sección.
La Sección de Declaraciones de Bison
La sección de declaraciones de Bison contiene declaraciones que definen símbolos terminales y no terminales, especifica la precedencia, etc. En algunas gramáticas simples puede que no necesite ninguna de las declaraciones. See section Declaraciones de Bison.
La Sección de Reglas Gramaticales
La sección de las
reglas gramaticales contiene una o más reglas gramaticales, y nada más. See section Sintaxis de las Reglas Gramaticales.
Debe haber siempre al menos una regla gramatical, y el primer `
' que los separa de las reglas gramaticales.
El analizador de Bison en sí contiene muchas variables estáticas cuyos nombres comienzan con `yy' y muchas macros cuyos nombres comienzan con `YY'. Es una buena idea evitar el uso de cualquiera de estos nombres (excepto aquellos documentados en este menual) en la sección de código C adicional del archivo de la gramática.
Símbolos, Terminales y No Terminales
Los
símbolos en las gramáticas de Bison representan las clasificaciones gramaticales del lenguaje.
Un
símbolo terminal (también conocido como un
tipo de token) representa una clase de tokens equivalentes sintácticamente. Usted utiliza el símbolo en las reglas de la gramática para indicar que está permitido un token en esa clase. El símbolo se representa en el analizador de Bison por un código numérico, y la función
yylex devuelve un código de tipo de token para indicar qué tipo de token se ha leído. Usted no necesita conocer cual es el valor del código; puede utilizar el símbolo para representarlo.
Un
símbolo no terminal representa una clase de agrupaciones sintácticamente equivalentes. El nombre del símbolo se utiliza para escribir las reglas gramaticales. Por convención, todos deberían escribirse en minúsculas.
Los nombres de los símbolos pueden contener letras, dígitos (no al principio), subrayados y puntos. Los puntos tienen sentido únicamente en no-terminales.
Hay tres maneras de escribir símbolos terminales en la gramática:
- Un tipo de token designado se escribe con un identifiacador, de la misma manera que un identificador en C. Por convención, debería estar todo en mayúsculas. Cada uno de estos nombres debe definirse con una declaración de Bison tal como %token. See section Nombres de Tipo de Token.
- Un tipo de token de caracter (o token de caracter literal) se escribe en la gramática utilizando la misma sintaxis usada en C para las constantes de un caracter; por ejemplo, '+' es un tipo de token de caracter. Un tipo de token de caracter no necesita ser declarado a menos que necesite especificar el tipo de datos de su valor semántico (see section Tipos de Datos para Valores Semánticos), asociatividad, o precedencia (see section Precedencia de Operadores). Por convención, un tipo de token de caracter se utiliza únicamente para representar un token que consista de ese caracter en particular. De este modo, el tipo de token '+' se utiliza para representar el caracter `+' como un token. No hay nada que obligue a seguir esta convención, pero si no lo hace, su programa será confuso para otros lectores. Todas las secuencias usuales de escape que se utilizan en caracteres literales en C pueden ser utilizadas igualmente en Bison, pero no debe usar el caracter nulo como un caracter literal porque su codigo ASCII, el cero, es el código que yylex devuelve para el final de la entrada (see section Convención de Llamada para yylex).
- Un token de cadena literal se escribe como un string constante de C; por ejemplo, "<=" es un token de cadena literal. Un token de cadena literal no necesita ser declarado a menos que desee especificar el tipo de dato de su valor semántico (see section Tipos de Datos para Valores Semánticos), asociatividad, precedencia (see section Precedencia de Operadores). Puede asociar el token de cadena literal con un nombre simbólico como un alias, utilizando la declaración %token (see section Nombres de Tipo de Token). Si no lo hace, el analizador léxico debe recuperar el número del token para el token de cadena literal desde la tabla yytname (see section Convención de Llamada para yylex). ADVERTENCIA: los tokens de cadena literal no funcionan en YACC. Por convención, un token de cadena literal se utiliza únicamente para representar un token que consiste en esa cadena en particular. Así, debería utilizar el tipo de token "<=" para representar la cadena `<=' como un token. Bison no impone esta convención, pero si se aparta de ella, la gente que lea su programa se verá confusa. Todas las secuencias de escape utilizadas en las cadenas de literales de C pueden usarse igualmente en Bison. Un token de cadena literal debe contener dos o más caracteres; para un token que contenga un solo caracter, utilice un token de caracter (ver lo anterior).
El cómo se escoge la manera de escribir un símbolo no tiene efecto en su significado gramatical. Esto depende únicamente de dónde aparece en las reglas y cuándo la función de análisis sintáctico devuelve ese símbolo.
El valor devuelto por
yylex es siempre uno de los símbolos terminlaes (ó 0 para el fin de la entrada). Sea cual sea la manera en la que escriba el tipo de token en las reglas gramaticales, escríbala de la misma manera en la definición de
yylex. El código numérico para un tipo de token de caracter es simplemente el codigo ASCII para el caracter, así que
yylex puede utilizar la constante idéntica del caracter para generar el código requerido. Cada tipo de token denominado se convierte en una macro en C en el fichero del analizador, de manera que
yylex puede utilizar el nombre para hacer referencia al código. (Esta es la razón por la que los puntos no tienen sentido en los símbolos terminales.) See section Convención de Llamada para
yylex.
Si se define
yylex en un archivo aparte, debe prepararlo para que las definiciones de las macros de los tipos de tokens estén disponibles allí. Utilice la opción `-d' cuando ejecute Bison, de esta forma se escribirán estas definiciones de las macros en un archivo de cabecera por separado
`nombre.tab.h' que puede incluir en los otros archivos fuente que lo necesite. See section Invocando a Bison.
El símbolo
error es un símbolo terminal reservado para la recuperación de errores (see section Recuperación de Errores); no debería utilizarlo para cualquier otro propósito. En particular,
yylex nunca debería devolver este valor.
Sintaxis de las Reglas Gramaticales
Una regla gramatical de Bison tiene la siguiente forma general:
resultado: componentes...
;
donde resultado es el símbolo no terminal que describe esta regla y componentes son los diversos símbolos terminales y no terminales que están reunidos por esta regla (see section Símbolos, Terminales y No Terminales).
Por ejemplo,
exp: exp '+' exp
;
dice que dos agrupaciones de tipo
exp, con un token `+' en medio, puede combinarse en una agrupación mayor de tipo
exp.
Los espacios en blanco en las reglas son significativos únicamente para separar símbolos. Puede añadir tantos espacios en blanco extra como desee.
Distrubuídos en medio de los componentes pueden haber acciones que determinan la semántica de la regla. Una acción tiene el siguiente aspecto:
{sentencias en C}
Normalmente hay una única acción que sigue a los componentes. See section Acciones.
Se pueden escribir por separado varias reglas para el mismo resultado o pueden unirse con el caracter de barra vertical `|' así:
resultado: compoenentes-regla1...
| componentes-regla2...
...
;
Estas aún se consideran reglas distintas incluso cuando se unen de esa manera. Si los componentes en una regla están vacíos, significa que resultado puede concordar con la cadena vacía. Por ejemplo, aquí aparece cómo definir una secuencia separada por comas de cero o más agrupaciones
exp:
expseq: /* vacío */
| expseq1
;
expseq1: exp
| expseq1 ',' exp
;
Es habitual escribir el comentario `/* vacío */' en cada regla sin componentes.
Reglas Recursivas
Una regla se dice
recursiva cuando su no-terminal resultado aparezca también en su lado derecho. Casi todas las gramáticas de Bison hacen uso de la recursión, ya que es la única manera de definir una secuencia de cualquier número de cosas. Considere esta definición recursiva de una secuencia de una o más expresiones:
expseq1: exp
| expseq1 ',' exp
;
Puesto que en el uso recursivo de
expseq1 este es el símbolo situado más a la izquierda del lado derecho, llamaremos a esto
recursión por la izquierda. Por contraste, aquí se define la misma construcción utilizando
recusión por la derecha:
expseq1: exp
| exp ',' expseq1
;
Cualquier tipo de secuencia se puede definir utilizando ya sea la recursión por la izquierda o recursión por la derecha, pero debería utilizar siempre recursión por la izquierda, porque puede analizar una secuencia de elementos sin ocupar espacio de pila. La recursión por la derecha utiliza espacio en la pila de Bison en proporción al número de elementos en la secuencia, porque todos los elementos deben ser desplazados en la pila antes de que la regla pueda aplicarse incluso una única vez. See section El Algoritmo del Analizador de Bison, para una explicación adicional a cerca de esto.
La recursión
indirecta o
mutua sucede cuando el resultado de la regla no aparece directamente en su lado derecho, pero aparece en las reglas de otros no terminales que aparecen en su lado derecho.
Por ejemplo:
expr: primario
| primario '+' primario
;
primario: constante
| '(' expr ')'
;
define dos no-terminales recursivos mutuamente, ya que cada uno hace referencia al otro.
