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 oppstod som en avlegger av Yacc – Yet Another Compiler Compiler. Yacc ble laget i 1971 av Stephen C. Johnson ved Bell Laboratories innenfor AT&T Corporation. 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. 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, ved at det 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å mange egenskaper for å støtte C++ som ikke var nærværende i Yacc eller 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:


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

Ruby
PHP
Go
GNU Octave
GNU Pascal
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øyere
Unix-skallet og kommandospråket Bash
Noteprogrammet LilyPond
Structured Query Language (SQL) i databasene PostgreSQL, MySQL og MariaDB.


== 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.c ===


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


=== Parser.y ===
Ettersom de ulike token er produsert av Flex må det være en kommunikasjon mellom parseren og den leksikalske analysatoren. 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.


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


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


== Versjonshistorikk ==


== Referanser ==


== Litteratur ==
Bell Laboratories (1979). UNIX TM TIME-SHARING SYSTEM: UNIX PROGRAMMER’S MANUAL, Seventh Edition, Volume 2B (PDF). Bell Telephone Laboratories, Incorporated, Murray Hill, New Jersey, januar 1979. 
Brown, Doug; Levine, John; Mason, Tony (1995). lex & yacc. 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. ISBN 978-1565920002. CS1-vedlikehold: Flere navn: forfatterliste (link)
Corbett, Robert Paul (1985). Static Semantics in Compiler Error Recovery. 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. 
DeRemer, Franklin Lewis, Pennello, Thomas (1982). Efficient Computation of LALR(1) Look-Ahead Sets. ACM Transactions on Programming Languages and Systems, Vol. 4, No. 4, oktober 1982, side 615–649. CS1-vedlikehold: Flere navn: forfatterliste (link)
Donnelly, Charles (2015). Bison: The Yacc-compatible Parser Generator. Samurai Media Limited, 11. november 2015. ISBN 9 888 381 377. ISBN 978-9888381371. 
Free Software Foundation, Inc. (2015). Bison 3.0.4 Manual. 23. januar 2015. 
Free Software Foundation, Inc. (2004). GCC 3.4 Release Series Changes, New Features, and Fixes. 18. april 2004. 
Free Software Foundation, Inc. (2006). GCC 4.1 Release Series Changes, New Features, and Fixes. 24. mai 2006. 
Johnson, Stephen Curtis (1975). Yacc — Yet Another Compiler-Compiler (PDF). Computing Science Technical Report, Issue 32, AT&T Bell Laboratories, Murray Hill, New Jersey 07974, juli 1975. 
Levine, John (2009). flex & bison: Text Processing Tools. O'Reilly Media, 24. august 2009. ISBN 0 596 155 972. ISBN 978-0596155971. 
The PostgreSQL Global Development Group (2015). PostgreSQL 9.0.23 Documentation. 8. oktober 2015. 


== Eksterne lenker ==
(en) Offisielt nettsted 
Prosjektets hjemmeside ved Savannah
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)