Redigerer GNU Bison

{{infoboks programvare}}
'''GNU Bison''' er en [[fri og åpen programvare|fri og åpen]] [[parsergenerator]] for [[Unix]] og [[Unix-liknende]] [[operativsystem]]er.<ref name="GNU2015_Intro"/> GNU Bison inngår i [[GNU|GNU-prosjektet]] og er tilgjengelig under [[GNU General Public License]] versjon 3, med unntak som tillater den genererte kode å bli brukt uten lisensen [[copyleft]].<ref name="GNU2015_GPL"/><ref name="GNU2015_Cond"/>

GNU Bison leser en spesifikasjon i en [[kontekstfri grammatikk]], advarer mot [[Tvetydighet (grammatikk)|tvetydigheter]] og genererer en [[parsing|parser]] i [[C (programmeringsspråk)|C]], [[C++]]<ref name="GNU2015_10.1"/> eller [[Java (programmeringsspråk)|Java]].<ref name="GNU2015_10.2"/> Parseren leser sekvensen av [[leksikalsk analyse|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-parser]]e som standard, men kan også generere [[LR-parser|LR(1)]]-, IELR(1)- og [[GLR-parser]]e.<ref name="Levine2009_s50"/><ref name="GNU2015_1.5"/> [[Flex (leksikalsk analysator generator)|Flex]], som genererer [[leksikalsk analyse|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.<ref name="Brown1995_s177"/> [[Richard Stallman]] gjorde programmet kompatibelt med [[POSIX]] og [[Yacc]],<ref name="GNU2015_9.1"/> men det har flere forbedringer i forhold til Yacc. Versjon 3.8.2 ble lansert 25. september 2021.

==Historie==
===Yacc===
{{Utdypende|Yacc|TMG (parsergenerator){{!}}TMG|Portable C Compiler}}
GNU Bison oppstod som en avlegger av [[Yacc]] &ndash; ''Yet Another Compiler Compiler''.<ref name="Johnson1975"/><ref name="Unix1979"/> Yacc ble laget i 1971 av [[Stephen C. Johnson]] ved [[Bell Laboratories]] innenfor [[AT&T|AT&T Corporation]].<ref name="Raymond">Eric S. Raymond: [https://lists.gnu.org/archive/html/bison-patches/2019-02/msg00061.html Steve Johnson's reply], lists.gnu.org, 13. februar 2019</ref> Yacc ble opprinnelig skrevet i [[programmeringsspråk]]et [[B (programmeringsspråk)|B]] på en [[36-biter]] [[stormaskin]] av typen [[Ge-600 serien|Ge-635]] fra [[General Electric]],<ref name="Raymond"/><ref name="Ritchie"/> men ble raskt skrevet på nytt i [[C (programmeringsspråk)|C]].<ref name="Ritchie">{{cite conference |last=Ritchie |first=Dennis M. |authorlink=Dennis Ritchie |date=april 1993 |title=The Development of the C Language |publisher=Association for Computing Machinery, Inc. |url=http://heim.ifi.uio.no/inf2270/programmer/historien-om-C.pdf |accessdate=2019-06-14 |archivedate=2015-07-24 |archiveurl=https://web.archive.org/web/20150724071326/http://heim.ifi.uio.no/inf2270/programmer/historien-om-C.pdf }}</ref>

Yacc var i sin tur etterfølgeren til parsergeneratoren [[TMG (parsergenerator)|TMG]] (''TransMoGrifier''),<ref name="Raymond"/> som ble laget i 1964 for [[Multics]], [[OS/360]] og tidlige versjoner av [[UNIX]].<ref name="Raymond"/><ref name=mctmg>[http://www.multicians.org/tmg.html multicians.org - TMG], 2012-12-20</ref> TMG ble i 1964 brukt til å utvikle EPL, som var en tidlig versjon av [[PL/I]].<ref name=mctmg/> 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 [[Fortran]]kompilator på [[18-biter]] [[minidatamaskin]]en [[PDP-7]]. TMG genererte [[Rekursiv descendant parser|rekursivt descendant parsere]] som er et særtilfelle av [[Ovenfra-ned-parser|ovenfra-ned-parsere]],<ref name="Raymond"/> mens Yacc genererte [[LALR-parser]]e.

Yacc var en del av den tidlige utviklingen av UNIX,<ref name="Johnson1975"/> og ble en del av [[Forsknings-Unix|Unix versjon 3]] som ble lansert i februar 1973.<ref name="reader">{{cite journal |first1=M. D. |last1=McIlroy |authorlink1=Doug McIlroy |year=1987 |url=http://www.cs.dartmouth.edu/~doug/reader.pdf |title=A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986 |series=CSTR |number=139 |institution=Bell Labs}}</ref> Yacc hadde stor betydning i utbredelsen av UNIX, ved at det ble brukt til å generere parsere for [[operativsystem]]et. 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.<ref>{{cite web | author=Johnson, S.C. | year=1978 | title=A portable compiler: theory and practice | work=Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. Tucson, Arizona. | pages=97–104 | url=http://doi.acm.org/10.1145/512760.512771 | authorlink=Stephen C. Johnson }}</ref> En full beskrivelse av Yacc ble publisert i juli 1975.<ref name="Johnson1975"/> 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.<ref name="Unix1979"/>

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 Systems|Caldera International]] [[kildekode]]n 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.

[[Prefiks]]et ''ya-'' (''Yet Another'') levde sitt eget liv lenge etter at Yacc kom ut av bruk. Et eksempel er [[Yahoo!]] (''Yet Another Hierarchical Officious Oracle''),<ref name="Raymond"/> 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===
{{utdypende|Berkeley Yacc}}
Parsergeneratoren ''zoo'' ble skapt i 1985 av Robert Corbett ved [[University of California, Berkeley]].<ref name="Corbett1985"/> 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.<ref name="DeRemer1982"/>

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 <code>%expect n</code> sa at konflikter ikke skulle nevnes hvis der er ''n'' skift/reduser konflikter og ingen reduser/reduser konflikter. I nyere versjoner av Bison, kan <code>%expect</code> og varianten <code>%expect-rr</code> 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 <code>^</code> i feilmeldinger.

Sammenlignet med Yacc benytter Bison en raskere men mindre plass-effektiv koding for parsertabellene.<ref name="Corbett1985"/> og mer moderne teknikker for generering av mengden av lookahead.<ref name="DeRemer1982"/> 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, <code>%locations,</code> <code>%glr-parser</code>, <code>%printer</code>, <code>%destructor</code>, dumping av avfall til DOT, <code>%parse-param</code>, <code>%lex-param</code>, 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 (programmeringsspråk)|Go]] og ''Ocamlyacc'' for [[Objective Caml]].

===Operativsystemer===
GNU Bison har blitt portert til blant annet følgende [[operativsystemer]]:
{|
|-
| width="450" valign="top" |
* [[Linux]]<ref name="ultrix"/>
* [[MINIX]]
* [[MVS]]<ref>[http://h390-mvs.yahoogroups.narkive.com/qx7RE0hg/newbie-mvs-3-8j-tso-programming-information Newbie - MVS 3.8j TSO programming information], h390-mvs.yahoogroups.narkive.com, besøkt 1. juli 2017</ref>
* [[OS/390]]<ref name="OS390">[http://www-03.ibm.com/systems/resources/servers_eserver_zseries_zos_unix_redbook_sg245944.pdf Open Source Software for z/OS and OS/390 UNIX], IBM, 2002</ref>
* [[z/OS]]<ref name="OS390"/>
* [[SunOS]]<ref>[http://www-isl.ece.arizona.edu/islonly/computing/soft-sunos.html ISL Computing Software - SunOS], 5. mai 1999</ref>
* [[Solaris (operativsystem)|Solaris]]<ref>OpenCSW: [http://www.opencsw.org/package/bison/ bison Solaris package], 2016</ref>
* [[Illumos]]
* [[IRIX]]<ref>Georg Schwarz: [https://lists.gnu.org/archive/html/bug-bison/2006-05/msg00041.html gnu bison 2.2 on IRIX 5.3], lists.gnu.org, 21. mai 2006</ref>
* [[Tru64 UNIX]]<ref name="NCO netCDF Operators">[https://sourceforge.net/p/nco/discussion/9830/thread/e1a4dd80/ NCO netCDF Operators], SourceForge.net, NCO on Tru64 UNIX, 1. desember 2003</ref>
* [[DEC Ultrix]]<ref name="ultrix">[https://old.la1k.no/archive/gamleweb/tech/free-compilers.html Compilers available for free via Internet], old.la1k.no, 4. april 1995</ref>
* [[QNX]]<ref>[http://www.polarhome.com/service/man/?qf=BISON&tf=2&of=QNX&sf=1 BISON man page on QNX], Polarhome, 1999</ref>
* [[Plan 9]]<ref>[https://research.swtch.com/yaccalive Yacc is Not Dead], research.swtch.com 6. desember 2010</ref>
* [[SCO OpenServer]]<ref>The SCO Group, Inc.: [http://ftp.sco.com/pub/openserver6/600/other/gnuutils.mp4/GNUutils.RelNotes.html Release Notes GNU Utilities for OpenServer 6.0.0 6.0.0Da] {{Wayback|url=http://ftp.sco.com/pub/openserver6/600/other/gnuutils.mp4/GNUutils.RelNotes.html |date=20090327110159 }}, 2009</ref>
* [[Mach (operativsystemkjerne)|Mach]]<ref name="ultrix"/>
| width="480" valign="top" |
* [[DYNIX]]<ref name="NCO netCDF Operators"/>
* [[SHARP X68000|Human68k]]<ref name="ultrix"/>
* [[UnixWare]]<ref>[http://www.sco.com/skunkware/devtools/ Caldera Skunkware Open Source Software] {{Wayback|url=http://www.sco.com/skunkware/devtools/ |date=20160316143644 }}, 19. juli 2001</ref>
* [[AIX]]<ref>[http://bio.gsi.de/DOCS/AIX/aixpdslib.seas.ucla.edu/packages/bison.html bison. GNU yacc replacement] {{Wayback|url=http://bio.gsi.de/DOCS/AIX/aixpdslib.seas.ucla.edu/packages/bison.html |date=20151129210524 |df=iso }}, Public Domain Software Library for AIX, 10. april 2006</ref>
* [[HP-UX]]<ref>HP-UX Porting and Archiving Centre: [http://hpux.connect.org.uk/hppd/hpux/Gnu/bison-2.7.1/readme.html GNU Bison parser generator], besøkt 23. februar 2016</ref>
* [[Xenix]]
* [[LynxOS]]
* [[Mac OS X]]<ref>[https://discussions.apple.com/thread/1040495?start=0&tstart=0 What's the deal with bison?], Apple Support Communities, 14. juli 2007</ref>
* [[FreeBSD]]<ref>The FreeBSD Ports Archive [http://www.freebsdsoftware.org/devel/bison.html bison. A parser generator from FSF, (mostly) compatible with Yacc] {{Wayback|url=http://www.freebsdsoftware.org/devel/bison.html |date=20170704132137 }}, 2007</ref>
* [[OpenBSD]]<ref>[https://de.osdn.jp/projects/openbsd-octeon/scm/git/openbsd-octeon/tree/master/src/gnu/usr.bin/binutils/gdb/config/djgpp/ OpenBSD/OCTEON] {{Wayback|url=https://de.osdn.jp/projects/openbsd-octeon/scm/git/openbsd-octeon/tree/master/src/gnu/usr.bin/binutils/gdb/config/djgpp/ |date=20160819223405 }}, OSDN, 16. august 2010</ref>
* [[NetBSD]]<ref>[http://pkgsrc.se/devel/bison bison-3.0.4nb3. GNU yacc(1) replacement], pkgsrc.se, 9. juli 2016</ref>
* [[DragonFly BSD]]<ref>[https://www.dragonflybsd.org/cgi/web-man?command=bison&section=1 bison - GNU Project parser generator (yacc replacement)], DragonFly On-Line Manual Pages, april 2013</ref>
* [[MS-DOS]]<ref name="ultrix"/>
* [[OS/2]]<ref name="ultrix"/>
* [[Microsoft Windows]]<ref>[http://gnuwin32.sourceforge.net/packages/bison.htm Bison for Windows. Bison: Yacc-compatible parser generator. Version 2.4.1], gnuwin32.sourceforge.net, 4. mai 2009</ref>
|}

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

* [[Ruby]]<ref>Pat Shaughnessy: [http://patshaughnessy.net/2012/6/18/the-start-of-a-long-journey-how-ruby-parses-and-compiles-your-code The Start of a Long Journey: How Ruby Parses and Compiles Your Code], 18. juni 2012</ref>
* [[PHP]]<ref>Mehdi Achour, Friedhelm Betz, Antony Dovgal, Nuno Lopes, Hannes Magnusson, Georg Richter, Damien Seguy, Jakub Vrana: [http://php.net/manual/en/faq.build.php Build Problems ¶], PHP Manual, 7. august 2016</ref>
* [[Go (programmeringsspråk)|Go]]<ref>[https://libraries.io/languages/Bison Bison], libraries.io, 23. mai 2016</ref>
* [[GNU Octave]]<ref>http://octave.org/doxygen/4.0/d5/d60/oct-parse_8cc_source.html</ref>
* [[GNU Pascal]]<ref>[http://www.gnu-pascal.de/gpc/Compiling-GPC.html 4.3 Compiling GPC], The GNU Pascal Manual,</ref>
* [[CHILL|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<ref name="GNU2004"/>
* [[GNAT|GNU Ada]] i GCC forut for versjon 3.4<ref name="GNU2004"/>
* [[Fortran|GNU Fortran]] i GCC forut for versjon 3.4<ref name="GNU2004"/>
* [[Java (programmeringsspråk)|GNU Java]] forut for versjon 3.4<ref name="GNU2004"/>
* [[C (programmeringsspråk)|C]] og [[Objective C]] i GCC forut for versjon 4.1 som utkom den 28. februar 2006<ref name="GNU2006"/>
* [[Perl 5]] versjon 5.10 eller høyere<ref>http://perldoc.perl.org/perl5100delta.html</ref>
* [[Unix-skall]]et og [[kommandospråk]]et [[Bash]]<ref>[http://lfs.sourceforge.net/view/4.0/appendixa/bison.html Linux From Scratch: Version 4.0. Bison Official Download Location]</ref>
* [[Note]]programmet [[LilyPond]]<ref>[http://www.lilypond.org/doc/v2.19/Documentation/contributor/lilypond-programming-languages LilyPond — Contributor’s Guide v2.19.36-1, 10.2 LilyPond programming languages]</ref>
* [[Structured Query Language]] (SQL) i [[database]]ne [[PostgreSQL]],<ref name="PostgreSQL2015"/> [[MySQL]]<ref name="Levine2009_ch4"/> og [[MariaDB]].<ref>MariaDB Corporation Ab: [https://mariadb.com/kb/en/mariadb/Build_Environment_Setup_for_Linux/ Build Environment Setup for Linux. Required tools], 2016</ref>

==Eksempelprogram: Kalkulator==
Følgende eksempel viser hvordan GNU Bison og Flex kan brukes til å lage et enkelt [[kalkulator]]program (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===
<syntaxhighlight lang="c">
/*
 * 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__
</syntaxhighlight>

===Expression.c===
<syntaxhighlight lang="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);
}
</syntaxhighlight>

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

<syntaxhighlight lang="c">
%{
 
/*
 * 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;
}
</syntaxhighlight>

===Parser.y===
Ettersom de ulike token er produsert av Flex må det være en kommunikasjon mellom parseren og [[leksikalsk analyse|den leksikalske analysatoren]].<ref name="flex-bison-bridge">[http://flex.sourceforge.net/manual/Bison-Bridge.html GNU Bison Manual: C Scanners with Bison Parsers]  {{Wayback|url=http://flex.sourceforge.net/manual/Bison-Bridge.html |date=20101217042916 }}</ref> [[Datatype]]n 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''.<ref name="flex-bison-bridge" /> Dette blir gjort gjennom Bison's ''%lex-param'' og ''%parse-param'' deklarasjoner.<ref name="pure-calling-conventions">[https://www.gnu.org/software/bison/manual/html_node/Pure-Calling.html GNU Bison Manual: Calling Conventions for Pure Parsers]</ref>

<syntaxhighlight lang="c">
%{
 
/*
 * 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); }
    ;
 
%%
</syntaxhighlight>

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

<syntaxhighlight lang="c">
/*
 * 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;
}
</syntaxhighlight>

===Makefil===
Til slutt en [[makefil]] som bygger prosjektet.

<syntaxhighlight lang="make">
# 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
</syntaxhighlight>

==Versjonshistorikk==
{| class="wikitable"
!Versjon
!Lansert
!Merknader
|-bgcolor=#FFE1E1
|1.22
|7. september 1993
|
|-bgcolor=#FFE1E1
|1.23
|1993<ref>Charles Donnelly, Richard Stallman: [http://www.worldcat.org/title/bison-the-yacc-compatible-parser-generator/oclc/31825164?ht=edition&referer=di Bison. The YACC-compatible Parser Generator], 1993, Bison Version 1.23</ref>
|
|-bgcolor=#FFE1E1
|1.24
|30. mai 1995<ref>[https://www.math.utah.edu/docs/info/bison_toc.html Bison. The YACC-compatible Parser Generator], May 1995, Bison Version 1.24</ref>
|
|-bgcolor=#FFE1E1
|1.25
|11. mai 1996
|
|-bgcolor=#FFE1E1
|1.26
|11. februar 1999
|
|-bgcolor=#FFE1E1
|1.27
|16. februar 1999
|
|-bgcolor=#FFE1E1
|1.28
|6. juli 1999
|
|-bgcolor=#FFE1E1
|1.29
|7. september 2001
|
|-bgcolor=#FFE1E1
|1.30
|29. oktober 2001
|
|-bgcolor=#FFE1E1
|1.31
|14. januar 2002
|
|-bgcolor=#FFE1E1
|1.32
|23. januar 2002
|
|-bgcolor=#FFE1E1
|1.33
|7. februar 2002
|
|-bgcolor=#FFE1E1
|1.34
|12. mars 2002
|
|-bgcolor=#FFE1E1
|1.35
|25. mars 2002
|
|-bgcolor=#FFE1E1
|1.50
|5. oktober 2002
|
|-bgcolor=#FFE1E1
|1.75
|14. oktober 2002
|
|-bgcolor=#FFE1E1
|1.875
|1. januar 2003
|
|-bgcolor=#FFE1E1
|2.0
|4. januar 2005
|
|-bgcolor=#FFE1E1
|2.1
|19. september 2005
|
|-bgcolor=#FFE1E1
|2.2
|19. mai 2006
|
|-bgcolor=#FFE1E1
|2.3
|5. juni 2006
|
|-bgcolor=#FFE1E1
|2.4.0
|2. november 2008
|
|-bgcolor=#FFE1E1
|2.4.1
|11. desember 2008
|
|-bgcolor=#FFE1E1
|2.4.2
|20. mars 2010
|
|-bgcolor=#FFE1E1
|2.4.3
|5. august 2010
|
|-bgcolor=#FFE1E1
|2.5.0
|14. mai 2012
|
|-bgcolor=#FFE1E1
|2.5.1
|5. juni 2012
|
|-bgcolor=#FFE1E1
|2.6.0
|19. juli 2012
|
|-bgcolor=#FFE1E1
|2.6.1
|30. juli 2012
|
|-bgcolor=#FFE1E1
|2.6.2
|3. august 2012
|
|-bgcolor=#FFE1E1
|2.6.3
|22. oktober 2012
|
|-bgcolor=#FFE1E1
|2.6.4
|23. oktober 2012
|
|-bgcolor=#FFE1E1
|2.6.5
|7. november 2012
|
|-bgcolor=#FFE1E1
|2.7.0
|12. desember 2012
|
|-bgcolor=#FFE1E1
|2.7.1
|15. april 2013
|
|-bgcolor=#FFE1E1
|3.0.0
|25. juli 2013
|
|-bgcolor=#FFE1E1
|3.0.1
|12. november 2013
|
|-bgcolor=#FFE1E1
|3.0.2
|5. desember 2013
|
|-bgcolor=#FFE1E1
|3.0.3
|15. januar 2015
|
|-bgcolor=#FFE1E1
|3.0.4
|23. januar 2015
|
|-bgcolor=#FFE1E1
|3.0.5
|28. mai 2018
|
|-bgcolor=#FFE1E1
|3.1
|27. august 2018
|
|-bgcolor=#FFE1E1
|3.2
|29. oktober 2018
|
|-bgcolor=#FFE1E1
|3.2.1
|9. november 2018
|
|-bgcolor=#FFE1E1
|3.2.2
|21. november 2018
|
|-bgcolor=#FFE1E1
|3.2.3
|18. desember 2018
|
|-bgcolor=#FFE1E1
|3.2.4
|24. desember 2018
|
|-bgcolor=#FFE1E1
|3.3
|26. januar 2019
|
|-bgcolor=#FFE1E1
|3.3.1
|27. januar 2019
|
|-bgcolor=#FFE1E1
|3.3.2
|3. februar 2019
|
|-bgcolor=#FFE1E1
|3.4
|19. mai 2019
|
|-bgcolor=#FFE1E1
|3.4.1
|22. mai 2019
|
|-bgcolor=#FFE1E1
|3.4.2
|12. september 2019
|
|-bgcolor=#FFE1E1
|3.5
|11. desember 2019
|
|-bgcolor=#FFE1E1
|3.5.1
|19. januar 2020
|
|-bgcolor=#FFE1E1
|3.5.2
|13. februar 2020
|
|-bgcolor=#FFE1E1
|3.5.3
|8. mars 2020
|
|-bgcolor=#FFE1E1
|3.5.4
|5. april 2020
|
|-bgcolor=#FFE1E1
|3.6
|8. mai 2020
|
|-bgcolor=#FFE1E1
|3.6.1
|10. mai 2020
|
|-bgcolor=#FFE1E1
|3.6.2
|17. mai 2020
|
|-bgcolor=#FFE1E1
|3.6.3
|3. juni 2020
|
|-bgcolor=#FFE1E1
|3.6.4
|15. juni 2020
|
|-bgcolor=#FFE1E1
|3.7.0
|23. juni 2020
|
|-bgcolor=#FFE1E1
|3.7.1
|2. august 2020
|
|-bgcolor=#FFE1E1
|3.7.2
|5. september 2020
|
|-bgcolor=#FFE1E1
|3.7.3
|13. oktober 2020
|
|-bgcolor=#FFE1E1
|3.7.4
|13. november 2020
|
|-bgcolor=FFE1E1
|3.7.5
|24. januar 2021
|
|-bgcolor=FFE1E1
|3.7.6
|9. mars 2021
|
|-bgcolor=FFE1E1
|3.8.0
|7. september 2021
|
|-bgcolor=FFE1E1
|3.8.1
|11. september 2021
|
|-bgcolor=72F660
|3.8.2
|25. september 2021
|
|}

==Referanser==
<references>
<ref name="Brown1995_s177">[[#Brown1995|Brown 1995]], Appendix D, side 277</ref>
<ref name="Corbett1985">[[#Corbett1985|Corbett 1985]]</ref>
<ref name="DeRemer1982">[[#DeRemer1982|DeRemer 1982]]</ref>
<ref name="Johnson1975">[[#Johnson1975|Johnson 1975]]</ref>
<ref name="Levine2009_s50">[[#Levine2009|Levine 2009]], side 50</ref>
<ref name="Levine2009_ch4">[[#Levine2009|Levine 2009]], kapittel 4</ref>
<ref name="GNU2004">[[#GNU2004|GCC 3.4]]</ref>
<ref name="GNU2006">[[#GNU2006|GCC 4.1]]</ref>
<ref name="GNU2015_Intro">[[#GNU2015|Bison Manual]], Introduction</ref>
<ref name="GNU2015_GPL">[[#GNU2015|Bison Manual]], GNU GENERAL PUBLIC LICENSE</ref>
<ref name="GNU2015_Cond">[[#GNU2015|Bison Manual]], Conditions for Using Bison</ref>
<ref name="GNU2015_1.5">[[#GNU2015|Bison Manual]], 1.5 Writing GLR Parsers</ref>
<ref name="GNU2015_9.1">[[#GNU2015|Bison Manual]], 9.1 Bison Options</ref>
<ref name="GNU2015_10.1">[[#GNU2015|Bison Manual]], 10.1 C++ Parsers</ref>
<ref name="GNU2015_10.2">[[#GNU2015|Bison Manual]], 10.2 Java Parsers</ref>
<ref name="PostgreSQL2015">[[#PostgreSQL2015|PostgreSQL 2015]], kapittel 44.3</ref>
<ref name="Unix1979">[[#Unix1979|Unix 1979]]</ref>
</references>

== Litteratur ==
* {{Kilde bok
  | ref=Unix1979
  | forfatter=[[Bell Laboratories]]
  | utgivelsesår=1979
  | tittel=UNIX TM TIME-SHARING SYSTEM: UNIX PROGRAMMER’S MANUAL, Seventh Edition, Volume 2B
  | side=
  | forlag=Bell Telephone Laboratories, Incorporated, Murray Hill, [[New Jersey]], januar 1979
  | isbn=
  | url= https://s3.amazonaws.com/plan9-bell-labs/7thEdMan/v7vol2b.pdf
}}
* {{Kilde bok
  | ref=Brown1995 
  | forfatter=Brown, Doug; Levine, John; Mason, Tony
  | utgivelsesår=1995
  | artikkel=
  | redaktør=
  | tittel=lex & yacc
  | side=
  | forlag=O'Reilly Media, 1. utgave, mai 1990, ISBN 0 937 175 498, ISBN 978-0937175491; 2. utgave, 1. februar 1995
  | isbn=1 565 920 007
  | id= ISBN 978-1565920002
}}
* {{Kilde bok
  | ref=Corbett1985
  | forfatter=Corbett, Robert Paul
  | utgivelsesår=1985
  | tittel=  Static Semantics in Compiler Error Recovery
  | side=
  | forlag=Ph.D. Dissertation, Report No. UCB/CSD 85/251, Department of Electrical Engineering and Computer Science, Compute Science Division, University of California, Berkeley, California, juni 1985
  | isbn=
  | url= http://xtf.lib.berkeley.edu/reports/TRWebData/accessPages/CSD-85-251.html 
}}
* {{Kilde bok
  | ref=DeRemer1982
  | forfatter=[[Franklin DeRemer|DeRemer, Franklin Lewis]], Pennello, Thomas
  | utgivelsesår=1982
  | tittel= Efficient Computation of LALR(1) Look-Ahead Sets
  | side=
  | forlag= ACM Transactions on Programming Languages and Systems, Vol. 4, No. 4, oktober 1982, side 615–649
  | isbn=
  | url= http://xtf.lib.berkeley.edu/reports/TRWebData/accessPages/CSD-85-251.html 
}}
* {{Kilde bok
  | ref=Donnelly2015 
  | forfatter=Donnelly, Charles
  | utgivelsesår=2015
  | artikkel=
  | redaktør=
  | tittel= Bison: The Yacc-compatible Parser Generator
  | url=http://www.amazon.com/Bison-Yacc-compatible-Generator-Charles-Donnelly/dp/9888381377/ref=sr_1_fkmr2_1?s=books&ie=UTF8&qid=1456285239&sr=1-1-fkmr2&keywords=bison+the+yacc+compatible+compiler
  | side=
  | forlag=Samurai Media Limited, 11. november 2015
  | isbn=9 888 381 377
  | id= ISBN 978-9888381371
}}
* {{Kilde bok
  | ref=GNU2015 
  | forfatter=[[Free Software Foundation|Free Software Foundation, Inc.]]
  | utgivelsesår=2015
  | tittel= Bison 3.0.4 Manual
  | url=https://www.gnu.org/software/bison/manual/html_node/index.html#SEC_Contents
  | forlag=23. januar 2015
}}
* {{Kilde bok
  | ref=GNU2004 
  | forfatter=Free Software Foundation, Inc.
  | utgivelsesår=2004
  | tittel= GCC 3.4 Release Series Changes, New Features, and Fixes
  | url=http://gcc.gnu.org/gcc-3.4/changes.html
  | forlag=18. april 2004
}}
* {{Kilde bok
  | ref=GNU2006
  | forfatter=Free Software Foundation, Inc.
  | utgivelsesår=2006
  | tittel= GCC 4.1 Release Series Changes, New Features, and Fixes
  | url=http://gcc.gnu.org/gcc-4.1/changes.html
  | forlag=24. mai 2006
}}
* {{Kilde bok
  | ref=Johnson1975
  | forfatter=[[Stephen Curtis Johnson|Johnson, Stephen Curtis]]
  | utgivelsesår=1975
  | tittel= Yacc — Yet Another Compiler-Compiler
  | side=
  | forlag=Computing Science Technical Report, Issue 32, AT&T Bell Laboratories, Murray Hill, [[New Jersey]] 07974, juli 1975 
  | isbn=
  | url= https://s3.amazonaws.com/plan9-bell-labs/7thEdMan/v7vol2b.pdf
}}
* {{Kilde bok
  | ref=Levine2009 
  | forfatter=[[John R. Levine|Levine, John]]
  | utgivelsesår=2009
  | artikkel=
  | redaktør=
  | tittel= flex & bison: Text Processing Tools
  | url= https://www.safaribooksonline.com/library/view/flex-bison/9780596805418/pr02.html
  | side=
  | forlag= O'Reilly Media, 24. august 2009
  | isbn=0 596 155 972
  | id=ISBN 978-0596155971
}}
* {{Kilde bok
  | ref=PostgreSQL2015
  | forfatter=The PostgreSQL Global Development Group
  | utgivelsesår=2015
  | artikkel=
  | redaktør=
  | tittel=PostgreSQL 9.0.23 Documentation
  | url=http://www.postgresql.org/docs/9.0/static/index.html
  | side=
  | forlag= 8. oktober 2015
  | isbn=
}}

== Eksterne lenker ==
* {{Offisielle lenker}}
* {{Språkikon|en}} [https://directory.fsf.org/bison.html Omtale i Free Software Directory]
* {{Språkikon|en}} [https://web.archive.org/web/20061126170612/http://cs.uic.edu/~spopuri/cparser.html Forklaring av C-parsere som er generert av GNU Bison]
* {{Språkikon|en}} [https://github.com/Sleepful/C-Parser-with-Bison C Parser With Bison], hos github-com
* {{Språkikon|en}} [https://www.geeksww.com/tutorials/miscellaneous/bison_gnu_parser_generator/installation/installing_bison_gnu_parser_generator_ubuntu_linux.php How to download and install Bison (GNU Parser Generator) on Linux] (Geeks Worldwide)
* {{Språkikon|en}} [https://gnuwin32.sourceforge.net/packages/bison.htm GNU Bison for Microsoft Windows] (versjon 2.4.1)

{{Autoritetsdata}}

[[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]]