De Wikipedia, la enciclopedia libre
  (Redirigido desde GNU bison )
Saltar a navegación Saltar a búsqueda
GNU Bison
Heckert GNU blanco.svg
Autor (es) original (es)Robert Corbett
Desarrollador (es)El proyecto GNU
Versión inicialJunio ​​de 1985 ; Hace 35 años [1] ( 1985-06 )
Lanzamiento estable
3.7.5 / 24 de enero de 2021 ; Hace 2 meses [2] ( 24/01/2021 )
Repositorio
Edita esto en Wikidata
Escrito enC y m4
Sistema operativoTipo Unix
TipoGenerador de analizador
LicenciaGPL
Sitio webwww .gnu .org / software / bison / Edita esto en Wikidata

GNU Bison , comúnmente conocido como Bison, es un generador de analizador que forma parte del Proyecto GNU . Bison lee una especificación de un lenguaje libre de contexto , advierte sobre cualquier ambigüedad de análisis y genera un analizador (ya sea en C , C ++ o Java ) 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 ningún compilador específico. Bison genera por defecto analizadores LALR (1) pero también puede generar analizadores LR , IELR (1) y GLR canónicos .[3]

En el modo POSIX , Bison es compatible con Yacc , pero también tiene varias extensiones sobre este programa anterior, que incluyen:

  • generación de contraejemplos de conflictos,
  • seguimiento de ubicación (por ejemplo, archivo, línea, columna),
  • mensajes de error de sintaxis ricos e internacionalizables en los analizadores generados,
  • generación de errores de sintaxis personalizables,
  • analizadores reentrantes,
  • Push parsers, con autocompletado,
  • soporte para referencias nombradas,
  • varios tipos de informes (gráficos, XML) en el analizador generado,
  • soporte para varios lenguajes de programación,
  • etc.

Flex , un analizador léxico automático , se usa a menudo con Bison, para tokenizar los datos de entrada y proporcionar tokens a Bison. [4]

Bison fue escrito originalmente por Robert Corbett en 1985. [1] Más tarde, en 1989, Robert Corbett lanzó otro generador de analizador sintáctico llamado Berkeley Yacc . Bison se hizo compatible con Yacc por Richard Stallman . [5]

Bison es software libre y está disponible bajo la Licencia Pública General GNU , con una excepción (discutida a continuación) que permite que su código generado se use sin activar los requisitos de copyleft de la licencia.

Algunas características de Bison [ editar ]

Generación de contraejemplos [ editar ]

Un tema delicado con los generadores de analizadores sintácticos LR es la resolución de conflictos (cambiar / reducir y reducir / reducir conflictos). La resolución de conflictos generalmente requiere el análisis del autómata del analizador como se describe en los informes, y cierta experiencia por parte del usuario. Los contraejemplos ayudan a comprender rápidamente algunos conflictos e incluso pueden demostrar que el problema es que la gramática es realmente ambigua.

Por ejemplo, en una gramática que sufre el infame problema de colgar el else , informa Bison

doc / if-then-else.y: advertencia : cambiar / reducir el conflicto en el token "else" [- Wcounterexamples ] Ejemplo: "if" expr "luego"  "if" expr "luego" stmt  •  "else" stmt Derivación de cambio if_stmt  ↳ "if" expr "luego"  stmt  ↳  if_stmt  ↳ "if" expr "luego" stmt  •  "else" stmt Ejemplo: "if" expr "then"  "if" expr "then" stmt  •  "else" stmt Reducir la derivación if_stmt  ↳ "if" expr "entonces"  stmt  "else" stmt  ↳  if_stmt  ↳ "if" expr "entonces" stmt  •

Reentrada [ editar ]

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 se %define api.puredebe utilizar la declaración . Se pueden encontrar más detalles sobre la reentrada de Bison en el manual de Bison. [6]

Varios idiomas de salida [ editar ]

Bison puede generar código para C , C ++ y Java . [7] También está disponible un backend experimental para D. [8]

Para usar el analizador generado por Bison desde otros idiomas , se puede usar una herramienta de enlace de idiomas como SWIG .

Licencia y distribución del código generado [ editar ]

Debido a que Bison genera código fuente que a su vez se agrega al código fuente de otros proyectos de software, plantea algunas preguntas simples pero interesantes sobre derechos de autor.

No se requiere una licencia compatible con GPL [ editar ]

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 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 salida también tenían licencia bajo la GPL, debido a la inclusión de la función yyparse () del código fuente original en la salida.

Distribución de paquetes usando Bison [ editar ]

Los proyectos de software libre que utilizan Bison pueden tener la opción de distribuir el código fuente que su proyecto alimenta a Bison o el código C resultante creado por Bison. Ambos son suficientes para que un destinatario pueda compilar el código fuente del proyecto. Sin embargo, distribuir solo la entrada conlleva el menor 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 humanos ni por humanos; su propósito es ingresar directamente en un compilador C.

Estos problemas se pueden evitar distribuyendo tanto los archivos de entrada como el código generado. La mayoría de la gente compilará usando el código generado, no diferente de cualquier otro paquete de software, pero cualquiera que quiera modificar el componente del analizador puede modificar los archivos de entrada primero 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 revisiones . Los archivos solo se generan al realizar un lanzamiento.

Algunas licencias, como la GPL , requieren que el código fuente esté en " la forma preferida del trabajo para realizar modificaciones ". Los proyectos con GPL que utilizan Bison deben distribuir los archivos que son la entrada para Bison. Por supuesto, también pueden incluir los archivos generados.

Utilice [ editar ]

Debido a que Bison fue escrito como un reemplazo de Yacc, y es en gran parte compatible, el código de muchos proyectos que usan Bison podría igualmente incorporarse a 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 "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, que usan herramientas de desarrollo de software libre y distribuyen código que está destinado a ser incluido en Bison o en un paquete compatible con Bison.

  • El shell Bash usa una gramática yacc para analizar la entrada del comando.
  • Bison genera el analizador gramatical propio de Bison. [11]
  • CMake usa varias gramáticas de Bison. [12]
  • GCC comenzó usando Bison, pero cambió a un analizador sintáctico de descenso recursivo escrito a mano para C ++ en 2004 (versión 3.4), [13] y para C y Objective-C en 2006 (versión 4.1) [14]
  • El lenguaje de programación Go (GC) usaba Bison, pero cambió a un escáner y analizador escritos a mano en la versión 1.5. [15]
  • LilyPond requiere que Bison genere su analizador. [dieciséis]
  • MySQL [17]
  • GNU Octave usa un analizador generado por Bison. [18]
  • Perl 5 usa un analizador generado por Bison a partir de 5.10. [19]
  • El lenguaje de programación PHP (Zend Parser).
  • PostgreSQL [20]
  • Ruby MRI , la implementación de referencia del lenguaje de programación Ruby , se basa en una gramática de Bison. [21]
  • syslog-ng usa varias gramáticas de Bison ensambladas juntas. [22]

Un ejemplo completo de analizador reentrante [ editar ]

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 abstracto . Los siguientes dos archivos 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 * /  valor int ;  / * / <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 numérico * @return La expresión o NULL en caso de no haber memoria * / SExpression  * createNumber ( valor int  );/ ** * @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 memoria * / SExpression  * createOperation ( EOperationType  tipo ,  SExpression  * izquierda ,  SExpression  * derecha );/ ** * @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  "Expression.h"#include  <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 )); if  ( b  ==  NULL )  return  NULL ; b -> tipo  =  eVALUE ;  b -> valor  =  0 ; b -> izquierda  =  NULO ;  b -> derecha  =  NULO ; volver  b ; }SExpression  * createNumber ( int  valor ) {  SExpression  * b  =  allocateExpression (); if  ( b  ==  NULL )  return  NULL ; b -> tipo  =  eVALUE ;  b -> valor  =  valor ; volver  b ; }SExpression  * createOperation ( tipo EOperationType  , SExpression * izquierda , SExpression * derecha ) { SExpression * b = allocateExpression ();         if  ( b  ==  NULL )  return  NULL ; b -> tipo  =  tipo ;  b -> izquierda  =  izquierda ;  b -> derecha  =  derecha ; volver  b ; }void  deleteExpression ( SExpression  * b ) {  if  ( b  ==  NULL )  return ; 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  "Expression.h"#include  "Parser.h"#include  <stdio.h>% }% Opción  archivo_salida = "Lexer.c"  cabecera - archivo = "Lexer.h" % opción de  advertir a  NODEFAULT% option  reentrant  noyywrap  never - sustantivo interactivoistd  % option bison - bridge %%[  \ r \ n \ t ] *  {  continuar ;  / * Omitir espacios en blanco. * /  } [ 0-9 ] +  {  sscanf ( yytext ,  "% d" ,  & yylval -> valor );  devuelve  TOKEN_NUMBER ;  }"*"  {  return  TOKEN_STAR ;  } "+"  {  return  TOKEN_PLUS ;  } "("  {  return  TOKEN_LPAREN ;  } ")"  {  return  TOKEN_RPAREN ;  }.  {  continuar ;  / * Ignora los caracteres inesperados. * / }%%int  yyerror ( const  char  * msg )  {  fprintf ( stderr ,  "Error:% s \ n " ,  msg );  return  0 ; }

Los nombres de los tokens suelen ser neutrales: "TOKEN_PLUS" y "TOKEN_STAR", no "TOKEN_ADD" y "TOKEN_MULTIPLY". Por ejemplo, si tuviéramos que admitir el unario "+" (como en "+1"), sería incorrecto nombrar esto "+" "TOKEN_ADD". En un lenguaje como C, "int * ptr" denota la definición de un puntero, no un producto: sería incorrecto nombrar esto "*" "TOKEN_MULTIPLY".

Dado que los tokens son proporcionados por 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 Bison % union .

Dado que en este ejemplo usamos 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 mediante declaraciones Bison % lex-param y % parse-param . [24]

% {/ * * Archivo Parser.y * Para generar el analizador ejecute: "bison Parser.y" * /#include  "Expression.h"#include  "Parser.h"#include  "Lexer.h"int  yyerror ( expresión SExpression  ** , escáner yyscan_t , const char * msg ) { / * Agregar rutina de manejo de errores según sea necesario * / }       % }% código  requiere  {  typedef  void *  yyscan_t ; }% de salida  "Parser.c" % define  "Parser.h"% define  api . pure % lex - param  {  yyscan_t  scanner  } % parse - param  {  SExpression  ** expression  } % parse - param  {  yyscan_t  scanner  }% union  {  valor int  ; 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 " + ". * / % restante  "+" % restante  "*"%%entrada  :  expr  {  * expresión  =  $ 1 ;  }  ;expr  :  expr [ L ]  "+"  expr [ R ]  {  $$  =  createOperation (  eADD ,  $ L ,  $ R  );  }  |  expr [ L ]  "*"  expr [ R ]  {  $$  =  createOperation (  eMULTIPLY ,  $ L ,  $ R  );  }  |  "("  expr [ E ]  ")"  {  $$  =  $ E;  }  |  "número"  {  $$  =  createNumber ( $ 1 );  }  ;%%

El código necesario para obtener el árbol de sintaxis utilizando el analizador generado por Bison y el analizador generado por flex es el siguiente.

/ * * archivo main.c * /#include  "Expression.h"#include  "Parser.h"#include  "Lexer.h"#include  <stdio.h>int  yyparse ( expresión SExpression  ** , escáner yyscan_t );  SExpression  * getAST ( const  char  * expr ) {  SExpression  * expresión ;  yyscan_t  escáner ;  Estado YY_BUFFER_STATE  ; if  ( yylex_init ( & scanner ))  {  / * no se pudo inicializar * /  return  NULL ;  } state  =  yy_scan_string ( expr ,  escáner ); if  ( yyparse ( & expression ,  scanner ))  {  / * error al analizar * /  return  NULL ;  } yy_delete_buffer ( estado ,  escáner ); yylex_destroy ( escáner );  expresión de retorno ; }int  evaluar ( SExpression  * e ) {  switch  ( e -> type )  {  case  eVALUE :  return  e -> value ;  case  eMULTIPLY :  return  evaluar ( e -> izquierda )  *  evaluar ( e -> derecha );  case  eADD :  return  evaluar ( e -> izquierda )  +  evaluar (e -> derecha );  predeterminado :  / * no debería estar aquí * /  return  0 ;  } }int  main ( void ) {  char  prueba []  =  "4 + 2 * 10 + 3 * (5 + 1)" ;  SExpression  * e  =  getAST ( prueba );  int  resultado  =  evaluar ( e );  printf ( "El resultado de '% s' es% d \ n " ,  prueba ,  resultado );  deleteExpression ( e );  return  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 -ansiprueba :  $ ( ARCHIVOS ) $ ( CC )  $ ( CFLAGS )  $ ( ARCHIVOS ) -o pruebaLexer.c :  Lexer . lflex Lexer.lParser.c :  Analizador . y  Lexer . Cbison Parser.yclean :	rm -f * .o * ~ Lexer.c Lexer.h Parser.c Parser.h test

Ver también [ editar ]

  • Berkeley Yacc (byacc): otro software gratuito que reemplaza a Yacc y comparte el mismo autor que GNU Bison

Referencias [ editar ]

  1. ↑ a b Corbett, Robert Paul (junio de 1985). Semántica estática y recuperación de errores del compilador (Ph.D.). Universidad de California, Berkeley . DTIC ADA611756 .
  2. ^ "Bison 3.7.5 lanzado [estable]" .
  3. ^ Manual de bisonte: Introducción.
  4. ^ Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.
  5. ^ "AUTORES" . bison.git. GNU Savannah . Consultado el 26 de agosto de 2017 .
  6. ^ Manual de bisonte: un analizador puro (reentrante)
  7. ^ Manual de bisonte: resumen de la declaración de bisonte
  8. ^ https://savannah.gnu.org/forum/forum.php?forum_id=9639 Bison 3.5 lanzado
  9. ^ Manual de Bison: Condiciones para usar Bison
  10. ^ Un archivo de código fuente, parse-gram.c, que incluye la excepción
  11. ^ "parse-gram.y" . bison.git. GNU Savannah . Consultado el 29 de julio de 2020 .
  12. ^ "LexerParser en CMake" . github.com .
  13. ^ Cambios, nuevas funciones y correcciones de la serie de versiones GCC 3.4
  14. ^ Cambios, nuevas funciones y correcciones de la serie de versiones GCC 4.1
  15. ^ Definición de la gramática de Golang
  16. ^ https://git.savannah.gnu.org/cgit/lilypond.git/tree/lily/parser.yy
  17. ^ https://www.safaribooksonline.com/library/view/flex-bison/9780596805418/ch04.html
  18. ^ http://octave.org/doxygen/4.0/d5/d60/oct-parse_8cc_source.html
  19. ^ "¿Qué hay de nuevo en perl 5.10.0?" . perl.org.
  20. ^ "La etapa del analizador" . postgresql.org.
  21. ^ "Analizador de resonancia magnética Ruby" . github.com .
  22. ^ "Analizador XML de syslog-ng" . github.com .
  23. ^ a b Manual Flex: Escáneres C con analizadores de bisontes Archivado el 17 de diciembre de 2010 en la Wayback Machine.
  24. ^ Manual de Bison: Convenciones de llamada para analizadores puros

Lectura adicional [ editar ]

  • Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.

Enlaces externos [ editar ]

  • Sitio web del proyecto GNU
    • Manual
  • Proyecto Bison en GNU Savannah
  • Entrada en el directorio de software libre
  • Elementos internos de los analizadores sintácticos de C generados por GNU Bison
  • Cómo descargar e instalar Bison (GNU Parser Generator) en Linux
  • Binarios de Win32 por GnuWin32 (versión 2.4.1)