GNU Bison

GNU Bison er en fri og åpen parsergenerator for Unix og Unix-liknende operativsystemer. GNU Bison inngår i GNU-prosjektet og er tilgjengelig under GNU General Public License versjon 3, med unntak som tillater den genererte kode å bli brukt uten lisensen copyleft.

GNU Bison leser en spesifikasjon i en kontekstfri grammatikk, advarer mot tvetydigheter og genererer en parser i C, C++ eller Java. Parseren leser sekvensen av token og bestemmer hvorvidt sekvensen følger syntaksen som er spesifisert av grammatikken. Den genererte parser er plattformuavhengig, og er ikke avhengig av noen spesifikk kompilator. GNU Bison genererer LALR-parsere som standard, men kan også generere LR(1)-, IELR(1)- og GLR-parsere. Flex, som genererer leksikalske analysatorer, kan dele strømmen av innmatede data opp i token før de behandles av GNU Bison.

GNU Bison ble skapt i 1988 av Robert Corbett fra University of Berkeley; den 2. september 1989 lanserte han også parsergeneratoren Berkeley Yacc, og GNU Bison ble påvirket mye av tidligere versjoner av Berkeley Yacc. Richard Stallman gjorde programmet kompatibelt med POSIX og Yacc, men det har flere forbedringer i forhold til Yacc. Versjon 3.8.2 ble lansert 25. september 2021.

Historie
Yacc

GNU Bison er en avlegger av Yacc – Yet Another Compiler Compiler. Yacc ble laget i 1971 av Stephen C. Johnson ved Bell Laboratories innenfor AT&T Corporation.Eric S. Raymond: Steve Johnson's reply, lists.gnu.org, 13. februar 2019 Yacc ble opprinnelig skrevet i programmeringsspråket B på en 36-biter stormaskin av typen Ge-635 fra General Electric, men ble raskt skrevet på nytt i C.

Yacc var i sin tur etterfølgeren til parsergeneratoren TMG (TransMoGrifier), som ble laget i 1964 for Multics, OS/360 og tidlige versjoner av UNIX.multicians.org - TMG, 2012-12-20 TMG ble i 1964 brukt til å utvikle EPL, som var en tidlig versjon av PL/I. I 1969 brukte Ken Thompson TMG for å lage programmeringsspråket B, og i 1970 brukte han også denne parsergeneratoren som et verktøy til å utvikle en Fortrankompilator på 18-biter minidatamaskinen PDP-7. TMG genererte rekursivt descendant parsere som er et særtilfelle av ovenfra-ned-parsere, mens Yacc genererte LALR-parsere.

Yacc var en del av den tidlige utviklingen av UNIX, og ble en del av Unix versjon 3 som ble lansert i februar 1973. Yacc hadde stor betydning i utbredelsen av UNIX, og ble brukt til å generere parsere for operativsystemet. Yacc ble brukt til utviklingen av Portable C Compiler (pcc) på midten av 1970-tallet. Stephen C. Johnson var opphavsmannen til både Yacc og pcc. En full beskrivelse av Yacc ble publisert i juli 1975. Yacc blir noen ganger skrevet YACC (med store bokstaver), men opphavsmannen brukte navneformen Yacc (med små bokstaver), deriblant i beskrivelsen som er gitt i Version 7 Unix Manual i januar 1979.

Omkring 1990 kom Yacc mer eller mindre ut av bruk, fordi parsergeneratorer med mindre restriktive lisenser og flere egenskaper var blitt tilgjengelige. I 2002 gjorde Caldera International kildekoden til Yacc på gamle versjoner av Unix – fra UNIX versjon 7 til UNIX/32V, åpent tilgjengelig. På denne tiden hadde Yacc lenge vært erstattet av GNU Bison selv på Yacc’s egne Unix-varianter.

Prefikset ya- (Yet Another) levde sitt eget liv lenge etter at Yacc kom ut av bruk. Et eksempel er Yahoo! (Yet Another Hierarchical Officious Oracle), som er navnet på et IT-selskap som ble opprettet i California i 1994. Et annet eksempel er installerings- og konfigureringsverktøyet YaST (Yet another Setup Tool) på SUSE Linux som ble lansert i 1996.

yacchack
Yacc manglet evnen til å produsere innadgående parsere. Dette ble ordnet ved et sett med modifikasjoner, kalt yacchack, som ble publisert av Eric S. Raymond på USENET omkring 1983. Disse utvidelsene ble overflødige da parsergeneratorene zoo og Berkeley Yacc ble tilgjengelige noen få år senere.

Berkeley Yacc

Parsergeneratoren zoo ble skapt i 1985 av Robert Corbett ved University of California, Berkeley. Den 2. september 1989 skiftet den navn til Berkeley Yacc (byacc).

Berkeley Yacc hadde tre forbedringer i forhold til Yacc: Den genererte raskere parsere, den kunne generere innadgående parsere, og kildekoden var offentlig eiendom i stedet for å være under en proprietær lisens fra AT&T. Forbedret ytelse oppstod ved å implementere teknikker som Franklin DeRemer og Thomas Penello hadde beskrevet i deres avhandling om LALR-parsere fra 1982.

Bruken av byacc spredte seg raskt på grunn av dens liberale lisens. Da GNU Bison ble tilgjengelig, gikk likevel byacc ut av offentlig bruk.

zoo, Byson og GNU Bison
Robert Corbett laget to beslektede LALR-parsergeneratorer i 1985, som begge benyttet teknikkene til DeRemer og Penello. Den ene var zoo, den andre var Byson. I 1987 begynte Richard Stallman å arbeide med Byson; han endret navnet til Bison og gjorde grensesnittet kompatibelt med Yacc.

Til forskjell fra Yacc, støttet Byson konstruksjonen @n. Denne ga tilgang til det innledende og det avsluttende linjenummer og til antall tegn knyttet til alle symbolene i den gjeldende regel. Kommandoen %expect n sa at konflikter ikke skulle nevnes hvis der er n skift/reduser konflikter og ingen reduser/reduser konflikter. I nyere versjoner av Bison, kan %expect og varianten %expect-rr anvendes på individuelle regler med reduser-reduser konflikter.

Senere versjoner av Bison tilføyde mange flere egenskaper, deriblant bedre feilmeldinger. Av disse kan vi merke oss at Yacc og Byson manglet tegnet ^ i feilmeldinger.

Sammenlignet med Yacc benytter Bison en raskere men mindre plass-effektiv koding for parsertabellene. og mer moderne teknikker for generering av mengden av lookahead. Dette har vært standard siden første versjon. Det har vært påstått at disse forskjeller stammer fra den temporære løsning som Johnson måtte benytte for å få den opprinnelige Yacc til å passe på 16-biter minidatamaskinen PDP-11.

Navngitte referanser, semantiske predikater, %locations, %glr-parser, %printer, %destructor, dumping av avfall til DOT, %parse-param, %lex-param, og dumping av avfall til XSLT, LAC og generering av IELR(1)-parsere er nytt i Bison. 

Bison har også egenskaper for å støtte C++ som manglet i Yacc og Byson.

Alle tidligere Yacc-varianter, og lignende parsergeneratorer som genererte C-kode, ble gjort foreldet av Bison i 1995.

PLY, goyacc og ocamlyacc
Yacc-konseptet har ofte blitt portert til andre programmeringsspråk. Noen av de tidligere porteringer er opphørt å eksistere sammen med språkene som ble brukt på dem; andre har blitt erstattet av parserskjeletter som leveres sammen med Bison. 

Det finnes også uavhengige implementasjoner, deriblant David Beazley’s PLY (Python Lex-Yacc) for Python, goyacc for programmeringsspråket Go og Ocamlyacc for Objective Caml.

Operativsystemer
GNU Bison har blitt portert til blant annet følgende operativsystemer:
 Linux
 MINIX
 MVSNewbie - MVS 3.8j TSO programming information, h390-mvs.yahoogroups.narkive.com, besøkt 1. juli 2017
 OS/390Open Source Software for z/OS and OS/390 UNIX, IBM, 2002
 z/OS
 SunOSISL Computing Software - SunOS, 5. mai 1999
 SolarisOpenCSW: bison Solaris package, 2016
 Illumos
 IRIXGeorg Schwarz: gnu bison 2.2 on IRIX 5.3, lists.gnu.org, 21. mai 2006
 Tru64 UNIXNCO netCDF Operators, SourceForge.net, NCO on Tru64 UNIX, 1. desember 2003
 DEC UltrixCompilers available for free via Internet, old.la1k.no, 4. april 1995
 QNXBISON man page on QNX, Polarhome, 1999
 Plan 9Yacc is Not Dead, research.swtch.com 6. desember 2010
 SCO OpenServerThe SCO Group, Inc.: Release Notes GNU Utilities for OpenServer 6.0.0 6.0.0Da , 2009
 Mach DYNIX
 Human68k
 UnixWareCaldera Skunkware Open Source Software , 19. juli 2001
 AIXbison. GNU yacc replacement , Public Domain Software Library for AIX, 10. april 2006
 HP-UXHP-UX Porting and Archiving Centre: GNU Bison parser generator, besøkt 23. februar 2016
 Xenix
 LynxOS
 Mac OS XWhat's the deal with bison?, Apple Support Communities, 14. juli 2007
 FreeBSDThe FreeBSD Ports Archive bison. A parser generator from FSF, (mostly) compatible with Yacc , 2007
 OpenBSDOpenBSD/OCTEON , OSDN, 16. august 2010
 NetBSDbison-3.0.4nb3. GNU yacc(1) replacement, pkgsrc.se, 9. juli 2016
 DragonFly BSDbison - GNU Project parser generator (yacc replacement), DragonFly On-Line Manual Pages, april 2013
 MS-DOS
 OS/2
 Microsoft WindowsBison for Windows. Bison: Yacc-compatible parser generator. Version 2.4.1, gnuwin32.sourceforge.net, 4. mai 2009

Programvare generert ved hjelp av GNU Bison
Eksempler på programmeringsspråk og annen programvare som er generert ved hjelp av GNU Bison:

 RubyPat Shaughnessy: The Start of a Long Journey: How Ruby Parses and Compiles Your Code, 18. juni 2012
 PHPMehdi Achour, Friedhelm Betz, Antony Dovgal, Nuno Lopes, Hannes Magnusson, Georg Richter, Damien Seguy, Jakub Vrana: Build Problems ¶, PHP Manual, 7. august 2016
 GoBison, libraries.io, 23. mai 2016
 GNU Octave
 GNU Pascal4.3 Compiling GPC, The GNU Pascal Manual,
 GNU CHILL i versjon 2.95 av GCC
 C++ i GNU Compiler Collection (GCC) forut for versjon 3.4 som utkom den 18. april 2004
 GNU Ada i GCC forut for versjon 3.4
 GNU Fortran i GCC forut for versjon 3.4
 GNU Java forut for versjon 3.4
 C og Objective C i GCC forut for versjon 4.1 som utkom den 28. februar 2006
 Perl 5 versjon 5.10 eller høyerehttp://perldoc.perl.org/perl5100delta.html
 Unix-skallet og kommandospråket BashLinux From Scratch: Version 4.0. Bison Official Download Location
 Noteprogrammet LilyPondLilyPond — Contributor’s Guide v2.19.36-1, 10.2 LilyPond programming languages
 Structured Query Language (SQL) i databasene PostgreSQL, MySQL og MariaDB.MariaDB Corporation Ab: Build Environment Setup for Linux. Required tools, 2016

Eksempelprogram: Kalkulator
Følgende eksempel viser hvordan GNU Bison og Flex kan brukes til å lage et enkelt kalkulatorprogram (kun addisjon og multiplikasjon) og et program for å skape et abstrakt syntakstre. De to neste filene sørger for definisjoner og implementasjon av syntakstreets funksjoner.

Expression.h
/*
 * Expression.h
 * Definisjon av strukturen brukt til å bygge syntakstreet. */
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__

/**
 * Operasjonstyper
 */
typedef enum tagEOperationType
{
    eVALUE,
    eMULTIPLY,
    ePLUS
} EOperationType;

/**
 * Uttrykks-struktur
 */
typedef struct tagSExpression
{
    EOperationType type;///< typen av operasjon

    int value;///< gyldig bare hvis typen er eVALUE
    struct tagSExpression *left; ///< venstre side av treet
    struct tagSExpression *right;///< høyre side av treet
} SExpression;

/**
 * Skapelse av en identifikator
 * Parameteren er tallverdien
 * Funksjonen returnerer uttrykket eller NULL hvis det ikke er nok minne
 */
SExpression *createNumber(int value);

/**
 * Skapelse av en operasjon
 * Parameteren "type" definerer operasjonstype
 * Parameteren "left" definerer venstre operand
 * Parameteren "right" definerer høyre operand
 * Funksjonen returnerer uttrykket eller NULL hvis det ikke er nok minne
 */
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right);

/**
 * Sletter et uttrykk
 * Parameteren b er uttrykket
 */
void deleteExpression(SExpression *b);

#endif // __EXPRESSION_H__

Expression.c
/*
 * Expression.c
 * Implementasjon av funksjoner til å bygge syntakstreet.
 */

#include "Expression.h"

#include <stdlib.h>

/**
 * Allokerer plass for uttrykket
 * Funksjonen returnerer uttrykket eller NULL hvis det ikke er nok minne
 */
static SExpression *allocateExpression()
{
    SExpression *b = (SExpression *)malloc(sizeof(SExpression));

    if (b == NULL)
        return NULL;

    b->type = eVALUE;
    b->value = 0;

    b->left = NULL;
    b->right = NULL;

    return b;
}

SExpression *createNumber(int value)
{
    SExpression *b = allocateExpression();

    if (b == NULL)
        return NULL;

    b->type = eVALUE;
    b->value = value;

    return b;
}

SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right)
{
    SExpression *b = allocateExpression();

    if (b == NULL)
        return NULL;

    b->type = type;
    b->left = left;
    b->right = right;

    return b;
}

void deleteExpression(SExpression *b)
{
    if (b == NULL)
        return;

    deleteExpression(b->left);
    deleteExpression(b->right);

    free(b);
}

Lexer.l
Token som behøves av parseren vil bli generert av Flex.

%{

/*
 * Lexer.l filen
 * For å generere den leksikalske analysator kjøres "flex Lexer.l"
 */

#include "Expression.h"
#include "Parser.h"

#include <stdio.h>

%}

%option outfile="Lexer.c" header-file="Lexer.h"
%option warn nodefault

%option reentrant noyywrap never-interactive nounistd
%option bison-bridge

LPAREN      "("
RPAREN      ")"
PLUS        "+"
MULTIPLY    "*"

NUMBER      [0-9]+
WS          [ \r\n\t]*

%%

{WS}            { /* Fjern blanke tegn. */ }
{NUMBER}        { sscanf(yytext, "%d", &yylval->value); return TOKEN_NUMBER; }

{MULTIPLY}      { return TOKEN_MULTIPLY; }
{PLUS}          { return TOKEN_PLUS; }
{LPAREN}        { return TOKEN_LPAREN; }
{RPAREN}        { return TOKEN_RPAREN; }
.               {  }

%%

int yyerror(const char *msg) {
    fprintf(stderr,"Error:%s\n",msg); return 0;
}

Parser.y
Ettersom de ulike token er produsert av Flex må det være en kommunikasjon mellom parseren og den leksikalske analysatoren.GNU Bison Manual: C Scanners with Bison Parsers   Datatypen som brukes til kommunikasjon, YYSTYPE, er satt til bruke Bisons %union deklarasjon.

Vi må også sørge for parametere til yylex-funksjonen, når den kalles fra yyparse. Dette blir gjort gjennom Bison's %lex-param og %parse-param deklarasjoner.GNU Bison Manual: Calling Conventions for Pure Parsers

%{

/*
 * Parser.y file
 * For å generere parseren, kjør "bison Parser.y"
 */

#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"

int yyerror(SExpression **expression, yyscan_t scanner, const char *msg) {
    // Feilhåndteringsrutiner
}

%}

%code requires {

#ifndef YY_TYPEDEF_YY_SCANNER_T
#define YY_TYPEDEF_YY_SCANNER_T
typedef void* yyscan_t;
#endif

}

%output  "Parser.c"
%defines "Parser.h"

%define api.pure
%lex-param   { yyscan_t scanner }
%parse-param { SExpression **expression }
%parse-param { yyscan_t scanner }

%union {
    int value;
    SExpression *expression;
}

%left '+' TOKEN_PLUS
%left '*' TOKEN_MULTIPLY

%token TOKEN_LPAREN
%token TOKEN_RPAREN
%token TOKEN_PLUS
%token TOKEN_MULTIPLY
%token <value> TOKEN_NUMBER

%type <expression> expr

%%

input
    : expr { *expression = $1; }
    ;

expr
    : expr[L] TOKEN_PLUS expr[R] { $$ = createOperation( ePLUS, $L, $R ); }
    | expr[L] TOKEN_MULTIPLY expr[R] { $$ = createOperation( eMULTIPLY, $L, $R ); }
    | TOKEN_LPAREN expr[E] TOKEN_RPAREN { $$ = $E; }
    | TOKEN_NUMBER { $$ = createNumber($1); }
    ;

%%

Main.c
Den følgende koden skaper syntakstreet ved å bruke parseren generert av Bison og den leksikalske analysator som er generert av Flex.

/*
 * main.c file
 */

#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"

#include <stdio.h>

int yyparse(SExpression **expression, yyscan_t scanner);

SExpression *getAST(const char *expr)
{
    SExpression *expression;
    yyscan_t scanner;
    YY_BUFFER_STATE state;

    if (yylex_init(&scanner)) {
        // couldn't initialize
        return NULL;
    }

    state = yy_scan_string(expr, scanner);

    if (yyparse(&expression, scanner)) {
        // error parsing
        return NULL;
    }

    yy_delete_buffer(state, scanner);

    yylex_destroy(scanner);

    return expression;
}

int evaluate(SExpression *e)
{
    switch (e->type) {
        case eVALUE:
            return e->value;
        case eMULTIPLY:
            return evaluate(e->left) * evaluate(e->right);
        case ePLUS:
            return evaluate(e->left) + evaluate(e->right);
        default:
            // shouldn't be here
            return 0;
    }
}

int main(void)
{
    SExpression *e = NULL;
    char test[]=" 4 + 2*10 + 3*( 5 + 1 )";
    int result = 0;

    e = getAST(test);

    result = evaluate(e);

    printf("Result of '%s' is %d\n", test, result);

    deleteExpression(e);

    return 0;
}

Makefil
Til slutt en makefil som bygger prosjektet.

# Makefile

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

test:		$(FILES)
		$(CC) $(CFLAGS) $(FILES) -o test

Lexer.c:	Lexer.l 
		flex Lexer.l

Parser.c:	Parser.y Lexer.c
		bison Parser.y

clean:
		rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h test

Versjonshistorikk
VersjonLansertMerknader1.227. september 19931.231993Charles Donnelly, Richard Stallman: Bison. The YACC-compatible Parser Generator, 1993, Bison Version 1.231.2430. mai 1995Bison. The YACC-compatible Parser Generator, May 1995, Bison Version 1.241.2511. mai 19961.2611. februar 19991.2716. februar 19991.286. juli 19991.297. september 20011.3029. oktober 20011.3114. januar 20021.3223. januar 20021.337. februar 20021.3412. mars 20021.3525. mars 20021.505. oktober 20021.7514. oktober 20021.8751. januar 20032.04. januar 20052.119. september 20052.219. mai 20062.35. juni 20062.4.02. november 20082.4.111. desember 20082.4.220. mars 20102.4.35. august 20102.5.014. mai 20122.5.15. juni 20122.6.019. juli 20122.6.130. juli 20122.6.23. august 20122.6.322. oktober 20122.6.423. oktober 20122.6.57. november 20122.7.012. desember 20122.7.115. april 20133.0.025. juli 20133.0.112. november 20133.0.25. desember 20133.0.315. januar 20153.0.423. januar 20153.0.528. mai 20183.127. august 20183.229. oktober 20183.2.19. november 20183.2.221. november 20183.2.318. desember 20183.2.424. desember 20183.326. januar 20193.3.127. januar 20193.3.23. februar 20193.419. mai 20193.4.122. mai 20193.4.212. september 20193.511. desember 20193.5.119. januar 20203.5.213. februar 20203.5.38. mars 20203.5.45. april 20203.68. mai 20203.6.110. mai 20203.6.217. mai 20203.6.33. juni 20203.6.415. juni 20203.7.023. juni 20203.7.12. august 20203.7.25. september 20203.7.313. oktober 20203.7.413. november 20203.7.524. januar 20213.7.69. mars 20213.8.07. september 20213.8.111. september 20213.8.225. september 2021

Referanser
Brown 1995, Appendix D, side 277
Corbett 1985
DeRemer 1982
Johnson 1975
Levine 2009, side 50
Levine 2009, kapittel 4
GCC 3.4
GCC 4.1
Bison Manual, Introduction
Bison Manual, GNU GENERAL PUBLIC LICENSE
Bison Manual, Conditions for Using Bison
Bison Manual, 1.5 Writing GLR Parsers
Bison Manual, 9.1 Bison Options
Bison Manual, 10.1 C++ Parsers
Bison Manual, 10.2 Java Parsers
PostgreSQL 2015, kapittel 44.3
Unix 1979

 Litteratur 












 Eksterne lenker 

  Omtale i Free Software Directory
  Forklaring av C-parsere som er generert av GNU Bison
  C Parser With Bison, hos github-com
  How to download and install Bison (GNU Parser Generator) on Linux (Geeks Worldwide)
  GNU Bison for Microsoft Windows (versjon 2.4.1)

Kategori:GNU
Kategori:UC Berkeley
Kategori:Unix-programmer
Kategori:Linux-programmer
Kategori:AIX
Kategori:IRIX
Kategori:Programvare for Solaris
Kategori:Plan 9
Kategori:Slackware
Kategori:Debian
Kategori:Ubuntu
Kategori:Red Hat Linux
Kategori:Programvare for Fedora
Kategori:Programvare for Red Hat Enterprise Linux
Kategori:Gentoo
Kategori:SUSE Linux
Kategori:Arch Linux
Kategori:Mandriva
Kategori:FreeBSD
Kategori:OpenBSD
Kategori:DragonFly BSD
Kategori:Windows-programmer
Kategori:Parsergeneratorer
Kategori:Programvare fra 1988
Kategori:1988 i USA