GNU Bison , comúnmente conocido como Bison , es un generador de analizadores que forma parte del Proyecto GNU . Bison lee una especificación en la sintaxis de Bison (descrita como " BNF legible por máquina " [3] ), advierte sobre cualquier ambigüedad en el análisis y genera un analizador que lee secuencias de tokens y decide si la secuencia se ajusta a la sintaxis especificada por la gramática.
Los analizadores generados son portátiles: no requieren compiladores específicos. Bison genera de forma predeterminada analizadores LALR(1) 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 llamado Berkeley Yacc . Richard Stallman hizo que Bison fuera compatible con Yacc . [6]
Bison es software gratuito y está disponible bajo la Licencia Pública General GNU , con una excepción (que se analiza a continuación) que permite utilizar su código generado sin activar los requisitos de copyleft de la licencia.
Un tema delicado con los generadores de analizadores LR es la resolución de conflictos (cambiar/reducir y reducir/reducir conflictos). Con muchos generadores de analizadores LR, la resolución de conflictos requiere el análisis del autómata analizador, lo que exige cierta experiencia por parte del usuario.
Para ayudar al usuario a comprender los conflictos de manera más intuitiva, Bison puede generar contraejemplos automáticamente. Para gramáticas ambiguas , Bison a menudo puede incluso producir contraejemplos que muestren que la gramática es ambigua.
Por ejemplo, en una gramática que sufre el infame problema de colgar otra cosa , informa Bison
doc/if-then-else.y: advertencia : cambiar/reducir el conflicto en el token "else" [- Wcounterexamples ] Ejemplo: "si" expr "entonces" "si" expr "entonces" stmt • "else" stmt derivación de turnos if_stmt ↳ "si" expr "entonces" stmt ↳ if_stmt ↳ "si" expr "entonces" stmt • "else" stmt Ejemplo: "si" expr "entonces" "si" expr "entonces" stmt • "else" stmt Reducir la derivación if_stmt ↳ "si" expr "entonces" stmt "si no" 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 enlace de idiomas como SWIG .
Debido a que Bison genera código fuente que a su vez se agrega al código fuente de otros proyectos de software, surgen algunas preguntas simples pero interesantes sobre derechos de autor.
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 (GPL) de GNU, pero se ha agregado una excepción para que la GPL no se aplique a la salida. [9] [10]
Las versiones anteriores de Bison estipulaban que partes de su producción también tenían licencia 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 tener la opción de 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 sólo la entrada conlleva el pequeño inconveniente de que los destinatarios deben tener instalada una copia compatible de Bison para que puedan 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 ingresarlo 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 cual no es diferente de cualquier otro paquete de software, pero cualquiera que quiera modificar el componente del analizador puede modificar primero los archivos de entrada y volver a generar los archivos generados antes de compilar. Los proyectos que distribuyen ambos generalmente no tienen los archivos generados en sus sistemas de control de revisiones . Los archivos sólo se generan al realizar un lanzamiento.
Algunas licencias, como la GPL , exigen que el código fuente esté en " la forma preferida de la obra para realizar modificaciones ". Los proyectos GPL que utilizan Bison deben distribuir los archivos que son la entrada para Bison. Por supuesto, también pueden incluir los archivos generados.
Debido a que Bison fue escrito como un reemplazo de Yacc y es en gran medida compatible, el código de muchos proyectos que utilizan Bison también podría introducirse en Yacc. Esto hace que sea difícil determinar si un proyecto "utiliza" código fuente específico de Bison o no. En muchos casos, el "uso" de Bison podría sustituirse 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 verdaderamente que algunos proyectos "utilizan" Bison, ya que Yacc no sería suficiente.
La siguiente lista es de proyectos que se sabe que "utilizan" Bison en el sentido más amplio, que utilizan herramientas de desarrollo de software gratuitas y distribuyen código destinado a ser introducido en Bison o en un paquete compatible con Bison.
El siguiente ejemplo muestra cómo usar 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 y la 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 tipo ; /* /< tipo de operación */ valor entero ; /* /< válido sólo 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 valor El valor del número * @return La expresión o NULL en caso de no tener memoria */ SExpression * createNumber ( int valor ); /** * @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 escriba , SExpression * izquierda , SExpression * derecha ); /** * @brief Elimina una expresión * @param b La expresión */ void deleteExpression ( SExpression * b ); #endif /* __EXPRESIÓN_H__ *//* * Expression.c * Implementación de funciones utilizadas para construir el árbol de sintaxis. */#incluir "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 = NULO ; b -> derecha = NULO ; devolver b ; } SExpression * createNumber ( int valor ) { SExpression * b = allocateExpression (); si ( b == NULL ) devuelve NULL ; b -> tipo = eVALUE ; b -> valor = valor ; devolver b ; } SExpression * createOperation ( EOperationType tipo , SExpression * izquierda , SExpression * derecha ) { SExpression * b = allocateExpression (); si ( b == NULL ) devuelve NULL ; b -> tipo = tipo ; b -> izquierda = izquierda ; b -> derecha = derecha ; devolver b ; } void eliminarExpresión ( SExpresión * b ) { si ( b == NULL ) retorno ; eliminarExpresión ( b -> izquierda ); eliminarExpresión ( b -> derecha ); gratis ( segundo ); }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" */#incluye "Expresión.h" #incluye "Parser.h" #incluir <stdio.h> % }% opción outfile = "Lexer.c" encabezado - archivo = "Lexer.h" % opción warn nodefault % opción reentrante noyywrap nunca - nounistd interactivo % opción bisonte - puente %%[ \ r \ n \ t ] * { continuar ; /* Saltar espacios en blanco. */ } [ 0-9 ] + { sscanf ( yytext , "%d" y yylval - > valor ); devolver TOKEN_NUMBER ; } "*" { devolver TOKEN_STAR ; } "+" { regresar TOKEN_PLUS ; } "(" { devolver TOKEN_LPAREN ; } ")" { devolver TOKEN_RPAREN ; } . { continuar ; /* Ignora caracteres inesperados. */ } %%int yyerror ( SExpression ** expresión , escáner yyscan_t , 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 llamarlo "+" "TOKEN_ADD". En un lenguaje como C, "int *ptr" denota la definición de un puntero, no un producto: sería incorrecto llamar a este "*" "TOKEN_MULTIPLY".
Dado que los tokens los proporciona flex, debemos proporcionar los medios para comunicarse entre el analizador y el lexer . [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 Bison %lex-param y %parse-param . [24]
% {/* * Archivo Parser.y * Para generar el analizador ejecute: "bison Parser.y" */#incluye "Expresión.h" #incluye "Parser.h" #incluye "Lexer.h" // hace referencia a la implementación proporcionada en Lexer.l int yyerror ( SExpression ** expresión , yyscan_t scanner , const char * msg ); % }% código requiere { typedef void * yyscan_t ; } % salida "Parser.c" % define "Parser.h" % define API . puro % lex - param { escáner yyscan_t } % parse - param { SExpression ** expresión } % parse - param { escáner yyscan_t } % unión { valor int ; SExpresión * 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 " +". */ % restante "+" % restante "*" %%entrada : expr { * expresión = $1 ; } ; expr : expr [ L ] "+" expr [ R ] { $$ = crearOperación ( eADD , $L , $R ); } | expr [ L ] "*" expr [ R ] { $$ = crearOperación ( eMULTIPLY , $L , $R ); } | "(" expr [ E ] ")" { $$ = $E ; } | "número" { $$ = crearNúmero ( $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 principal.c */#incluye "Expresión.h" #incluye "Parser.h" #incluye "Lexer.h" #incluir <stdio.h> int yyparse ( SExpression ** expresión , escáner yyscan_t ); SExpresión * getAST ( const char * expr ) { SExpresión * expresión ; escáner yyscan_t ; Estado YY_BUFFER_STATE ; if ( yylex_init ( & scanner )) { /* no se pudo inicializar */ return NULL ; } estado = yy_scan_string ( expr , escáner ); if ( yyparse ( & expresión , escáner )) { /* error al analizar */ return NULL ; } yy_delete_buffer ( estado , escáner ); yylex_destroy ( escáner ); expresión de retorno ; } int evaluar ( SExpression * e ) { cambiar ( e -> tipo ) { caso eVALUE : devolver e -> valor ; caso eMULTIPLY : retorno evaluar ( e -> izquierda ) * evaluar ( e -> derecha ); caso eADD : devolver evaluar ( e -> izquierda ) + evaluar ( e -> derecha ); predeterminado : /* no debería estar aquí */ return 0 ; } } int principal ( vacío ) { prueba de caracteres [] = "4 + 2*10 + 3*(5 + 1)" ; SExpression * e = getAST ( prueba ); int resultado = evaluar ( e ); printf ( "El resultado de '%s' es %d \n " , prueba , resultado ); eliminarExpresión ( e ); devolver 0 ; } Un archivo MAKE simple para construir el proyecto es el siguiente.
# MakefileARCHIVOS = Lexer.c Parser.c Expression.c main.c CC = g++ CFLAGS = -g -ansi prueba : $( ARCHIVOS ) $( CC ) $( CFLAGS ) $( ARCHIVOS ) -o prueba Lexer.c : Lexer . Flexiono 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}