Redigerer LALR-parser (avsnitt)

==Historie==
I juli 1965 ble [[LR-parser]]en (''Left to Right, Rightmost derivation'') oppfunnet av den [[usa|amerikanske]] [[informatiker]]en [[Donald Knuth|Donald Ervin Knuth]] ved [[Stanford University]]. Denne parseren godtar ethvert [[deterministiske kontekstfrie språk|deterministisk kontekstfritt språk]] i en lineært avgrenset tid.<ref name="Knuth1965"/> Høyre-deriveringer har svært store minnekrav, og å implementere en LR-parser var upraktisk på denne tiden grunn av den begrensede mengden med [[RAM]] i datamaskiner.

For å løse dette problemet, foreslo informatikeren [[Franklin DeRemer]] ved [[Massachusetts Institute of Technology]] (MIT) i oktober 1969 to forenklede versjoner av LR-parseren, nemlig en Look Ahead LR (LALR) parser<ref name="DeRemer1969"/> og en [[Simpel LR-parser]] (SLR). Begge hadde mye mindre krav til RAM, men håndterte færre grammatikker, og LALR-parseren var den mest effektive av de to.<ref name="DeRemer1969"/>

I mai 1975 konverterte [[Bell Laboratories]] sin [[C (programmeringsspråk)|C-kompilator]] til LALR-algoritmen; denne kompilatoren ble tatt i bruk på [[UNIX versjon 6]] og var tidligere blitt implementert ved hjelp av en [[rekursiv descendant parser]].

I 1977 ble minneoptimaliseringer oppfunnet for LR-parseren, men fortsatt var den mindre minne-effektiv enn de forenklede versjonene.

Den 1. august 1977 utga [[Alfred Aho]] og [[Jeffrey Ullman]] den såkalte «[[Principles of Compiler Design|drageboken]]»;<ref name="Aho1977"/> denne klassiske teksten som snart ble en lærebok i [[kompilatorteknikk]], er kjent for sitt omslagsbilde av en ridder som bekjemper en drage. På ridderens lanse stod det skrevet LALR, og denne parseralgoritmen stod sentralt i boken.<ref name="Aho1977"/><ref name="Aho1986_215_247"/> Den 1. januar 1986 kom [[Compilers: Principles, Techniques, and Tools|andre utgave]] med [[Ravi Sethi]] som medforfatter,<ref name="Aho1986"/> og den 10. september 2006 tredje utgave med Sethi og [[Monica Sin-Ling Lam]] som medforfattere.<ref name="Aho2006"/>

I 1979 kunngjorde Franklin DeRemer og [[Thomas Pennello]] en serie optimaliseringer for LALR-parseren som ville forbedre minne-effektiviteten.<ref name="DeRemer1982"/> Deres arbeid ble publisert i oktober 1982.<ref name="DeRemer1982"/>

[[UNIX versjon 7]] ble lansert av Bell Laboratories den 11. januar 1979, og inkluderte den mest omfattende og lett tilgjengelige verktøykjede for kompilator-konstruksjon som noensinne er utviklet. Sentralt i denne verktøykjeden var [[Yacc]], en [[LALR-parsergenerator]]. [[Operativsystemet]]s hovedkompilator, [[Portable C Compiler]] (pcc), var også implementert ved hjelp av LALR. PCC var standard i [[Berkeley Software Distribution]] (BSD) frem til lanseringen av 4.4BSD i 1994, da den ble erstattet av [[GNU Compiler Collection|GNU C Compiler]] (GCC). PCC ble også benyttet i [[FreeBSD]], [[OpenBSD]], [[NetBSD]] og av enkelte [[Linuxdistribusjon]]er.

Etter år 2000 har vi sett et paradigmeskifte bort fra LALR-parsere og tilbake til rekursive descendant parsere. Fordi LALR-parseren utfører høyrederivasjoner i stedet for den mer intuitive venstrederivasjon, er forståelsen av dens virkemåte svært vanskelig. Dette gjør det vanskelig og tidkrevende å finne den korrekte og effektive LALR-grammatikk. Av samme grunn er LALR-parseres feilmeldinger ikke alltid forståelige for sluttbrukere. Enhver LR(k > 0)-tabell gjør det likevel trivielt å oppliste de ulike gyldige [[leksikalsk analyse|token]] når en syntaksfeil inntreffer. Av denne grunn er en rekursiv descendant parser å foretrekke. Den krever mer håndskrevet kode fordi den skal anerkjenne språk på et lavere nivå. De har likevel ikke de spesielle vanskelighetene ved LALR-parsere, fordi de bruker venstrederivering.

Den 23. mai 1987 lanserte [[GNU]] første versjon av GNU C Compiler (GCC).<ref>[https://gcc.gnu.org/releases.html GCC Releases],  Free Software Foundation, Inc., 16. juli 2015</ref> Kompilatoren var basert på en LALR-parser generert av Yacc. Den 6. mars 2006 lanserte GNU versjon 3.4.6 av [[GNU Compiler Collection]] (GCC).<ref name="gcc34">[https://gcc.gnu.org/gcc-3.4/changes.html GCC 3.4 Release Series. Changes, New Features, and Fixex], gnu.org, 6. mars 2006</ref>  Den Yacc-baserte LALR-parseren for C og [[C++]] i tidligere versjoner, ble erstattet av en håndskrevet rekursivt descendant parser.<ref name="gcc34"/> Denne parseren brukes fortsatt i versjon 14.2, som ble lansert 1. august 2024.

[[Clang]], som ble lansert 26. september 2007 som en konkurrent til GCC, har fra starten av benyttet en rekursiv descendant parser.<ref>Kevin Hu's Blog: [https://blog.kevinhu.me/2014/11/24/24-what-parsers-are-they-using/ What Parsers Are They Using?], 24. november 2014</ref> Versjon 18.1.8, som ble lansert 18. juni 2024, bruker fortsatt denne parseren.

Den 18. desember 1987 lanserte [[Larry Wall]] den første versjonen av det [[funksjonell programmering|funksjonelle]] [[skriptspråk]]et [[Perl]].<ref>[[Larry Wall]]: [http://groups.google.com/group/comp.sources.unix/tree/browse_frm/month/1988-02?_done=%2Fgroup%2Fcomp.sources.unix%2Fbrowse_frm%2Fmonth%2F1988-02%3F& v13i001: Perl, a "replacement" for awk and sed, Part01/10], nyhetsgruppen comp.sources.unix, 1. februar 1988</ref> Dette språket har en større kompleksitet enn noen tidligere språk, og benytter seg aggressivt av en LALR-parser, produsert med Yacc.<ref>casiano: [http://www.perlmonks.org/?node_id=876097 Yacc is dead], perlmonks.org, 8. desember 2010</ref>

Den 19. juli 2000 startet arbeidet med [[Perl 6]],<ref>Kline, Joe: [http://www.perl.com/pub/a/2000/08/tpc4.html Report from the Perl Conference], perl.com, 21. august 2000</ref> en radikal nyimplementasjon av dette språket. [[Rakudo Perl 6]], med første lansering av både kompilatoren og dens moduler den 29. juli  2010, tar likeledes i bruk en rekursiv descendant parser som alternativ til LALR.<ref>[http://irclog.perlgeek.de/parrot/2010-03-03 IRC log for #parrot, 2010-03-03] {{Wayback|url=http://irclog.perlgeek.de/parrot/2010-03-03 |date=20160306180409 }}, irclog.org, 3. mars 2010</ref>

Versjon 2024.08 #175 ble lansert 29. august 2024. Også denne bruker en rekursiv descendant parser.