GNU bisonte

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 notación BNF (un lenguaje libre de contexto), advierte sobre cualquier ambigüedad de 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 ningún compilador específico. Bison por defecto genera analizadores LALR(1) pero también puede generar analizadores canónicos LR, IELR(1) y GLR.

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 para 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 error de sintaxis personalizable,
• Persianas de resistencia
• Empujar persianas, con autocomplesión
• Apoyo a las referencias mencionadas
• Varios tipos de informes (gráficos, XML) sobre el parser generado
• Soporte para varios idiomas de programación (C, C++, D o Java)

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

Bison fue escrito originalmente por Robert Corbett en 1985. Más tarde, en 1989, Robert Corbett lanzó otro generador de analizador llamado Berkeley Yacc. Richard Stallman hizo que Bison fuera compatible con Yacc.

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

Características

Generación de contraejemplos

Un tema delicado con los generadores de analizadores 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 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 ambigua.

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

doc/if-then-else.y: advertencia: cambio/reducir conflicto en señal "else" [-Wcounterexamples]
Ejemplo: "si" expr "entonces" "si" expr "entonces" stmt • "else" stmtDerivación de robo
 Si. "si" expr "entonces" stmt ↳ Si. ↳ "si" expr "entonces" stmt • "else" stmtEjemplo: "si" expr "entonces" "si" expr "entonces" stmt • "else" stmtReducir la derivación
 Si. "si" expr "entonces" stmt "else" stmt ↳ Si. ↳ "si" expr "entonces" stmt •

Reentrada

La reentrada es una característica que se agregó a Bison y no existe en Yacc.

Normalmente, Bison genera un analizador que no es reentrante. Para lograr la reentrada, se debe usar la declaración %define api.pure. Se pueden encontrar más detalles sobre la reentrada de Bison en el manual de Bison.

Idiomas de salida

Bison puede generar código para C, C++, D y Java.

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

Licencia y distribución del 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 de derechos de autor simples pero interesantes.

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 de GNU (GPL), pero se agregó una excepción para que la GPL no se aplique a la salida.

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.

Distribución de paquetes usando Bison

Los proyectos de software libre que usan Bison pueden tener la opción de distribuir el código fuente que su proyecto alimenta a 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 la entrada conlleva el inconveniente menor 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 por un humano ni para humanos. - su propósito es alimentar directamente a un compilador de 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 desee 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 no suelen tener los archivos generados en sus sistemas de control de revisiones. Los archivos solo se generan al hacer un lanzamiento.

Algunas licencias, como la GPL, requieren que el código fuente esté en "la forma preferida de la obra para hacerle modificaciones". 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.

Usar

Debido a que Bison se escribió como un reemplazo de Yacc y es en gran parte compatible, el código de muchos proyectos que utilizan Bison podría introducirse igualmente 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" of Bison podría reemplazarse 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 realmente 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 "utilizan" Bison en el sentido más amplio, que usan herramientas de desarrollo de software libre y distribuyen código que está destinado a ser introducido en Bison o en un paquete compatible con Bison.

• Bash shell utiliza una gramática yacc para analizar la entrada de comando.
• El propio analizador de gramática de Bison es generado por Bison.
• CMake utiliza varias gramáticas Bison.
• GCC comenzó a utilizar Bison, pero se cambió a un parser recursivo-descenso manuscrito a mano para C++ en 2004 (versión 3.4), y para C y Objective-C en 2006 (versión 4.1)
• El lenguaje de programación Go (GC) utilizó Bison, pero cambió a un escáner manuscrito a mano y analizador en la versión 1.5.
• LilyPond requiere Bison para generar su parser.
• MySQL
• GNU Octave usa un parser generado por Bison.
• Perl 5 utiliza un parser generado por Bison a partir de 5.10.
• El lenguaje de programación PHP (Zend Parser).
• PostgreSQL
• Ruby MRI, la aplicación de referencia del lenguaje de programación Ruby, se basa en una gramática Bison.
• syslog-ng utiliza varias gramáticas Bison juntas.

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 abstracta. Los siguientes dos archivos proporcionan 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 Tipo de operación */Tipodef enum tagEOperación Tipo{} eVALUE, eMULTIPLY, eADD} EOperación Tipo;* * @brief La estructura de expresión */Tipodef struct tagSExpression{} EOperación Tipo Tipo; /* / Tipo de operación realizado */ int valor; /* / realizado válido sólo cuando el tipo es eVALOR */ struct tagSExpression *izquierda; /* / Se realizó el lado izquierdo del árbol */ struct tagSExpression *derecho; /* / A la derecha del árbol */} SExpresión;* * @brief Crea un identificador * Valor @param El valor número *Retorno La expresión o NULL en caso de no memoria */SExpresión *crearNúmero()int valor);* * @brief Crea una operación * Tipo @param Tipo de operación * @param left El operado izquierdo * @param right El funcionamiento correcto *Retorno La expresión o NULL en caso de no memoria */SExpresión *crearOperación()EOperación Tipo Tipo, SExpresión *izquierda, SExpresión *derecho);* * @brief Elimina una expresión * @param b La expresión */vacío Eliminación()SExpresión *b);#endif * __EXPRESSION_H_ */

/* * Expression.c * Implementación de funciones utilizadas para construir el árbol de sintaxis. */#include "Expresión.h"#include ■stdlib.h* * @brief Asigna espacio para la expresión *Retorno La expresión o NULL si no suficiente memoria */estática SExpresión *asignar Expresión(){} SExpresión *b = ()SExpresión *)malloc()tamaño()SExpresión)); si ()b == NULL) retorno NULL; b-Tipo = eVALUE; b-valor = 0; b-izquierda = NULL; b-derecho = NULL; retorno b;}SExpresión *crearNúmero()int valor){} SExpresión *b = asignar Expresión(); si ()b == NULL) retorno NULL; b-Tipo = eVALUE; b-valor = valor; retorno b;}SExpresión *crearOperación()EOperación Tipo Tipo, SExpresión *izquierda, SExpresión *derecho){} SExpresión *b = asignar Expresión(); si ()b == NULL) retorno NULL; b-Tipo = Tipo; b-izquierda = izquierda; b-derecho = derecho; retorno b;}vacío Eliminación()SExpresión *b){} si ()b == NULL) retorno; Eliminación()b-izquierda); Eliminación()b-derecho); gratis()b);}

Los tokens que necesita el analizador Bison se generarán mediante flex.

%{}/* * Archivo Lexer.l * Para generar la carrera de analizador léxico: "flex Lexer.l" */#include "Expresión.h"#include "Parser.h"#include Identificado.h%}%Opción outfile="Lexer.c" header-archivo="Lexer.h"%Opción Warn nodefault%Opción reentrant Noywrap nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás-interactiva Nounistd%Opción Bison-puente%%[ rnt]* {} continuar; /* Skip blanks. */ }[0-9]+ {} sscanf()Yytext, "%d", "yylval-valor); retorno TOKEN_NUMBER; }"* {} retorno TOKEN_STAR; }"+" {} retorno TOKEN_PLUS; }"( {} retorno TOKEN_LPAREN; }")" {} retorno TOKEN_RPAREN; }. {} continuar; /* Ignorar caracteres inesperados. */}%%int Yunerror()SExpresión #expresión, Yyscan_t escáner, const char *msg) {} fprintf()stderr, "Error: %sn", msg); retorno 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 llamarlo "+" "FICHA_AÑADIR". En un lenguaje como C, "int *ptr" denota la definición de un puntero, no de un producto: sería incorrecto llamarlo "*" 'TOKEN_MULTIPLY'.

Dado que los tokens los proporciona flex, debemos proporcionar los medios para comunicarse entre el analizador y el lexer. El tipo de datos utilizado para la comunicación, YYSTYPE, se establece mediante la declaración de Bison %union.

Dado que en esta muestra 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. Esto se hace a través de declaraciones de Bison %lex-param y %parse-param.

%{}/* * Archivo Parser.y * Para generar la carrera de parser: "bison Parser.y" */#include "Expresión.h"#include "Parser.h"#include "Lexer.h"// referencia la implementación proporcionada en Lexer.lint Yunerror()SExpresión #expresión, Yyscan_t escáner, const char *msg);%}%código Requisitos {} Tipodef vacío* Yyscan_t;}%Producto "Parser.c"%defines "Parser.h"%definir api.puro%lex-param {} Yyscan_t escáner }%parse-param {} SExpresión #expresión }%parse-param {} Yyscan_t escáner }%sindicato {} int valor; 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■ expreso/* Precedencia (aumento) y asociación: a+b+c es (a+b)+c: izquierda asociatividad a+b*c es a+(b*c): la precedencia de "*" es superior a la de "+". */%izquierda "+"%izquierda "*%%entrada : expreso {} *expresión = 1 dólar; } ;expreso : expreso[L] "+" expreso[R] {} dólares = crearOperación() eADD, $L, $R ); } Silencio expreso[L] "* expreso[R] {} dólares = crearOperación() eMULTIPLY, $L, $R ); } Silencio "( expreso[E] ")" {} dólares = $E; } Silencio "Número" {} dólares = crearNúmero()1 dólar); } ;%%

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 "Parser.h"#include "Lexer.h"#include Identificado.hint Yyparse()SExpresión #expresión, Yyscan_t escáner);SExpresión *getAST()const char *expreso){} SExpresión *expresión; Yyscan_t escáner; YY_BUFFER_STATE estado; si ()Yylex_init()"escáner) {} /* no podía inicializar */ retorno NULL; } estado = Yy_scan_string()expreso, escáner); si ()Yyparse()"expresión, escáner) {} /* error pareado */ retorno NULL; } Yy_delete_buffer()estado, escáner); Yylex_destroy()escáner); retorno expresión;}int evaluación()SExpresión *e){} interruptor ()e-Tipo) {} Caso eVALUE: retorno e-valor; Caso eMULTIPLY: retorno evaluación()e-izquierda) * evaluación()e-derecho); Caso eADD: retorno evaluación()e-izquierda) + evaluación()e-derecho); por defecto: /* no debe estar aquí */ retorno 0; }}int principal()vacío){} char prueba[] = " 4 + 2*10 + 3*(5 + 1)"; SExpresión *e = getAST()prueba); int resultado = evaluación()e); printf()"Resultado de '%s' es %dn", prueba, resultado); Eliminación()e); retorno 0;}

Un archivo MAKE simple para compilar el proyecto es el siguiente.

# MakefileFILES = Lexer.c Parser.c Expression.c main.c
CC = g++
CFLAGS = -g -ansi

prueba: $(FILES)$(CC) $(CFLAGS) $(FILES) -o pruebaLexer.c: Lexer.lflex Lexer.l

Parser.c: Parser.Sí. Lexer.cbison Parser.y

limpio:rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h prueba