Redigerer GNU Bison (avsnitt)

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