GNU Bison , conocido comúnmente como Bison , es un generador de analizadores sintácticos que forma parte del Proyecto GNU . Bison lee una especificación en sintaxis Bison (descrita como " BNF legible por máquina " [3] ), advierte sobre cualquier ambigüedad en el análisis sintáctico y genera un analizador sintáctico que lee secuencias de tokens y decide si la secuencia se ajusta a la sintaxis especificada por la gramática.
Los analizadores generados son portables: no requieren ningún compilador específico. Bison genera analizadores LALR(1) de forma predeterminada , pero también puede generar analizadores canónicos LR , IELR(1) y GLR . [4]
En modo POSIX , Bison es compatible con Yacc , pero también tiene varias extensiones sobre este programa anterior, incluyendo
Flex , un analizador léxico automático , se utiliza a menudo con Bison para tokenizar datos de entrada y proporcionar tokens a Bison. [5]
Bison fue escrito originalmente por Robert Corbett en 1985. [1] Más tarde, en 1989, Robert Corbett lanzó otro generador de analizadores sintácticos llamado Berkeley Yacc . Richard Stallman hizo que Bison fuera compatible con Yacc . [6]
Bison es software libre y está disponible bajo la Licencia Pública General GNU , con una excepción (que se analiza más adelante) que permite utilizar el código generado sin activar los requisitos de copyleft de la licencia.
Un tema delicado con los generadores de analizadores sintácticos LR es la resolución de conflictos (conflictos shift/reduce y reduce/reduce). Con muchos generadores de analizadores sintácticos LR, la resolución de conflictos requiere el análisis del autómata del analizador sintáctico, lo que exige cierta experiencia por parte del usuario.
Para ayudar al usuario a comprender los conflictos de forma más intuitiva, Bison puede generar automáticamente contraejemplos. En el caso de gramáticas ambiguas , Bison puede incluso generar contraejemplos que demuestren que la gramática es ambigua.
Por ejemplo, en una gramática que sufre del infame problema de la palabra "el resto" colgando , Bison informa
doc/if-then-else.y: advertencia : conflicto de cambio/reducción en el token "else" [- Wcounterexamples ] Ejemplo: "si" expr "entonces" "si" expr "entonces" sentencia • "sino" sentencia Derivación de cambio if_stmt ↳ "si" expr "entonces" stmt ↳ if_stmt ↳ "si" expr "entonces" stmt • "sino" stmt Ejemplo: "si" expr "entonces" "si" expr "entonces" stmt • "sino" stmt Reducir la derivación if_stmt ↳ "si" expr "entonces" stmt "sino" stmt ↳ if_stmt ↳ "si" expr "entonces" stmt •
La reentrada es una característica que se ha agregado a Bison y no existe en Yacc.
Normalmente, Bison genera un analizador que no es reentrante . Para lograr la reentrada, %define api.purese debe utilizar la declaración. Se pueden encontrar más detalles sobre la reentrada de Bison en el manual de Bison. [7]
Bison puede generar código para C , C++ , D y Java . [8]
Para utilizar el analizador generado por Bison desde otros idiomas, se puede utilizar una herramienta de vinculación de idiomas como SWIG .
Dado que Bison genera código fuente que a su vez se agrega al código fuente de otros proyectos de software, plantea algunas cuestiones de derechos de autor simples pero interesantes.
El código generado por Bison incluye cantidades significativas de código del propio proyecto Bison. El paquete Bison se distribuye bajo los términos de la Licencia Pública General GNU (GPL), pero se ha añadido una excepción para que la GPL no se aplique a los resultados. [9] [10]
Las versiones anteriores de Bison estipulaban que partes de su salida también estaban licenciadas bajo la GPL, debido a la inclusión de la función yyparse() del código fuente original en la salida.
Los proyectos de software libre que utilizan Bison pueden elegir entre distribuir el código fuente que su proyecto introduce en Bison o el código C resultante generado por Bison. Ambos son suficientes para que un destinatario pueda compilar el código fuente del proyecto. Sin embargo, distribuir solo el código de entrada conlleva el pequeño inconveniente de que los destinatarios deben tener una copia compatible de Bison instalada para poder generar el código C necesario al compilar el proyecto. Y distribuir solo el código C en la salida crea el problema de hacer que sea muy difícil para los destinatarios modificar el analizador, ya que este código no fue escrito ni por un humano ni para humanos; su propósito es ser introducido directamente en un compilador de C.
Estos problemas se pueden evitar distribuyendo tanto los archivos de entrada como el código generado. La mayoría de las personas compilarán utilizando el código generado, lo mismo que ocurre con cualquier otro paquete de software, pero cualquiera que desee modificar el componente analizador puede modificar primero los archivos de entrada y volver a generar los archivos generados antes de compilar. Los proyectos que distribuyen ambos no suelen tener los archivos generados en sus sistemas de control de versiones . Los archivos solo se generan al realizar una versión.
Algunas licencias, como la GPL , exigen que el código fuente esté en " la forma preferida de la obra para realizar modificaciones en ella ". Por lo tanto, los proyectos con licencia GPL que utilizan Bison deben distribuir los archivos que son la entrada para Bison. Por supuesto, también pueden incluir los archivos generados.
Como Bison fue escrito como reemplazo de Yacc y es en gran medida compatible, el código de muchos proyectos que usan Bison podría igualmente ser utilizado en Yacc. Esto hace que sea difícil determinar si un proyecto "usa" código fuente específico de Bison o no. En muchos casos, el "uso" de Bison podría ser reemplazado trivialmente por el uso equivalente de Yacc o uno de sus otros derivados.
Bison tiene características que no se encuentran en Yacc, por lo que se puede decir que algunos proyectos realmente "usan" Bison, ya que Yacc no sería suficiente.
La siguiente lista es de proyectos que se sabe que "usan" Bison en el sentido más amplio, es decir, que utilizan herramientas de desarrollo de software libre y distribuyen código destinado a ser incorporado a Bison o a un paquete compatible con Bison.
El siguiente ejemplo muestra cómo utilizar Bison y flex para escribir un programa de calculadora simple (solo suma y multiplicación) y un programa para crear un árbol de sintaxis abstracta . Los dos archivos siguientes proporcionan la definición e implementación de las funciones del árbol de sintaxis.
/* * Expression.h * Definición de la estructura utilizada para construir el árbol de sintaxis. */ #ifndef __EXPRESSION_H__ #define __EXPRESSION_H__/** * @brief El tipo de operación */ typedef enum tagEOperationType { eVALUE , eMULTIPLY , eADD } EOperationType ; /** * @brief La estructura de la expresión */ typedef struct tagSExpression { EOperationType type ; /* /< tipo de operación */ int value ; /* /< válido solo cuando el tipo es eVALUE */ struct tagSExpression * left ; /* /< lado izquierdo del árbol */ struct tagSExpression * right ; /* /< lado derecho del árbol */ } SExpression ; /** * @brief Crea un identificador * @param value El valor del número * @return La expresión o NULL en caso de no tener memoria */ SExpression * createNumber ( int value ); /** * @brief Crea una operación * @param type El tipo de operación * @param left El operando izquierdo * @param right El operando derecho * @return La expresión o NULL en caso de no tener memoria */ SExpression * createOperation ( EOperationType type , SExpression * left , SExpression * right ); /** * @brief Elimina una expresión * @param b La expresión */ void deleteExpression ( SExpression * b ); #endif /* __EXPRESSION_H__ *//* * Expression.c * Implementación de funciones utilizadas para construir el árbol de sintaxis. */#include "Expresión.h" #incluir <stdlib.h> /** * @brief Asigna espacio para la expresión * @return La expresión o NULL si no hay suficiente memoria */ static SExpression * allocateExpression () { SExpression * b = ( SExpression * ) malloc ( sizeof ( SExpression )); si ( b == NULL ) devuelve NULL ; b -> tipo = eVALUE ; b -> valor = 0 ; b -> izquierda = NULL ; b -> derecha = NULL ; devolver b ; } SExpression * createNumber ( int valor ) { SExpression * b = allocateExpression (); si ( b == NULL ) devuelve NULL ; b -> tipo = eVALUE ; b -> valor = valor ; devolver b ; } SExpression * createOperation ( tipo EOperationType , SExpression * izquierda , SExpression * derecha ) { SExpression * b = allocateExpression (); si ( b == NULL ) devuelve NULL ; b -> tipo = tipo ; b -> izquierda = izquierda ; b -> derecha = derecha ; devolver b ; } void deleteExpression ( SExpression * b ) { si ( b == NULL ) devolver ; deleteExpression ( b -> izquierda ); deleteExpression ( b -> derecha ); libre ( b ); }Los tokens que necesita el analizador Bison se generarán mediante flex.
% {/* * Archivo Lexer.l * Para generar el analizador léxico ejecute: "flex Lexer.l" */#include "Expresión.h" #include "Analizador.h" #incluir <stdio.h> % }% opción archivo_salida = "Lexer.c" encabezado - archivo = "Lexer.h" % opción advertir nodo predeterminado % opción reentrante noyywrap nunca - interactivo nounistd % opción bisonte - puente %%[ \ r \ n \ t ] * { continuar ; /* Omitir espacios en blanco. */ } [ 0-9 ] + { sscanf ( yytext , "%d" , & yylval -> valor ); return TOKEN_NUMBER ; } "*" { devolver TOKEN_STAR ; } "+" { devolver TOKEN_PLUS ; } "(" { devolver TOKEN_LPAREN ; } ")" { devolver TOKEN_RPAREN ; } . { continuar ; /* Ignorar caracteres inesperados. */ } %%int yyerror ( SExpression ** expresión , yyscan_t escáner , const char * msg ) { fprintf ( stderr , "Error: %s \n " , msg ); devolver 0 ; } Los nombres de los tokens suelen ser neutrales: "TOKEN_PLUS" y "TOKEN_STAR", no "TOKEN_ADD" y "TOKEN_MULTIPLY". Por ejemplo, si admitiéramos el unario "+" (como en "+1"), sería incorrecto nombrar este "+" "TOKEN_ADD". En un lenguaje como C, "int *ptr" denota la definición de un puntero, no un producto: sería incorrecto nombrar este "*" "TOKEN_MULTIPLY".
Dado que los tokens son proporcionados por flex, debemos proporcionar los medios para comunicarse entre el analizador y el analizador léxico . [23] El tipo de datos utilizado para la comunicación, YYSTYPE , se establece mediante la declaración %union de Bison .
Dado que en este ejemplo utilizamos la versión reentrante de flex y yacc, nos vemos obligados a proporcionar parámetros para la función yylex , cuando se llama desde yyparse . [23] Esto se hace a través de las declaraciones %lex-param y %parse-param de Bison . [24]
% {/* * Archivo Parser.y * Para generar el analizador ejecute: "bison Parser.y" */#include "Expresión.h" #include "Analizador.h" #include "Extractor léxico.h" // hace referencia a la implementación proporcionada en Lexer.l int yyerror ( SExpression ** expresión , yyscan_t escáner , const char * msg ); % }% código requiere { typedef void * yyscan_t ; } % salida "Parser.c" % define "Parser.h" % define api . pure % lex - parámetro { yyscan_t escáner } % parse - parámetro { SExpression ** expresión } % parse - parámetro { yyscan_t escáner } % unión { int valor ; SExpression * expresión ; } % token TOKEN_LPAREN "(" % token TOKEN_RPAREN ")" % token TOKEN_PLUS "+" % token TOKEN_STAR "*" % token < valor > TOKEN_NUMBER "número" % tipo < expresión > expr /* Precedencia (creciente) y asociatividad: a+b+c es (a+b)+c: asociatividad izquierda a+b*c es a+(b*c): la precedencia de "*" es mayor que la de "+". */ % left "+" % left "*" %%entrada : expr { * expresión = $1 ; } ; expr : expr [ L ] "+" expr [ R ] { $$ = crearOperacion ( eADD , $L , $R ); } | expr [ L ] "*" expr [ R ] { $$ = crearOperacion ( eMULTIPLY , $L , $R ); } | "(" expr [ E ] ")" { $$ = $E ; } | "numero" { $$ = crearNumero ( $1 ); } ; %%El código necesario para obtener el árbol de sintaxis utilizando el analizador generado por Bison y el escáner generado por flex es el siguiente.
/* * archivo main.c */#include "Expresión.h" #include "Analizador.h" #include "Extractor léxico.h" #incluir <stdio.h> int yyparse ( SExpression ** expresión , yyscan_t escáner ); SExpression * getAST ( const char * expr ) { SExpression * expresión ; yyscan_t escáner ; YY_BUFFER_STATE estado ; if ( yylex_init ( & scanner )) { /* no se pudo inicializar */ return NULL ; } estado = yy_scan_string ( expr , escáner ); if ( yyparse ( & expresión , escáner )) { /* error de análisis */ return NULL ; } yy_delete_buffer ( estado , escáner ); yylex_destroy ( escáner ); expresión de retorno ; } int evaluar ( SExpression * e ) { switch ( e -> tipo ) { caso eVALUE : devuelve e -> valor ; caso eMULTIPLY : devuelve evaluar ( e -> izquierda ) * evaluar ( e -> derecha ); caso eADD : devuelve evaluar ( e -> izquierda ) + evaluar ( e -> derecha ); predeterminado : /* no debería estar aquí */ devuelve 0 ; } } int main ( void ) { char test [] = "4+2*10+3*(5+1)" ; SExpression * e = getAST ( test ); int result = evaluation ( e ); printf ( "El resultado de '%s' es %d \n " , test , result ); deleteExpression ( e ); return 0 ; } Un makefile simple para construir el proyecto es el siguiente.
#Archivo MakeARCHIVOS = Lexer.c Parser.c Expression.c main.c CC = g++ CFLAGS = -g -ansi prueba : $( ARCHIVOS ) $( CC ) $( CFLAGS ) $( ARCHIVOS ) -o prueba Lexer.c : Lexer.l flex Lexer.l Parser.c : Analizador . y Lexer . c bison parser.y limpio : rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h prueba .svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}