Informatico

¿Qué es Bison?
GNU bison es un programa generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos, se usa normalmente acompañado de flex aunque los analizadores léxicos se pueden también obtener de otras formas.
Bison convierte la descripción formal de un lenguaje, escrita como una gramática libre decontexto LALR, en un programa en C, C++, o Java que realiza análisis sintáctico. Es utilizado para crear analizadores para muchos lenguajes, desde simples calculadoras hasta lenguajes complejos. Para utilizar Bison, es necesaria experiencia con el la sintaxis usada para describir gramáticas.
GNU bison tiene compatibilidad con Yacc, todas las gramáticas bien escritas para Yacc, funcionan en Bison sinnecesidad de ser modificadas. Cualquier persona que esté familiarizada con Yacc podría utilizar Bison sin problemas.
Bison fue escrito en un principio por Robert Corbett; Richard Stallman lo hizo compatible con Yacc y Wilfred Hansen de la Carnegie Mellon University añadió soporte para literales multicaracter y otras características.

Desarrollo
Al Bison, se le entra un fichero con extensión".y" que contiene la especificación de una gramática y genera una función en C++ que reconoce cadenas validas de esa gramática.
El fichero para la especificación de la gramática contiene 4 partes, dividas por los delimitadores como se muestra a continuación.

%{
Prologo
%}
Declaraciones del Bison
%%
Reglas de la gramática
%%
Epilogo

Prologo
Se realizan las definiciones de lasmacros, las declaraciones de las funciones y las declaraciones de las variables que van a ser utilizadas posteriormente.
Ejemplo de Macros definidas en esta sección es la que se utiliza para especificar el tipo de datos con que se va a trabajar, se define la directiva: #difine YYSTYPE tipo, si no se especifica, el tipo que toma por defecto es int.

Declaraciones del Bison
Se declaran los símbolosterminales y no terminales que hagan falta, se definen la prioridad de los operadores, etc.
NOTA: Las dos primeras secciones son opcionales.

Reglas de la gramática
En esta parte se definen las reglas de la gramática, al menos debe de existir una, y siempre después del delimitador %% el cual es obligatorio (aunque sea la primera sección que aparezca en el fichero).

Epilogo
Se definenfunciones en C++ que van a ser copiadas exactamente a como se definan al final del fichero generado por Bison, de la misma forma que las declaraciones del prologo son copiadas al inicio del mismo fichero generado por el Bison.
Nota: Esta sección también es opcional.

Símbolos terminales y no terminales
En Bison se declaran los Token, que serian los no terminales de la gramática. Hay tres formas dedeclarar Tokens.
1. %token
2. Un carácter entre comillas simples, este no es necesario declararlo, se puede utilizar directamente en la gramática y se reconoce como Token, si se desea darle algún valor semántica, entonces si se tendría que declarar.
3. %left o %right para definir la asociatividad de los operadores.

La Sintaxis de las reglas de la Gramática
: ;
Lo que se encuentra en laparte izquierda de ":" es el no Terminal que comienza la regla, lo que está a la derecha lo que genera esa regla y el ";" es lo que define el final de la producción.
Para asociarle una semántica a una determinada regla se pone un código en C++ entre llaves.
Para poner múltiples reglas asociadas con un no Terminal se utiliza "|" para obtener la separación.
Ejemplo:
exp: NUM {$$ = $1;}
| exp'+' exp {$$ = $1 + $3;}
| exp '-' exp {$$ = $1 - $3;}
| exp '*' exp {$$ = $1 * $3;}
| exp '/' exp {$$ = $1 / $3;}
| '(' exp ')' {$$ = $2;}
;

Declaraciones del Bison
Como se mencionó anteriormente, en esta parte se declaran los símbolos que se utilizan en gramática y además se definen los tipos de los valores semánticos.
Los no terminales se declaran si es necesario asociarle un...