GNU Bison
| ||||
Bison es un generador de analizadores sintácticos, convierte una descripción para una gramática independiente del contexto en un programa en C a fin de analizar esa gramática. Es compatible con Yacc, otra herramienta de GNU que genera también analizadores léxicos. Junto a Flex Bison permite construir compiladores de lenguajes. Bison fue escrito originalmente por Robert Corbett; Richard Stallman lo hizo compatible con Yacc. El lenguaje debe estar escrito en una gramática independiente del contexto para poder ser analizada por el generador léxico Bison, lo que significa que se deben definir y detallar grupos sintácticos y proporcionar las reglas para construirlos. El sistema formal más utilizado para presentar las reglas en una gramática independiente del contexto es la Forma de Backus-Naur (BNF, por sus siglas en inglés).
Sumario
Formato de una Gramática de Bison
La forma general de una gramática de Bison es la siguiente:
%{
Declaraciones en C
%}
Declaraciones de Bison
%%
Reglas gramaticales
%%
Código C adicional
Los siguientes símbolos: %%%{%} son signos de puntuación que están en todos los archivos de gramática de Bison y se utilizan para aislar una sección de la otra.
Sección de Declaraciones en C
Las declaraciones en C definen tipos y variables utilizadas en las acciones. Se pueden utilizar comandos del preprocesador para definir macros usados en las acciones, e #include para incluir archivos de cabecera que realicen cualquiera de dichas acciones.
Sección de Declaraciones en Bison
Las declaraciones de Bison declaran los nombres de los símbolos terminales (tokens) y no terminales (agrupaciones); también describe la precedencia de operadores y los tipos de datos de los valores semánticos de varios símbolos.
Sección de Reglas Gramaticales
Las reglas gramaticales (también producciones de la gramática) definen cómo construir cada símbolo no terminal (agrupaciones) a partir de sus partes. Llevan asociadas acciones y código en C, que se ejecutan cuando el analizador encuentra las reglas correspondientes.
Sección de Código C Adicional
El código C adicional puede contener cualquier código C que desee utilizar. Frecuentemente, van la definición del analizador léxico yylex y los procedimientos invocados por las acciones en las reglas gramaticales. En general, un programa simple casi todo el resto del programa va aquí. Los comentarios (/* : : : */ )pueden aparecer en cualquiera de estas secciones.
Símbolos terminales y no terminales
En las reglas gramaticales formales para un lenguaje, cada tipo de unidad sintáctica o agrupación se identifica por un símbolo.
Símbolos No Terminales: Son aquellos que son construidos agrupando construcciones más pequeñas (Agrupaciones). Los símbolos no terminales suelen escribirse en minúsculas. Se llama grupo a un fragmento que corresponde a un solo símbolo no terminal. Las agrupaciones sintácticas de C incluyen a las expresiones, las sentencias, las declaraciones, y las definiciones de funciones.
Símbolos Terminales: Son aquellos que no pueden subdividirse. (Tipos de tokens). Se llama token a un fragmento de la entrada que corresponde a un solo símbolo terminal. Los tokens deben declararse en la sección de definiciones y suelen escribirse en mayúsculas. Los tokens de Bison se corresponden con los de C, y son: los Identificadores (Nombres de las instancias de los tipos de datos), Constantes (Numéricas y Cadenas de caracteres), las llaves de apertura y cierre de los módulos ({,} (Para Bison son los delimitadores de las acciones)) las diversas Palabras Reservadas (if, return, const, static, int, char…), Operadores Aritméticos (+,-,*,/,^) y Marcas de Puntuación (coma, punto, punto y coma, paréntesis). Existen tres formas de escribir los símbolos terminales en la gramática Bison, pero solo las dos primeras son más usuales:
Token declarado: Se escribe con un identificador (un nombre cualquiera), definiéndose con una declaración de %token. %token q
Token de carácter: Se escribe utilizando la misma sintaxis usada en C para las constantes de un carácter; por ejemplo, ‘*’ es un tipo de token de carácter. Un tipo de token de carácter no necesita ser declarado salvo que necesite especificar el tipo de datos de su valor semántico, asociatividad, o precedencia. En general, un token de carácter solo se utiliza para representar un token consistente en ese mismo carácter.
Token de cadena literal: Se escribe como un string (cadena de caracteres) constante de C; por ejemplo, "<=" es un token de cadena literal. Un token de cadena literal no necesita ser declarado salvo que se desee explicar el tipo de dato de su valor semántico. Se puede asociar el token de cadena literal con un nombre simbólico, como un alias, utilizando la declaración %token. El problema con esta forma de escribir el token es que los tokens de cadena literal no funcionan en YACC.
%token arrow "=>" 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.
Ejemplo:
char word (s)
/* Palabra reservada “char”, identificador, paréntesis abrir, identificador, paréntesis cerrar */
char s; (Declaración de variable)
/* Palabra reservada “char”, identificador, punto y coma */
{/*llave-abrir*/
return (s = ‘S’); (Sentencia de Asignación)
/* Palabra reservada `return', identificador, operador, identificador, punto y coma */
} /* llave-cerrar */
En el ejemplo anterior se define una función; tiene una declaración, y una sentencia. En la sentencia, cada `x' es una expresión y también lo es `x * x'. Cada agrupación debe poseer reglas gramaticales para especificar cómo está compuesta de construcciones más simples (símbolos no terminales). Por ejemplo, un tipo de sentencia en C es la sentencia return;, que se podría decir que está compuesta de la siguiente manera:
Una palabra clave return, una expresión (que puede ser simple (cuyos componentes no van entre paréntesis) o compuesta (cuyos componentes van entre paréntesis)) y un punto y coma (marcador de puntuación). Obviamente, por cada tipo de sentencia habrá otra regla de construcción.
