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]
Autor (es) original (es) | Robert Corbett |
---|---|
Desarrollador (es) | El proyecto GNU |
Versión inicial | Junio de 1985 [1] |
Lanzamiento estable | 3.7.6 / 9 de marzo de 2021 [2] |
Repositorio | |
Escrito en | C y m4 |
Sistema operativo | Tipo Unix |
Tipo | Generador de analizador |
Licencia | GPL |
Sitio web | www |
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 (p. Ej., 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
- Analizadores push, con autocompletado
- Soporte para referencias nombradas
- Varios tipos de informes (gráficos, XML) en el analizador generado
- Soporte para varios lenguajes de programación
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 . Richard Stallman hizo Bison compatible con Yacc . [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.
Características
Generación de contraejemplos
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
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.pure
debe utilizar la declaración . Se pueden encontrar más detalles sobre la reentrada de Bison en el manual de Bison. [6]
Idiomas de salida
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 de código generado
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
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
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.
Usar
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 utiliza 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
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 ; / * / valor int ; / * / álido> struct tagSExpression * left ; / * / struct tagSExpression * right ; / * / } 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 haber 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 / ** * @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 % }% 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 ; / * Ignorar 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 int yyparse ( expresión SExpression ** , escáner yyscan_t ); SExpression * getAST ( const char * expr ) { SExpression * expresión ; escáner yyscan_t ; 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
- Berkeley Yacc (byacc): otro software gratuito que reemplaza a Yacc y comparte el mismo autor que GNU Bison
Referencias
- ↑ 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 .
- ^ "[Bison-Announce] Bison 3.7.6 lanzado" .
- ^ Manual de bisonte: Introducción.
- ^ Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.
- ^ Manual de bisonte: un analizador puro (reentrante)
- ^ Manual de bisonte: resumen de la declaración de bisonte
- ^ https://savannah.gnu.org/forum/forum.php?forum_id=9639 Bison 3.5 lanzado
- ^ Manual de bisonte: condiciones para usar Bison
- ^ Un archivo de código fuente, parse-gram.c, que incluye la excepción
- ^ "parse-gram.y" . bison.git. GNU Savannah . Consultado el 29 de julio de 2020 .
- ^ "LexerParser en CMake" . github.com .
- ^ Cambios, nuevas funciones y correcciones de la serie de versiones GCC 3.4
- ^ Cambios, nuevas funciones y correcciones de la serie de versiones GCC 4.1
- ^ Definición de la gramática de Golang
- ^ https://git.savannah.gnu.org/cgit/lilypond.git/tree/lily/parser.yy
- ^ https://www.safaribooksonline.com/library/view/flex-bison/9780596805418/ch04.html
- ^ http://octave.org/doxygen/4.0/d5/d60/oct-parse_8cc_source.html
- ^ "¿Qué hay de nuevo en perl 5.10.0?" . perl.org.
- ^ "La etapa del analizador" . postgresql.org.
- ^ "Analizador de resonancia magnética Ruby" . github.com .
- ^ "Analizador XML de syslog-ng" . github.com .
- ^ a b Manual Flex: Escáneres C con analizadores de bisontes Archivado el 17 de diciembre de 2010 en la Wayback Machine.
- ^ Manual de Bison: Convenciones de llamada para analizadores puros
Otras lecturas
- Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.
enlaces externos
- Sitio web del Proyecto GNU
- Manual
- Proyecto Bison en GNU Savannah
- Entrada en el directorio de software libre
- Internos de analizadores 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)